Освобождение двойного связанного списка, который я создал

Question

Я пытался освободить созданный мной связанный список, но потерпел неудачу.

Расширение предыдущего вопроса, которое я задал: «Объединить двойной связанный список», это нормально, если вы не проверите его или не знаетеничего об этом.Я создал два двойных связанных списка, и я объединил их, и после этого я хочу освободить их всех.Поэтому я написал функцию delete_list ().Но, в конце концов, мне не удалось, ошибка «ошибка для объекта 0x100404110: освобожденный указатель не был выделен».Если я освобожу только первый список l, код работает.Но если я попытаюсь освободить все или два, код сокрушитсяМожет ли кто-нибудь помочь мне с этим?Спасибо !!

 #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));
       if(!new) exit(-1);
       new->next=NULL;
       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 delete_List(list l)
   {
       if(l==NULL)
       {
          printf("List is empty!");
          exit(-1);
       }
       list temp;

       while(l)
      {
         temp = l->next;
         free(l);
         l=NULL;
         l=temp;
      }
     return 1;
   }

   int main() {
       list l = create_list();
       l=l->next;//throw away the empty node
       list m = create_list();
       m=m->next;//throw away the empty node
       list n =merge_list(l,m);
       n=n->next;  //throw away the empty node
       delete_List(l);
       delete_List(m);
       delete_List(n);   
       return 0;
   }

НЕТ ошибки.

Answer 1

Очевидный ответ, почему вы не можете освободить 3 списка, состоит в том, что у вас нет 3 списков. Ваша функция merge_list делает именно то, что предлагает название (своего рода). Он берет 2 списка и объединяет их в 1 список. Таким образом, вам не нужно освобождать 2 исходных списка, вам нужно только освободить объединенный.

Answer 2

функция: create_list() имеет несколько проблем, в том числе не проверяет ошибки и неправильно обрабатывает вставку нового узла в начало списка, а также неправильно обрабатывает первую запись в связанном списке.

Форматирование / стиль кода оставляет желать лучшего.

Односимвольный параметр и имена локальных переменных не имеют смысла. Такие имена должны обозначать content или usage

delete_list() не должен ничего возвращать, так как нечего возвращать. Таким образом, подпись изменилась на:

void delete_List( Node *list )

не должен typedef указатель, поскольку это только добавляет путаницу к коду.

Следующий предлагаемый код устраняет вышеуказанные проблемы и форматирует код для удобства чтения

Предостережение: еще не было проверено

struct NODE
{
   struct NODE* prior;
   struct NODE* next;
   int value;
};
typedef struct NODE  Node;

Node * create_list()
{
    Node * head = NULL;

    printf("Please enter the length of double linked list:\n");
    int len;
    if( scanf("%d",&len) != 1 )
    {
        fprintf( stderr, "scanf for length of list failed\n" );
        return NULL;
    }

    for( int i=0; i<len; i++ )
    {
        Node * newNode = malloc(sizeof(Node));
        if ( !newNode )
        {
            perror( "malloc for list nodefailed" );
            // cleanup here
            exit( EXIT_FAILURE );
        }

        if ( !head )
        { // then first entry into linked list
            newNode->next  = NULL;
            newNode->prior = NULL;
        }

        else
        {
            //insert node at front of list
            newNode->next  = head;
            head->prior = newNode;
            newNode->prior = NULL;
        }

        printf("Please enter the value of node:\n");
        int val;
        if( scanf("%d",&val) != 1 )
        {
            fprintf( stderr, "scanf for node value failed\n" );
            // clean up here
            exit( EXIT_FAILURE );
        }

        newNode->value = val;
        head = newNode;
    }
    return head;
}


Node * merge_list( Node *left, Node *right )//合并两个非递减双向链表
{
    if( !left || !right)
        exit(-1);

    Node * workNode   = NULL;
    Node * returnNode = NULL;

    while ( left && right ) 
    {
        if( !workNode )
        { // then first loop
            if( left->value <= right->value )
            {
                workNode = left;
                left = left->next;
            }

            else
            {
                 workNode = right;
                 right = right->next;
            }

            // remember address of beginning of merged list
            returnNode = workNode;
        }


        else if( left->value <= right->value )
        {
            workNode->next  = left;
            left->prior = workNode;
            workNode = left;
            left = left->next;
        }

        else
        {
            workNode->next  = right;
            right->prior = workNode;
            workNode = right;
            right = right->next;
        }
    }

    // if more entries in left
    if( left )
    {
        workNode->next = left;
    }

    else if( right )
    {
        workNode->next = right;
    }
    return returnNode;
}


void delete_List( Node *list )
{
    if(list==NULL)
    {
        printf("List is empty!");
        exit(-1);
    }

    Node * temp;

    while(list)
    {
        temp = list->next;
        free( list );
        list = temp;
    }
}

Answer 3

Я считаю, что ваша проблема заключается в вызове delete_list в списках компонентов, которые вы передали своей функции merge_list.

Если я правильно понимаю ваш код, list на самом деле является просто указателем напервый узел связанного списка.Ваш create_list выделяет узлы и возвращает адрес первого, который вы затем по какой-либо причине отбрасываете, что приводит к указателю на второй выделенный узел.

Примерно так:

list l = pointer to [1] -> [2] -> [3] ...
list m = pointer to [5] -> [10] -> [15] ...

Ваш merge_list выполняет сортировку слиянием двух списков, , используя одинаковые узлы , изменяя указатели next / prev.

while(a&&b)
{
    if(a->value<=b->value)
    {
       p->next = a;
       a->prior=p;
       p=a;
       a=a->next;

Это означает, что указатель списка l и указатель списка m и указатель списка n (объединенный список) указывают на одни и те же узлы.Когда вы делаете list n = merge_list(l,m), результат выглядит примерно так:

list n = pointer to [1] -> [2] -> [3] -> [5] -> [10] ...
list l = pointer to ^
list m = pointer to 5 ...................^

(указатели 'l' и 'm' не меняются, но узлы, на которые они указывают, изменяются функцией слияния.)

Когда вы попытаетесь free перечислить узлы в вашей функции удаления, сработает первый вызов для удаления списка 'l'.Вызов для удаления списка «m» либо сразу завершится неудачей (если первый узел «m» был больше, чем первый узел «l», как в моем примере), либо освободит некоторые узлы, а затем завершится ошибкой.Удаление 'n' не удастся, так как все узлы, составляющие 'n', удаляются в вызовах для удаления 'l' и 'm'.

Это можно исправить несколькими способами.Самый простой - просто сбросить указатель списка l и m на NULL при вызове слияния, поскольку в вашей системе слияние двух списков «потребляет» их, и, следовательно, право собственности переходит от параметров к результату.

list n = merge_list(l, m); l = m = NULL;

Другим способом было бы создание функции слияния для создания дублирующихся узлов, что означает, что merge_list фактически создаст копии двух списков, что позволит владельцу сохранять параметры владения параметрами.

list n = merge_list(l, m);
// now n, l, m, all exist and are separate

Окончательным решением было бы создание истинного объекта «списка», который находится между вызывающим и объектами узлов.Этот объект может быть изменен, чтобы отражать любую реальность, но он будет отдельным, и поэтому не будет перезаписан во время операций слияния и т. Д. (Я не рекомендую это, кстати. Это формально, но неэффективно.)