Sinlge Linked List, C++, 删除所有和搜索功能的问题。

Question

我试图实现一个单一的链接列表。但是，我在搜索和删除功能上遇到了问题。我得到了分段故障，我不知道为什么。谁能给我解释一下，我做错了什么，以及如何改进这段代码的工作？谢谢你的帮助

#include <iostream>

class T
{
private:
    float t;
public:
    T *next;
    T()
    {
        this->t = 0.0;
        this->next = NULL;
    }
    float getT()
    {
        return this->t;
    }
    T(float t, T* next)
    {
        this->t = t;
        this->next = next;
    }
    T(const T& tx)
    {
        this->t = tx.t;
        this->next = tx.next;
    }
    void print()
    {
        std::cout << this->t << "\n";
    }
};

class MyList
{
private:
    T *head;
public:
    T* add_T(T *x)
    {
        T *new_head = new T(*head);
        new_head -> next = head;
        head = new_head;
        return head;
    }
    void print()
    {
        for(T *curr = head; curr != NULL; curr = curr->next)
            curr->print();
    }
    void delete_all()
    {
        T *x = head;
        while (x!= NULL)
        {
            head = head->next;
            delete x;
            x = head;
        }
        head = NULL;
    }
    T * search_val(T * k)
    {
        if (this->head == NULL)
            return NULL;

        if (this->head->getT() == k->getT())
            return this->head;

        return search_val(this->head->next);
    }
};

int main()
{
    MyList ml;
    T a,b,c;

    ml.add_T(&a);
    ml.add_T(&b);
    ml.add_T(&c);
    ml.print();

    T *y = new T(3.14, NULL);
    T *x = ml.search_val(y);

    ml.delete_all();
    delete x,y;

    return 0;
}

Answer 1

看起来你的列表头没有初始化（可能应该是0）。T* add_T(T *x) 创建一个新元素？它可能应该只是将给定的元素插入到列表中，而不是创建一个新元素。如果你的List类有一个 T head; 你可以通过调用类似

T* next = t.head;
t.head = x;
x->next = next;

在这种情况下，销毁列表将是空的，因为列表元素来自堆。

Answer 2

class MyList
{
private:
    T *head;
public:
    T* add_T(T *x)
    {
        T *new_head = new T(*head);
        new_head -> next = head;
        head = new_head;
        return head;
    }

Q1：什么是 head 指向 MyList 是构造出来的？A1：我们无法知道（它是未定义的）。

Q2：为什么会有 add_T() 不使用 x 参数？A2: 它实际上并没有添加由 x，而不是重复当前的 head.

修复这两个bug会让你更进一步。

另请参见 如何调试小程序.

Answer 3

你在这里处理节点的方式是 main() 是完全错误的。 列表外的代码应该关注 价值观，不在 节点.

您没有初始化列表的 head 成员，作为 MyList 缺少一个默认的构造函数。

add_T() 完全忽略了它的 x 争论。 它是在制作一个 head 节点，然后将该副本插入到列表的前面。

您正在尝试 delete 返回的节点 search_val() 之后 delete_all() 已经 delete'd该节点。

试试像这样的东西代替。

#include <iostream>

class MyNode
{
public:
    float data;
    MyNode *next;

    MyNode(float data = 0.0f, MyNode* next = NULL)
        : data(data), next(next)
    {
    }

    void print() const
    {
        std::cout << data << std::endl;
    }
};

class MyList
{
private:
    MyNode *head;

public:
    MyList()
        : head(NULL)
    {
    }

    ~MyList()
    {
        delete_all();
    }

    MyNode* addToFront(float value)
    {
        head = new MyNode(value, head);
        return head;
    }

    /*
    MyNode* addToBack(float value)
    {
        MyNode **curr = &head;
        while (*curr != NULL)
            curr = &((*curr)->next);
        return (*curr = new MyNode(value));
    }
    */

    void print() const
    {
        for(MyNode *curr = head; curr != NULL; curr = curr->next)
            curr->print();
    }

    void delete_all()
    {
        for(MyNode *curr = head; curr != NULL; curr = head)
        {
            head = curr->next;
            delete curr;
        }
    }

    MyNode* search_val(float value)
    {
        for(MyNode *curr = head; curr != NULL; curr = curr->next)
        {
            if (curr->data == value)
                return curr;
        }
        return NULL;
    }
};

int main()
{
    MyList ml;

    ml.addToFront(3.14f);
    ml.addToFront(2.99f);
    ml.addToFront(1.25f);
    ml.print();

    if (ml.search_val(3.14f) != NULL)
        std::cout << "found" << std::endl;
    else
        std::cout << "not found" << std::endl;

    return 0;
}