邓公数据结构与算法3-列表

事实上 2017 年的这个时候我看了一遍浙大陈越老师的《数据结构》,并且有详细的做笔记。但现在回过头来看,这些好像基本上又都忘了。。问题应该是在于学过之后不怎么使用,当时也只是看了视频,而没有去刷题。

所以这次总结下经验,只看视频并做笔记是远远不够的。视频的缺陷在于不像书本那样,能够随意的翻到你不懂或者模糊的知识点。所以,这次我应该做的是,把视频快速过一遍,记下老师说的知识点,然后对照书本去敲代码。更更更重要的是,不断的练习。

列表(链表)

这部分内容的结构跟 向量 那一章是一样的。先介绍操作接口,然后逐个介绍它们的实现。

列表,也就是链表,与向量对称且互补。

向量: 循秩访问 call-by-rank

列表: 循位置访问 call-by-position

双向链表和单向链表。

邓老师讲的是双向链表,所以含有 头节点 header 和 尾节点 trailer。

header 和 trailer 是与生俱来的,也是不可见的。所以初始化的链表节点中含有两个空节点。

双向链表的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485

# ifndef DOUBLE_LINK_HPP

# define DOUBLE_LINK_HPP

/*

双向链表的节点结构

*/

template <typename T>

struct Node

{

public:

Node()= default;

Node(T value, Node<T>* preptr, Node<T>* nextptr)

:_value(value), pre_ptr(preptr), next_ptr(nextptr){}



public:

T _value;

Node<T>* pre_ptr;

Node<T>* next_ptr;

};



/*

* 双向链表类

*/

template<typename T>

class DoubleLink

{

public:

typedef Node<T>* pointer;

public:

DoubleLink();

~DoubleLink(){};

public:

Node<T>* insert(int index, T value);

Node<T>* insert_front(T value);

Node<T>* insert_last(T value);



Node<T>* del(int index);

Node<T>* delete_front();

Node<T>* delete_last();



bool isEmpty();

int size();



T get(int index);

T get_front();

T get_last();

Node<T>* getHead();



private:

Node<T>* phead;

int count;

private :

Node<T>* getNode(int index);

};

/*

* 构造函数

*

*/

template <typename T>

DoubleLink<T>::DoubleLink()

{

phead = new Node<T>(0, NULL, NULL);

phead->next_ptr = phead;

phead->pre_ptr = phead;

count = 0;

};

template<typename T>

Node<T>* DoubleLink<T>::getHead()

{

return phead;

}



/*

*返回链表长度

*/

template <typename T>

int DoubleLink<T>::size()

{

return count;

}

/*

获取指定下标的元素

*/

template <typename T>

Node<T>* DoubleLink<T>::getNode(int index)

{

if (index >= count || index < 0)

return NULL;



if (index<=count / 2) //如果在前半部分

{

Node<T>* pnode = phead->next_ptr;

while (index)

{

pnode = pnode->next_ptr;

index--;

}

return pnode;

} //在后半部分



index = count - index-1;

Node<T>* pnode = phead->pre_ptr;

while (index)

{

pnode = pnode->pre_ptr;

index--;

}

return pnode;

};

/*

*将新节点插到第一个位置

*/

template <typename T>

Node<T>* DoubleLink<T>::insert_front(T value)

{

Node<T>* newNode = new Node<int>(value, phead, phead->next_ptr);

phead->next_ptr ->pre_ptr= newNode;

phead->next_ptr = newNode;

count++;

return newNode;

};

/*

*将新节点插到链表尾部

*/

template <typename T>

Node<T>* DoubleLink<T>::insert_last(T value)

{

Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead);

phead->pre_ptr->next_ptr = newNode;

phead->pre_ptr = newNode;

count++;

return newNode;

};

/*

*将节点位置插到index位置之前

*/



template <typename T>

Node<T>* DoubleLink<T>::insert(int index, T value)

{

if (index == 0)

return insert_front(value);



Node<T>* pNode = getNode(index);

if (pNode == NULL)

return NULL;

Node<T>* newNode = new Node<T>(value, pNode->pre_ptr, pNode);

pNode->pre_ptr->next_ptr = newNode;

pNode->pre_ptr = newNode;

count++;



return newNode;

};

/*

*删除链表第一个节点

*返回删除后链表第一个节点

*/

template<typename T>

Node<T>* DoubleLink<T>::delete_front()

{

if (count == 0) //空树,返回NULL

{

return NULL;

}

Node<T>* pnode = phead->next_ptr;

phead->next_ptr = pnode->next_ptr;

pnode->next_ptr->pre_ptr = phead;

delete pnode;

count--;

return phead->next_ptr;

};

/*

*删除链表的末尾节点

*返回删除后链表尾部元素

*/

