返回节点链表时出现分段错误

Question

在 find(T item) 函数中，我检查输入的数据是否为字符串，然后我单独处理它，对于其他数据类型，我在其他情况下处理它，因为我使用的是字符串函数 compare( ) 检查匹配。当链表中有匹配的字符串和 returns 节点并打印节点数据时，程序运行良好，但是当找不到匹配的字符串时，程序不会返回空的 tmp 节点，而是崩溃并说“分段故障（核心已转储）”。有什么办法可以解决吗？

#include <iostream>
#include <typeinfo>
using namespace std;

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

    Node(){};
};

template <typename T>
class LinkedList {
private:
    Node<T> *head;
    Node<T> *tail;

public:
    LinkedList(){
        head = NULL;
        tail = NULL;
    }

    void insertHead(T item){
        Node<T> *tmp = new Node<T>();
        if (head == NULL){
            head = tmp;
            head->prev = NULL;
            head->data = item;
            head->next = NULL;
            tail = tmp;
        } else {
            tmp->next = head;
            tmp->data = item;
            tmp->prev = NULL;
            head->prev = tmp;
            head = tmp;
        }
    }

    void insertLast(T item){
        Node<T> *tmp = new Node<T>();
        tmp->data = item;
        if (head == NULL){
            head = tmp;
            head->prev = NULL;
            head->next = NULL;
            tail = tmp;
        } else {
            tmp->prev = tail;
            tail->next = tmp;
            tmp->next = NULL;
            tail = tmp;
        }
    }

    Node<T>* find(T item){
        Node<T> *tmp = head;
        if (typeid(item) == typeid(string)){
            string s, d;
            s = item;
            d = tmp->data;
            while(tmp != NULL){
                if(s.compare(d) == 0){
                    return tmp;
                }
                tmp = tmp->next;
                d = tmp->data;
            }
            Node<string> *tmp = new Node<string>();
            tmp->data = "";
            return tmp;
        } else {
            while(tmp != NULL){
                if(tmp->data == item){
                    return tmp;
                }
                tmp = tmp->next;
            }

            tmp = new Node<T>();
            tmp->data = -1;
            return tmp;
        }
    }

    void print(){
        Node<T> *tmp;
        tmp = head;
        while (tmp != NULL){
            cout << tmp->data << "->";
            tmp = tmp->next;
        }
        cout << endl;
    }
};

int main(){

    LinkedList<string> l;
    l.insertHead("Abc");
    l.insertHead("def");
    l.insertHead("ghi jk");

    Node<string>* tmp = new Node<string>();
    tmp = l.find("ghi");
    cout << tmp << endl;

    l.print();
}

Answer 1

问题是这个循环：

while(tmp != NULL){     // tmp is not null, good
    if(s.compare(d) == 0){
         return tmp;
    }
    tmp = tmp->next;    // after this tmp MIGHT be null!
    d = tmp->data;      // possibly dereferencing null-pointer, bad!
}

一旦这个循环到达列表的末尾并且没有找到搜索的字符串，它就会解除对空指针的引用，并且您会得到未定义的行为，这表现为分段错误。

在非字符串版本中，您做对了，据我所知，您根本不需要这两个版本。

s.compare(d) == 0

与s == d完全相同，与item == tmp->data相同。

唯一的区别就是 return 值，如果找不到该项目，我建议 return 一个 nullptr。如果列表包含值 "" 或 -1 怎么办？除了“默认值”之外，您将无法分辨列表中的值。

Answer 2

问题：

行中：

s = item;
d = tmp->data;
while(tmp != NULL){
    if(s.compare(d) == 0){
        return tmp;
    }
    tmp = tmp->next;
    d = tmp->data;
}

当 tmp->next 变为 NULL 时，您将对 d = tmp->data; 使用 NULL->data，这会导致分段错误。

解法：

将代码替换为：

