Posted on by

simple node and list merge

Insert-sorted node list.
  1. #include "stdafx.h"
  2. #include <stdlib.h>
  4. #include <iostream>
  5. #include <iomanip>
  6. using namespace std;
  8. class Node
  9. {
  10. public:
  11.     Node();
  12.     ~Node();
  13.     void    SetData(int n) { m_data = n; };
  14.     int     GetData() { return m_data; };
  15.     Node*   Next() { return m_lpNext; };
  16.     void    SetNext(Node* newPos);
  17.     void    Print();
  19. protected:
  20.     int     m_data;
  21.     Node*   m_lpNext;
  22. };
  24. Node::Node() :m_data(0), m_lpNext(nullptr)
  25. {
  27. }
  29. Node::~Node()
  30. {
  31.     cout <<  " begin to delete-" << GetData() << endl;
  32. }
  34. void Node::Print()
  35. {
  36.     cout << "data=" << m_data << " next=" << m_lpNext << endl;
  37. }
  39. void Node::SetNext(Node* newPos)
  40. {
  41.     if ( newPos )
  42.     {
  43.         m_lpNext = newPos;
  44.     }
  45. }
  47. class NodeList
  48. {
  49. public:
  50.     NodeList() :m_pHead(nullptr), m_pLast(nullptr)
  51.     {
  53.     };
  54.     ~NodeList()
  55.     {
  56.         while (m_pHead)
  57.         {
  58.             Node* temp = m_pHead;
  59.             m_pHead = temp->Next();
  60.             delete temp;
  61.         }
  63.         m_pHead = nullptr;
  64.         m_pLast = nullptr;
  65.     };
  67.     void Print()
  68.     {
  69.         Node * temp = m_pHead;
  70.         while (temp)
  71.         {
  72.             temp->Print();
  73.             temp = temp->Next();
  74.         }
  75.     }
  77.     bool    push_back(int n)
  78.     {
  79.         if (m_pHead == nullptr)
  80.         {
  81.             m_pHead = new Node;
  82.             if (m_pHead)
  83.                 m_pHead->SetData(n);
  85.             m_pLast = m_pHead;
  86.         }
  87.         else
  88.         {
  89.             Node* newPos = new Node;
  90.             if (newPos)
  91.             {
  92.                 newPos->SetData(n);
  93.                 m_pLast->SetNext(newPos);
  94.                 m_pLast = m_pLast->Next();
  95.             }
  96.         }
  98.         return true;
  99.     };
  101.     //! add list2 to the last
  102.     void MergeList(NodeList& list2)
  103.     {
  104.         Node* newHead = list2.GetHead();
  105.         while (newHead)
  106.         {
  107.             push_back(newHead->GetData());
  108.             newHead = newHead->Next();
  109.         }
  110.     };
  112.     Node*   GetHead()
  113.     {
  114.         return m_pHead;
  115.     };
  116. protected:
  117.     Node*   m_pHead;
  118.     Node*   m_pLast;
  119. };
  121. int _tmain(int argc, _TCHAR* argv[])
  122. {
  123.     NodeList nodeTest;
  124.     nodeTest.push_back(1);
  125.     nodeTest.push_back(2);
  126.     nodeTest.push_back(3);
  127.     nodeTest.push_back(4);
  128.     nodeTest.push_back(5);
  129.     nodeTest.push_back(6);
  131.     nodeTest.Print();
  133.     NodeList nodeTest2;
  135.     nodeTest2.push_back(11);
  136.     nodeTest2.push_back(22);
  137.     nodeTest2.push_back(33);
  138.     nodeTest2.push_back(44);
  139.     nodeTest2.push_back(55);
  140.     nodeTest2.push_back(66);
  142.     nodeTest.MergeList(nodeTest2);
  144.     nodeTest.Print();  // should print out 1,2,3,...11,22,33,...
  146.     return 0;
  147. }
this is the first version and there is not sort function. //上面是第一个版本，没有sort的功能。
below code has the sort function. //下面是带sort的功能。
===============================
#include "stdafx.h"#include <stdlib.h>#include <iostream>#include <iomanip>using namespace std;
 
class Node
{
public:
    Node();
    ~Node();
    void    SetData(int n) { m_data = n; };
    int     GetData() { return m_data; };
    Node*   Next() { return m_lpNext; };
    void    SetNext(Node* newPos);
    void    Print();
 
protected:
    int     m_data;
    Node*   m_lpNext;
};
 
Node::Node() :m_data(0), m_lpNext(nullptr)
{
 
}
 
Node::~Node()
{
    cout <<  " begin to delete-" << GetData() << endl;
}
 
void Node::Print()
{
    cout << "data=" << m_data << " next=" << m_lpNext << endl;
}
 
void Node::SetNext(Node* newPos)
{
    if ( newPos )
    {
        m_lpNext = newPos;
    }
}
 
