編寫一個函數來複制C++中的鏈接列表

Question

我需要實現一個名爲copyList的輔助函數，它有一個參數，一個指向ListNode的指針。這個函數需要返回一個指向原始鏈表副本的第一個節點的指針。換句話說，我需要在C++中編寫一個函數，該函數採用鏈表的頭節點並複製整個鏈表，並將指針返回給新的頭節點。我需要幫助實現這個功能，這就是我現在所擁有的。

Listnode *SortedList::copyList(Listnode *L) { 

    Listnode *current = L; //holds the current node 

    Listnode *copy = new Listnode; 
    copy->next = NULL; 

    //traverses the list 
    while (current != NULL) { 
     *(copy->student) = *(current->student); 
     *(copy->next) = *(current->next); 

     copy = copy->next; 
     current = current->next; 
    } 
    return copy; 
} 

而且，這是Listnode結構我一起工作：

struct Listnode {  
    Student *student; 
    Listnode *next; 
}; 

注：我正在與此功能的另一因素是一個指針返回到局部變量的想法。

Answer 1

你需要問自己的第一個問題是複製語義是什麼。特別是，您使用的是Student*作爲節點內容。複製節點內容是什麼意思？我們是否應該複製指針，以便兩個列表指向（共享）相同的學生實例，還是應該執行deep copy？

struct Listnode {  
    Student *student; // a pointer? shouldn't this be a `Student` object? 
    Listnode *next; 
}; 

你應該問自己接下來的問題是，你將如何分配節點到第二份名單。目前，您只在副本中分配1個節點。

我覺得你的代碼應該看起來更像是：

Listnode *SortedList::copyList(Listnode *L) { 

    Listnode *current = L; 

    // Assume the list contains at least 1 student. 
    Listnode *copy = new Listnode; 
    copy->student = new Student(*current->student); 
    copy->next = NULL; 

    // Keep track of first element of the copy. 
    Listnode *const head = copy; 

    // 1st element already copied. 
    current = current->next; 

    while (current != NULL) { 
     // Allocate the next node and advance `copy` to the element being copied. 
     copy = copy->next = new Listnode; 

     // Copy the node contents; don't share references to students. 
     copy->student = new Student(*current->student); 

     // No next element (yet). 
     copy->next = NULL; 

     // Advance 'current' to the next element 
     current = current->next; 
    } 

    // Return pointer to first (not last) element. 
    return head; 
} 

---

如果您願意分享兩個列表之間的學生的情況下，你可以使用

copy->student = current->student; 

，而不是

copy->student = new Student(*current->student); 

Answer 2

該聲明 copy->next = current->next 是錯誤的。你應該做

Create the first node copy here 
copy->student = current->student; 
copy->next = NULL; 
while(current->next!=NULL) 
{ 
    Create new node TEMP here 
    copy->next = TEMP; 
    TEMP->student = current->student; 
    TEMP->next = NULL; 
    copy = TEMP; 
} 

Answer 3

由於需要鏈表的副本，你需要在循環創建一個新的節點，同時通過原始列表遍歷。

Listnode *startCopyNode = copy; 

while (current != NULL) { 
    *(copy->student) = *(current->student); 
    copy->next = new Listnode; 
    copy = copy->next; 
    current = current->next; 
} 

copy->next = NULL; 
return startCopyNode; 

記得要delete鏈表的節點。

Answer 4

這是一個優秀問題，因爲你自己做了大量的工作，遠遠勝過大多數「請爲我做我的作業」的問題。

幾點。

首先，如果你傳入一個空列表會發生什麼？您可能希望先捕獲該信息，然後向呼叫者返回一個空列表。

其次，您只分配副本列表中的第一個節點，您需要在原始列表中爲每個節點執行一個。

類似的信息（僞代碼（但C++ - 等）的家庭作業，不好意思）：

# Detect empty list early. 

if current == NULL: 
    return NULL; 

# Do first node as special case, maintain pointer to last element 
# for appending, and start with second original node. 

copy = new node() 
last = copy 

copy->payload = current->payload 
current = current->next 

# While more nodes to copy. 

while current != NULL: 
    # Create a new node, tracking last. 

    last->next = new node() 
    last = last->next 

    # Transfer payload and advance pointer in original list. 

    last->payload = current->payload 
    current = current->next 

# Need to terminate new list and return address of its first node 

last->next = NULL 
return copy 

而且，雖然你是正確的，你不應該返回一個指針到一個局部堆棧變量，那是不是你在做什麼。你正在返回的變量指向堆分配內存，這將存活功能退出。

Answer 5

@pat，我想你會得到一個seg_fault，因爲你只創建一次內存。您需要爲每個節點創建內存（基本上稱爲「新建」）。找出需要使用「新」關鍵字的位置，爲所有節點創建內存。

一旦你完成了這個，你需要將它鏈接到前一個節點，因爲它是一個單獨的鏈表，所以你需要保持一個指向前一個節點的指針。如果你想學習，並應該能夠記住所有的生活，不要看到上面提到的任何代碼。試着去思考上面提到的因素，並試着想出自己的代碼。

Answer 6

由於其他人有寶您需要在原始列表中爲每個節點調用new來爲副本分配空間，然後將舊節點複製到新節點並更新複製節點中的指針。

我用這個函數運行的另一個因素是返回指向局部變量的指針的想法。

您沒有返回指向局部變量的指針;當你調用new時，你在堆上分配了內存並且正在返回一個指向該內存的指針（這當然意味着當你完成新列表時，你需要記得調用delete來釋放它，從外部的函數） 。

Answer 7

我一直在嘗試做同樣的事情。我的要求是：

1.每個節點是一個非常基本和簡單的類（我離開了結構模型）。
2.我想創建一個深層副本，而不僅僅是一個指向舊鏈表的指針。

，我選擇這樣做的方法是使用下面的C++代碼：

template <class T> 
Node <T> * copy(Node <T> * rhs) 
{ 
    Node <T> * current = new Node<T>(); 
    Node <T> * pHead = current; 
    for (Node <T> * p = rhs; p; p = p->pNext) 
    { 
     Node <T> * prev = current; 
     prev->data = p->data; 
     if (p->pNext != NULL) 
     { 
      Node <T> * next = new Node<T>(); 
      prev->pNext = next; 
      current = next; 
     } 
     else 
     { 
      prev->pNext = NULL; 
     } 
    } 
    return pHead; 
} 

這種運作良好，沒有任何錯誤。由於「頭」是一種特殊情況，因此需要實現「當前」指針。