【C++】C++模板实现的单向链表

0x55AA

C++模板实现的单向链表，实现了链表的初始化创建，元素插入，元素链表末尾添加，元素删除，链表清空
Lists.h

1. //Lists.h
   
2. #ifndef DDXXLISTS_H
   
3. #define DDXXLISTS_H
   
4. #include <iostream>
   
5. using namespace std;
   
6. template<typename Type>
   
7. class Lists
   
8. {
   
9. public:
   
10.         Lists();
    
11.         Lists(int nSize);
    
12.         ~Lists();
    
13. public:
    
14.         struct Node
    
15.         {
    
16.                 Type  e;
    
17.                 Node* next;
    
18.                 Node()
    
19.                 {
    
20.                 }
    
21.                 Node(Type _e)
    
22.                 {
    
23.                         e = _e;
    
24.                         next = NULL;
    
25.                 }
    
26.         };
    
27. public:
    
28.         bool insert(Type e,int pos);
    
29.         bool add(Type e);
    
30.         bool erase(int pos);
    
31.         void clear();
    
32.         bool isEmpty();
    
33.         int getLength();
    
34.         void print();
    
35. private:
    
36.         Node* m_head;
    
37.         int m_nLength;
    
38. };
    
39. 
    
40. template<typename Type> Lists<Type>::Lists()
    
41. {
    
42.         Node *pPos = new Node;
    
43.         pPos->next = NULL;
    
44.         m_head = pPos;
    
45.         m_nLength = 0;
    
46. }
    
47. 
    
48. template<typename Type> Lists<Type>::Lists(int nSize)
    
49. {
    
50.         m_nLength = nSize;
    
51.         Node *pPos = new Node;
    
52.         pPos->next = NULL;
    
53.         m_head = pPos;
    
54.         m_nLength = nSize;
    
55.        
    
56.         for (int i=0;i<m_nLength;i++)
    
57.         {
    
58.                 pPos->next = new Node;
    
59.                 pPos = pPos->next;
    
60.         }
    
61. }
    
62. 
    
63. template<typename Type> bool Lists<Type>::insert(Type e,int pos)
    
64. {
    
65.         if (pos >= m_nLength)
    
66.         {
    
67.                 cout<<"The position to insert out of range"<<endl;
    
68.                 return false;
    
69.         }
    
70.         else
    
71.         {
    
72.                 Node *ptr = m_head;
    
73.                 int cnt = 0;
    
74.                 while(cnt <= pos)
    
75.                 {
    
76.                         ptr = ptr->next;
    
77.                         cnt++;
    
78.                 }
    
79.                 Node *pNew = new Node(e);
    
80.                 pNew->next = ptr->next;
    
81.                 ptr->next = pNew;
    
82. 
    
83.                 m_nLength++;
    
84.                 return true;
    
85.         }
    
86. }
    
87. 
    
88. template<typename Type> bool Lists<Type>::add(Type e)
    
89. {
    
90.         Node *pNew = new Node(e);
    
91.         if (pNew == NULL)
    
92.         {
    
93.                 cout<<"allocate memory for new node failed"<<endl;
    
94.                 return false;
    
95.         }
    
96.         else
    
97.         {
    
98.                 Node *ptr = m_head;
    
99.                 while(ptr->next != NULL)
    
100.                 {
     
101.                         ptr = ptr->next;
     
102.                 }
     
103.                 ptr->next = pNew;
     
104.                 pNew->next = NULL;
     
105.                 m_nLength++;
     
106.                 return true;
     
107.         }
     
108. }
     
109. 
     
110. template<typename Type> bool  Lists<Type>::erase(int pos)
     
111. {
     
112.         if (pos >= m_nLength)
     
113.         {
     
114.                 cout<<"The position to delete out of range"<<endl;
     
115.                 return false;
     
116.         }
     
117.         else
     
118.         {
     
119.                 Node *ptr = m_head;
     
120.                 int i = 0;
     
121.                 while( i<pos )
     
122.                 {
     
123.                         ptr = ptr->next;
     
124.                         i++;
     
125.                 }
     
126.                 Node *pdel = ptr->next;
     
127.                 ptr->next = ptr->next->next;
     
128.                 delete pdel;
     
129.                 pdel = NULL;
     
130.                 m_nLength--;
     
131. 
     
132.                 return true;
     
133.         }
     
134. }
     
