Объединить двойной связанный список на языке Си

Question

Объединить два связанных списка на языке Си.

Я попытался объединить два отсортированных двойных списка. Когда я запускал свой код с разными входами, иногда код просто разбивался с ошибкой 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

Самая важная ошибка (то есть отсутствие инициализации new->next) уже была устранена ответом @ alinsoar.

Однако в вашем коде есть другие ошибки, которые а) вызывают утечки памяти и b) вызвать неверный связанный список.

В main у вас есть:

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

Почему вы «выбрасываете» первый элемент, подобный этому?Это утечка памяти!Кроме того, это означает, что l->prio не равно NULL, как должно быть!

Я знаю, что это потому, что ваш 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;
}

С этим кодом вы не получите лишний элемент в начале, и вы можете удалить код l=l->next; в main.Аналогичные изменения применяются к 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;
}

Answer 2

Проблема в том, что в create_list вы не инициализируете new->next с NULL.

Из этой ошибки нет смысла в merge_list сравнивать указатели с NULL.