Копирование связанного списка - вылетает программа

Question

У меня есть следующий код C для копирования связанного списка (взятый из файлов библиотеки Stanford CS):

struct Node* CopyList(struct Node* head)
{
       struct Node* current = head;
       struct Node* newList= NULL;
       struct Node* tail= NULL;

       while (current !=NULL)
       {
             if(newList==NULL)
             {
                 newList=malloc(sizeof(struct Node));
                 newList->data=current->data;
                 newList->next=NULL;
                 tail= newList;
             }
             else
             {
                 tail= malloc(sizeof(struct Node));
                 tail= tail->next;
                 tail->data=current->data;
                 tail->next = NULL;
             }
             current= current->next;
       }
       return(newList);
}

У меня есть следующее как часть моей основной функции:

struct Node* head = NULL;
for (i=3; i >=1;i--)   //insert 3 elements into the linked list
   {                   //push inserts elements in the front
       Push(&head,i); 
   } //now a linked list 1->2->3->NULL is formed

struct Node* newlst= CopyList(head); // copies contents into a new linked list

Я компилирую код, используя Bloodshed Dev C ++.Я не получаю никаких ошибок компиляции, но когда я запускаю его, он просто падает.В чем может быть проблема с этим?Я передаю правильный параметр в функцию CopyList?

Answer 1

Ваша проблема лежит здесь, в else бите:

tail = malloc (sizeof (struct Node));
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

Вы выделяете новый узел и устанавливаете tail для указания на него (в первой строке). Тогда вы используете tail, как будто это старый хвост. В частности, эта вторая строка даст вам мошеннический указатель (так как вы не инициализировали новый узел с действительными указателями), который, вероятно, вылетит в третьей строке, когда вы попытаетесь разыменовать его.

Вам нужно что-то вроде:

// First, set up the new node.

newList = malloc (sizeof (struct Node));
newList->data = current->data;
newList->next = NULL;

// Then, adjust the tail pointers.

tail->next = newList;
tail = newList;

На самом деле, оглядываясь на свой код, то, что вы вероятно намеревались, было:

tail->next = malloc (sizeof (struct Node)); // use tail->next, not tail.
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

, который достигает того же результата.

Полагаю, я должен упомянуть, что вам действительно следует проверить возвращаемые значения из malloc на случай, если вам не хватит памяти. Вы можете сделать это с чем-то вроде:

tail->next = malloc (sizeof (struct Node)); // use tail->next, not tail.
if (tail->next == NULL) {
    // do something here for recovery.
    return;
}
// Only continue here if the allocation worked.
tail = tail->next;
tail->data = current->data;
tail->next = NULL;

Без таких проверок вы получите сбой при исчерпании памяти.

Answer 2

Вы выделяете память для tail, она должна быть tail-> next.Без этого вы потеряли бы предыдущие указатели.Модифицированный код

struct Node* CopyList(struct Node* head) 
{        
    //.... same as before

    while (current !=NULL)        
    {              
        if(newList==NULL) 
        {              
            //.... same as before
         }              
         else
         {                   
            tail->next = malloc(sizeof(struct Node));                   
            tail= tail->next;                   
            tail->data=current->data;                   
            tail->next = NULL;                   
          }              

          current= current->next;        
     }        

     return(newList); 
}

Шаш

Answer 3

в блоке else вы написали этот код

             tail= malloc(sizeof(struct Node));
             tail= tail->next;
             tail->data=current->data;
             tail->next = NULL;

Строка 1: хвост указывает на узел, и все члены этого узла имеют значение, поскольку хвост не был инициализирован.

Линия2: хвост-> следующий, который имеет значение мусора, присваивается хвосту. Теперь хвост не указывает на какую-либо запутанную память. И вы потеряли указатель уже заблокированной памяти

Так что на самом деле здесь не создается список ссылок

Answer 4

Вот ваша проблема:

              tail= malloc(sizeof(struct Node));
              tail= tail->next;

хвост указывает на унифицированную область памяти. Так что tail-> next может быть чем угодно.

Попробуйте

              tail->next= malloc(sizeof(struct Node));
              tail= tail->next;

Answer 5

Рассмотрим эту строку -

tail = tail->next;

Когда вы создаете первый узел в новом списке, все нормально, и newList, и tail указывают на этот узел. Теперь подумайте, что произойдеткогда в новом списке будет создан второй узел -

tail = malloc(sizeof(struct Node));    // tail points to the new node
tail = tail->next;                     // You are assigning new node's next to tail, but
                                       // did you initialize next to anything?

Так что next ни к чему не инициализируется, и вы назначаете его на tail, поэтому tail теперь содержит мусор.Когда вы присваиваете ему какое-то значение в следующих двух строках, ваша программа обязательно сокрушится.

Вместо того, чтобы назначать новый узел для tail, вам необходимо назначить его для хвостового next -

tail->next = (struct Node *) malloc(sizeof(struct Node) * 1);

Answer 6

Если он просто умирает, это обычно признак доступа к неверному указателю.Скорее всего, нулевой указатель.