合并 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("%dn",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("%dn",n->value);
        n=n->next;
    }
    return 0;
}