編寫一個C程序來創建一個鏈接列表的副本

Question

我想寫一個copy_list函數，它創建一個鏈接列表（函數結果），其中包含與單個參數引用的鏈接列表相同的數據的新節點copy_list.But我的copy_list函數不起作用。它進入無限循環，while循環沒有退出。 我的結構

typedef struct name_node_s { 
    char name[11]; 
    struct name_node_s *restp; 
}name_node_t; 
typedef struct { 
    name_node_t *headp; 
    int size; 
}name_list_t; 

我copy_list功能：

name_node_t *copy_list(name_node_t *head){ 
    name_node_t *current = head; 
    name_node_t *newList = NULL; 
    name_node_t *tail = NULL; 

    while (current != NULL){ 
     if (newList == NULL) { 
      newList = malloc(sizeof(name_node_t)); 
      strcpy(newList->name, current->name); 
      newList->restp = NULL; 
      tail = newList; 
     } 
     else { 
      tail->restp = malloc(sizeof(name_node_t)); 
      tail = tail->restp; 
      strcpy(tail->name, current->name); 
      tail->restp = NULL; 
     } 
     current = current->restp; 
    } 
    return(newList); 
} 

休息的代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct name_node_s { 
    char name[11]; 
    struct name_node_s *restp; 
}name_node_t; 
typedef struct { 
    name_node_t *headp; 
    int size; 
}name_list_t; 
name_node_t* presidents(void); 
void insertAfter(name_node_t* mynode,name_node_t* newNode); 
//void delete_last(name_node_t** headRef); 
//void ListDelete(name_list_t* listP, char pname[]); 
void lastDelete(name_list_t* listP); 
void place_first(name_node_t **headRef, char pname[]); 
name_node_t *copy_list(name_node_t *head); 
int main(void) 
{ 
    name_list_t list; 
    name_list_t list_two; 
    //name_node_t *np, *qp; 
    list.headp = presidents(); 
    name_node_t *new_node; 
    new_node = malloc(sizeof(name_node_t)); 
    strcpy(new_node->name, "Eisenhower"); 
    insertAfter(list.headp->restp, new_node); 
    lastDelete(&list); 
    place_first(&list.headp, "Mustafa"); 
    printf("%s %s %s %s", list.headp->name, list.headp->restp->name, list.headp->restp->restp->name, list.headp->restp->restp->restp->name); 
    list_two.headp = copy_list(list.headp); 
    printf("%s %s %s %s", list_two.headp->name, list.headp->restp->name, list.headp->restp->restp->name, list.headp->restp->restp->restp->name); 

    return(0); 
} 
name_node_t* presidents(void) 
{ 
    name_node_t* head = NULL; 
    name_node_t* second = NULL; 
    name_node_t* third = NULL; 

    head = malloc(sizeof(name_node_t)); 
    second = malloc(sizeof(name_node_t)); 
    third = malloc (sizeof(name_node_t)); 

    strcpy(head->name, "Washington"); 
    head->restp = second; 

    strcpy(second->name, "Roosevelt"); 
    second->restp = third; 

    strcpy(third->name, "Kennedy"); 
    third->restp = NULL; 

    return(head); 
} 
void insertAfter(name_node_t* mynode,name_node_t* newNode) 
{ 
    newNode->restp = mynode->restp; 
    mynode->restp = newNode; 
} 

void ListDelete(name_list_t* listP, char pname[]){ 
    name_node_t *to_freep, *cur_nodep; 
    if(strcmp(listP->headp->name, pname)){ 
     to_freep = listP->headp; 
     listP->headp = to_freep->restp; 
     --(listP->size); 
    } 
    else { 
     for (cur_nodep = listP->headp; 
      cur_nodep->restp != NULL && !strcmp(cur_nodep->restp->name, pname); 
      cur_nodep = cur_nodep->restp) { 
       if(cur_nodep->restp != NULL && strcmp(cur_nodep->restp->name, pname)) { 
        to_freep = cur_nodep->restp; 
        cur_nodep->restp = to_freep->restp; 
        free(to_freep); 
        --(listP->size); 
       } 
      } 
     } 
    } 
