【原创】链表模板类

略游

1. /*******************************************
   
2. **名称：链表模板类
   
3. **作者：吴泔游
   
4. **用法：
   
5.         LinkList<int> list;                                                        //创建
   
6.         list.Create(10);                                                        //批量输入10个元素(cin)
   
7.         list.GetLength();                                                        //返回链表长度
   
8.         list.ShowAll();                                                                //打印所有元素(cout)
   
9.         list.RemoveDuplicate();                                                //去掉重复的元素
   
10.         list.Delete(2,(int)data);                                        //删除第2个元素，值用data返回,函数返回值代表是否成功
    
11.         list.Insert(3,(int)data);                                        //插入data，成为第3个元素
    
12.         list.InsertByOrder((int)data);                                //按升序插入data
    
13.         list.Release();                                                                //清空链表元素
    
14.         list.Reverse();                                                                //逆置链表
    
15.         list.InsertSort();                                                        //直接插入排序(升序),链表基本升序时较慢，反之较快
    
16.         list.MergeSort();                                                        //归并排序(升序)
    
17.         list.GetNodeData(6,int(data));                                //用data返回第6个节点，函数返回值代表是否成功
    
18.         list.GetNodeDataPointer(5,int*(p_data));        //用p_pata返回第5个节点的地址，用于直接修改节点等操作
    
19.         list.Search((int)key);                                                //遍历查找元素，函数返回值为位置
    
20.         list.SetSortMethod(SortInt);                                //指定排序函数
    
21. 
    
22. 
    
23.         list_1+list_2                                                                //返回两者元素集合，list_1元素在前
    
24.         list_1=list_2                                                                //赋值
    
25.         list_1+=list_2                                                                //list_1=list_1+list_2
    
26. **最后修改：2015/1/26
    
27. 1.添加RemoveDuplicate函数
    
28. 2.添加SetCompareMethod函数
    
29. ********************************************/
    
30. #ifndef _LINK_LIST_H_
    
31. #define  _LINK_LIST_H_
    
32. 
    
33. 
    
34. 
    
35. #include <iostream>
    
36. #include <iomanip>
    
37. using namespace std;
    
38. #define NULL 0
    
39. 
    
40. template <class ElemType>
    
41. class ListNode
    
42. {
    
43. public:
    
44.         ElemType data;
    
45.         ListNode *next;
    
46.         ListNode(){next=NULL;}
    
47.         ListNode(ElemType data)
    
48.         {
    
49.                 this->data=data;
    
50.                 next=NULL;
    
51.         }
    
52. };
    
53. //------------------------------------------------------------
    
54. template <class ElemType>
    
55. class LinkList
    
56. {
    
57. private:
    
58.         ListNode<ElemType> *head;
    
59.         int length;
    
60.         bool (*SortMethod)(const ElemType& a,const ElemType& b);
    
61.         bool (*CompareMethod)(const ElemType& a,const ElemType& b);
    
62.         ListNode<ElemType>* Merge(ListNode<ElemType>*& a,ListNode<ElemType>*& b);
    
63. public:
    
64.         LinkList();
    
65.         LinkList(LinkList &b);
    
66.         ~LinkList();
    
67.         int GetLength();
    
68. 
    
69.         void ShowAll();
    
70. 
    
71.         void Create(int n);                                                //创建
    
72. 
    
73.         void RemoveDuplicate();
    
74.         bool Delete(int n,ElemType &data);                //删除
    
75.         bool Insert(int n,ElemType data);                        //插入
    
76.         bool InsertByOrder(ElemType data);
    
77.         void Release();
    
78. 
    
79.         void Reverse();                                                        //转置
    
80.         void InsertSort();                                                                        //升序
    
81.        
    
82.         void MergeSort();
    
83.         bool GetNodeData(int n,ElemType &data);
    
84.         bool GetNodeDataPointer(int n,ElemType*& p_data);
    
85.         int  Search(ElemType key);                        //查找
    
86.         void SetSortMethod(bool (*fun)(const ElemType& a,const ElemType& b));        //设置排序比较方法(<)
    
87.         void SetCompareMethod(bool (*fun)(const ElemType& a,const ElemType& b));        //设置比较方法(==)
    
88. 
    
89.         LinkList operator+(const LinkList &b);
    
90.         LinkList operator=(const LinkList &b);
    
91.         LinkList& operator+=(const LinkList &b);
    
92. };
    
