Bằng cách trả về một con trỏ trỏ tới một nút, phần còn lại của danh sách có được trả lại không? C++

Question

Tôi có một dự án để làm nơi tôi phải thay đổi SLList thành LispList và thêm một vài chức năng khác. Câu hỏi duy nhất của tôi là Prof của tôi. đã yêu cầu chúng tôi không tạo các nút mới cho một hàm gọi là rest(), trong đó danh sách còn lại được trả về mà không có đầu.

Node* rest(){ 
     Node* nextToHead = head -> next; //this is a pointer to the next node in the list 
     return nextToHead; 
    } 

bằng cách sử dụng con trỏ nextToHead, nó sẽ trỏ đến phần còn lại của danh sách không? Nếu không, sẽ rất tuyệt nếu các bạn có thể cho tôi lời khuyên về cách trả lại danh sách mà không cần đầu và không sử dụng bất kỳ nút nào khác.

Answer 1

Khi bạn trả về con trỏ Node, mọi thứ có thể sử dụng và lạm dụng được hiển thị là Node. Điều này bao gồm phần còn lại của danh sách.

Giải pháp thông thường là để tóm tắt Node sau một số iterator để người dùng thậm chí không nhìn thấy Node. Tất cả những gì họ nhận được là một trình lặp. Các iterator vẫn cung cấp quyền truy cập vào phần còn lại của danh sách, vì vậy bạn phải hạn chế điều hơn nữa

SingleNode rest(){ 
    return SingleNode (head -> next); 
} 

nơi SingleNode trông giống như

class SingleNode 
{ 
    Node* node; 
public: 
    MyDataType& operator*() 
    { 
     return node->data; 
    } 
}; 

Nếu bạn không thể làm được điều này,

1. Tạo liên kết trong Nodeprivate để giới hạn quyền truy cập.
2. Làm cho SLList một người bạn của Node để chỉ Node và SLList mới có thể xem liên kết.
3. Không có bất kỳ chức năng truy cập nào cho các liên kết.

Ví dụ:

struct Node 
{ 
    friend class SLList; 
    MyDataType data; 
    // other public stuff 
private: 
    Node * next; 
    // other private stuff 
}; 

Bây giờ người nắm giữ một con trỏ Node không thể nhìn thấy phần còn lại của danh sách. Họ vẫn có thể làm nổ tung danh sách bằng cách làm hư hại số Node mà họ có quyền truy cập, nhưng họ phải làm việc với nó.

Answer 2

Có, mã của bạn là chính xác cho câu hỏi của bạn "không tạo nút mới cho hàm có tên là rest(), trong đó danh sách còn lại được trả về không có đầu".

Nhưng bạn cần phải xóa nút đầu trong trường hợp giáo sư của bạn muốn. Nhưng anh ấy không đề cập đến nó vì vậy tôi cho rằng anh ấy chỉ muốn trả lại phần còn lại mà không cần đầu.

template<typename T> 
struct ListNode{ 
    T value; 
    ListNode<T>* next; 
    ListNode(const T &v) : value(v), next(nullptr) {} 
}; 

ListNode<int>* rest(ListNode<int> *head) 
{ 
    if (head) // head is not nullptr 
     return nullptr; 
    else 
     return head->next; 
} 

Bạn có thể tưởng tượng như dưới đây:

Trong ví dụ, chúng tôi có một danh sách với một vài yếu tố và một con trỏ đầu mà trỏ đến phần tử đầu tiên:

0x1    0x2     0x3 
-------   -------------- 
|head |  --> |value1| next| --> ..... 
-------   -------------- 

để có nghĩa là:

& head = 0x1; // địa chỉ của đầu con trỏ là 0x1

head = 0x2; // con trỏ đầu sẽ trỏ đến bộ nhớ khối có địa chỉ 0x2, ý tôi là, phần tử đầu tiên của danh sách

tiếp theo = 0x3; // con trỏ tiếp theo sẽ trỏ đến bộ nhớ khối có địa chỉ 0x3, phần tử thứ hai của danh sách

Vì vậy, khi chúng ta gọi "return head-> next", bạn có thể dễ dàng thấy nó sẽ trả về 0x3, địa chỉ của yếu tố thứ hai.

Answer 3

Trong khi đó về mặt kỹ thuật không trả về con trỏ đến phần còn lại của danh sách hoặc ít nhất nút của nó, phần còn lại của danh sách Lisp là danh sách Lisp - không phải loại khác (như node).

"Danh sách Lisp" không có đầu như vậy; nó trông khá nhiều như thế này:

struct List 
{ 
    ElementType data; 
    List* next; 
}; 

và có các hoạt động

ElementType first(List* l) { return l->data; } /* or "car" */ 
List* rest(List* l) { return l->next; }  /* or "cdr" */ 

hoặc, như thành viên:

ElementType List::first() { return data; } 
List* List::rest() { return next; } 

Lưu ý rằng tất cả các nút trong danh sách Lisp là "người đứng đầu" của danh sách phụ của toàn bộ danh sách.