[砖头]我也来个链表

duzhi5368

以前学数据结构时候,忘记在哪儿弄的的一份单向链表代码,如下,当时可真是加了不少注释[s:5]

2. //*****************************************************************
3. //
4. //    SingleList单链表学习代码(2004.5.12日)
5. //  FreedomKnight_Duzhi 转载并添加注释
6. //
7. //*****************************************************************/
8. // 本文件为SingleList全文件
9. // 附注: 遍历时间复杂度为O(N),查询结点时间复杂度为O(N/2)
11. #ifndef __SINGLE_LIST_H__
12. #define __SINGLE_LIST_H__
14. #include <assert.h>        // 用以支持断言
15. #include <crtdbg.h>        // 用以支持内存泄露检测
17. // DEBUG模式下,定义获得错误信息,文件名,行数
18. #ifdef _DEBUG
19.     #define DEBUG_NEW new ( _NORMAL_BLOCK, THIS_FILE, __LINE__ )
20. #endif
22. #ifdef _DEBUG
23.     #define new DEBUG_NEW
24. #undef THIS_FILE
25. // 节省空间,没必要生成大量的错误信息,仅保存一个常量,
26. // 出现错误其他指针指向这里则可
27. static char THIS_FILE[] = __FILE__;
28. #endif
30. // 若是DEBUG模式,则断言有效,否则使其无效
31. #ifdef _DEBUG
32.     #ifndef ASSERT
33.     #define ASSERT assert
34.     #endif
35. #else
36.     #ifndef ASSERT
37.     #define ASSERT
38.     #endif
39. #endif
41. // 单链表每一个结点结构
42. template < typename T >
43. class CNode
44. {
45. public:
46.     T data;
47.     // 因为是单链表，结点中除了数据,就仅有一个next指针了
48.     CNode< T > *next;
49.     // 构造函数初始化表
50.     CNode() : data( T() ), next(NULL){};
51.     // 重载构造函数
52.     CNode(const T &initdata) : data(initdata), next(NULL){};
53.     // 重载构造函数2
54.     CNode(const T &initdata, CNode< T > *p) : data(initdata), next(p)){};
55. };
57. // 整个单链表结构
58. template < typename T >
59. class CSList
60. {
61. protected:
62.     // 因为是单链表,仅仅需要知道链表长度和首指针就可以了
63.     int m_nCount;
64.     CNode< T > *m_pNodeHead;
65. public:
66.     CSList();
67.     CSList(const T &initdata);
68.     ~CSList();
69. public:        // 常用方法对外接口
70.     /* 注意该部分的const用法,修饰参数,修饰成员函数
71.     修饰成员函数时,此函数中不允许调用非const函数,且不许修改成员变量
72.     所以,这部分函数中都自定义了一套临时变量nCount而没有使用m_nCount
73.     */
74.     /* 关于T与T&返回值的说明.该部分的所有获取函数都实现了两次,
75.     目的是,返回值为T的,允许修改,即读写操作均允许.
76.     返回值为T&的,是其内存地址所写的常量值,不允许进行写操作,进行了保护
77.     const的目的在于进行函数重载,若不加的话,编译器认为是相同的函数
78.     */
80.     // 判断单链表是否为空
81.     bool    IsEmpty() const;
82.     // 获取单链表结点个数
83.     int        GetCount() const;
84.     // 在指定位置之前添加结点
85.     int        InsertBefore(const int pos, const T data);
86.     // 在指定位置之后添加结点
87.     int        InsertAfter(const int pos, const T data);
88.     // 在链表头部添加结点
89.     int        AddHead(const T data);
90.     // 在链表尾部添加结点
91.     int        AddTail(const T data);
92.     // 删除指定位置结点
93.     void    RemoveAt(const int pos);
94.     // 删除头结点
95.     void    RemoveHead();
96.     // 删除尾结点
97.     void    RemoveTail();
98.     // 删除所有结点
99.     void    RemoveAll();
100.     // 获取头结点数据
101.     T&        GetHead();
102.     // 获取头结点数据
103.     T        GetHead() const;
104.     // 获取尾结点数据
105.     T&        GetTail();
106.     // 获取尾结点数据
107.     T        GetTail() const;
108.     // 获取指定位置结点
109.     T&        GetAt(const int pos);
110.     // 获取指定位置结点
111.     T        GetAt(const int pos) const;
112.     // 更改指定位置结点数据
113.     void    SetAt(const int pos, T data);
114.     // 查询指定数据位置
115.     int        Find(const T data) const;
116. };
118. /* 由于模版类不支持.h和.cpp分离,故实现也写在头文件中
119. 除非编译器支持export关键字,而实际上基本没有编译器支持\(-_-)/ */
120. /* 代码短小常用的函数使用内联比较迅速 */
121. //-----------------------------------
123. template< typename T>
124. inline CSList< T >::CSList()
125.     : m_nCount            (0),
126.       m_pNodeHead        (NULL)
127. {
128. }
130. //-----------------------------------
132. template< typename T >
133. inline CSList< T >::CSList(const T &initdata)
134.     : m_nCount            (0),
135.       m_pNodeHead        (NULL)
136. {
137.     AddHead(initdata);
138. }
140. //-----------------------------------
142. template< typename T >
143. inline CSList< T >::~CSList()
144. {
145.     RemoveAll();
146. }
148. //-----------------------------------
150. template< typename T >
151. inline bool CSList< T >::IsEmpty() const
152. {
153.     if( m_nCount == 0 )
154.     {
155.         return true;
156.     }
157.     else
158.     {
159.         return false;
160.     }
161. }
163. //-----------------------------------
165. template< typename T >
166. inline int CSList< T >::AddHead(const T data)
167. {
168.     CNode< T > *pNewNode;
169.     pNewNode = new CNode< T >;
171.     if( pNewNode == NULL )
172.     {
173.         return 0;
174.     }
176.     pNewNode->data = data;
177.     pNewNode->next = m_pNodeHead;
179.     m_pNodeHead = pNewNode;
180.     ++m_nCount;
182.     return 1;
183. }
185. //-----------------------------------
187. template< typename T >
188. inline int CSList< T >::AddTail(const T data)
189. {
190.     if( InsertAfter(GetCount(), data) )
191.     {
192.         return 1;
193.     }
194.     else
195.     {
196.         return 0;
197.     }
198. }
200. //-----------------------------------
202. // 返回值说明:若返回0,则代表插入失败.若返回数字大于0,则记录插入结点的当前位置
203. template< typename T >
204. inline int CSList< T >::InsertBefore(const int pos, const T data)
205. {
206.     /* 将结点插入指定位置之前的操作要分为三种可能
207.     1:    空链表插入,头指针需要添加,新结点的指针无效
208.     2:  插入链表头部,头指针需要改变,新结点的指针赋值
209.     3:  插入链表中间,头指针不改变,改变位置前结点指针,自身指针赋值
210.     */
211.     int i;
212.     int nRetPos;                // 结点实际所在位,0代表插入失败
213.     CNode< T > *pTmpNode;        // 目标位置前结点
214.     CNode< T > *pNewNode;        // 想插入的目标结点
216.     // 若创建结点失败
217.     pNewNode = new CNode< T >;
218.     if( pNewNode == NULL )
219.     {
220.         return 0;            
221.     }
223.     pNewNode->data = data;
225.     // 若表为空,则相当于将数据结点设置为首结点
226.     if(m_pNodeHead == NULL)
227.     {
228.         pNewNode->next = NULL;
229.         m_pNodeHead = pNewNode;
230.         nRetPos = 1;
231.         ++m_nCount;
232.         return nRetPos;
233.     }
234.    
235.     // 断言:传的参数必须在合理范围内
236.     ASSERT((1 <= pos) && (pos <= m_nCount));
238.     // 若插入的是链表头位置
239.     if(pos == 1)
240.     {
241.         pNewNode->next = m_pNodeHead;
242.         m_pNodeHead = pNewNode;
243.         nRetPos = 1;
244.         ++m_nCount;
245.         return nRetPos;
246.     }
248.     // 一般情况的处理
249.     pTmpNode = m_pNodeHead;
250.     for(i = 1; i < pos - 1; ++i)
251.     {   
252.         pTmpNode = pTmpNode->next;
253.     }
254.     // 通过循环获得的指定位置原来的结点的前一个结点pTmpNode
255.     pNewNode->next = pTmpNode->next;
256.     pTmpNode->next = pNewNode;
258.     nRetPos = pos;
259.     ++m_nCount;
260.     return nRetPos;
261. }
263. //-----------------------------------
265. template< typename T >
266. inline int CSList< T >::InsertAfter(const int pos, const T data)
267. {
268.     /* 比起InsertBefore来说, InsertAfter少了一种特殊情况处理
269.     1: 链表为空时依旧需要处理
270.     2: 插入点不可能为最前,若为最后的话,也可按照一般情况,所以仅
271.        需两种处理方式.
272.     */
273.     int i;
274.     int nRetPos;
275.     CNode< T > *pTmpNode;
276.     CNode< T > *pNewNode;
278.     pNewNode = new CNode< T >;
279.     if (pNewNode == NULL)
280.     {
281.         return 0;
282.     }
284.     pNewNode->data = data;
286.     if (m_pNodeHead == NULL)
287.     {
288.         m_pNodeHead = pNewNode;
289.         pNewNode->next = NULL;
290.         m_nCount++;
291.         nRetPos = 1;
292.         return nRetPos;
293.     }
295.     ASSERT((pos >= 1) && (pos <= m_nCount));
297.     pTmpNode = m_pNodeHead;
298.     /* 注意! 和InsertInsertBefore不同,此处循环多了一次
299.     InsertInsertBefore获得的是目标位置原结点的前一个结点
300.     InsertInsertAfter获得的是目标位置原结点
301.     */
302.     for (i = 1; i < pos; i++)
303.     {
304.         pTmpNode = pTmpNode->next;
305.     }
306.     // 通过循环获得的指定位置原结点pTmpNode
307.     pNewNode->next = pTmpNode->next;
308.     pTmpNode->next = pNewNode;
309.     ++m_nCount;
310.     nRetPos = pos + 1;    /* 注意: 此处加1 */
311.     return nRetPos;
312. }
314. //-----------------------------------
316. template < typename T >
317. inline int CSList< T >::GetCount() const
318. {
319.     return m_nCount;
320. }
322. //-----------------------------------
324. template < typename T >
325. inline void CSList< T >::RemoveAt(const int pos)
326. {
327.     // 判断合法性
328.     ASSERT(pos >= 1 && pos <= m_nCount);
330.     int i;
331.     CNode< T > *pTmpNode;        // 目标结点的前一个结点
332.     CNode< T > *pDestNode;        // 目标位置结点   
333.     pTmpNode = m_pNodeHead;
335.     // 如果删除的是头结点
336.     if (pos == 1)
337.     {
338.         m_pNodeHead = m_pNodeHead->next;
339.         delete pTmpNode;
340.         --m_nCount;
341.         return ;
342.     }
344.     // 一般情况
345.     for (i = 1; i < pos - 1; ++i)
346.     {
347.         pTmpNode = pTmpNode->next;
348.     }
349.     pDestNode = pTmpNode->next;
350.     pTmpNode->next = pDestNode->next;
351.     delete pDestNode;
352.     --m_nCount;
353. }
355. //-----------------------------------
357. template < typename T >
358. inline void CSList< T >::RemoveHead()
359. {
360.     ASSERT(m_nCount != 0);
361.     RemoveAt(1);
362. }
364. //-----------------------------------
366. template < typename T >
367. inline void CSList< T >::RemoveTail()
368. {
369.     ASSERT(m_nCount != 0);
370.     RemoveAt(m_nCount);
371. }
373. //-----------------------------------
375. template < typename T >
376. inline void CSList< T >::RemoveAll()
377. {
378.     int i;
379.     int nCount;
380.     CNode < T > *pTmpNode;
382.     nCount = m_nCount;
383.     for (i = 0; i < nCount; ++i)
384.     {
385.         /* 从链表头部开始删除 */
386.         pTmpNode = m_pNodeHead->next;
387.         delete m_pNodeHead;
388.         m_pNodeHead = pTmpNode;
389.     }
390.     m_nCount = 0;
391. }
393. //-----------------------------------
395. template < typename T >
396. inline T& CSList< T >::GetTail()
397. {
398.     ASSERT(m_nCount != 0);
400.     int i;
401.     int nCount;
402.     CNode < T > *pTmpNode;
404.     pTmpNode = m_pNodeHead;
405.     nCount = m_nCount;
406.     for (i = 0; i < nCount; ++i)
407.     {
408.         pTmpNode = pTmpNode->next;
409.     }
410.     return pTmpNode->data;
411. }
413. //-----------------------------------
415. template < typename T >
416. inline T CSList< T >::GetTail() const
417. {
418.     ASSERT(m_nCount != 0);
420.     int i;
421.     int nCount;
422.     CNode < T > *pTmpNode;
424.     pTmpNode = m_pNodeHead;
425.     nCount = m_nCount;
426.     for (i = 0; i < nCount; ++i)
427.     {
428.         pTmpNode = pTmpNode->next;
429.     }
430.     return pTmpNode->data;
431. }
433. //-----------------------------------
435. template < typename T >
436. inline T& CSList< T >::GetHead()
437. {
438.     ASSERT(m_nCount != 0);
439.     return m_pNodeHead->data;
440. }
442. //-----------------------------------
444. template < typename T >
445. inline T CSList< T >::GetHead() const
446. {
447.     ASSERT(m_nCount != 0);
448.     return m_pNodeHead->data;   
449. }
451. //-----------------------------------
453. template < typename T >
454. inline T& CSList< T >::GetAt(const int pos)
455. {
456.     ASSERT(pos >= 1 && pos <= m_nCount);
458.     int i;
459.     CNode< T > *pTmpNode;
460.     pTmpNode = m_pNodeHead;
462.     for (i = 1; i < pos; i++)
463.     {
464.         pTmpNode = pTmpNode->next;
465.     }
466.     return pTmpNode->data;
467. }
469. //-----------------------------------
471. template < typename T >
472. inline T CSList< T >::GetAt(const int pos) const
473. {
474.     ASSERT(pos >= 1 && pos <= m_nCount);
476.     int i;
477.     CNode< T > *pTmpNode;
478.     pTmpNode = m_pNodeHead;
480.     for (i = 1; i < pos; i++)
481.     {
482.         pTmpNode = pTmpNode->next;
483.     }
484.     return pTmpNode->data;
485. }
487. //-----------------------------------
489. template<typename T>
490. inline void CSList<T>::SetAt(const int pos, T data)
491. {
492.     ASSERT(1 <= pos && pos <= m_nCount);
494.     int i;
495.     CNode<T> *pTmpNode = m_pNodeHead;
497.     for (i = 1; i < pos; ++i)
498.     {
499.         pTmpNode = pTmpNode->next;
500.     }
501.     pTmpNode->data = data;
502. }
504. //-----------------------------------
506. template < typename T >
507. inline int CSList< T >::Find(const T data) const
508. {
509.     int i;
510.     int nCount;
511.     CNode< T >  *pTmpNode;
513.     pTmpNode = m_pNodeHead;
514.     nCount = m_nCount;
516.     // 遍历所有的结点
517.     for (i = 0; i < nCount; ++i)
518.     {
519.         if (data = pTmpNode->data)
520.         {
521.             return i + 1;    // 结点号和索引号差1
522.         }
523.         pTmpNode = pTmpNode->next;
524.     }
525.     // 若未找到则返回空
526.     return 0;
527. }
529. //-----------------------------------
531. #endif

