单向链表 C++ 构造函数、析构函数和打印输出

Question

单向链表 C++ 构造函数、析构函数和打印输出

3

我是一个初学者，正在学习C++，目前在制作单向链表。我遇到了一些问题，思考了很长时间，搜索了很多资料，但仍然没有找到这段代码的答案，所以我请求一些帮助。

这是我的linked.h文件：

template <class T>
class Node {
    public:
        T data;
        Node<T>* next;
};

template <class T>
class List {
    private:
        Node<T> *head;
    public:
        List() : head(NULL) {};
        ~List() {
            Node<T>* ptr, tmp;
            for(ptr = head->next; ptr == NULL; ptr = head->next) {
                delete ptr;
            }     
        }
        List(T* arr, int n_nodes) {
            head = NULL; 
            Node<T> *tmp = head;
            for(int i = 0; i < n_nodes; i++) {
                Node<T>* node = new Node<T>;
                node->data = arr[i];
                if(head == NULL) {
                    head->next = node;
                    tmp = node;
                }
                else {
                    tmp->next = node;
                    node->next = NULL;
                    tmp = node;
                }
            }
        }
        friend std::ostream& operator<<(std::ostream& out, List<T>& rhs) {                                                                                                                                 
            Node<T>* cur = rhs.head;
            out << cur;
            while(cur != NULL) {       
                if(cur->next != NULL) { 
                    out << cur->data << ", ";
                    cur = cur->next;
                }
                else
                    out << cur->data << " ";
            }
            return out;
        }
};

这是我的main.cc文件。

#include <iostream>
#include "linked.h"

int main() {
    int array[5] = {12, 7, 9, 21, 13};
    List<int> li(array, 5);
    std::cout << li;

    return 0;
}

我在运行构造函数时不断收到分段错误，但我不知道原因。我犯了什么错误？任何帮助都将不胜感激！

- Erica

3

我看到的第一个明显的错误是：“如果(head == NULL){head->next = node; ...}” - Paul R

想一想：如果 head 是 NULL，那么当你尝试给 head->next 赋值时会发生什么？ - Paul R

Erica，head->next 对你意味着什么？ - YSC

如果头节点为空，那么意味着你需要为头节点创建一个新的节点。 - stark

那么，我现在是不是可以开始像这样输入值：Node<T> *tmp = head; node->data = arr[i];？ - Erica

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aconcagua · Accepted Answer

你可以用指向指针的指针来解决这个问题：

List(T* arr, int n_nodes)
{
    Node<T>** tmp = &head; // tmp *pointing* to uninitialized(!) head pointer
    for(int i = 0; i < n_nodes; i++)
    {
        Node<T>* node = new Node<T>();
        node->data = arr[i];
        // now the trick:
        *tmp = node; // !!!
        // you now have assigned the new node to whatever pointer
        // the tmp pointer points to - which initially is - guess - head...

        // but we now need to advance!
        tmp = &node->next;
    }
    // tmp now points to latestly created node's next pointer
    // (or still head, if no nodes where created because of n_nodes == 0)
    // be aware that this one still is not initialized! so:
    *tmp = nullptr;
}

你的析构函数也必然会失败：

Node<T>* ptr, tmp;
for(ptr = head->next; ptr == NULL; ptr = head->next)
{
    delete ptr; // you delete ptr, but advancing (ptr = head->next)
                // is done AFTERWARDS, so you'd access already deleted memory
                // undefined behaviour
}

此外，您不应删除头节点！如果头节点是nullptr，则可能会出现未定义的行为。

请尝试以下方法：

while(head)
{
    Node<T>* tmp = head; // need a copy of pointer
    head = head->next;   // need to advance BEFORE deleting
    delete tmp;          // now can delete safely
}