链表程序在收到来自用户的值后崩溃

Question

我的程序旨在运行多个函数，insertnode从用户那里获取值并使用节点创建它们的列表，并按从最小到最大的顺序对它们进行排序，printlist打印用空格分隔的值，mergelist按顺序合并两个列表，反向列表反转列表。命令提示符接受值，但一旦为第二个列表输入停止条件 （0），它就会崩溃。Visual Studio 未显示任何错误。我认为函数或指针有问题。有人跟我说了内存泄漏，但我不确定如何解决这个问题。

#include <iostream>
#include <stack>
using namespace std;
class node {
private:
    double num;
    node *link;
public:
    node() { }
    node(double m, node *n) { num = m; link = n; }
    node* getlink() { return link; }
    double getdata() { return num; }
    void setdata(double m) { num = m; }
    void setlink(node* n) { link = n; }
};
typedef node* nodeptr;
void insertnode(nodeptr& head, double m);
void printlist(nodeptr head);
nodeptr mergelists(nodeptr& head1, nodeptr& head2);
void reverselist(nodeptr& head);
int main()
{
    double input;a
    nodeptr head1 = NULL;       // Pointer to the head of List #1
    nodeptr head2 = NULL;       // Pointer to the head of List #2
    nodeptr temp;
    // Part 1 - Create two sorted lists
    cout << "-------------------------------------" << endl;
    cout << "CREATE LIST #1: " << endl;
    cout << "-------------------------------------" << endl;
    do {
        cout << "Enter value (0 to quit): ";
        cin >> input;
        insertnode(head1, input);
    } while (input != 0);
    cout << "-------------------------------------" << endl;
    cout << "CREATE LIST #2: " << endl;
    cout << "-------------------------------------" << endl;
    do {
        cout << "Enter value (0 to quit): ";
        cin >> input;
        insertnode(head2, input);
    } while (input != 0);
    // Part 1 - Print the lists to make sure that they are correct.
    printlist(head1);
    printlist(head2);
    // Part 2 - Merge the two lists and display the new merged list
    temp = mergelists(head1, head2);
    printlist(temp);
    // Part 3 - Reverse the merged list and then display it
    reverselist(temp);
    printlist(temp);

    return 0;
}
void insertnode(nodeptr& head, double m){
    nodeptr p = head;
    nodeptr k = p;
    if (!p){
        nodeptr n = new node(m, NULL);
    }
    else {
        while (m >= p->getdata()){
            k = p;
            p = p->getlink();
        }
        nodeptr n = new node;
        n->setdata(m);
        k->setlink(n);
        if (p){
            n->setlink(p);
        }
    }
}
void printlist(nodeptr head){
    nodeptr p = head;
    while (p){
        double m = p->getdata();
        cout << m << " ";
        p = p->getlink();
    }
    cout << endl;
}
nodeptr mergelists(nodeptr &head1, nodeptr &head2){
    nodeptr result = 0, last = 0;;
    if (head1->getdata() <= head2->getdata()){
        result = head1;
        head1 = head1->getlink();
    }
    else {
        result = head2;
        head2 = head2->getlink();
    }
    last = result;
    while (head1 && head2){
        if (head1->getdata() <= head2->getdata()){
            last->setlink(head1);
            last = head1;
            head1 = head1->getlink();
        }
        else{
            last->setlink(head2);
            last = head2;
            head2 = head2->getlink();
        }
    }
    if (head1) 
        last->setlink(head1);
    else if (head2) 
        last->setlink(head2);
    last = 0;
    head1 = 0;
    head2 = 0;
    return result;
}
void reverselist(nodeptr& head){
    stack<double> holder;
    nodeptr p = head;
    while (p){
        holder.push(p->getdata());
        p = p->getlink();
    }
    p = head;
    while (p){
        p->setdata(holder.top());
        holder.pop();
        p = p->getlink();
    }
}

Answer 1

此方法存在一些问题：

void insertnode(nodeptr& head, double m){
    nodeptr p = head;
    nodeptr k = p;
    if (!p)
    {
        head = new node(m, NULL); // Update head
    }
    else 
    {
        while (p && m >= p->getdata()) // Check for p!=NULL
        {
            k = p;
            p = p->getlink();
        }
        nodeptr n = new node;
        n->setdata(m);
        k->setlink(n);
        if (p)
        {
            n->setlink(p);
        }
    }
}

---

简化版本：

void insertnode(nodeptr& head, double m)
{
    nodeptr p = head;
    nodeptr k = nullptr;
    while (p && m >= p->getdata())
    {
        k = p;
        p = p->getlink();
    }
    if (!k)
    {
        head = new node(m, p);
    }
    else
    {
        k->setlink(new node(m, p));
    }
}

Answer 2

有两个问题是插入链表时没有更新头节点。 @uncletall之前的回答概述了这一点。

第二个问题非常简单 - 当您默认构造node时，您未能将link初始化为 NULL。 在node类中进行以下更改：

class node {
private:
    double num;
    node *link;
public:
    node() : link(0) { }   // here is the change here
   //...
   //... the rest of your code
};

默认构造node链接现在已初始化。 如果没有此更改，您的link节点就是垃圾值，因此当您在列表中插入更多项目时，您没有正确遍历链接。

更改类似于（但不完全）与此相同：

class node {
private:
    double num;
    node *link;
public:
    node() { link = 0; }   // here is the change here
   //...
   //... the rest of your code
};

不同之处在于，link在此处的构造函数主体中分配，而第一个示例在构造函数启动之前将链接初始化为 0。 两者都最终做了同样的事情。