simple node and list merge

Insert-sorted node list.
  1. #include "stdafx.h"
  2. #include <stdlib.h>
  3. #include <iostream>
  4. #include <iomanip>
  5. using namespace std;
  6. class Node
  7. {
  8. public:
  9. Node();
  10. ~Node();
  11. void SetData(int n) { m_data = n; };
  12. int GetData() { return m_data; };
  13. Node* Next() { return m_lpNext; };
  14. void SetNext(Node* newPos);
  15. void Print();
  16. protected:
  17. int m_data;
  18. Node* m_lpNext;
  19. };
  20. Node::Node() :m_data(0), m_lpNext(nullptr)
  21. {
  22. }
  23. Node::~Node()
  24. {
  25. cout << " begin to delete-" << GetData() << endl;
  26. }
  27. void Node::Print()
  28. {
  29. cout << "data=" << m_data << " next=" << m_lpNext << endl;
  30. }
  31. void Node::SetNext(Node* newPos)
  32. {
  33. if ( newPos )
  34. {
  35. m_lpNext = newPos;
  36. }
  37. }
  38. class NodeList
  39. {
  40. public:
  41. NodeList() :m_pHead(nullptr), m_pLast(nullptr)
  42. {
  43. };
  44. ~NodeList()
  45. {
  46. while (m_pHead)
  47. {
  48. Node* temp = m_pHead;
  49. m_pHead = temp->Next();
  50. delete temp;
  51. }
  52. m_pHead = nullptr;
  53. m_pLast = nullptr;
  54. };
  55. void Print()
  56. {
  57. Node * temp = m_pHead;
  58. while (temp)
  59. {
  60. temp->Print();
  61. temp = temp->Next();
  62. }
  63. }
  64. bool push_back(int n)
  65. {
  66. if (m_pHead == nullptr)
  67. {
  68. m_pHead = new Node;
  69. if (m_pHead)
  70. m_pHead->SetData(n);
  71. m_pLast = m_pHead;
  72. }
  73. else
  74. {
  75. Node* newPos = new Node;
  76. if (newPos)
  77. {
  78. newPos->SetData(n);
  79. m_pLast->SetNext(newPos);
  80. m_pLast = m_pLast->Next();
  81. }
  82. }
  83. return true;
  84. };
  85. //! add list2 to the last
  86. void MergeList(NodeList& list2)
  87. {
  88. Node* newHead = list2.GetHead();
  89. while (newHead)
  90. {
  91. push_back(newHead->GetData());
  92. newHead = newHead->Next();
  93. }
  94. };
  95. Node* GetHead()
  96. {
  97. return m_pHead;
  98. };
  99. protected:
  100. Node* m_pHead;
  101. Node* m_pLast;
  102. };
  103. int _tmain(int argc, _TCHAR* argv[])
  104. {
  105. NodeList nodeTest;
  106. nodeTest.push_back(1);
  107. nodeTest.push_back(2);
  108. nodeTest.push_back(3);
  109. nodeTest.push_back(4);
  110. nodeTest.push_back(5);
  111. nodeTest.push_back(6);
  112. nodeTest.Print();
  113. NodeList nodeTest2;
  114. nodeTest2.push_back(11);
  115. nodeTest2.push_back(22);
  116. nodeTest2.push_back(33);
  117. nodeTest2.push_back(44);
  118. nodeTest2.push_back(55);
  119. nodeTest2.push_back(66);
  120. nodeTest.MergeList(nodeTest2);
  121. nodeTest.Print(); // should print out 1,2,3,...11,22,33,...
  122. return 0;
  123. }
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(NodenewPos)
{
    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 n1int n2)
    {
        return (n1 > n2) ? true : false;
    }
 
    //! add list2 to the lastvoid MergeList(NodeListlist2)
    {
        Node* newHead = list2.GetHead();
        while (newHead)
        {
            push_back(newHead->GetData());
            newHead = newHead->Next();
        }
    };
 
    //! add list2 and sortedvoid MergeListSort(NodeListlist2)
    {
        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_TCHARargv[])
{
    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;
}
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.