1

所以我试图创建一个链接列表类来更好地理解指针和数据结构是如何工作的，但我一直遇到 -11 SIGSEGV 错误。当我查看错误时，它说我可能正在使用取消引用的指针或访问超出其边界的数组，但这些对我的程序都没有意义。我到处寻找类似的问题，但似乎没有一个适用于我的程序。其他人可以看到我做错了什么吗？

#include <stdexcept>
#pragma once
using namespace std;

#define NODE typename LinkedList<T>::Node*

template <typename T>
class LinkedList {
public:
    void AddHead(const T& data); //Adds new node to the beginning of the list
    void AddTail(const T& data); //Adds new node to the end of the list
    LinkedList(); //Default constructor
    LinkedList(const LinkedList<T>& list); //Copy constructor

    struct Node {
        /*Individual node that stores the data*/
        T data;
        Node* prev;
        Node* next;
        Node(); //Default constructor for node
        Node(T _data); //Data constructor for node
        Node(T _data, Node* _prev, Node* _next); //Full constructor for node
    };
private:
    NODE head = nullptr;
    NODE tail = nullptr;
    unsigned int count;

};

/*Function definitions*/

template <typename T>
void LinkedList<T>::AddHead(const T& data) {
    NODE tempRef = new Node(data, nullptr, head);
    head->prev = tempRef;
    head = tempRef;
    delete tempRef;
    count++;
}

template <typename T>
void LinkedList<T>::AddTail(const T& data) {
    NODE tempRef = new Node(data, tail, nullptr);
    tail->next = tempRef;
    tail = tempRef;
    delete tempRef;
    count++;
}

template <typename T>
LinkedList<T>::LinkedList() {
    count = 0;
    head = nullptr;
    tail = nullptr;
}

template <typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& list) {
    this->head = list.head;
    this->tail = list.tail;
    this->count = list.count;
}

/*Node Constructors*/

template <typename T>
LinkedList<T>::Node::Node() {
    next = nullptr;
    prev = nullptr;
}

template <typename T>
LinkedList<T>::Node::Node(T _data) {
    next = nullptr;
    prev = nullptr;
    data = _data;
}

template <typename T>
LinkedList<T>::Node::Node(T _data, Node* _prev, Node* _next) {
    next = _next;
    prev = _prev;
    data = _data;
}
4

2 回答 2

1

这两个函数AddHead都有AddTail一个严重的错误，因为分配的节点被立即删除

head = tempRef;
delete tempRef;

和

tail = tempRef;
delete tempRef;

所以指针 head 和 tail 具有无效值。

此外，功能不会更新tail，并且head在每个功能中都相应地更新。

最初两个指针都等于nullptr。所以这些陈述

head->prev = tempRef;

和

tail->next = tempRef;

导致未定义的行为。

该函数AddHead可以通过以下方式定义

template <typename T>
void LinkedList<T>::AddHead(const T& data) {
    NODE tempRef = new Node(data, nullptr, head);

    if ( head == nullptr )
    {
        head = tail = tempRef;
    }
    else
    {
        head = head->prev = tempRef;
    }

    count++;
}

该功能AddTail看起来像

template <typename T>
void LinkedList<T>::AddTail(const T& data) {
    NODE tempRef = new Node(data, tail, nullptr);

    if ( tail == nullptr )
    {
        tail = head = tempRef;
    }
    else
    {
        tail = tail->next = tempRef;
    }

    count++;
}

复制构造函数（和复制赋值运算符）要么应该定义为已删除，要么应该对作为参数传递的列表进行深层复制。

否则，两个列表将尝试删除相同的节点两次（在你的析构函数中）。

该结构Node应声明为私有类成员。

于 2020-02-24T11:47:16.020 回答
0

您在和delete中添加到列表中的节点。这会在列表中留下指向垃圾的指针。AddTailAddHead

此外，尚不清楚如何使用您的链表。您不能调用AddHeadif headis nullptr（因为AddHead取消引用head），也不能调用AddTailif tailis nullptr。由于您的构造函数同时设置head和tail等于nullptr，接下来您可以做什么？

如果headto be是合法的nullptr，为什么不AddHead检查head->prev = tempRef;if headisnullptr呢？

我强烈敦促您记录您的代码。例如，AddHead被调用所需的先决条件是什么？head如果是的话，打电话应该是安全的，nullptr还是要求它不是？为什么没有记录？

于 2020-02-24T11:37:37.680 回答