c++ - 关于单链表的困惑

因此，我最近正在学习链接列表。这些函数有些直截了当，但是当我检查输出时，总是很困惑。

在测试文件中，从测试1到测试3，我更改了std::cout行的位置，在测试1中，未显示输出。我不知道简单的提示行或行的顺序会如何影响链表的输出。这非常令人困惑(详细信息在每个测试的输出中提供)

我的函数，特别是InsertHead，SearchList，InsertAfter，PreviousNode有时在特定输出中是正确的。

对于我的InsertBefore函数，我使用了一个名为PreviousNode的函数来获取指向当前节点的上一个节点的指针，并使用InsertAfter在该前一个节点之后插入一个节点。但是，结果是无限的。 (不允许使用双向链表)

文件node.h

#include <iostream>
using namespace std;

template <typename T>
struct Node{
    T _item;
    Node<T>* _next;

    Node() {
        _item = T();
        _next = NULL;
    }

    Node(T item){
        _item = item;
        _next = NULL;
    }

    // Print the value of a node
    friend std::ostream& operator <<(std::ostream& outs, const Node<T> &printMe){
        outs << "[" << printMe._item << "]";
    }
};

// Print the entire linked list
template <typename T>
void PrintList(Node<T>* head){
    Node<T>* walker = head;

    while(walker != NULL){
        cout << *walker;
        cout << "->";
        walker = walker->_next;
    }

    cout << "|||";
}

// Insert an item to the head
template <typename T>
Node<T>* InsertHead(Node<T>* &head, const T& item){
    Node<T>* temp = new Node<T>(item);
    temp->_next = head;
    head = temp;
    return head;
}

// Search an element in list, return the pointer to that node
template <typename T>
Node<T>* SearchList(Node<T>* head, const T& item){

    Node<T>* temp = head;

    // Iterate temp to find the match item
    while (temp->_item != item && temp->_next != NULL)
        temp = temp->_next;

    if (temp->_item == item) // If found, return temp
        return temp;
    else
        return NULL;
}

// find previous node
template <typename T>
Node<T>* PreviousNode(Node<T>* head, Node<T>* prevToThis) {
    if (prevToThis == head)
        return NULL;
    else {
        Node<T> *prev = head;

        // Iterate it until it reaches the one before prevToThis
        while(prev->_next != NULL && prev->_next != prevToThis)
            prev = prev->_next;
        return prev;
    }
}

template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
    // Create a temp node
    Node<T>* temp;
    temp->_item = insertThis;

    if (afterThis->_next == NULL){
        temp->_next = NULL;
        afterThis->_next = temp;
    }
    else {
        // Point temp to next node
        temp->_next = afterThis->_next;

        // Point mark node to temp
        afterThis->_next = temp;
    }

    return temp;
}


// Insert an item before a node
template <typename T>
Node<T>* InsertBefore(Node<T>*& head, Node<T>* beforeThis, T insertThis){
    Node<T> *prev = PreviousNode(head, beforeThis);

    Node<T>* temp;

    // If current node is head node
    if (beforeThis == head){
        temp->_item = insertThis;
        temp->_next = head;
        head = temp;
    }

    // Other nodes
    else {
        temp = InsertAfter(prev, insertThis);
    }

    return temp;
}

文件main.cpp，测试1，运行InsertAfter函数:

int main(){
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);
    cout << endl;

    Node<int> *pos_50 = SearchList(head, 50);
    cout << "Insert 500 after 50: ";
    cout << endl;
    InsertAfter(pos_50, 500);
    PrintList(head);

    Node<int> *pos_0 = SearchList(head, 0);
    cout << "Insert 600 after 0: ";
    cout << endl;
    InsertAfter(pos_0, 600);
    PrintList(head);
}

输出，测试1，不输出其余代码

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50:

文件main.cpp，测试2:运行InsertAfter函数，类似于 test 1 ，但更改std::cout行的位置:

int main(){
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);

    cout << endl;
    cout << "Insert 500 after 50: ";
    cout << endl;
    Node<int> *pos_50 = SearchList(head, 50);

    InsertAfter(pos_50, 500);
    PrintList(head);

    cout << endl;
    cout << "Insert 600 after 0: ";
    cout << endl;
    Node<int> *pos_0 = SearchList(head, 0);
    InsertAfter(pos_0, 600);
    PrintList(head);
}