template<typename T>

Node<T>* DoubleLink<T>::delete_last()

{

if (count == 0)

{

return NULL;

}

Node<T>*pnode = phead->pre_ptr;

pnode->pre_ptr->next_ptr = phead;

phead->pre_ptr = pnode->pre_ptr;

delete pnode;

count--;

return phead->pre_ptr;

}

/*

*删除指定位置的元素

*

*/

template <typename T>

Node<T>* DoubleLink<T>::del(int index)

{

if (index == 0)

return delete_front();

if (index == count - 1)

return delete_last();

if (index >= count)

return NULL;

Node<T>* pnode = getNode(index);

pnode->pre_ptr->next_ptr = pnode->next_ptr;

pnode->next_ptr->pre_ptr = pnode->pre_ptr;



Node<T>* ptemp = pnode->pre_ptr;

delete pnode;

count--;

return ptemp;

};



template <typename T>

bool DoubleLink<T>::isEmpty()

{

return count == 0;

};

/*

*获取第一个节点的值

*/

template<typename T>

T DoubleLink<T>::get_front()

{

return phead->next_ptr->_value;

};

/*

*获取最后一个节点的值

*/

template <typename T>

T DoubleLink<T>::get_last()

{

return phead->pre_ptr->_value;

};

/*

*获取指定位置节点的值

*/

template <typename T>

T DoubleLink<T>::get(int index)

{

Node<T> pnode = getNode(index);

return pnode->_value;

};

# endif

排序

leetcode 148: https://leetcode.com/problems/sort-list/submissions/

选择排序

实际上 冒泡排序 也可以看做是选择排序,不同的是,在选择最大元素的时候,冒泡排序每比较一次都会进行一次交换,这样亦步亦趋的方式增加了消耗。而选择排序,只是进行比较,每一趟遍历只交换一次。

邓老师这里的代码会比较复杂,是基于双向链表实现的。这里我们只需要理解算法思想。

列表的排序算法, 对于起始于位置 p 的 n 个元素的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#define ListNodePosi(T) ListNode<T>* //列表节点位置

template <typename T> //列表的选择排序算法:对起始于位置p的n个元素排序

void List<T>::selectionSort ( ListNodePosi(T) p, int n ) { //valid(p) && rank(p) + n <= size

ListNodePosi(T) head = p->pred; ListNodePosi(T) tail = p;

for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail)

while ( 1 < n ) { //在至少还剩两个节点之前,在待排序区间内

ListNodePosi(T) max = selectMax ( head->succ, n ); //找出最大者(歧义时后者优先)

insertB ( tail, remove ( max ) ); //将其移至无序区间末尾(作为有序区间新的首元素)

tail = tail->pred; n--;

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template <typename T> //从起始于位置p的n个元素中选出最大者

ListNodePosi(T) List<T>::selectMax ( ListNodePosi(T) p, int n ) {

ListNodePosi(T) max = p; //最大者暂定为首节点p

for ( ListNodePosi(T) cur = p; 1 < n; n-- ) //从首节点p出发,将后续节点逐一与max比较

if ( !lt ( ( cur = cur->succ )->data, max->data ) ) //若当前元素不小于max,则

max = cur; //更新最大元素位置记录

return max; //返回最大节点位置

}

插入排序

归并排序

对列表的归并排序,相比向量要更复杂些,主要在怎么找到中间点

  • 归并排序的整体思想

  • 找到一个链表的中间节点的方法

  • 合并两个已排好序的链表为一个新的有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution {

public:

ListNode* getMid(ListNode* head)

{

if (!head) return NULL;

if (!head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while(fast && fast->next)

{

slow = slow->next;

fast = fast->next->next;

}

return slow;

}



ListNode* mergeLists(ListNode* l1, ListNode* l2)

{

if (l1 == NULL) return l2;

if (l2 == NULL) return l1;

ListNode dummy(-1);

ListNode *tail = &dummy;



while(l1 && l2)

{

if (l1->val < l2->val)

{

tail->next = l1;

tail = tail->next;

l1 = l1->next;

}

else

{

tail->next = l2;

tail = tail->next;

l2 = l2->next;

}

}

if (l1) tail->next = l1;

if (l2) tail->next = l2;

return dummy.next;

}





ListNode* sortList(ListNode* head)

{

if (!head) return NULL;

if (head->next==NULL) return head;

// 找到中间点

ListNode *mid = getMid(head);

// 将链表分成两个子链表

ListNode *nextPart = NULL;

if (mid)

{

nextPart = mid->next;

mid->next = NULL;

}

return mergeLists(sortList(head), sortList(nextPart));

}

};

作者

Xie Pan

发布于

2018-12-21

更新于

2021-06-29

许可协议

评论