c -复制链表-使程序崩溃

Question

我有以下C代码来复制链表(取自斯坦福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);
}

我的main函数中有以下代码:

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

我正在编译代码使用流血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

如果它只是死亡，那通常是访问了一个无效的指针。很可能是空指针

Answer 4

你的问题是:

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

尾部指向一个未统一的内存区域。所以tail->下一个可能是任何东西

试

              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，不如将其分配给tail的next -

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

Answer 6

在else块中编写以下代码

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

第1行:tail指向一个节点，该节点的所有成员都有值，因为tail尚未初始化。

Line2: tail->next，有垃圾值被赋给tail。现在tail没有指向任何错锁内存。你丢失了已经错锁的内存的指针

所以这里并没有创建链接列表