Mã hóa một hàm để sao chép danh sách liên kết trong C++

Question

Tôi cần triển khai hàm auxilliary, có tên là copyList, có một tham số, một con trỏ đến một ListNode. Hàm này cần trả về một con trỏ tới nút đầu tiên của một bản sao của danh sách liên kết gốc. Vì vậy, nói cách khác, tôi cần mã hóa một hàm trong C++ mà lấy một nút tiêu đề của một danh sách liên kết và các bản sao toàn bộ danh sách liên kết, trả về một con trỏ tới nút tiêu đề mới. Tôi cần trợ giúp triển khai chức năng này và đây là những gì tôi có ngay bây giờ.

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; 
} 

Ngoài ra, đây là cấu trúc Listnode tôi đang làm việc với:

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

Lưu ý: một yếu tố tôi chạy vào với chức năng này là ý tưởng trở về một con trỏ đến một biến địa phương.

Answer 1

Câu hỏi đầu tiên bạn cần tự hỏi mình là ngữ nghĩa của bản sao là gì. Cụ thể, bạn đang sử dụng Student* làm nội dung nút. Sao chép nội dung nút nghĩa là gì?Chúng ta có nên sao chép con trỏ sao cho hai danh sách sẽ trỏ đến (chia sẻ) cùng một cá thể học sinh, hoặc bạn nên thực hiện một số deep copy?

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

Câu hỏi tiếp theo bạn nên tự hỏi mình là cách bạn sẽ phân bổ các nút cho danh sách thứ hai. Hiện tại, bạn chỉ phân bổ 1 nút trong bản sao.

Tôi nghĩ bạn mã nên trông giống như:

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; 
} 

---

Nếu bạn thích chia sẻ các trường hợp sinh viên giữa hai danh sách, bạn có thể sử dụng

copy->student = current->student; 

thay vì

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

Answer 2

Tuyên bố copy->next = current->next là sai. Bạn nên làm

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

Vì bạn cần một bản sao của danh sách liên kết, bạn cần phải tạo ra một nút mới trong vòng lặp trong khi vượt qua thông qua danh sách ban đầu.

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; 

Nhớ đến delete các nút trong danh sách được liên kết.

Answer 4

Đây là câu hỏi tuyệt vời vì bạn đã tự thực hiện phần lớn công việc, tốt hơn nhiều so với hầu hết các câu hỏi "làm bài tập về nhà cho tôi".

Một vài điểm.

Trước tiên, điều gì xảy ra nếu bạn chuyển vào danh sách trống? Bạn có thể muốn nắm bắt điều đó và chỉ trả lại một danh sách trống cho người gọi.

Thứ hai, bạn chỉ cấp phát nút đầu tiên trong danh sách sao chép, bạn cần thực hiện một nút trên mỗi nút trong danh sách gốc.

Giống như (pseudo-code (nhưng C++ - tương tự) cho bài tập về nhà, xin lỗi):

# 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 

Và, trong khi bạn đang đúng mà bạn không nên trả về một con trỏ đến một biến đống địa phương, đó là không phải những gì bạn đang làm. Biến bạn đang trả lại các điểm đến bộ nhớ phân bổ được phân bổ theo heap, sẽ tồn tại chức năng thoát.

Answer 5

@pat, tôi đoán bạn sẽ nhận được seg_fault, vì bạn chỉ tạo bộ nhớ một lần. Bạn cần tạo bộ nhớ (về cơ bản gọi là 'mới') cho mỗi nút. Tìm hiểu, nơi bạn cần sử dụng từ khóa 'mới', để tạo bộ nhớ cho tất cả các nút.

Khi bạn đã hoàn tất việc này, bạn cần liên kết nó với nút trước đó, vì đó là một danh sách được liên kết đơn lẻ, bạn cần phải duy trì con trỏ đến nút trước đó. Nếu bạn muốn tìm hiểu và sẽ có thể nhớ tất cả cuộc sống, không thấy bất kỳ mã nào được đề cập ở trên. Hãy thử suy nghĩ các yếu tố đã đề cập ở trên và cố gắng tìm ra mã của riêng bạn.

Answer 6

Khi những người khác có po liên quan, bạn cần gọi new cho mỗi nút trong danh sách gốc để cấp không gian cho bản sao, sau đó sao chép nút cũ sang bản sao mới và cập nhật con trỏ trong nút được sao chép.

một yếu tố khác mà tôi đang chạy vào với hàm này là ý tưởng trả về một con trỏ đến biến cục bộ.

Bạn không trả lại con trỏ cho biến cục bộ; khi bạn gọi là new, bạn đã cấp phát bộ nhớ trên heap và đang trả về con trỏ (nghĩa là bạn cần nhớ gọi số delete để giải phóng khi bạn hoàn thành danh sách mới, từ bên ngoài chức năng) .

Answer 7

Tôi đã cố gắng làm điều tương tự. Yêu cầu của tôi là:

1. Mỗi nút là một lớp rất cơ bản và đơn giản (tôi đã chuyển khỏi mô hình cấu trúc).
2. Tôi muốn tạo một bản sao sâu, và không chỉ là một con trỏ đến danh sách được liên kết cũ.

Cách mà tôi đã chọn để làm điều này là với C++ mã sau:

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; 
} 

này hoạt động tốt, không có lỗi. Bởi vì "đầu" là một trường hợp đặc biệt, cần phải thực hiện một con trỏ "hiện tại" của tôi.