93. //-----------------------------------------------------------------------------
    
94. 
    
95. template <class ElemType>
    
96. LinkList<ElemType>::LinkList():head(new ListNode<ElemType>),length(0),SortMethod(NULL),CompareMethod(NULL)
    
97. {
    
98.         head->next=NULL;
    
99. }
    
100. 
     
101. template <class ElemType>
     
102. LinkList<ElemType>::LinkList(LinkList &b):head(new ListNode<ElemType>),length(b.length),SortMethod(b.SortMethod),CompareMethod(b.CompareMethod)
     
103. {
     
104.         ListNode<ElemType> *p=this->head;
     
105.         ListNode<ElemType> *q;
     
106.         ListNode<ElemType> *pb=b.head->next;
     
107. 
     
108.         while(pb)
     
109.         {
     
110.                 q=new ListNode<ElemType>();
     
111.                 q->data=pb->data;
     
112.                 p->next=q;
     
113.                 p=q;
     
114.                 pb=pb->next;
     
115.         }
     
116.         p->next=NULL;
     
117. }
     
118. 
     
119. template <class ElemType>
     
120. int LinkList<ElemType>::GetLength()
     
121. {
     
122.         return length;
     
123. }
     
124. 
     
125. template <class ElemType>
     
126. void LinkList<ElemType>::ShowAll()
     
127. {
     
128.         cout<<"共"<<length<<"个元素:"<<endl;
     
129.         ListNode<ElemType> *p=this->head->next;
     
130.         int i=0;
     
131.         while(p)
     
132.         {
     
133.                 cout<<left<<setw(7)<<p->data<<" ";
     
134.                 p=p->next;
     
135.                 i++;
     
136.                 if(i%10==0)
     
137.                         cout<<endl;
     
138.         }
     
139.         cout<<endl;
     
140. }
     
141. //创建
     
142. 
     
143. template <class ElemType>
     
144. void LinkList<ElemType>::Create(int n)
     
145. {
     
146.         this->length=n;
     
147.         ListNode<ElemType> *p=this->head;
     
148.         ListNode<ElemType> *q;
     
149.         for(int i=0;i!=n;i++)
     
150.         {
     
151.                 q=new ListNode<ElemType>();
     
152.                 cin>>q->data;
     
153.                 p->next=q;
     
154.                 p=q;
     
155.         }
     
156.         p->next=NULL;
     
157. }
     
158. 
     
159. //插入
     
160. template <class ElemType>
     
161. bool LinkList<ElemType>::Insert(int n,ElemType data)
     
162. {
     
163.         ListNode<ElemType> *p=this->head;
     
164.         ListNode<ElemType> *q;
     
165.         int j=0;
     
166.         while(p&&j<n-1)
     
167.         {
     
168.                 p=p->next;
     
169.                 j++;
     
170.         }
     
171.         if(!p||j>n-1)return 0;
     
172.         q=new ListNode<ElemType>(data);
     
173.         q->next=p->next;
     
174.         p->next=q;
     
175. 
     
176.         this->length++;
     
177.         return 1;
     
178. }
     
179. 
     
180. template <class ElemType>
     
181. bool LinkList<ElemType>::InsertByOrder(ElemType data)
     
182. {
     
183.         ListNode<ElemType> *p=this->head;
     
184.         ListNode<ElemType> *q;
     
185.         while(p->next)
     
186.         {
     
187.                 if(SortMethod==NULL)
     
188.                 {
     
189.                         if(data < p->next->data)
     
190.                                 break;
     
191.                 }
     
192.                 else
     
193.                         if(SortMethod(data,p->next->data))
     
194.                                 break;
     
195.                 p=p->next;
     
196.         }
     
197.         q=new ListNode<ElemType>(data);
     
198.         q->next        = p->next;
     
199.         p->next = q;
     
200. 
     
201.         this->length++;
     
202.         return 1;
     
203. }
     