复制代码

3. //*****************************************************************
4. //
5. //    SingleList单链表学习代码(2004.5.12日)
6. //  FreedomKnight_Duzhi 转载并添加注释
7. //
8. //*****************************************************************/
9. // 本文件用以测试SinList
12. #include <iostream>
13. #include "SinList.h"
14. using namespace std;
16. int main(void)
17. {
18.     int i;
19.     int nCount;
20.     CSList< int > sList;
22. #ifdef _DEBUG
23.     /* 如果是DEBUG模式下,若main函数运行完毕,还有内存没有释放,则会将其信息反馈
24.     到编译器下方的调试窗口有提示(注:但是这句不进行错误位置的提示,所以若需要错误定位
25.     依旧需要依靠头文件中的__FILE__那一行) */
26.     _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
27. #endif
29.     sList.InsertAfter(sList.InsertAfter(sList.AddHead(1), 2), 3);    /* 1,2,3 */
30.     sList.InsertAfter(sList.InsertAfter(sList.GetCount(), 4), 5);    /* 1,2,3,4,5 */
31.     sList.InsertAfter(sList.GetCount(), 6);                            /* 1,2,3,4,5,6 */
32.     sList.AddTail(10);                                                /* 1,2,3,4,5,6,10 */
33.     sList.InsertAfter(sList.InsertBefore(sList.GetCount(), 7), 8);  /* 1,2,3,4,5,6,7,8,10 */
34.     sList.SetAt(sList.GetCount(), 9);                                /* 1,2,3,4,5,6,7,8,9  */
35.     sList.RemoveHead();                                                /* 2,3,4,5,6,7,8,9  */
36.     sList.RemoveTail();                                                /* 2,3,4,5,6,7,8  */
38.     nCount = sList.GetCount();
39.     for (i = 0; i < nCount; ++i)
40.     {
41.         cout << sList.GetAt(i + 1) << endl;
42.     }
43.     // 等待输入才退出
44.     getchar();
45. }

复制代码

duzhi5368

[s:5] 其实实现的原理到是很基础的,不过这个格式值得学习,写引擎的专用方式.