135. 
     
136. template<typename Type> void Lists<Type>::print()
     
137. {
     
138.         if(m_nLength ==0)
     
139.                 cout<<"The list is empty"<<endl;
     
140.         Node *ptr = m_head;
     
141.         while(ptr->next!= NULL)
     
142.         {
     
143.                 ptr = ptr->next;
     
144.                 cout<<"element value:"<<ptr->e<<endl;
     
145.         }
     
146. }
     
147. 
     
148. template<typename Type> int Lists<Type>::getLength()
     
149. {
     
150.         return m_nLength;
     
151. }
     
152. template<typename Type> bool Lists<Type>::isEmpty()
     
153. {
     
154.         return m_head->next == NULL;
     
155. }
     
156. 
     
157. template<typename Type> void Lists<Type>::clear()
     
158. {
     
159.         Node *ptr = m_head->next;
     
160.         Node *ptmp = NULL;
     
161.         while(ptr != NULL)
     
162.         {
     
163.                 ptmp = ptr;
     
164.                 ptr = ptr->next;
     
165.                 delete ptmp;
     
166.                 ptmp = NULL;
     
167.                 m_nLength--;
     
168.         }
     
169.         m_head->next = NULL;
     
170. 
     
171. }
     
172. template<typename Type> Lists<Type>::~Lists()
     
173. {
     
174.         Node *ptr = m_head;
     
175.         Node *ptmp = NULL;
     
176.         while(ptr->next != NULL)
     
177.         {
     
178.                 ptmp = ptr;
     
179.                 ptr = ptr->next;
     
180.                 delete ptmp;
     
181.                 ptmp = NULL;
     
182.         }
     
183.         delete ptr;
     
184.         ptr = NULL;
     
185. }
     
186. #endif

复制代码

main.cpp

1. //main.cpp
   
2. #include <iostream>
   
3. #include "Lists.h"
   
4. using namespace std;
   
5. void main()
   
6. {
   
7.         cout<<"*************************Test list init***************************"<<endl;
   
8.         Lists<int> Lisa;
   
9.         cout<<"List's length is:"<<Lisa.getLength()<<endl;
   
10.         cout<<"List is empty:"<<Lisa.isEmpty()<<endl;
    
11. 
    
12.         cout<<"*************************Test list add element********************"<<endl;
    
13.         Lisa.add(1);
    
14.         Lisa.add(2);
    
15.         Lisa.add(3);
    
16.         Lisa.add(4);
    
17.         Lisa.add(5);
    
18.         Lisa.print();
    
19.         cout<<"List's length is:"<<Lisa.getLength()<<endl;
    
20.         cout<<"List is empty:"<<Lisa.isEmpty()<<endl;
    
21. 
    
22.         cout<<"*************************Test list insert*************************"<<endl;
    
23.         Lisa.insert(-1,0);
    
24.         Lisa.insert(11,2);
    
25.         Lisa.insert(100,6);
    
26.         Lisa.print();
    
27.         cout<<"List's length is:"<<Lisa.getLength()<<endl;
    
28.         cout<<"List is empty:"<<Lisa.isEmpty()<<endl;
    
29. 
    
30.         cout<<"*************************Test list erase**************************"<<endl;
    
31.         Lisa.erase(0);
    
32.         Lisa.erase(2);
    
33.         Lisa.erase(5);
    
34.         Lisa.print();
    
35.         cout<<"List's length is:"<<Lisa.getLength()<<endl;
    
36.         cout<<"List is empty:"<<Lisa.isEmpty()<<endl;
    
37. 
    
38.         cout<<"*************************Test list clear**************************"<<endl;
    
39.         Lisa.clear();
    
40.         Lisa.print();
    
41.         cout<<"List's length is:"<<Lisa.getLength()<<endl;
    
42.         cout<<"List is empty:"<<Lisa.isEmpty()<<endl;
    
43. }

复制代码

程序运行结果：