第2节 线性表使用链式结构（单链表）实现
时间：2010-08-28 来源：chinazhangjie
代码
代码
1 /* 主题: 线性表使用链式结构（单链表）实现
2 * 作者: chinazhangjie(邮箱:[email protected])
3 * 开发语言: C++
4 * 开发环境: Microsoft Visual Studio 2008
5 * 日期: 2010.08.28
6 */
7
8 template <class T>
9 class linked_slist {
10 struct node; // 声明
11 public:
12 typedef T value_type;
13 typedef unsigned int ls_size;
14 typedef node* node_pointer;
15 public:
16 // 构造函数
17 linked_slist() {
18 __init_slist();
19 }
20 // 拷贝构造函数
21 linked_slist(linked_slist<T>& rhs) {
22 __init_slist();
23 __copy(rhs);
24 }
25 // 析构函数
26 ~linked_slist() {
27 __destroy_slist();
28 delete head;
29 head = NULL;
30 tail = NULL;
31 }
32
33 // 清空单链表
34 void clear() {
35 __destroy_slist();
36 }
37
38 // 判断单链表是否为空
39 bool empty() const {
40 return length == 0;
41 }
42 // 排序——递增
43 void sort_increase() {
44 if (length == 0 || length == 1)
45 return ;
46 for (ls_size i = 0; i < length-1; ++ i) {
47 ls_size ii = i;
48 for (ls_size j = i; j < length; ++ j) {
49 if (this->at(ii) > this->at(j)) {
50 ii = j;
51 }
52 }
53 if (ii != i) {
54 // 交换
55 value_type tmp = (*this)[ii];
56 (*this)[ii] = (*this)[i];
57 (*this)[i] = tmp;
58 }
59 }
60 }
61 // 排序——递减
62 void sort_decrease() {
63 if (length == 0 || length == 1)
64 return ;
65 for (ls_size i = 0; i < length-1; ++ i) {
66 ls_size ii = i;
67 for (ls_size j = i; j < length; ++ j) {
68 if (this->at(ii) < this->at(j)) {
69 ii = j;
70 }
71 }
72 if (ii != i) {
73 // 交换
74 value_type tmp = (*this)[ii];
75 (*this)[ii] = (*this)[i];
76 (*this)[i] = tmp;
77 }
78 }
79 }
80 // 排序——函数指针
81 void sort(bool (*compare)(value_type,value_type)) {
82 if (length == 0 || length == 1)
83 return ;
84 for (ls_size i = 0; i < length-1; ++ i) {
85 ls_size ii = i;
86 for (ls_size j = i; j < length; ++ j) {
87 if ((*compare)(this->at(ii),this->at(j))) {
88 ii = j;
89 }
90 }
91 if (ii != i) {
92 // 交换
93 value_type tmp = (*this)[ii];
94 (*this)[ii] = (*this)[i];
95 (*this)[i] = tmp;
96 }
97 }
98 }
99 // 排序——仿函数
100 template <class FuncObj>
101 void sort(FuncObj& funobj) {
102 if (length == 0 || length == 1)
103 return ;
104 for (ls_size i = 0; i < length-1; ++ i) {
105 ls_size ii = i;
106 for (ls_size j = i; j < length; ++ j) {
107 if (funobj(this->at(ii),this->at(j))) {
108 ii = j;
109 }
110 }
111 if (ii != i) {
112 // 交换
113 value_type tmp = (*this)[ii];
114 (*this)[ii] = (*this)[i];
115 (*this)[i] = tmp;
116 }
117 }
118 }
119
120 // 将两个按值非递减的单链表(*this,rhs)合并到*this中
121 void merge(linked_slist<T>& rhs) {
122
123 if (rhs.size() == 0)
124 return ;
125 linked_slist<T> other(rhs);
126 other.sort_increase();
127 this->sort_increase();
128 if (length == 0) {
129 // 将other复制到*this
130 __copy(other);
131 }
132 linked_slist<T> total;
133 ls_size len1 = 0;
134 ls_size len2 = 0;
135 while (len1 < this->size() && len2 < other.size()) {
136 if ((*this)[len1] <= other[len2]) {
137 total.push_back((*this)[len1]);
138 ++ len1;
139 }
140 else {
141 total.push_back(other[len2]);
142 ++ len2;
143 }
144 }
145 while (len1 < this->size()) {
146 total.push_back((*this)[len1]);
147 ++ len1;
148 }
149 while (len2 < other.size()) {
150 total.push_back(other[len2]);
151 ++ len2;
152 }
153 (*this) = total;
154 }
155
156 // 获得长度
157 ls_size size() const {
158 return length;
159 }
160
161 // 头插
162 void push_front(value_type elem) {
163 node_pointer tmp = new node(elem);
164 if (tmp == NULL)
165 throw std::bad_alloc("push_front bad_alloc");
166 tmp->next = head->next;
167 head->next = tmp;
168 if (length == 0) {
169 tail = tmp;
170 }
171 ++ length;
172 }
173
174 // 尾插
175 void push_back(value_type elem) {
176 node_pointer tmp = new node(elem);
177 if (tmp == NULL)
178 throw std::bad_alloc("push_back bad_alloc");
179 if (length == 0) {
180 head->next = tmp;
181 tail = tmp;
182 }
183 else {
184 tail->next = tmp;
185 tail = tmp;
186 }
187 ++ length;
188 }
189
190 // 删除第locate个元素，并返回其值
191 value_type delete_elem(ls_size locate) {
192 value_type del_value;
193 if (locate >= length) {
194 throw std::out_of_range("delete_elem out_of_rangle");
195 }
196 if (locate == length-1) {
197 // 删除最后一个元素，让tail指向最后一个元素
198 del_value = tail->data;
199 delete tail;
200 tail = NULL;
201 node_pointer tmp = head->next;
202 ls_size i = 0;
203 while (i < length - 1) {
204 tmp = tmp->next;
205 ++ i;
206 }
207 tail = tmp;
208 tail->next = NULL;
209
210 }
211 else {
212 node_pointer tmp = head;
213 ls_size i = 0;
214 while (i < locate) {
215 tmp = tmp->next;
216 ++ i;
217 }
218 node_pointer del_node = tmp->next;
219 tmp->next = tmp->next->next;
220 del_value = del_node->data;
221 delete del_node;
222 }
223 -- length;
224 return del_value;
225 }
226
227 // 在第locate个元素之前，插入元素elem
228 void insert(ls_size locate,value_type elem) {
229 if (locate == 0 && this->size() == 0) {
230 this->push_front(elem);
231 return ;
232 }
233 if (locate == this->size()) {
234 this->push_back(elem);
235 return ;
236 }
237 if (locate > this->size()) {
238 throw std::out_of_range("insert out_of_range");
239 }
240 node_pointer insert_node = new node(elem);
241 if (insert_node == NULL)
242 throw std::bad_alloc("insert bad_alloc");
243 ls_size i = 0;
244 node_pointer tmp = head;
245 while (i < locate) {
246 tmp = tmp->next;
247 ++ i;
248 }
249 insert_node->next = tmp->next;
250 tmp->next = insert_node;
251 ++ length;
252 }
253
254 // 将链表逆序排列
255 void reverse() {
256 if (length == 0 || length == 1)
257 return ;
258 ls_size len = length;
259 linked_slist<T> new_slist;
260 while (len > 0) {
261 new_slist.push_front(this->__pop_first());
262 -- len;
263 }
264 (*this) = new_slist;
265 }
266
267 //
268 value_type at(ls_size locate) const {
269 if (locate > length -1 )
270 throw std::out_of_range("[] out_of_range");
271 ls_size i=0;
272 node_pointer tmp = head->next;
273 while (i < locate && tmp) {
274 tmp = tmp->next;
275 ++ i;
276 }
277 return tmp->data;
278 }
279
280 // 重载下标运算符
281 value_type& operator[] (ls_size locate) {
282 if (locate > length -1 )
283 throw std::out_of_range("[] out_of_range");
284 ls_size i=0;
285 node_pointer tmp = head->next;
286 while (i < locate && tmp) {
287 tmp = tmp->next;
288 ++ i;
289 }
290 return tmp->data;
291 }
292 // 重载赋值运算符
293 linked_slist<T>& operator = (linked_slist<T>& rhs) {
294 if (this == &rhs) {
295 return *this;
296 }
297 __destroy_slist();
298 __copy(rhs);
299 return *this;
300 }
301 // 重载 "<<"
302 template <class T>
303 friend ostream& operator << (ostream& out,linked_slist<T>& rhs) {
304 if (rhs.size() == 0)
305 return out;
306 ls_size i=0;
307 while (i < rhs.size()) {
308 cout << rhs[i] << " ";
309 ++ i;
310 }
311 return out;
312 }
313
314 private:
315 // 初始化
316 void __init_slist() {
317 head = new node(0);
318 if (head == NULL)
319 throw std::bad_alloc("__init_slist() bad_alloc");
320 tail = NULL;
321 length = 0;
322
323 }
324
325 // 销毁，保留第一个结点
326 void __destroy_slist() {
327 if (length == 0) {
328 return ;
329 }
330 node_pointer tmp = head->next;
331 while (tmp) {
332 node_pointer del_node = tmp;
333 tmp = tmp->next;
334 delete del_node;
335 }
336 head->next = NULL;
337 tail = NULL;
338 length = 0;
339 }
340
341 // 复制
342 void __copy(linked_slist<T>& rhs) {
343 ls_size i = 0;
344 while (i < rhs.size()) {
345 this->push_back(rhs[i]);
346 ++ i;
347 }
348 }
349
350 // 删除第一个元素，返回第一个元素的值
351 value_type __pop_first() {
352 if (length == 0)
353 throw std::out_of_range("__pop_first out_of_range");
354 value_type tmp;
355 if (length == 1) {
356 tmp = head->next->data;
357 delete head->next;
358 head->next = NULL;
359 tail = NULL;
360 }
361 else {
362 tmp = head->next->data;
363 node_pointer del_node = head->next;
364 head->next = head->next->next;
365 delete del_node;
366 }
367 return tmp;
368 }
369
370 private:
371 ls_size length; // 单链表的长度
372 node_pointer head; // 头结点
373 node_pointer tail; // 尾结点
374
375 private:
376 // 内部节点类
377 struct node {
378 public:
379 node(value_type elem)
380 :data(elem),next(NULL) { }
381 public:
382 value_type data;
383 node* next;
384 };
385 };
相关阅读 更多 +
