当试图在第一个元素之前插入节点时，c中的单链表不起作用

Question

在使用下面的insertBefore（）函数之前，下面给出的C中的单链表实现运行良好。在insertBefore（）中，当我试图在第一个元素之前插入节点时，奇怪的事情正在发生。我尝试从insertBefore（）内部打印列表，它正确地打印了列表。但当我试图先回来的时候，似乎有些不对劲。因为在返回main之后，当我试图打印相同的列表时，它将进入无限循环。重点是，当我第一次尝试打印值时返回main。next->data显示的值与first.data的值相同。当我尝试在第一个节点之前的任何其他位置插入节点时，该代码适用于所有其他情况，如insertAfter（），甚至inserBefore（）。

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
   int data;
   node *next;
};
void printList(node *);
node * insertFirst(node *first, int x)
{
 node *ptr = (node *)malloc(sizeof(node));
 ptr->data = x;
 ptr->next = NULL;
 first = ptr;
 return first;
}
node *insertAfter(node *first, int x, int k)
{
  node *p = first;
  node *ptr = (node *)malloc(sizeof(node));
  ptr->data = x;
  while(p != NULL)
  {
         if(p->data == k)
                    break;
         p = p->next;       
  }
  if(p == NULL)
      printf("Element not foundn");
  else
  {
     ptr->next = p->next;
     p->next = ptr;
  }
  printList(first);
  return first;
}
node *insertBefore(node *first, int x, int k)
{
  node *ptr = (node *)malloc(sizeof(node));
  ptr->data = x;
  node *p = first, *follow = NULL;
  while(p != NULL)
  {
         if(p->data == k)
                    break;
         follow = p;
         p = p->next;
  }
  if(p == NULL)
      printf("Element not foundn");
  else
  {
     if(p == first)
     {
          ptr->next = first;
          first = ptr;
     }
     else
     {
         ptr->next = p;
         follow->next = ptr;
     }     
  }
  printList(first);
  printf("first->nxt %u", first->next->data);
  return first;
}
void printList(node *first)
{
  node *p = first;
  while(p != NULL)
  {
         printf(" %d",p->data);
         p = p->next;
  }
  printf("n");
}
main()
{
  struct node first, *p;
  int i, x, y, t=1;
  while(t)
  {
          printf("1:insertFirst 2:insertAfter 3:insertBefore 4:printList 5:exitn");
          scanf("%d", &i);
          switch(i)
          {
                   case 1:
                        printf("Enter element to be insertedn");
                        scanf("%d", &x);
                        first = *insertFirst(&first, x);
                        break;
                   case 2:
                        printf("Enter element to be insertedn");
                        scanf("%d", &x);
                        printf("Enter element after which to insert noden");
                        scanf("%d", &y);
                        first = *insertAfter(&first, x, y);
                        break;
                   case 3:
                        printf("Enter element to be insertedn");
                        scanf("%d", &x);
                        printf("Enter element before which to insert noden");
                        scanf("%d", &y);
                        first = *insertBefore(&first, x, y);
                        printf("first: %d", first.data);  
                        printf("first.nxt %d", first.next->data);
                        printList(&first);                     
                        break;
                   case 4:
                        printf("Linked list:");
                        printList(&first);
                        break;             
                   case 5:
                        t = 0;
                        break;
          }
  }
  getch();
}

Answer 1

我建议将first（在main()中）转换为指针（node*），并重新访问所有可以执行以下操作的地方：

first = *insertBefore(&first, x, y);

这应该是：

first = insertBefore(first, x, y);

否则，您将从左到右、从中泄漏内存，并创建无限循环的可能性（其中first.next指向first）。

您还需要确保first已正确初始化，并将first.X的所有使用替换为first->X。

编辑：考虑以下代码：

node * insertFirst(node *first, int x)
{
 node *ptr = (node *)malloc(sizeof(node));
 ...
 return ptr;
}
struct node first;
...
first = *insertFirst(&first, x);

insertFirst()的结果被取消引用，返回的结构被复制到first中。一旦赋值完成，malloc()ed指针将永远丢失。

还有类似的内存泄漏会影响其他功能。

Answer 2

我认为insertFirst应该在first之前插入新节点。然而，这并不是因为新节点的next指针应该指向旧的第一个节点。

试试这个：

node * insertFirst(node *first, int x)
{
    node *ptr = (node *)malloc(sizeof(node));
    ptr->data = x;
    ptr->next = first;  /* The old first node is now second first */
    return ptr;  /* Return the new first node */
}

Answer 3

之前的插入应该如下。假设您将head保持为全局，并传递新节点的head节点和data作为参数。

NODE * addfront(NODE *head, int data)
{
        NODE * newnode = (NODE *) malloc(sizeof(NODE));
        newnode->data = data;
        newnode->next = head;
        head = newnode;
        return head;
}

上述代码应按如下方式使用：

NODE * head = NULL;
head = addfront(head, 9);