利用C++模板实现单链表的各种操作
1 /*
2 * SingleLink.cpp
3 * author : freejohn
4 * time : 2012-07-08 night
5 */
6
7 #include <cstdio>
8 #include <cstring>
9 #include <iostream>
10 #include <iterator>
11 #include <string>
12 #include <cstdlib>
13 #include <cassert>
14 using namespace std;
15
16 //siglink class
17 template <class T>
18 class SLinkList;
19
20 //link node
21 template <class T>
22 class LNode
23 {
24 friend class SLinkList<T>;
25 public:
26 T data;
27 LNode<T>* next;
28 };
29
30 template <class T>
31 class SLinkList
32 {
33 public:
34 SLinkList();
35 ~SLinkList();
36
37 public:
38 bool Insert(int pos, T e);
39 LNode<T>* Find(int pos);
40 LNode<T>* middle();
41 int GetSize();
42 bool Delete(int pos, T& e);
43 void print();
44 void reverse();
45
46 private:
47 LNode<T>* first;
48 };
49
50
51 template <class T> SLinkList<T>::SLinkList()
52 {
53 first = new LNode<T>;
54 assert(first!=NULL);
55 first->data = NULL;
56 first->next = NULL;
57 }
58
59 template <class T> SLinkList<T>::~SLinkList()
60 {
61 LNode<T>* p = first;
62 while(p != NULL)
63 {
64 LNode<T> *q = p;
65 p = p->next;
66 delete q;
67 }
68 }
69
70 template <class T> int SLinkList<T>::GetSize()
71 {
72 if( first == NULL )
73 return -1;
74 LNode<T>* p = first->next;
75 int len = 0;
76 while( p != NULL )
77 {
78 ++len;
79 p = p->next;
80 }
81 return len;
82 }
83
84 template <class T> LNode<T>* SLinkList<T>::Find(int pos)
85 {
86 if(pos == 0)
87 return first;
88 int index = 0;
89 LNode<T>* p = first;
90 while(p != NULL && index < pos)
91 {
92 ++index;
93 p = p->next;
94 }
95 return p;
96 }
97
98 template <class T> bool SLinkList<T>::Insert(int pos, T e)
99 {
100 LNode<T>* p = Find(pos-1);
101 if(p == NULL)
102 return false;
103 LNode<T>* q = new LNode<T>;
104 q->data = e;
105 q->next = p->next;
106 p->next = q;
107 return true;
108 }
109
110 template <class T> bool SLinkList<T>::Delete(int pos, T& e)
111 {
112 LNode<T>* p = Find(pos-1);
113 if(p == NULL)
114 return false;
115 e = p->next->data;
116 p->next = p->next->next;
117 return true;
118 }
119
120 template <class T>
121 void SLinkList<T>::print()
122 {
123 LNode<T>* p = first->next;
124 while(p!=NULL)
125 {
126 cout << p->data << " ";
127 p = p->next;
128 }
129 }
130
131
132 template <class T>
133 void SLinkList<T>::reverse()
134 {
135 /*这种方法是利用插入的办法，不太好
136 LNode<T>* head = new LNode<T>;
137 head->data = NULL;
138 head->next = NULL;
139 LNode<T>* p = first->next;
140 while(p!=NULL)
141 {
142 LNode<T>* q = new LNode<T>;
143 q->data = p->data;
144 q->next = head->next;
145 head->next = q;
146 //cout << p->data<<endl;
147 p = p->next;
148 }
149 first = head;*/
150 LNode<T> *p1, *p2, *p3;
151 if(first == NULL || first->next == NULL)
152 return ;
153 /*p1 = first;
154 p2 = first->next;
155 while(p2)
156 {
157 p3 = p2->next;
158 p2->next = p1;
159 p1 = p2;
160 p2 = p3;
161 }
162 first->next->next = NULL;
163 first->next = p1;*/
164 p1 = first->next;
165 p2 = p1->next;
166 p1->next = NULL;
167 while(p2)
168 {
169 p3 = p2->next;
170 p2->next = p1;
171 p1 = p2;
172 p2 = p3;
173 }
174 //first->next->next = NULL;
175 first->next = p1;
176 }
177
178 template <class T>
179 LNode<T>* SLinkList<T>::middle()
180 {
181 if(first == NULL || first->next == NULL)
182 return first;
183 LNode<T>* p = first->next;
184 LNode<T>* q = p;
185 //int index=0;
186 while(p->next!=NULL&&q->next!=NULL&&q->next->next!=NULL)
187 {
188 //++index;
189 //cout<<index<<endl;
190 //if(index == 5) cout << q->next->data << endl;
191 //p = p->next;
192 q = q->next->next;
193 p = p->next;
194 }
195 return p;
196 }
197
198 //test
199 int main()
200 {
201 int x = NULL;
202 SLinkList<int> testList;
203 //cout << testList.Insert(1,5) << endl;
204 //cout << testList.Insert(2,5) << endl;
205 for(int i=1;i<=10;++i)
206 {
207 testList.Insert(i, i*2);
208 }
209 cout << testList.GetSize() << endl;
210 cout << testList.Find(2)->data << endl;
211 testList.print();
212 cout << endl;
213 testList.reverse();
214 testList.print();
215 cout << endl;
216 LNode<int>* p = testList.middle();
217 if(p!=NULL)
218 cout << "middle is " << p->data << endl;
219 else cout << "error!" << endl;
220 cout << testList.Delete(2, x) << endl;
221 cout << x << endl;
222 testList.print();
223 cout << endl;
224 }
225