class NodeList
{
public:
    NodeList() :m_pHead(nullptr), m_pLast(nullptr)
    {
 
    };
    ~NodeList()
    {
        while (m_pHead)
        {
            Node* temp = m_pHead;
            m_pHead = temp->Next();
            delete temp;
        }
 
        m_pHead = nullptr;
        m_pLast = nullptr;
    };
 
    void Print()
    {
        Node * temp = m_pHead;
        while (temp)
        {
            temp->Print();
            temp = temp->Next();
        }
    }
 
    bool    push_back(int n)
    {
        if (m_pHead == nullptr)
        {
            m_pHead = new Node;
            if (m_pHead)
                m_pHead->SetData(n);
 
            m_pLast = m_pHead;
        }
        else
        {
            Node* newPos = new Node;
            if (newPos)
            {
                newPos->SetData(n);
                m_pLast->SetNext(newPos);
                m_pLast = m_pLast->Next();
            }
        }
 
        return true;
    };
 
    bool push_back_sorted(int n)
    {
        if (m_pHead == nullptr)
        {
            m_pHead = new Node;
            if (m_pHead)
                m_pHead->SetData(n);
 
            m_pLast = m_pHead;
        }
        else
        {
            Node* newPos = new Node;
            if (newPos)
            {
                newPos->SetData(n);
 
                Node* pFind = LookupNewPos(n);
                if (pFind)
                {
                    Node* pFindNext = pFind->Next();
                    pFind->SetNext(newPos);
                    newPos->SetNext(pFindNext);
                    m_pLast = pFindNext ? pFindNext : newPos;
                }
                else
                {
                    Node* tempHeadNext = m_pHead;
                    m_pHead = newPos;
                    newPos->SetNext(tempHeadNext);
                }
            }
        }
 
        return true;
    };
 
    Node*   LookupNewPos(int n)
    {
        Node* tempCur = m_pHead;
        if (tempCur && !Sort(n, tempCur->GetData()))
            return nullptr;
 
        Node* tempFind = m_pHead;
        tempCur = m_pHead->Next();
        if (tempCur == nullptr)
            return tempFind;
 
        while (tempCur)
        {
            if (!Sort(n, tempCur->GetData()))
            {
                break;
            }
            else
            {
                tempFind = tempCur;
                tempCur = tempCur->Next();
            }
        }
 
        return tempFind ? tempFind : m_pHead;
    }
 
    //! can be override anybool    Sort(int n1, int n2)
    {
        return (n1 > n2) ? true : false;
    }
 
    //! add list2 to the lastvoid MergeList(NodeList& list2)
    {
        Node* newHead = list2.GetHead();
        while (newHead)
        {
            push_back(newHead->GetData());
            newHead = newHead->Next();
        }
    };
 
    //! add list2 and sortedvoid MergeListSort(NodeList& list2)
    {
        Node* newHead = list2.GetHead();
        while (newHead)
        {
            push_back_sorted(newHead->GetData());
            newHead = newHead->Next();
        }
    };
 
    Node*   GetHead()
    {
        return m_pHead;
    };
protected:
    Node*   m_pHead;
    Node*   m_pLast;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    NodeList nodeTest;
    nodeTest.push_back(1);
    nodeTest.push_back(2);
    nodeTest.push_back(3);
    nodeTest.push_back(4);
    nodeTest.push_back(5);
    nodeTest.push_back(6);
 
    nodeTest.Print();
 
    NodeList nodeTest2;
 
    nodeTest2.push_back(11);
    nodeTest2.push_back(22);
    nodeTest2.push_back(33);
    nodeTest2.push_back(44);
    nodeTest2.push_back(55);
    nodeTest2.push_back(66);
 
    nodeTest.MergeList(nodeTest2);
 
    nodeTest.Print();  // should print out 1,2,3,...11,22,33,...//test sorted node listNodeList sortNodeList;
    sortNodeList.push_back_sorted(4);
    sortNodeList.push_back_sorted(5);
    sortNodeList.push_back_sorted(3);
    sortNodeList.push_back_sorted(2);
    sortNodeList.push_back_sorted(14);
 
    sortNodeList.Print();   // should print: 2,3,4,5,14
 
    sortNodeList.MergeListSort(nodeTest2);
 
    sortNodeList.push_back_sorted(10);
    sortNodeList.push_back_sorted(18);
    sortNodeList.push_back_sorted(1);
 
    cout << "new merged:" << endl;
    sortNodeList.Print();   // should print: 2,3,4,5,14return 0;
}
4 comments to “simple node and list merge”

    • Hi,To my surprise!! You are also getting hu1erds?I&#82l7;m one of the victims complaining about the same issue. Did anyone get the solution? I was wondering if this issue would ever be solved.Can anyone tell a possible solution to the prob.. to change the region?

Comments are closed.