合并两个排序列表 - 不工作

Here is my code for merging two sorted lists. The problem is in the mergelists function as well as I start without debugging, it stops.

这是我合并两个排序列表的代码。问题在于合并列表功能以及我在没有调试的情况下启动,它会停止。

#include <iostream>
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);
nodeptr search(nodeptr head, double searchterm);
void insert(nodeptr afterme, double newdata);
int main()
{
    double input;
    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;
        // Insert the "input" value into the list
        insertnode(head1, input);
    } while (input != 0);

    cout << "-------------------------------------" << endl;
    cout << "CREATE LIST #2: " << endl;
    cout << "-------------------------------------" << endl;
    do {
        cout << "Enter value (0 to quit): ";
        cin >> input;
        // Insert the "input" value into the list       
        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
    cout << "Merge lists: " << endl;
    temp = mergelists(head1, head2);
    printlist(temp);
    // Part 3 - Reverse the merged list and then display it

    return 0;
}

nodeptr search(nodeptr head, double searchterm) 
{
    nodeptr p = head;
    nodeptr q = head->getlink();
    if (p == NULL)
        return NULL;
    else
    {

        /*set p from beginning, q is the next node of p
        *while q is not NULL, search until the 'searchterm' < value of q
        *if q is NULL, means the 'searchterm' larger than all element in the  linked list, p is the last position, so just attatch the new node after the last node.
        *if q is not NULL and 'q->getdata() < searchterm' means, the 'searchterm' > p and < q, so put it in between p and q.
        *for both cases, the position is after the p node.
        */

        while (p != NULL)
        {
            q = p->getlink();
            while (q != NULL && q->getdata() < searchterm)
            {
                p = p->getlink();
                q = q->getlink();
            }
            return p;
        }
    }
}

void insertnode(nodeptr& head, double m)
{
    // CASE 1 - List is empty
    if (head == NULL)
    {
        head = new node(m, NULL);
    }

    // CASE 2 - List is not empty and new value is < 1st value
    else if (m < head->getdata())
    {
        head = new node(m, head);
    }

    // CASE 3 - List is not empty and new value goes inside list
    else
    {
        // search for correct location - notes on Search
        nodeptr afterme = search(head,m);
        // insert at this location -- see notes on insert inside list
        nodeptr temp;
        temp = new node(m, afterme->getlink());
        afterme->setlink(temp);
    }
}

void printlist(nodeptr head)
{
    nodeptr p;
    p = head;
    while (p != NULL)
    {
        cout << p->getdata() << endl;
        p = p->getlink();
    }
}

// Problem is here

//问题在这里

nodeptr mergelists(nodeptr& head1, nodeptr& head2)
{
    if (head1 == NULL)
        return head2;
    if (head2 == NULL)
        return head1;
    nodeptr p1 = head1;
    nodeptr p2 = head2;
    nodeptr head = NULL;
    nodeptr temp = head;
    while (head1 != NULL&&head2 != NULL)
    {

        if (head == NULL)
        {
            if (p1->getdata() < p2->getdata() || p1->getdata() == p2->getdata())
            {
                head = p1;
                p1 = p1->getlink();
            }
            else
            {
                head = p2;
                p2 = p2->getlink();
            }
        }
        else
        {

            if (p1->getdata() < p2->getdata() || p1->getdata() == p2->getdata())
            {
                temp = p1;
                temp->setlink(p1);              
                p1 = p1->getlink();
            }
            else
            {
                temp = p2;
                temp->setlink(p2);              
                p2 = p2->getlink();
            }
            temp = temp->getlink();
        }
    }
    if (p1 != NULL){
        while (p1 != NULL)
        {
            temp->setlink(p1);
            p1 = p1->getlink();
            temp = temp->getlink();
        }
    }
    if (p2 != NULL)
    {
        while (p2 != NULL)
        {
            temp->setlink(p2);
            p2 = p2->getlink();
            temp = temp->getlink();
        }
    }       
    return head;
}

Here is the image of my output: enter image description here

这是我输出的图像:在此处输入图像描述

1 个解决方案

#1

nodeptr mergelists(nodeptr& head1, nodeptr& head2)
{
if (head1 == NULL)
    return head2;
if (head2 == NULL)
    return head1;
nodeptr p1 = head1;
nodeptr p2 = head2;
nodeptr head = NULL;
nodeptr temp;
while (p1 != NULL && p2 != NULL) //here p1 and p2 should be checked for NULL
{
    if (head == NULL)
    {
        if (p1->getdata() <= p2->getdata())
        {
            head = p1;
            p1 = p1->getlink();
        }
        else
        {
            head = p2;
            p2 = p2->getlink();
        }
        temp=head;  // point temp to head
    }
    else
    {

        if (p1->getdata() <= p2->getdata())
        {
           // temp = p1; // this should be removed
            temp->setlink(p1);    //the temp's link should be set to p1           
            p1 = p1->getlink();
        }
        else
        {
           // temp = p2;
            temp->setlink(p2);   //temp's link should be set to p2           
            p2 = p2->getlink();
        }
        temp = temp->getlink();
    }
}
if (p1 != NULL){
     temp->setlink(p1); //here you can remove the while loop
}
if (p2 != NULL)
{
    temp->setlink(p2);
}       
return head;
}

And one more suggestion in your main function, while reading the inputs use a while loop instead of do while, because 0 is also getting added to the list before quitting. I am guessing u don't want that.

在main函数中还有一个建议,在读取输入时使用while循环而不是while,因为在退出之前0也会被添加到列表中。我猜你不想那样。