循环链表进入无限循环

I am supposed to do a program which can do polynomial addition/subtraction/multiplication/evaluation using circular linked list.

我应该做一个程序,可以使用循环链表进行多项式加法/减法/乘法/评估。

My multiplication code is going in infinite loop, and I have marked a comment where it is happening (detected with printf statements, removed).

我的乘法代码进入无限循环,我已经标记了它发生的注释(用printf语句检测,删除)。

list* poly_mul(list *p1, list *p2) {
  term tmp;
  list *result = malloc(sizeof(list));
  memcpy(result, p1, sizeof(list));
  node *b = p2->head;
  node *r = result->head;
  do {
    do {
      tmp.exp = r->data.exp + b->data.exp;
      tmp.coeff = r->data.coeff * b->data.coeff;
      unsigned int add_term = 1;
      node *c = result->head;
      do {
        if(c->data.exp == tmp.exp) {
          c->data.coeff += tmp.coeff;
          add_term = 0;
          break;
        }
        c = c->next;
        //Here it goes in infinite loop
      } while(c != result->head);
      if(add_term)
        node_add(result, &tmp);
      b = b->next;
    } while(b != p2->head);
    r = r->next;
  } while(r != result->head);
  return result;
}

The structures used are here:

使用的结构如下:

typedef struct {
  int exp;
  int coeff;
} term;

typedef struct node {
  term data;
  struct node *next;
} node;

typedef struct {
  node *head;
  node *tail;
  unsigned int count;
} list;

And this is the code in main:

这是主要的代码:

void main() {
  list p1, p2, *p3;
  p1.count = p2.count = 0;
  poly_create(&p1);
  p3 = poly_mul(&p1, &p2);
  poly_print(p3);
}

void poly_create(list *l) {
  int i, n;
  printf("\nEnter number of terms in the polynomial: ");
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    printf("\nEnter details for term %d: ", i);
    term_append(l);
}

void node_add(list *l, term *t) {
  node *tmp = malloc(sizeof(node));
  memcpy(&tmp->data, t, sizeof(term));
  if(l->count == 0) {
    l->head = tmp;
    l->tail = tmp;
    tmp->next = tmp;
  }
  else {
    l->tail->next = tmp;
    tmp->next = l->head;
    l->tail = tmp;    
  }
  l->count++;
}

void term_append(list *l) {
  term t;
 enter:
  printf("\nEnter term as <coefficient>,<exponent>: ");
  scanf("%d,%d", &t.coeff, &t.exp);
  if(!t.coeff) {
    printf("\nCoefficient is zero, reenter term");
    goto enter;
  }
  if(l->count >= 1) {
    node *i = l->head;
    do {
      if(i->data.exp == t.exp) {
        printf("\nExponent %d was already entered, reenter term", t.exp);
        goto enter;
      }
      i = i->next;
    } while(i != l->head);
    node_add(l, &t);
  }
  else
    node_add(l, &t);
}

Please get me a solution for this problem, I've been trying to solve this for the past three hours.

请帮我解决这个问题,过去三个小时我一直试图解决这个问题。

3 个解决方案

#1

Why is it going into an infinite loop? You can find out by using a debugger and stepping through the code. Just put a breakpoint at the appropriate place and you should be able to find it yourself. In all likelihood, you have a loop in your linked list.

它为什么会进入无限循环?您可以通过使用调试器并单步执行代码来查找。只需在适当的地方放置一个断点,你就可以自己找到它。很有可能,您的链表中有一个循环。

You can check for loops in your linked list with two pointers. The first one (tail) point to the start of your list. The second (head) points to the second element of your list. Loop till head is past the last element (I have those pointed to NULL, not head) by incrementing both head and tail by one. If at any point tail > head, you have a loop.

您可以使用两个指针检查链表中的循环。第一个(尾部)指向列表的开头。第二个(头部)指向列表的第二个元素。通过将头部和尾部递增1来循环直到头部超过最后一个元素(我有那些指向NULL,而不是头部)。如果在任何时候尾巴>头部,你有一个循环。

#2

What happens if you printf("%d",(int) c); at each iteration? I suspect that result->head is pointing to a node which is pointing to a member of the linked list, but is not in the linked list itself.

如果你是printf会发生什么(“%d”,(int)c);在每次迭代?我怀疑result-> head指向一个指向链表成员的节点,但不在链表中。

Potential test: Add a int seen to each member of the list and increment it on each member as you loop for a given number of nodes (something excessively high such as INT_MAX) and, when the loop stops, see if result->head->seen > 0:

潜在测试:添加一个看到列表中每个成员的int,并在循环访问给定数量的节点(超出某些东西,如INT_MAX)时在每个成员上递增它,并且当循环停止时,查看result-> head- >看到> 0:

typedef struct node {
  term data;
  struct node *next;
  // to be removed later
  int seen;
} node;

// place this before you get the infinite loop
unsigned int i = 1;
c->seen = 0;
do
{
    c = c->next;
    c->seen = i;
// replace INT_MAX with some number which is greater than the maximum list length
} while(++i <= INT_MAX);
// this should be roughly equal to i (might be off by 1).
// I'll bet it isn't though!
printf("result->head->seen = %d", result->head->seen);

#3

One possible cause: you're never creating p2. Are you missing a line like this in your main function:

一个可能的原因:你永远不会创造p2。你在主函数中是否遗漏了这样的一行:

poly_create(&p2);

?