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

Question

在我使用下面的 insertBefore() 函数之前，C 中的单向链表实现工作正常。在 insertBefore() 中，当我尝试在第一个元素之前插入节点时，奇怪的事情发生了。我尝试从 insertBefore() 内部打印列表，它正确地打印了列表。但是当我尝试先返回时似乎有些不对劲。因为在 main 返回后，当我尝试打印相同的列表时，它会进入无限循环。重点是，当我尝试打印值 first.next->data 时返回 main 后，它显示与 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 found\n");
  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 found\n");
  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:exit\n");
          scanf("%d", &i);
          switch(i)
          {
                   case 1:
                        printf("Enter element to be inserted\n");
                        scanf("%d", &x);
                        first = *insertFirst(&first, x);

                        break;
                   case 2:
                        printf("Enter element to be inserted\n");
                        scanf("%d", &x);
                        printf("Enter element after which to insert node\n");
                        scanf("%d", &y);
                        first = *insertAfter(&first, x, y);
                        break;
                   case 3:
                        printf("Enter element to be inserted\n");
                        scanf("%d", &x);
                        printf("Enter element before which to insert node\n");
                        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 指针就永远丢失了。

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