204. 
     
205. template <class ElemType>
     
206. void LinkList<ElemType>::RemoveDuplicate()
     
207. {
     
208.         if(!this->head->next || !this->head->next->next)
     
209.                 return;
     
210.         ListNode<ElemType> *p=this->head->next;
     
211.         ListNode<ElemType> *q,*temp;
     
212.         if(CompareMethod==NULL)
     
213.         {
     
214.                 while(p)
     
215.                 {
     
216.                         q=p;
     
217.                         while(q->next)
     
218.                         {
     
219.                                 if(p->data == q->next->data)
     
220.                                 {
     
221.                                         temp=q->next;
     
222.                                         q->next=temp->next;
     
223.                                         delete temp;
     
224.                                         length--;
     
225.                                 }
     
226.                                 else
     
227.                                         q=q->next;
     
228. 
     
229.                         }
     
230.                         p=p->next;
     
231.                 }
     
232.         }
     
233.         else
     
234.         {
     
235.                 while(p)
     
236.                 {
     
237.                         q=p;
     
238.                         while(q->next)
     
239.                         {
     
240.                                 if(CompareMethod(p->data , q->next->data))
     
241.                                 {
     
242.                                         temp=q->next;
     
243.                                         q->next=temp->next;
     
244.                                         delete temp;
     
245.                                         length--;
     
246.                                 }
     
247.                                 else
     
248.                                         q=q->next;
     
249. 
     
250.                         }
     
251.                         p=p->next;
     
252.                 }
     
253.         }
     
254.        
     
255. }
     
256. 
     
257. template <class ElemType>
     
258. bool LinkList<ElemType>::Delete(int n,ElemType &data)
     
259. {
     
260.         ListNode<ElemType> *p=this->head;
     
261.         ListNode<ElemType> *q;
     
262.         int j=0;
     
263.         while(p->next&&j<n-1)
     
264.         {
     
265.                 p=p->next;
     
266.                 j++;
     
267.         }
     
268.         if(!(p->next)||j>n-1)return 0;
     
269.         q=p->next;
     
270.         p->next=q->next;
     
271.         data=q->data;
     
272.         delete q;
     
273.         this->length--;
     
274.         return 1;
     
275. 
     
276. }
     
277. 
     
278. template <class ElemType>
     
279. void LinkList<ElemType>::Release()
     
280. {
     
281.         length        =        0;
     
282.         ListNode<ElemType> *p=head->next;
     
283.         while(p)
     
284.         {
     
285.                 ListNode<ElemType> *q=p->next;
     
286.                 delete p;
     
287.                 p=q;
     
288.         }
     
289.         head->next = NULL;
     
290. }
     
291. //逆置
     
292. template <class ElemType>
     
293. void LinkList<ElemType>::Reverse()
     
294. {
     
295.         ListNode<ElemType> *p=this->head->next;//p为待处理节点，q为下一个
     
296.         this->head->next=NULL;
     
297.         ListNode<ElemType> *q;
     
298.         while(p)
     
299.         {
     
300.                 q=p->next;//q保存下一个位置
     
301.                 p->next=this->head->next;
     
302.                 this->head->next=p;
     
303.                 p=q;
     
304.         }
     
305. }
     
306. 
     
307. template <class ElemType>
     
308. void LinkList<ElemType>::InsertSort()
     
309. {
     
310.         if(!head->next || !head->next->next)
     
311.                 return;
     
312.         ListNode<ElemType> *p,*q=head->next->next;
     
313.         ListNode<ElemType> *temp;
     
314.         head->next->next=NULL;
     
315.         while(q)
     
316.         {
     
317.                 p=head;
     
318.                 while(p&&p->next)
     
319.                 {
     
320.                         if(SortMethod==NULL)
     
321.                         {
     
322.                                 if(p->next->data < q->data)
     
323.                                         break;
     
324.                         }
     
325.                         else
     
326.                         {
     
327.                                 if(SortMethod(p->next->data,q->data))
     
328.                                         break;
     
329.                         }
     
330.                         p=p->next;
     
331.                 }
     
332.                 temp=q->next;
     
333.                 q->next=p->next;
     
334.                 p->next=q;
     
335.                 q=temp;
     
336.         }
     
337.         this->Reverse();
     
338. }
     
