问题描述:

My program is meant to run several functions, insertnode takes values from the user and creates a list of them using nodes and sorts them in order from least to greatest, printlist prints the values separated by spaces, mergelist merges the two lists in order, and reverselist reverses the list. The command prompt accepts values but once the stopping condition (0) is entered for the second list it crashes. Visual Studio shows no errors. I figure something is either wrong with the functions or the pointers. Someone spoke to me of a memory leak but Im unsure as to how to fix that.

#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();

}

}

网友答案:

There are a few issues with this method:

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);
        }
    }
}

The simplified version:

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));
    }
}
网友答案:

There are two issue is that you are not updating the head node when you insert into the linked list. The previous answer by @uncletall outlined this.

The second issue is very simple -- you failed to initialize the link to NULL when you default construct a node. Make the following change in your node class:

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

When you default construct a node the link is now initialized. Without this change, your link node was a garbage value, thus you were not traversing the links properly when you were inserting more items in the list.

The change is similar to (but not exactly) the same as this:

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

The difference is that link is assigned in the body of the constructor here, while the first example initializes the link to 0 before the constructor has started. Both wind up doing the same thing.

相关阅读:
Top