C++模板实现单循环链表的各种操作
1 /*
2 * LoopLink.cpp
3 * author : freejohn
4 * time : 2012-07-12 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 template <class T> class CLinkList;
17
18 //定义节点
19 template <class T>
20 class CLNode
21 {
22 friend class CLinkList<T>;
23 public:
24 T data;
25 CLNode<T>* next;
26 };
27
28 template <class T>
29 class CLinkList
30 {
31 public:
32 CLinkList();
33 CLinkList(const CLinkList& );
34 ~CLinkList();
35
36 public:
37 bool Insert(int pos, T e);
38 CLNode<T>* find(int pos);
39 int GetSize();
40 bool Delete(int pos, T& e);
41 private:
42 CLNode<T>* first;
43 };
44
45 template <class T>
46 CLinkList<T>::CLinkList()
47 {
48 first = new CLNode<T>;
49 assert(first!=NULL);
50 first->data = NULL;
51 first->next = first;
52 }
53
54 template <class T>
55 CLinkList<T>::CLinkList(const CLinkList& myList)
56 {
57 CLNode<T>* q = myList.first->next;
58 CLNode<T>* pb = new CLNode<T>;
59 first = pb;
60 while(q != myList.first)
61 {
62 CLNode<T>* p = new CLNode<T>;
63 p->data = q->data;
64 p->next = first;
65 pb->next = p;
66 pb = p;
67 q = q->next;
68 }
69 }
70
71 template <class T>
72 CLinkList<T>::~CLinkList()
73 {
74 CLNode<T>* p = first->next;
75 while(p!=first)
76 {
77 CLNode<T>* q = p;
78 p = p->next;
79 delete q;
80 }
81 delete first;
82 }
83
84 template <class T>
85 bool CLinkList<T>::Insert(int pos, T e)
86 {
87 CLNode<T>* p = find(pos-1);
88 if(p == NULL)
89 return false;
90 CLNode<T>* q = new CLNode<T>;
91 q->data = e;
92 q->next = p->next;
93 p->next = q;
94 return true;
95 }
96
97 template <class T>
98 CLNode<T>* CLinkList<T>::find(int pos)
99 {
100 if(pos<0) return NULL;
101 if(pos==0) return first;
102 int cnt=0;
103 CLNode<T>* p = first->next;
104 while(p!=first&&cnt<pos-1)
105 {
106 ++cnt;
107 p = p->next;
108 }
109 if(cnt<pos-1) return NULL;
110 return p;
111 }
112
113 template <class T>
114 int CLinkList<T>::GetSize()
115 {
116 CLNode<T>* p = first->next;
117 int cnt=0;
118 while(p!=first)
119 {
120 ++cnt;
121 p = p->next;
122 }
123 return cnt;
124 }
125
126 template <class T>
127 bool CLinkList<T>::Delete(int pos, T&e)
128 {
129 CLNode<T>* p = find(pos-1);
130 if(p == NULL)
131 return false;
132 CLNode<T>* q = p->next;
133 p->next = q->next;
134 e = q->data;
135 return true;
136 }
137 //test
138 int main()
139 {
140 int x = NULL;
141 CLinkList<int> testList;
142 cout << testList.Insert(1,4) << endl;
143 cout << testList.Insert(2,5) << endl;
144 cout << testList.Insert(2,5) << endl;
145 cout << testList.GetSize() << endl;
146 cout << testList.find(2)->data << endl;
147 cout << testList.Delete(1, x) << endl;
148 cout << x << endl;
149 }
150
151