6.5 k个已排好序链表合并为一个排序链表

  1 typedef int DataType;
  2 //建立链表
  3 class Link
  4 {
  5 private:
  6     struct Node
  7     {
  8         DataType data;
  9         Node *next;
 10     };
 11     Node *head; //哨兵位
 12 public:
 13     Link()
 14     {
 15         Init();
 16     }
 17     ~Link()
 18     {
 19         Delete();
 20     }
 21     void Init()
 22     {
 23         head = new Node;
 24         head->next = NULL;
 25     }
 26     void Delete()
 27     {
 28         for (Node *p = head; p != NULL;)
 29         {
 30             Node *pTemp = p->next;
 31             delete p;
 32             p = pTemp;
 33         }
 34         head = NULL;
 35     }
 36     bool Empty()
 37     {
 38         return head->next == NULL;
 39     }
 40     void Print()
 41     {
 42         for (Node *p = head->next; p != NULL; p = p->next)
 43         {
 44             cout << p->data << endl;
 45         }
 46     }
 47     //顺序插入 考虑两种情况 1.空表 2.当插入值是最大值的时候
 48     void SortInsert(DataType data)
 49     {
 50         Node *p = head;
 51         do 
 52         {
 53             if (p->next == NULL || p->next->data > data)
 54             {
 55                 Node *pNew = new Node;
 56                 pNew->data = data;
 57                 pNew->next = p->next;
 58                 p->next = pNew;
 59 
 60                 return;
 61             }
 62             p = p->next;
 63         } while (true);
 64     }
 65     //使用数组初始化列表
 66     void ArrayInsert(DataType array[], int size)
 67     {
 68         for (int i=0; i<size; ++i)
 69         {
 70             SortInsert(array[i]);
 71         }
 72     }
 73     //尾插法直接插入
 74     void Insert(DataType data)
 75     {
 76         Node *p = head;
 77         while(p->next != NULL)
 78         {
 79             p = p->next;
 80         }
 81 
 82         Node *pNew = new Node;
 83         pNew->data = data;
 84         pNew->next = NULL;
 85         p->next = pNew;
 86     }
 87     //去掉首结点并返回首结点的值
 88     int ExtractDate()
 89     {
 90         if (! Empty())
 91         {
 92             DataType data = head->next->data;
 93             Node *p = head->next;
 94             Node *pFirst = p->next;
 95 
 96             delete p;
 97             p = NULL;
 98 
 99             head->next = pFirst; 
100             return data;
101         }
102         return -1;
103     }
104     int GetData()
105     {
106         if (!Empty())
107         {
108             return head->next->data;
109         }
110     }
111     bool Find(const DataType data)
112     {
113         for (Node *p = head->next; p != NULL; p = p->next)
114         {
115             if (p->data == data)
116             {
117                 return true;
118             }
119         }
120         return false;
121     }
122     void Swap(Link &p)   //交换两个链表主要是交换 head->next
123     {
124         if (head != p.head)
125         {
126             Node *tmp = head->next;
127             head->next = p.head->next;
128             p.head->next = tmp;
129         }
130     }
131 };
132 //保持最小堆性质 参数inode为内部结点 注意结点从1开始，数组从0开始
133 void MinHeapify(int array[], int size, int inode)
134 {
135     int least= inode;                //父结点
136     int left = inode*2;                //左子结点
137     int right = inode*2+1;            //右子结点
138 
139     if (left <= size && array[left-1] < array[least-1])
140     {
141         least = left;
142     }
143     if (right <= size && array[right-1] < array[least-1])
144     {
145         least = right;
146     }
147 
148     if (least != inode)                    //父结点小于 左子结点 或者 右子结点
149     {
150         int temp = array[inode-1];            //子结点值与父结点值交换
151         array[inode-1] = array[least-1];
152         array[least-1] = temp;
153 
154         MinHeapify(array, size, least);            //再次验证被交换的值的子结点是否满足 最小堆性质
155     }
156 }
157 //建立最小堆 使每一个父结点小于子结点
158 void BuildMinHeap(int array[],int size)
159 {
160     for(int i=size/2; i>0; --i)     //最多有 size/2 个内部结点
161     {
162         MinHeapify(array, size, i);
163     }
164 }
165 //k个已排好序的链表合并为一个链表
166 //pLink 链表数组的地址, linkSize链表数组的大小, link为需要合并的链表
167 void SortLink(Link *pLink, int linkSize, Link *link)
168 {
169     int *pArray = new int[linkSize]; //动态分配k个大小的数组
170     for (int i=0; i<linkSize; ++i)    //从k个链表中取首结点的值
171     {
172         pArray[i] = pLink[i].GetData();
173     }
174 
175     int j=0;
176     do 
177     {
178         BuildMinHeap(pArray,linkSize); //构造最小堆，即每个父结点小于或等于子结点，根结点为最小值
179         int b1 = pArray[0];
180         for (j=0; j<linkSize; ++j)
181         {
182             if(pLink[j].Find(pArray[0]))   //寻找最小值来自于哪一个链表
183             {
184                 int b2 = pLink[j].GetData();
185                 link->Insert(pLink[j].ExtractDate());  //去掉并返回链表的的值（更新链表）
186                 break;
187             }
188         }
189         if (!pLink[j].Empty())  //确保取出值的链表不为空
190         {
191             pArray[0] = pLink[j].GetData();   //更新数组
192         }
193         else 
194         {
195             pArray[0] = pArray[linkSize-1];  
196             pLink[j].Swap(pLink[linkSize-1]);  //交换两个链表
197             --linkSize;
198         }
199     } while (linkSize != 0);
200 
201     delete [] pArray;
202 }
203 void main()
204 {
205     //检测是否有内存泄露 需要加头文件#include <crtdbg.h>
206     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
207 
208     Link k[5];
209 
210     int Array[5][5] = {    {21, 12, 11, 10, 1}, 
211                         {22, 17, 16, 7, 2},
212                         {23, 18, 13, 8, 3},
213                         {24, 19, 14, 9, 4},
214                         {25, 20, 15, 6, 5}};
215 
216     for (int i=0; i<5; ++i)
217     {
218         k[i].ArrayInsert(Array[i],sizeof(Array[i])/sizeof(Array[i][0]));
219     }
220     //for (int i=0; i<5; ++i)
221     //{
222     //    k[i].Print();
223     //}
224 
225     Link link;
226 
227     SortLink(k, sizeof(k)/sizeof(k[0]), &link);
228 
229     link.Print();
230 
231     system("pause");
232 }