s = item;
while(tmp != NULL){
    d = tmp->data;
    if(s.compare(d) == 0){
        return tmp;
    }
    tmp = tmp->next;
}

补充信息：

正如churill所说，C++字符串比较不像Java，你可以使用s == d。实际上正因为如此，需要字符串专业化。
我也会考虑使用 nullptr 而不是 NULL。
您不应使用 using namespace std;（更多信息 here）。
在 cout << tmp << endl; 中打印 tmp 会打印 tmp 的地址，而不是它存储的值。
tmp->data = -1; return tmp; 将导致错误。您可能应该改用 return NULL; 或 return nullptr;。
Node<string>* tmp = new Node<string>(); tmp = l.find("ghi"); 使用未释放的额外 space。请改用 Node<string>* tmp; tmp = l.find("ghi");。

完整代码：

#include <iostream>
using std::endl;
using std::string;
using std::cout;

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

    Node(){};
};

template <typename T>
class LinkedList {
private:
    Node<T> *head;
    Node<T> *tail;

public:
    LinkedList(){
        head = nullptr;
        tail = nullptr;
    }

    void insertHead(T item){
        Node<T> *tmp = new Node<T>();
        if (head == nullptr){
            head = tmp;
            head->prev = nullptr;
            head->data = item;
            head->next = nullptr;
            tail = tmp;
        } else {
            tmp->next = head;
            tmp->data = item;
            tmp->prev = nullptr;
            head->prev = tmp;
            head = tmp;
        }
    }

    void insertLast(T item){
        Node<T> *tmp = new Node<T>();
        tmp->data = item;
        if (head == nullptr){
            head = tmp;
            head->prev = nullptr;
            head->next = nullptr;
            tail = tmp;
        } else {
            tmp->prev = tail;
            tail->next = tmp;
            tmp->next = nullptr;
            tail = tmp;
        }
    }

    Node<T>* find(T item){
        Node<T> *tmp = head;
        while(tmp != nullptr){
            if(tmp->data == item){
                return tmp;
            }
            tmp = tmp->next;
        }
        return nullptr;
    }

    void print(){
        Node<T> *tmp;
        tmp = head;
        while (tmp != nullptr){
            cout << tmp->data << "->";
            tmp = tmp->next;
        }
        cout << endl;
    }
};

int main(){

    LinkedList<string> l;
    l.insertHead("Abc");
    l.insertHead("def");
    l.insertHead("ghi jk");

    Node<string>* tmp;
    tmp = l.find("ghi");

    cout << ((tmp == nullptr) ? "nullptr":tmp->data) << endl;

    l.print();
}

Answer 3

对于初学者来说，成员函数find可以在一开始就调用未定义的行为

Node<T>* find(T item){
    Node<T> *tmp = head;
    if (typeid(item) == typeid(string)){
        string s, d;
        s = item;
        d = tmp->data;
        ^^^^^^^^^^^^^
        //

因为一般来说head可以等于nullptr.

在 while 循环中，您也没有检查指针 tmp 是否等于 nullptr。

tmp = tmp->next;
d = tmp->data;

正在创建虚拟节点

Node<string> *tmp = new Node<string>();
tmp->data = "";
return tmp;

是个坏主意，可能会导致内存泄漏。最好return一个空指针。

这个在main中分配一个节点

Node<string>* tmp = new Node<string>();
tmp = l.find("ghi");

产生内存泄漏。

至少可以通过以下方式声明和定义函数

Node<T> * find( const T &item )
{
    Node <T> *result = head;

    while ( result && result->data != item ) result = result->next;

    return result;
}

此外还可以通过以下方式重载

template <typename BinaryPredicate>
Node<T> * find( const T &item, BinaryPredicate binary_predicate )
{
    Node <T> *result = head;

    while ( result && not binary_predicate( result->data, item ) ) result = result->next;

    return result;
}

返回节点链表时出现分段错误

Segmentation fault while returning a Node Linkedlist

c++

templates

class

linked-list

function-definition