339. 
     
340. template <class ElemType>
     
341. ListNode<ElemType>* LinkList<ElemType>::Merge(ListNode<ElemType>*& a,ListNode<ElemType>*& b)
     
342. {
     
343.         if(a==NULL)
     
344.                 return b;
     
345.         if(b==NULL)
     
346.                 return a;
     
347.         ListNode<ElemType> *r=new ListNode<ElemType>();
     
348.         ListNode<ElemType> *c;
     
349.         ListNode<ElemType> *p;
     
350.         ListNode<ElemType> *q;
     
351.        
     
352.         c=r;
     
353.         q=a->next;
     
354.         p=b->next;
     
355.         while(q&&p)
     
356.         {
     
357.                 if(SortMethod==NULL)
     
358.                 {
     
359.                         if(p->data < q->data)
     
360.                         {
     
361.                                 c->next=p;
     
362.                                 p=p->next;
     
363.                         }
     
364.                         else
     
365.                         {
     
366.                                 c->next=q;
     
367.                                 q=q->next;
     
368.                         }
     
369.                 }
     
370.                 else
     
371.                 {
     
372.                         if(SortMethod(p->data,q->data))
     
373.                         {
     
374.                                 c->next=p;
     
375.                                 p=p->next;
     
376.                         }
     
377.                         else
     
378.                         {
     
379.                                 c->next=q;
     
380.                                 q=q->next;
     
381.                         }
     
382.                 }
     
383.                 c=c->next;
     
384.         }
     
385. 
     
386.         if(q==NULL)
     
387.                 c->next=p;
     
388.         else if(p==NULL)
     
389.                 c->next=q;
     
390. 
     
391.         delete a,b;
     
392.         a=NULL;
     
393.         b=NULL;
     
394.         return r;
     
395. 
     
396.        
     
397. }
     
398. 
     
399. 
     
400. template <class ElemType>
     
401. void LinkList<ElemType>::MergeSort()
     
402. {
     
403.         if(length <= 1)
     
404.                 return;
     
405.         int l=(length+1)/2*2;
     
406.         ListNode<ElemType>** r=new ListNode<ElemType>*[l];
     
407.         ListNode<ElemType> *p=head->next;
     
408. 
     
409.         for(int i=0;i!=l;i++)
     
410.                 r[i]=new ListNode<ElemType>();
     
411. 
     
412.         int i=0;
     
413.         while(p)
     
414.         {
     
415.                 r[i]->next=p;
     
416.                 if(p->next ==NULL)
     
417.                         break;
     
418.                 p=p->next;
     
419.                 r[i]->next->next=NULL;
     
420.                
     
421.                 i++;
     
422.         }
     
423.         for(int d=l;d!=1;d=(d+1)/2)
     
424.                 for(int i=0,j=0;j <=d-1;i++,j+=2)
     
425.                         r[i]=Merge(r[j],r[j+1]);
     
426.         head=r[0];
     
427. }
     
428. 
     
429. template <class ElemType>
     
430. bool LinkList<ElemType>::GetNodeData(int n,ElemType &data)
     
431. {
     
432.         if(n<=0)
     
433.                 return 0;
     
434.         ListNode<ElemType> *p=this->head;
     
435.         int j=0;
     
436.         while(p&&j<n)
     
437.         {
     
438.                 p=p->next;
     
439.                 j++;
     
440.         }
     
441.         if(!p||j>n)
     
442.                 return 0;
     
443.         else
     
444.         {
     
445.                 data=p->data;
     
446.                 return 1;
     
447.         }
     
448. 
     
449. 
     
450. }
     
451. 
     
452. template <class ElemType>
     
453. bool LinkList<ElemType>::GetNodeDataPointer(int n,ElemType*& p_data)
     
454. {
     
455.         if(n<=0)
     
456.                 return 0;
     
457.         ListNode<ElemType> *p=this->head;
     
458.         int j=0;
     
459.         while(p&&j<n)
     
460.         {
     
461.                 p=p->next;
     
462.                 j++;
     
463.         }
     
464.         if(!p||j>n)
     
465.                 return 0;
     
466.         else
     
467.         {
     
468.                 p_data=&p->data;
     
469.                 return 1;
     
470.         }
     
471. 
     
472. 
     
473. }
     
