单链表的一个C++实现

  

下面是单链表的一个C++实现，参考了《数据结构与算法分析C语言版》及不少牛人的分析总结，在此一并感谢了。在VC2005上经反复验证试验，结果非常不错。但可能还有不少bug，如果发现bug, 请告诉我一下。

  注意：单链表及双向及循环链表均不适用表头（即哑节点，dummy node）, 即m_pNodeHead指针指向链表的第一个真正节点。

[cpp] view plaincopyprint?

1. /*slist.h*/  
2. #include <assert.h>  
3. #include <crtdbg.h>  
4.   
5. template<typename T>//class T must have default constructor  
6. class Node  
7. {  
8. public:  
9.     T data;  
10.     Node<T> *next;  
11.     Node() : data(T()), next(NULL) {}  
12.     Node(const T &initdata) : data(initdata), next(NULL) {}  
13.     Node(const T &initdata, Node<T> *p) : data(initdata), next(p) {}  
14. };  
15.   
16.   
17. template<typename T>  
18. class SList  
19. {  
20. public:  
21.     SList();  
22.     SList(const T &initdata);  
23.     SList(const SList<T>& other);  
24.     SList<T>& operator=(const SList<T>& other);  
25.     ~SList();  
26.   
27. public:  
28.     void    Invert();  
29.     int     IsEmpty() const;  
30.     int     GetCount() const;  
31.     int     InsertBefore(const int pos, const T data);  
32.     int     InsertAfter(const int pos, const T data);  
33.     int     AddHead(const T data);  
34.     int     AddTail(const T data);  
35.     void    RemoveAt(const int pos);  
36.     void    RemoveHead();  
37.     void    RemoveTail();  
38.     void    RemoveAll();  
39.     T&      GetTail();  
40.     T       GetTail() const;  
41.     T&      GetHead();  
42.     T       GetHead() const;  
43.     T&      GetAt(const int pos);  
44.     T       GetAt(const int pos) const;  
45.     void    SetAt(const int pos, T data);  
46.     int     Find(const T data) const;  
47.     int     FindCircle() const;  
48.     int     FindCross(SList& testlist);  
49. protected:  
50.     int m_nCount;  
51.     Node<T> *m_pNodeHead;  
52. };  
53.   
54.   
55. template<typename T>  
56. inline SList<T>::SList() : m_nCount(0), m_pNodeHead(NULL)  
57. {  
58. }  
59.   
60. template<typename T>  
61. inline SList<T>::SList(const T &initdata) : m_nCount(0), m_pNodeHead(NULL)  
62. {  
63.     AddHead(initdata);  
64. }  
65.   
66. template<typename T>  
67. inline SList<T>::SList(const SList<T>& other) : m_nCount(0), m_pNodeHead(NULL)  
68. {  
69.     if(other.m_nCount>0)  
70.     {  
71.         for(int i=1;i<=other.m_nCount;i++)  
72.         {  
73.             AddTail(other.GetAt(i));  
74.         }  
75.     }  
76.   
77. }  
78.   
79. template<typename T>  
80. inline SList<T>& SList<T>::operator=(const SList<T>& other)  
81. {  
82.     if(this==&other)  
83.     {  
84.         return *this;  
85.     }  
86.   
87.     if(m_nCount>0)  
88.     {  
89.         RemoveAll();  
90.     }  
91.   
92.     if(other.m_nCount>0)  
93.     {  
94.         for(int i=1;i<=other.m_nCount;i++)  
95.         {  
96.             AddTail(other.GetAt(i));  
97.         }  
98.     }  
99.   
100.     return *this;  
101.   
102.   
103. }  
104.   
105. template<typename T>  
106. inline SList<T>::~SList()  
107. {  
108.     RemoveAll();  
109. }  
110. //reverse the list  
111. template<typename T>  
112. inline void SList<T>::Invert()  
113. {  
114.     if(m_nCount<=1) return;  
115.   
116.     Node<T> *curNod,*preNod,*nextNod;  
117.     curNod=m_pNodeHead;  
118.     preNod=NULL;  
119.     for(int i=1;i<=m_nCount;i++)  
120.     {  
121.         nextNod=curNod->next;  
122.         curNod->next=preNod;  
123.         preNod=curNod;  
124.         curNod=nextNod;  
125.     }  
126.     m_pNodeHead=preNod;  
127.     return;  
128. }  
129.   
130. template<typename T>  
131. inline int SList<T>::IsEmpty() const  
132. {  
133.     return 0 == m_nCount;  
134. }  
135.   
136. template<typename T>  
137. inline int SList<T>::AddHead(const T data)  
138. {  
139.     /*Node<T> *pNewNode; 
140.  
141.     try{ 
142.         pNewNode = new Node<T>; 
143.     } 
144.     catch (std::bad_alloc&)  
145.     { 
146.         return 0; 
147.     } 
148.      
149.  
150.     pNewNode->data = data; 
151.     pNewNode->next = m_pNodeHead; 
152.  
153.     m_pNodeHead = pNewNode; 
154.     ++m_nCount; 
155.     return 1;*/  
156.   
157.     return InsertBefore(1,data);  
158. }  
159.   
160. template<typename T>  
161. inline int SList<T>::AddTail(const T data)  
162. {  
163.     return InsertAfter(GetCount(), data);  
164. }  
165.   
166. // if success, return the position of the new node.  
167. // if fail, return 0.  
168. template<typename T>  
169. inline int SList<T>::InsertBefore(const int pos, const T data)  
170. {  
171.     int i;  
172.     int nRetPos;  
173.     Node<T> *pTmpNode1;  
174.     Node<T> *pTmpNode2;  
175.     Node<T> *pNewNode;  
176.   
177.     try{  
178.         pNewNode = new Node<T>;  
179.     }  
180.     catch (std::bad_alloc&)   
181.     {  
182.         nRetPos = 0;  
183.         return nRetPos;  
184.     }  
185.   
186.     pNewNode->data = data;  
187.   
188.     // if the list is empty, replace the head node with the new node.  
189.     if (NULL == m_pNodeHead)  
190.     {  
191.         pNewNode->next = NULL;  
192.         m_pNodeHead = pNewNode;  
193.         nRetPos = 1;  
194.         ++m_nCount;  
195.         return nRetPos;  
196.     }  
197.   
198.     // is pos range valid?  
199.     ASSERT(1 <= pos && pos <= m_nCount);  
200.   
201.     // insert before head node?  
202.     if (1 == pos)  
203.     {  
204.         pNewNode->next = m_pNodeHead;  
205.         m_pNodeHead = pNewNode;  
206.         nRetPos = 1;  
207.         ++m_nCount;  
208.         return nRetPos;  
209.     }  
210.   
211.     // if the list is not empty and is not inserted before head node,  
212.     // seek to the pos of the list and insert the new node before it.  
213.     pTmpNode1 = m_pNodeHead;  
214.     for (i = 1; i < pos; ++i)  
215.     {  
216.         pTmpNode2 = pTmpNode1;  
217.         pTmpNode1 = pTmpNode1->next;  
218.     }  
219.     pNewNode->next = pTmpNode1;  
220.     pTmpNode2->next = pNewNode;  
221.   
222.     nRetPos = pos;  
223.     ++m_nCount;  
224.     return nRetPos;  
225. }  
226.   
227. // if success, return the position of the new node.  
228. // if fail, return 0.  
229. template<typename T>  
230. inline int SList<T>::InsertAfter(const int pos, const T data)  
231. {  
232.     int i;  
233.     int nRetPos;  
234.     Node<T> *pTmpNode;  
235.     Node<T> *pNewNode;  
236.   
237.     try{  
238.         pNewNode = new Node<T>;  
239.     }  
240.     catch (std::bad_alloc&)   
241.     {  
242.         nRetPos = 0;  
243.         return nRetPos;  
244.     }  
245.   
246.     pNewNode->data = data;  
247.   
248.     // if the list is empty, replace the head node with the new node.  
249.     if (NULL == m_pNodeHead)  
250.     {  
251.         pNewNode->next = NULL;  
252.         m_pNodeHead = pNewNode;  
253.         nRetPos = 1;  
254.         ++m_nCount;  
255.         return nRetPos;  
256.     }  
257.   
258.     // is pos range valid?  
259.     ASSERT(1 <= pos && pos <= m_nCount);  
260.   
261.     // if the list is not empty,  
262.     // seek to the pos of the list and insert the new node after it.  
263.     pTmpNode = m_pNodeHead;  
264.     for (i = 1; i < pos; ++i)  
265.     {  
266.         pTmpNode = pTmpNode->next;  
267.     }  
268.     pNewNode->next = pTmpNode->next;  
269.     pTmpNode->next = pNewNode;  
270.   
271.     nRetPos = pos + 1;  
272.     ++m_nCount;  
273.     return nRetPos;  
274. }  
275.   
276. template<typename T>  
277. inline int SList<T>::GetCount() const  
278. {  
279.     return m_nCount;  
280. }  
281.   
282. template<typename T>  
283. inline void SList<T>::RemoveAt(const int pos)  
284. {  
285.     ASSERT(1 <= pos && pos <= m_nCount);  
286.   
287.     int i;  
288.     Node<T> *pTmpNode1;  
289.     Node<T> *pTmpNode2;  
290.   
291.     pTmpNode1 = m_pNodeHead;  
292.   
293.     // head node?  
294.     if (1 == pos)  
295.     {  
296.         m_pNodeHead = m_pNodeHead->next;  
297.         delete pTmpNode1;  
298.         --m_nCount;  
299.         return;  
300.     }  
301.   
302.     for (i = 1; i < pos; ++i)  
303.     {  
304.         // we will get the previous node of the target node after  
305.         // the for loop finished, and it would be stored into pTmpNode2  
306.         pTmpNode2 = pTmpNode1;  
307.         pTmpNode1 = pTmpNode1->next;  
308.     }  
309.     pTmpNode2->next = pTmpNode1->next;  
310.     delete pTmpNode1;  
311.     --m_nCount;  
312. }  
313.   
314. template<typename T>  
315. inline void SList<T>::RemoveHead()  
316. {  
317.     ASSERT(0 != m_nCount);  
318.     RemoveAt(1);  
319. }  
320.   
321. template<typename T>  
322. inline void SList<T>::RemoveTail()  
323. {  
324.     ASSERT(0 != m_nCount);  
325.     RemoveAt(m_nCount);  
326. }  
327.   
328. template<typename T>  
329. inline void SList<T>::RemoveAll()  
330. {  
331.     int i;  
332.     int nCount;  
333.     Node<T> *pTmpNode;  
334.   
335.     nCount = m_nCount;  
336.     if(nCount==0)  
337.     {  
338.         return;  
339.     }  
340.     for (i = 0; i < nCount; ++i)  
341.     {  
342.         pTmpNode = m_pNodeHead->next;  
343.         delete m_pNodeHead;  
344.         m_pNodeHead = pTmpNode;  
345.     }  
346.   
347.     m_pNodeHead=NULL;  
348.     m_nCount = 0;  
349. }  
350.   
351. template<typename T>  
352. inline T& SList<T>::GetTail()  
353. {  
354.     ASSERT(0 != m_nCount);  
355.   
356.     int i;  
357.     int nCount;  
358.     Node<T> *pTmpNode = m_pNodeHead;  
359.   
360.     nCount = m_nCount;  
361.     for (i = 1; i < nCount; ++i)  
362.     {  
363.         pTmpNode = pTmpNode->next;  
364.     }  
365.   
366.     return pTmpNode->data;  
367. }  
368.   
369. template<typename T>  
370. inline T SList<T>::GetTail() const  
371. {  
372.     ASSERT(0 != m_nCount);  
373.   
374.     int i;  
375.     int nCount;  
376.     Node<T> *pTmpNode = m_pNodeHead;  
377.   
378.     nCount = m_nCount;  
379.     for (i = 1; i < nCount; ++i)  
380.     {  
381.         pTmpNode = pTmpNode->next;  
382.     }  
383.   
384.     return pTmpNode->data;  
385. }  
386.   
387. template<typename T>  
388. inline T& SList<T>::GetHead()  
389. {  
390.     ASSERT(0 != m_nCount);  
391.     return m_pNodeHead->data;  
392. }  
393.   
394. template<typename T>  
395. inline T SList<T>::GetHead() const  
396. {  
397.     ASSERT(0 != m_nCount);  
398.     return m_pNodeHead->data;  
399. }  
400.   
401. template<typename T>  
402. inline T& SList<T>::GetAt(const int pos)  
403. {  
404.     ASSERT(1 <= pos && pos <= m_nCount);  
405.   
406.     int i;  
407.     Node<T> *pTmpNode = m_pNodeHead;  
408.   
409.     for (i = 1; i < pos; ++i)  
410.     {  
411.         pTmpNode = pTmpNode->next;  
412.     }  
413.   
414.     return pTmpNode->data;  
415. }  
416.   
417. template<typename T>  
418. inline T SList<T>::GetAt(const int pos) const  
419. {  
420.     ASSERT(1 <= pos && pos <= m_nCount);  
421.   
422.     int i;  
423.     Node<T> *pTmpNode = m_pNodeHead;  
424.   
425.     for (i = 1; i < pos; ++i)  
426.     {  
427.         pTmpNode = pTmpNode->next;  
428.     }  
429.   
430.     return pTmpNode->data;  
431. }  
432.   
433. template<typename T>  
434. inline void SList<T>::SetAt(const int pos, T data)  
435. {  
436.     ASSERT(1 <= pos && pos <= m_nCount);  
437.   
438.     int i;  
439.     Node<T> *pTmpNode = m_pNodeHead;  
440.   
441.     for (i = 1; i < pos; ++i)  
442.     {  
443.         pTmpNode = pTmpNode->next;  
444.     }  
445.     pTmpNode->data = data;  
446. }  
447.   
448. template<typename T>  
449. inline int SList<T>::Find(const T data) const  
450. {  
451.     int i;  
452.     int nCount;  
453.     Node<T> *pTmpNode = m_pNodeHead;  
454.   
455.     nCount = m_nCount;  
456.     for (i = 0; i < nCount; ++i)  
457.     {  
458.         if (data == pTmpNode->data)  
459.             return i + 1;  
460.         pTmpNode = pTmpNode->next;  
461.     }  
462.   
463.     return 0;  
464. }  
465.   
466. /*判断链表是否有环，如果有环则返回环的首结点位置，否则返回0*/    
467. template<typename T>  
468. inline int SList<T>::FindCircle() const  
469. {  
470.     if(0==m_nCount)  
471.     {  
472.         return 0;  
473.     }  
474.   
475.     Node<T>* p1=m_pNodeHead;  
476.     Node<T>* p2=m_pNodeHead;  
477.   
478.     /*判断链表是否有环，当p1=p2时说明链表有环，程序跳出循环。如果p2一直走到链表尽头则说明没有环。*/    
479.     do{    
480.         if(p1!=NULL&&p2!=NULL&&p2->next!=NULL)    
481.         {    
482.             p1=p1->next;    
483.             p2=p2->next->next;       
484.         }    
485.         else    
486.             return 0;    
487.     }    
488.     while(p1!=p2);   
489.   
490.     /*求出环的起点节点，并将其返回*/    
491.     p2=m_pNodeHead;    
492.     while(p1!=p2)    
493.     {    
494.         p1=p1->next;    
495.         p2=p2->next;        
496.     }    
497.       
498.     int i;  
499.     p2=m_pNodeHead;  
500.     for(i=1;i<=m_nCount;i++)  
501.     {  
502.         if(p1==p2) break;  
503.         p2=p2->next;  
504.     }  
505.     return i;  
506.   
507. }  
508.   
509. /*判断两个链表是否交叉，如果交叉返回首个交叉节点位置（在本链表中的位置，而不是testlist中的位置），否则返回0。 
510. 假定：这两个链表本身均无环*/    
511. template<typename T>  
512. inline int SList<T>::FindCross(SList& testlist)  
513. {  
514.     if(0==m_nCount||0==testlist.m_nCount)  
515.     {  
516.         return 0;  
517.     }  
518.   
519.     if(FindCircle()||testlist.FindCircle())  
520.     {  
521.         return 0;  
522.     }  
523.   
524.     /*将第二个链表接在第一个链表后面*/    
525.     Node<T>* pTail=m_pNodeHead;  
526.     for(int i=1;i<m_nCount;i++)  
527.     {  
528.         pTail=pTail->next;  
529.     }  
530.   
531.     pTail=testlist.m_pNodeHead;  
532.     m_nCount+=testlist.m_nCount;  
533.   
534.     int i=FindCircle();  
535.   
536.     pTail=NULL;  
537.     m_nCount-=testlist.m_nCount;  
538.     return i;  
539. }  
540.   
541. #endif