输出测试2:更改std::cout行的位置后，显示其余输出

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50:
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||
Insert 600 after 0:
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->[600]->|||

文件main.cpp test 3，像 test 1 一样运行InsertAfter，但是只运行一次:

int main() {
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);
    cout << endl;

    Node<int> *pos_50 = SearchList(head, 50);
    cout << "Insert 500 after 50: ";
    cout << endl;
    InsertAfter(pos_50, 500);
    PrintList(head);
}

输出测试3，输出如下:

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50:
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||

文件main.cpp测试4，运行测试4，将InsertAfter放在 test 3 之类，然后检查PreviousNode

int main() {
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);
    cout << endl;

    cout << "Insert 500 after 50: ";
    cout << endl;
    Node<int> *pos_50 = SearchList(head, 50);
    InsertAfter(pos_50, 500);
    PrintList(head);


    cout << "Previous node before 50: " << *PreviousNode(head, pos_50);
}

输出:上一个节点为0，不正确

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50:
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||
Previous node before 50: [0]

文件main.cpp test 5，类似于 test 4 ，类似地运行InsertAfter和PreviousNode，但是我首先运行PreviousNode。

int main(){
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);
    cout << endl;


    Node<int> *pos_50 = SearchList(head, 50);
    cout << "Previous node before 50: " << *PreviousNode(head, pos_50);
    cout << endl;
    cout << "Insert 500 after 50: ";
    cout << endl;
    InsertAfter(pos_50, 500);
    PrintList(head);
}

输出测试5，类似于测试4，但输出正确:

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Previous node before 50: [60]
Insert 500 after 50:
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||

Main.cpp测试6，仅运行InsertBefore

int main(){
    Node<int>* head = NULL;
    for (int i = 0; i < 10; i++)
        InsertHead(head, i * 10);
    PrintList(head);
    cout << endl;


    Node<int> *pos_50 = SearchList(head, 50);
    cout << "Insert 700 before 50: " << endl;
    InsertBefore(head, pos_50, 700);
    PrintList(head);

}

输出测试6:结果无限显示

[700]->[700]->[700]->[700]->[700]->

我衷心希望您能看一下并向我解释为什么测试1不显示其余的输出，为什么由于cout行的细微变化而导致4中的PreviousNode，以及为什么InsertBefore具有循环(即使我仅使用了该循环)以前的功能。非常感谢!

最佳答案

您必须以outs返回operator<<流。目前，您什么也没返回。它应该是:

friend std::ostream& operator <<(std::ostream& outs, const Node<T> &printMe){
    outs << "[" << printMe._item << "]";
    return outs; // added missing return
}

另外，InsertAfter具有悬空指针。只需观察gcc发出警告(在GCC和Clang上使用-Wall以及在Visual Studio上使用/ w4运行所有编译):

prog.cc: In function 'Node<T>* InsertAfter(Node<T>*, const T&) [with T = int]':
prog.cc:83:5: warning: 'temp' is used uninitialized in this function [-Wuninitialized]
   83 |     temp->_item = insertThis;
      |     ^~~~

令人反感的代码是:

template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
    // Create a temp node
    Node<T>* temp;
    temp->_item = insertThis;

temp变量是一个指针，而不是节点。最初，它指向没有特定内容，并且访问它是未定义的行为。您必须创建一个新节点:

template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
    // Create a temp node
    auto temp = new Node<T>;
    temp->_item = insertThis;

使用InsertBefore会更加复杂，因为有时需要一个新对象，而有时则不需要:

template <typename T>
Node<T>* InsertBefore(Node<T>*& head, Node<T>* beforeThis, T insertThis){
    Node<T> *prev = PreviousNode(head, beforeThis);

    Node<T>* temp;

因此，最安全的方法是重新组织一下代码:

if (beforeThis != head){
    return InsertAfter(prev, insertThis);
}
auto temp = new Node<T>;

temp->_item = insertThis;
temp->_next = head;
head = temp;

一般说明:最好使用std::unique_ptr和std::make_unique代替原始指针和new。如果可能，请完全避免使用new。如果正确使用std::unique_ptr，则大大减少了指针悬空和内存泄漏的可能性。
另外，我强烈建议您使用C++最佳做法。例如，使用nullptr而不是NULL向类的用户隐藏实现细节，在无法使用nullptr且无需对指针进行操作时返回引用，使用return而不是在可能的情况下通过引用参数进行修改，等等。上。
编辑
在开发代码时添加了咨询警告的建议。