void lastDelete(name_list_t* listP){ 
    name_node_t *to_freep, *cur_nodep; 
    for (cur_nodep = listP->headp; 
      cur_nodep->restp != NULL; 
      cur_nodep = cur_nodep->restp) {} 
    to_freep = cur_nodep; 
    cur_nodep->restp = to_freep->restp; 
    free(to_freep); 
    --(listP->size); 
} 
void place_first(name_node_t **headRef, char pname[]) { 
    name_node_t *newNode = malloc(sizeof(name_node_t)); 
    strcpy(newNode->name, pname); 
    newNode->restp = *headRef; 
    *headRef = newNode; 
} 
/*name_node_t *copy_list(name_node_t *head) { 
    name_node_t *current = head; 
    name_node_t *newList = NULL; 
    name_node_t **lastPtr; 

    lastPtr = &newList; 

    while (current != NULL) { 
     printf("**"); 
     place_first(lastPtr, current->name); 
     lastPtr = &((*lastPtr)->restp); 
     current = current->restp; 
    } 
    return(newList); 
}*/ 
/*name_node_t *copy_list(name_node_t *head) { 
    if (head == NULL) 
     return NULL; 
    else { 
     name_node_t *newList = malloc(sizeof(name_list_t)); 
     strcpy(newList->name, head->name); 
     newList->restp = copy_list(head->restp); 

     return(newList); 
    } 
}*/ 
/name_node_t *copy_list(name_node_t *head){ 
    name_node_t *current = head; 
    name_node_t *newList = NULL; 
    name_node_t *tail = NULL; 

    while (current != NULL){ 
     if (newList == NULL) { 
      newList = malloc(sizeof(name_node_t)); 
      strcpy(newList->name, current->name); 
      newList->restp = NULL; 
      tail = newList; 
     } 
     else { 
      tail->restp = malloc(sizeof(name_node_t)); 
      tail = tail->restp; 
      strcpy(tail->name, current->name); 
      tail->restp = NULL; 
     } 
     current = current->restp; 
    } 
    return(newList); 
} 

Answer 1

在lastDelete()，這個循環：

for (cur_nodep = listP->headp; 
      cur_nodep->restp != NULL; 
      cur_nodep = cur_nodep->restp) {} 

...停止在列表中的最後一個節點。之後，您從未在倒數第二個元素中將restp設置爲NULL。你只在最後一個工作，因爲to_freep和cur_nodep指向相同的元素。

Answer 2

這可能是更容易做遞歸，因爲單鏈表是遞歸結構：

• A NULL的副本只是NULL。
• 一個name_node_t的副本是新鮮malloc倒是name_node_t具有相同name作爲原始和複製原來的restp爲restp的。

Answer 3

自從我寫C++以來已經很長時間了。仍然：

看起來不像copy_list中有任何東西應該讓它進入無限循環。

邏輯有： while (current!=null) current = current->next;

也許copy_list被不好的名單通過呢？ （即最後一個元素沒有restp == null的列表）。

主要致電：
insertAfter（....）;
lastDelete（....）;
... copy_list（....）;

所以這個問題可能是insertAfter或lastDelete ......或者......

檢查lastDelete：

name_node_t *to_freep, *cur_nodep; 
for (cur_nodep = listP->headp; 
     cur_nodep->restp != NULL; 
     cur_nodep = cur_nodep->restp) {} 
to_freep = cur_nodep; 
cur_nodep->restp = to_freep->restp; 
free(to_freep); //what if listP->headp was null? i.e. list had size 0? 
--(listP->size); 

的問題

1. ，如果你通過了充足什麼列表中有0個元素？
2. 如果你傳遞了一個包含1個元素的列表，該怎麼辦？
3. 無論如何，在釋放「to_freep」之後，「to_freep」之前的節點沒有將restp設置爲null。所以第二個節點現在指向一個被刪除的節點！這意味着列表永遠不會終止。

更好lastDelete：（只是一個算法中，不記得語法了...）

if (head == null) return; //do nothing 
if (head->next == null) 
{ 
    listP->head = null; 
    listP->size = 0; 
    return; 
} 
node* prev = head; 
head = head->next; 
while (head->next != null) 
{ 
    prev = head; 
    head = head->next; 
} 
//now prev points to a 2nd last node 
//head points to last node 
free(head); 
prev->restp = null;