用C语言合并双向链表

Question

用C语言实现两个链表的合并。

我尝试合并这两个排序的双向链表。当我用不同的输入运行我的代码时，有时代码会因为EXC_BAD_ACCESS错误而崩溃。我不知道为什么，代码对我来说似乎很完美，我用类似的方法合并两个单一的链表，它起作用了。有人能解释一下吗？谢谢!

   #include <stdio.h>  

   #include <stdlib.h>

   typedef struct Node
   {

    struct Node* prior;

    struct Node* next;

    int value;

   }Node,*list;

  list create_list()
  {          

      list head = (list)malloc(sizeof(Node));

      if(!head) exit(-1);

      list tail;

      tail=head;

      printf("Please enter the length of double linked list:\n");

      int len;

      scanf("%d",&len);

       for(int i=0;i<len;i++)

        {

         list new = (list)malloc(sizeof(Node));

         printf("Please enter the value of node:\n");

         int val;

         scanf("%d",&val);

         new->value=val;

         tail->next = new;

         new->prior=tail;

         tail=new;
    }
    return head;
  }

   list merge_list(list a, list b)
   {

      if(a==NULL||b==NULL) exit(-1);

      list p=(list)malloc(sizeof(Node));

      list l=p;

      while(a&&b)
      {

         if(a->value<=b->value)
          {

            p->next = a;

            a->prior=p;

            p=a;

            a=a->next;

           }
      else
      {

           p->next = b;

          b->prior=p;

          p=b;

          b=b->next;

      }
    }
   if(a!=NULL)

     {

        p->next=a;

        a->prior=p;
    }

    if(b!=NULL)
    {

      p->next=b;

      b->prior=p;

     }

    return l;
}

    int main() {

     list l = create_list();

     l=l->next;

     list m = create_list();

     m=m->next;

    list n =merge_list(l,m);

     n=n->next;

    while(n)
   {

       printf("%d\n",n->value);

       n=n->next;
   }

     return 0;
}

Answer 1

问题是，在create_list中，您不能用NULL初始化new->next。

从这个错误中可以看出，在merge_list中比较指针和NULL是没有意义的。

Answer 2

最重要的错误(即没有初始化new->next)已经在@alinsoar的答案中得到了解决。

但是，您的代码中还有其他错误，a)导致内存泄漏，b)导致链表不正确。

在main中，您可以：

 list l = create_list();
 l=l->next;  // Why ......

为什么你要“扔掉”第一个元素呢？这是一个内存泄漏！此外，它还意味着l->prio不应该是空的！

我知道这是因为你的create_list在开头插入了一个伪节点。但不要仅仅通过丢弃节点来修复它。改为修复函数。

这样做：

list create_list()
{          
  list head = NULL; // Do not use malloc here - just assign NULL
  list tail = NULL;

  printf("Please enter the length of double linked list:\n");
  int len;
  scanf("%d",&len);

  for(int i=0;i<len;i++)
  {
     list new = malloc(sizeof(Node));  // do not cast malloc
     new->next = NULL;                 // set the next pointer

     printf("Please enter the value of node:\n");
     int val;
     scanf("%d",&val);
     new->value=val;

     // Add the node to the end
     new->prior=tail;
     if (tail)
     {
         tail->next = new;
     }
     else
     {
         // First element so update head
         head = new;
     }
     tail=new;
  }
  return head;
}

使用此代码，您不会在开始时获得额外的元素，并且您可以删除main中的代码l=l->next;。类似的更改也适用于merge_list，但我将把它留给您作为练习。

最后，你的main应该只是：

int main() {
    list l = create_list();
    list m = create_list();
    list n =merge_list(l,m);
    while(n) {
        printf("%d\n",n->value);
        n=n->next;
    }
    return 0;
}