474. 
     
475. template <class ElemType>
     
476. int LinkList<ElemType>::Search(ElemType key)
     
477. {
     
478.         ListNode<ElemType> *p=this->head->next;
     
479.         int i=1;
     
480.         if(CompareMethod==NULL)
     
481.         {
     
482.                 while(p)
     
483.                 {
     
484.                         if(p->data == key)
     
485.                                 return i;
     
486.                         i++;
     
487.                         p=p->next;
     
488.                 }
     
489.         }
     
490.         else
     
491.         {
     
492.                 while(p)
     
493.                 {
     
494.                         if(CompareMethod(p->data,key))
     
495.                                 return i;
     
496.                         i++;
     
497.                         p=p->next;
     
498.                 }
     
499.         }
     
500.         return 0;
     
501. }
     
502. 
     
503. //设置排序比较方法(<)
     
504. template <class ElemType>
     
505. void LinkList<ElemType>::SetSortMethod(bool (*fun)(const ElemType& a,const ElemType& b))
     
506. {
     
507.         SortMethod = fun;
     
508. }
     
509. 
     
510. //设置排序比较方法(==)
     
511. template <class ElemType>
     
512. void LinkList<ElemType>::SetCompareMethod(bool (*fun)(const ElemType& a,const ElemType& b))
     
513. {
     
514.         CompareMethod = fun;
     
515. }
     
516. 
     
517. template <class ElemType>
     
518. LinkList<ElemType> LinkList<ElemType>::operator+(const LinkList<ElemType> &b)
     
519. {
     
520.         LinkList<ElemType> c(*this);
     
521.         ListNode<ElemType> *p=b.head->next;
     
522.         ListNode<ElemType> *q;
     
523.         ListNode<ElemType> *pc=c.head;
     
524.         while(pc->next)
     
525.         {
     
526.                 pc=pc->next;
     
527.         }
     
528.         while(p)
     
529.         {
     
530.                 q=new ListNode<ElemType>();
     
531.                 q->data=p->data;
     
532.                 pc->next=q;
     
533.                 pc=q;
     
534.                 p=p->next;
     
535.         }
     
536.         pc->next=NULL;
     
537. 
     
538.         c.length+=b.length;
     
539.         return c;
     
540. 
     
541. }
     
542. template <class ElemType>
     
543. LinkList<ElemType> LinkList<ElemType>::operator=(const LinkList<ElemType> &b)
     
544. {
     
545.         this->Release();
     
546.         ListNode<ElemType> *p=this->head;
     
547.         ListNode<ElemType> *q;
     
548.         ListNode<ElemType> *pb=b.head->next;
     
549. 
     
550.         while(pb)
     
551.         {
     
552.                 q=new ListNode<ElemType>();
     
553.                 q->data=pb->data;
     
554.                 p->next=q;
     
555.                 p=q;
     
556.                 pb=pb->next;
     
557.         }
     
558.         p->next=NULL;
     
559.         this->length=b.length;
     
560.         this->SortMethod=b.SortMethod;
     
561.         this->CompareMethod=b.CompareMethod;
     
562.         return *this;
     
563. }
     
564. template <class ElemType>
     
565. LinkList<ElemType>& LinkList<ElemType>::operator+=(const LinkList<ElemType> &b)
     
566. {
     
567.         *this=*this+b;
     
568.         return *this;
     
569. }
     
570. template <class ElemType>
     
571. LinkList<ElemType>::~LinkList()
     
572. {
     
573.         ListNode<ElemType> *p=head->next;
     
574.         if(head)
     
575.         {
     
576.                 delete head;
     
577.         }
     
578.         while(p)
     
579.         {
     
580.                 ListNode<ElemType> *q=p->next;
     
581.                 delete p;
     
582.                 p=q;
     
583.         }
     
584. }
     
585. 
     
586. 
     
587. #endif

复制代码

例子和源码在附件内