邓公数据结构与算法5-树

树:

  • 无环连通图

  • 极小连通图

  • 极大无环图

任一节点 v 与根节点 r 存在唯一的路径

path(v, r) = path( r)

树的表示

二叉树

二叉树的实现

先序遍历

中序遍历

层次遍历

重构

邓公数据结构与算法4-栈和队列

栈和队列 都是线性结构的特例,因此其实现都可以用 向量或列表 来实现。

STL 中 stack 的接口使用

栈的使用

栈与递归

递归算法所需的空间量,主要决定于最大递归深度。在达到这一深度的时刻,同时活跃的递归实例最多。

那么操作系统是如何实现函数(递归)调用的呢?如何同时记录调用与被调用函数(递归)实例之间的关系?如何实现函数(递归)调用的返回?又是如何维护同时活跃的所有函数(递归)实例的?

这些问题,都归结于栈。[课本 88 页]

场景一:逆序输出

逆序输出:conversion, 输出次序与处理过程颠倒,递归深度和输出长度不易预知。

进制转换

场景二:递归嵌套

具有自相似性的问题多可嵌套的递归描述,但因分支位置和嵌套深度并不固定,其递归算法的复杂度不易控制。栈结构及其操作天然的具有递归嵌套性,故可以高效的解决这类问题。

括号匹配

课本[92页]

算法其实很简单,主要是思考的过程。使用减治 和 分治 都不能解决这个问题。

从大规模问题到小规模问题并不完全等效。也就是分成子问题之后,不满足条件的情况下,合成大问题却可以满足情况。

用 栈 真的太合适了。而且可以推广到多种括号的情况。

栈混洗

借助一个中间 栈, 将 栈A 的数转移到 栈B 中去。称作 栈混洗(stack permutation).

在 pytorch 中根据 index 进行重新排列 permutation,实际上也是用的 栈 对吧? index_select

n 个数的栈混洗的总数, 恰好是著名的 catalan 数

$$\dfrac{2n!}{(n+1)!n!}$$

怎么甄别出哪些不是栈混洗的序列呢?

这里有一个禁止的情况出现。对于任何三个互异的数

$1\le i < i < j < k \le n$ 出现 $k…,i,…,j$ 则必非为栈混洗。

怎么判断一个序列 B 是否是另一个序列 A 的 栈混洗? 通过 栈 能实现,线性复杂度的算法。

延时

队列

邓公数据结构与算法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));

}

};

邓公数据结构与算法2-向量

这章以向量为例,讲解了如何写接口并实现。

接口与实现

Abstract Data Type vs. Data Structure

抽象数据类型 = 数据类型 + 定义在该模型上的一些列操作

  • 抽象定义, 操作和定义

  • 不考虑时间复杂度,不涉及数据的存储方式

数据结构 = 基于某种特定的语言,实现 ADT 的一整套算法。

  • 与复杂度密切相关

  • 要考虑数据的具体存储机制

向量

向量就是抽象数据类型:从数组到向量,循秩访问。

接下来的部分,通过模板类来实现 向量 ADT 接口

  • size()

  • get(r )

  • put(r, e) 用e替换秩为 r 元素的数值

  • insert(r, e) e作为秩为r元素插入,原后继依次移动

  • remove(r) 删除秩为 r 的元素,返回该元素原值

  • disordered() 判断所有元素是否已按非降序排列

  • sort() 调整各元素的位置,使之按非降序排列

  • find(e) 查找元素 e

  • search(e) 查找e,返回不大于e且秩最大的元素 仅适用于有序向量

  • deduplicate(),uniquify() 剔除重复元素

  • traverse() 遍历向量并统一处理所有元素

向量模板类定义

那么如何构造 向量 的模板类呢?

“myvector.h” 头文件,主要是对各种成员数据、成员函数的声明

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

#ifndef MYVECTOR_H_INCLUDED

#define MYVECTOR_H_INCLUDED



typedef int Rank; //秩

#define DEFAULT_CAPACITY 3 //默认的初始容量(实际应用中可设置为更大)



template <typename T> class MyVector{



protected: //只能被成员函数和友元访问



Rank _size; // 规模

int _capacity; //容量

T* _elem; // 数据区 _elem 是指针,所以可用数组形式来表示 vector_



void copyFrom(T const* A, Rank lo, Rank hi); //复制数据区间 A[lo, hi)

void expand(); //空间不足时扩容

void shrink(); //装填因子过小时压缩

bool bubble ( Rank lo, Rank hi ); //扫描交换

void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法

Rank max ( Rank lo, Rank hi ); //选取最大元素

void selectionSort ( Rank lo, Rank hi ); //选择排序算法

void merge ( Rank lo, Rank mi, Rank hi ); //归并算法

void mergeSort ( Rank lo, Rank hi ); //归并排序算法

Rank partition ( Rank lo, Rank hi ); //轴点构造算法

void quickSort ( Rank lo, Rank hi ); //快速排序算法

void heapSort ( Rank lo, Rank hi ); //堆排序(稍后结合完全堆讲解)



public: // 公有成员,提供给用户使用的



// 构造函数的几种形式

MyVector ( int c = DEFAULT_CAPACITY, int s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v

{

_elem = new T[_capacity = c];

for ( _size = 0; _size < s; _elem[_size++] = v ); //s<=c

}

MyVector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } // 数组 整体复制_

MyVector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //复制数组区间

MyVector ( MyVector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //复制 向量 整体_

MyVector ( MyVector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //复制向量区间_



// 析构函数

~MyVector() { delete [] _elem; } //释放内部空间_



// 只读访问接口 const 关键字

// 通常一个类如果想被广泛使用,其中不修改类数据成员的成员函数应该声明为 const 成员函数



Rank size() const { return _size; } //规模_

bool empty() const { return !_size; } //判空_

int disordered() const; //判断向量是否已排序

Rank find ( T const& e ) const { return find ( e, 0, _size ); } //无序向量整体查找_

Rank find ( T const& e, Rank lo, Rank hi ) const; //无序向量区间查找



Rank search ( T const& e ) const //有序向量整体查找

{ return ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }



// 可写访问接口_

T& operator[] ( Rank r ); //重载下标操作符,可以类似于数组形式引用各元素, 可以作为左值



const T& operator[] ( Rank r ) const; //仅限于做右值的重载版本,const T&



Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符,以便直接克隆向量



T remove ( Rank r ); //删除秩为r的元素



int remove ( Rank lo, Rank hi ); //删除秩在区间[lo, hi)之内的元素



Rank insert ( Rank r, T const& e ); //插入元素



Rank insert ( T const& e ) { return insert ( _size, e ); } //默认作为末元素插入_



void sort ( Rank lo, Rank hi ); //对[lo, hi)排序



void sort() { sort ( 0, _size ); } //整体排序_



void unsort ( Rank lo, Rank hi ); //对[lo, hi)置乱



void unsort() { unsort ( 0, _size ); } //整体置乱_



int deduplicate(); //无序去重



int uniquify(); //有序去重



// 遍历

void traverse ( void (* ) ( T& ) ); //遍历(使用函数指针,只读或局部性修改



template <typename VST> void traverse ( VST& ); //遍历(使用函数对象,可全局性修改)

};



#endif // MYVECTOR_H_INCLUDED

可以看到模板类定义主要是以下几个部分:

  • 内部函数

  • 构造函数

  • 析构函数

  • 只读接口

  • 可写接口

  • 遍历接口

模板类和函数定义

先复习一下模板函数和模板类的构造,关键字 typename

typename和class的区别

在c++ Template中很多地方都用到了typename与class这两个关键字,而且好像可以替换,是不是这两个关键字完全一样呢?

相信学习C++的人对class这个关键字都非常明白,class用于定义类,在模板引入c++后,最初定义模板的方法为: template<class T>……

在这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字,它的作用同

class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了:

template<typename T>……

在模板定义语法中关键字class与typename的作用完全一样。

typename难道仅仅在模板定义中起作用吗? 其实不是这样,typename另外一个作用为:使用嵌套依赖类型(nested depended name),如下所示:

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

class MyArray

{

public

typedef int LengthType;

.....

}



template<class T>

void MyMethod( T myarr )

{

typedef typename T::LengthType LengthType;

LengthType length = myarr.GetLength;

}

这个时候typename的作用就是告诉c++编译器,typename后面的字符串为一个类型名称,而不是成员函数或者成员变量,这个时候如果前面没有typename,编译器没有任何办法知道T::LengthType是一个类型还是一个成员名称(静态数据成员或者静态函数),所以编译不能够通过。

模板成员函数

定义成员函数的模板函数:

“#include “vector_functions.h””

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

#ifndef VECTOR_CONSTRUCTOR_BY_COPYING_H_INCLUDED

#define VECTOR_CONSTRUCTOR_BY_COPYING_H_INCLUDED



//基于复制的构造函数

template <typename T> // 元素类型

void Vector<T>::copyFrom(T const*A, Rank lo, Rank hi) //以数组区间A[lo, hi)为蓝本复制向量

{

_elem = new T[_capacity = 2 * ( hi - lo ) ]; _size = 0; //分配空间,规模清零

while ( lo < hi ) //A[lo, hi)内的元素逐一

_elem[_size++] = A[lo++]; //复制至_elem[0, hi - lo)

}



//遍历

template <typename T> void Vector<T>::traverse ( void ( *visit ) ( T& ) ) //借助函数指针机制

{ for ( int i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量



template <typename T> template <typename VST> //元素类型、操作器

void Vector<T>::traverse ( VST& visit ) //借助函数对象机制

{ for ( int i = 0; i < _size; i++ ) visit ( _elem[i] ); } //遍历向量



//删除

template <typename T> T Vector<T>::remove ( Rank r ) { //删除向量中秩为r的元素,0 <= r < size

T e = _elem[r]; //备份被删除元素

remove ( r, r + 1 ); //调用区间删除算法,等效于对区间[r, r + 1)的删除

return e; //返回被删除元素

}



template <typename T> int Vector<T>::remove ( Rank lo, Rank hi ) { //删除区间[lo, hi)

if ( lo == hi ) return 0; //出于效率考虑,单独处理退化情况,比如remove(0, 0)

while ( hi < _size )

_elem[lo++] = _elem[hi++]; //[hi, _size)顺次前移hi - lo个单元

_size = lo; //更新规模,直接丢弃尾部[lo, _size = hi)区间

return hi - lo; //返回被删除元素的数目

}





//冒泡排序

//....

#endif // VECTOR_CONSTRUCTOR_BY_COPYING_H_ INCLUDED

可以看到模板类和模板函数的定义,需要加上

template <typename T>…

通过主函数进行测试

“main.cpp”

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

#include <iostream>

using namespace std;



#include "myvector.h"

#include "vector_functions.h"



int main()

{

cout << "Hello world!" << endl;





Vector<int> myvector(10, 10, 0);

int res = myvector.remove(0);

cout << res << endl;

return 0;

}

所以模板类和模板函数的定义,以及使用大致就是这个样子。接下来,对类定义中的声明的成员函数进行定义。既然是作为模板类,当然函数的效率越高越好,所以会涉及到很多算法分析的内容~

可扩充向量:扩容 expand()

通过算法分析得:加倍扩容~

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

//加倍扩容

template <typename T> void Vector<T>::expand () // 向量不足时扩容

{

if (_size < _capacity) return; // 尚未满员,不需要扩容_

if ( _capacity < DEFAULT_CAPACITY ) _capacity = DEFAULT_CAPACITY; //容量不低于最小容量_

T* oldelem = _elem; // 重新申请地址

_elem = new T[_capacity << 1]; //容量加倍

for (int i=0; i<_size; i++)

_elem[i] = oldelem[i]; //复制原向量内容(T为基本类型,或已重载赋值操作符'=')_

delete [] oldElem; //释放原空间_

}

需要注意的是扩容时,是重新申请地址空间,保证连续?

为什么要使用加倍策略呢?

通过平摊法分析可得加倍扩容累计增容时间是 O(n).

元素访问

需要重载下标操作符 “[]”, 复习一波操作符重载

如果 T 不是内置数据类型,那么就需要对下标操作符进行重载。

1
2
3
4
5
6
7
8
9
10
11

template <typename T> T& Vector<T>::operator[] ( Rank r ) //重载下标操作符

{ return _elem[r]; } // assert: 0 <= r < _size



const template <typename T> T& Vector<T>::operator[] ( Rank r ) const //仅限于做右值

{ return _elem[r]; } // assert: 0 <= r < _size

插入 insert()

  • 主要是否需要扩容

  • 注意元素向后移动的顺序,自后向前

删除 remove()

  • 删除单个元素和删除区间

  • 删除区间时,需要注意删除顺序,从左到右逐个复制

有序向量的去重

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

template <typename T> int Vector<T>::uniquify()

{

Rank i = 0, j = 0; //各对互异“相邻”元素的秩

while(++j < _size){

if (_elem[j] != _elem[i])

_elem[++i] = _elem[j];

}

_size = ++i;

shrink();

return j-1; //被删除元素的总数



}

去重高效版的图解。回过头来看,实际上就是解决了一种问题,比如 5 这个元素不在是一步步向前,而是直接就到了最终的位置,这显然更高效。

有序向量的查找

减而治之:

  • fibdearch

  • binsearch

二分查找

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

// 二分查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size

template <typename T> static Rank binSearch ( T* A, T const& e, Rank lo, Rank hi ) {

while ( lo < hi ) { //每步迭代可能要做两次比较判断,有三个分支

Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移)

if ( e < A[mi] ) hi = mi; //深入前半段[lo, mi)继续查找

else if ( A[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找

else return mi; //在mi处命中

} //成功查找可以提前终止

return -1; //查找失败

}//有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置

复杂度是 1.5log(n).

fibonacci 查找

fibonacci 查找和 binary 查找本质上差不多,区别就在于 middle 的选取。在比对当前位置失败之后,我们需要比较查找元素与当前位置元素的大小,向左侧深入需要 +1, 向右侧深入需要 +2. 所以这就造成了一种不平衡。

通过公式证明,$\lambda$ 选在何处时,复杂度最小。

二分查找改进版

二分查找的改进版: 使得向左右两侧深入的代价平衡,不能及时命中轴点所在的元素。牺牲了最好情况,但整体性能更趋于稳定。

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

// 二分查找算法(版本B):在有序向量的区间[lo, hi)内查找元素e,0 <= lo < hi <= _size

template <typename T> static Rank binSearch(T* A, T const& e, Rank lo, Rank hi)

{

while (1 < hi-lo) //每步迭代仅需做一次比较判断,有两个分支;成功查找不能提前终止

{

Rank mi = (lo + hi) >> 1;

(e < A[mi]) ? (hi = mi) : (lo = mi); //经比较后确定深入[lo, mi)或[mi, hi)

} //出口时hi = lo + 1,查找区间仅含一个元素A[lo]

return ( e == A[lo] ) ? lo : -1 ; //查找成功时返回对应的秩;否则统一返回-1

} //有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置

二分查找最终版

但是,在这之前所有的 search() 算法都未严格满足定义的语义,也就是返回 不大于 e 的元素的最后一个元素的 秩。

  • 多个元素命中,必须返回 秩 最大者

  • 失败时,应返回小于 e 的最大者(含哨兵 [lo-1])

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

// 二分查找算法(版本C):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size

template <typename T> static Rank binSearch(T* A, T const& e, Rank lo, Rank hi)

{

while (lo < hi) //每步迭代仅需做一次比较判断,有两个分支

{

Rank mi = (lo + hi) >> 1;

(e < A[mi]) ? (hi=mi) : (lo = mi + 1); //经比较后确定深入[lo, mi)或(mi, hi)

} //成功查找不能提前终止

return --lo; //循环结束时,lo为大于e的元素的最小秩,故lo - 1即不大于e的元素的最大秩

} //有多个命中元素时,总能保证返回秩最大者;查找失败时,能够返回失败的位置

插值查找

Interpolation search

如果有数据的先验分布,比如是均匀分布的,那么可以根据先验知识有效的提高查找效率。

$$\dfrac{mi-lo}{hi-lo} = \dfrac{e-A[lo]}{A[hi]-A[lo]}$$

这样可以更快的接近所需查找的元素。但是在小范围内,却容易被恶性分布所干扰,比如不满足均匀分布的情况下。

最好的查找方式是:插值查找 -> 二分查找 -> 顺序查找

排序

前面的查找算法都是对应于有序向量的,所以我们需要用排序算法先把向量变得有序起来,这样才能更高效的 查找 或 去重。

冒泡排序

冒泡排序:从后向前逐渐有序

其改进

  • 改进一:如果在某一趟循环之后,已经完全有序了,后面的循环也就不需要了。所以需要设置设否有序的标志

  • 改进二: 如果数据只是在前缀的一小部分乱序,后缀很多一部分已经有序了。这个时候我们是否还需要亦步亦趋的从后往前一步步的有序呢? 所以可以在一趟交换走完之后,标记出交换的最后位置。然后只需要考虑前缀无序的部分即可。

改进一

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

template <typename T> //向量的起泡排序

void Vector<T>::bubbleSort ( Rank lo, Rank hi ) //assert: 0 <= lo < hi <= size

{ while ( !bubble ( lo, hi-- ) ); } //逐趟做扫描交换,直至全序



//一趟扫描交换

template <typename T> bool Vector<T>::bubble ( Rank lo, Rank hi ) {

bool sorted = true; //整体有序标志

while ( ++lo < hi ) //自左向右,逐一检查各对相邻元素

if ( _elem[lo - 1] > _elem[lo] ) { //若逆序,则_

sorted = false; //意味着尚未整体有序,并需要

swap ( _elem[lo - 1], _elem[lo] ); //通过交换使局部有序_

}

return sorted; //返回有序标志

}

自己动手实现一个整体的形式。。

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

template <typename T> void Vector<T>::my_bubbleSort(Rank lo, Rank hi)

{

while (lo < hi)

{

bool sorted = true;

Rank a = lo;

while ( ++a < hi) //自左向右,逐一检查各对相邻元素

{

if ( _elem[a - 1] > _elem[a] ) //若逆序,则_

{

sorted = false; //意味着尚未整体有序,并需要

swap ( _elem[a - 1], _elem[a] ); //通过交换使局部有序_

}

}

if (sorted == true) break;

hi--;

}

}

改进二

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

// 改进后的冒泡排序

template <typename T> //向量的起泡排序

void Vector<T>::bubbleSort ( Rank lo, Rank hi ) //assert: 0 <= lo < hi <= size

{

while ( lo < ( hi = bubble_fast(lo, hi) ) );

} //逐趟做扫描交换,直至全序





template <typename T> Rank Vector<T>::bubble_fast ( Rank lo, Rank hi ) { //一趟扫描交换

Rank last = lo; //最右侧的逆序对初始化为[lo - 1, lo]

while ( ++lo < hi ) //自左向右,逐一检查各对相邻元素

{

if ( _elem[lo - 1] > _elem[lo] ) { //若逆序,则

last = lo; //更新最右侧逆序对位置记录,并

swap ( _elem[lo - 1], _elem[lo] ); //通过交换使局部有序

}

}

return last; //返回最右侧的逆序对位置

}

归并排序

分治策略:

  • 一分为二

  • 子序列递归排序

  • 合并两个子序列

代码形式就是这样:

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

template <typename T> //向量归并排序

void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size

if ( hi - lo < 2 ) return; //单元素区间自然有序,否则...

int mi = ( lo + hi ) / 2; //以中点为界

mergeSort ( lo, mi ); mergeSort ( mi, hi ); //分别排序

merge ( lo, mi, hi ); //归并

}

前两个比较简单,那么第三步归并(merge)怎么实现呢? 下图是个实例图解

每次只比较首个元素。

接下来具体如何实现两个子序列的归并。

把两个子序列分别是 B,C. 合并后的序列是 A. 其中复制 [lo, mi) 到 B. C 子序列不需要复制。

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

template <typename T> //有序向量的归并

void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ) { //各自有序的子向量[lo, mi)和[mi, hi)

T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi)

// 复制前字向量

int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi)

for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制前子向量

// 后子向量 不需要复制

int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)

// B 和 C 中较小者续至A末尾

for ( Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc ); ) { //B[j]和C[k]中的小者续至A末尾

if ( ( j < lb ) && ( ! ( k < lc ) || ( B[j] <= C[k] ) ) ) A[i++] = B[j++];

if ( ( k < lc ) && ( ! ( j < lb ) || ( C[k] < B[j] ) ) ) A[i++] = C[k++];

}

delete [] B; //释放临时空间B

}//归并后得到完整的有序向量[lo, hi)

其中需要注意的是,将 B 和 C 接到 A 中时,跳出循环的条件是:

( j < lb ) || ( k < lc )

即两个子序列都越界了。

但其实 B 已经越界后,C 后面的并不需要一一复制到 A 中。所以这里也是可以改进的。

1
2
3
4
5
6
7
8
9

for ( Rank i = 0, j = 0, k = 0; j < lb ; ) { //B[j]和C[k]中的小者续至A末尾

if ( ( j < lb ) && ( B[j] <= C[k] ) ) A[i++] = B[j++];

if ( ! ( j < lb ) || ( C[k] < B[j] ) ) A[i++] = C[k++];

}

所以两个条件分别是:

  • B 还没越界,并且 B 中元素较小, 则 B -> A

  • B 已经越界,或者 B 中元素较大, 则 C -> A.

邓老师提供了一个思路,假设 B 已经越界,可以理解为在哨兵处有一个无穷大的元素,那么等同于 B 中元素始终较大。

课后习题

邓公数据结构与算法1-算法分析

  • 算法分析

  • 迭代、递归

  • 动态规划

算法分析

  • 级数的大 O 分析

  • 循环 vs 级数

非极端元素+冒泡排序

算法分析:

通过挖掘算法中的不变性、单调性,进而证明正确性是算法分析的重要技巧。

迭代与递归

减而治之 (decrease and conquer)

求解一个大规模问题,可以将其划分为两个子问题,一个 naive,一个规模缩减。

算法分析:线性递归,使用递归跟踪,仅使用于简明的递归

example: 颠倒数组

任意给定数组 A[0, n), 将其中的子区间 A[lo, hi] 颠倒

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

void reverse (int* A, int lo, int hi)

{

if (lo < hi)

{

swap (A[lo], A[hi]);

reverse (A, lo++, hi--)

}

}

迭代:

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

void reverse (int* A, int lo, int hi)

{

while(lo < hi)

{

swap(A[lo--], A[hi++])

}

}

分而治之 (divide and conquer)

求解一个大规模问题,可以将其划分为两个子问题,规模大体相当。

分别求解子问题

由子问题的解,得到原问题的解。

Example: MAX2,二分递归

从数组区间 A[lo,hi] 中找出最大的两个整数。

迭代解法

遍历整个数组,分别与 x1, x2 比较。

每迭代一次,比较 1/2 次。O(2n-3).

递归+分治解法

分而治之:

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

void max2(int A[], int lo, int hi, int x1, int x2)

{

// 递归基, 总共只有 3个/4个 元素

if (lo + 2 == hi) {* ... * ; return;}

if (lo + 3 == hi) {* ... * ; return;}



// 递归过程,分为两组,两边至少2个元素

int mi = (lo + hi)/2;



// 递归

int x1L, x2L;

max2(A, lo, mi, x1L, x2L);

int x1R, x2R;

max2(A, mi, hi, x1R, x2R);



// 每个递归实例所需操作

if (A[x1L] > A[x1R])

{

x1 = x1L;

x2 = (A[x2L] > A[x1R]) ? x2L : x1R;

}

else

{

x1 = x1R;

x2 = (A[x1L] > A[x2R]) ? x1L : x2R;

}

}

动态规划

记忆法:example Fabonacci

$$fib(n)=fib(n-1)+fib(n-2)$$

1
2
3
4
5
6
7
8
9

int fib(n)

{

return (2 > n) ? n : fib(n-1) + fib(n-2);

}

速度很慢很慢! 因为大量的递归实例被重复的调用。

解决方法:

  • 记忆,通过制表,避免重复调用

  • 动态规划:颠倒计算方向,自顶而下递归,转换为自底而上迭代

这个可以类比上台阶,每一步可以是 1 或 2 级台阶。

那么走到第 n 级台阶的方式是 第 n-1 阶 和 第n-2 阶的方式之和。

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

f = 1; g = 0;

while( 0 < n-- )

{

g = g + f;

f = g - f;

}

return g;

不断的从下而上的更新 g, f.

example: LCS (longest common sequence)

题目详情(子序列不同于子串,子序列可以是不连续的):

思考:从递归的角度去想,缩小规模无非是 分而治之 和 减而治之。

将规模缩小,A[0, n], B[0, m], LCS[A, B] 只有三种情况:

  • n=-1 或 m=-1, 则为空

  • A[n] = B[m] = “X”, 减而治之,同时缩小两个字串 LCS(A[0, n-1], B[0, m-1]) + “X”

  • $A[n] \ne B[m]$, 分而治之,LCS(A[0, n-1], B[0,m]) 和 LCS(A[0, n],B[0, m-1]) 中的较大值。

分析算法的可行性:

解决这种递归实例反复调用的方法:

  • 将所有子问题列成一张表

  • 颠倒计算方向,从 LCS(A[0], B[0]) 依次计算所有项。

从上图可以很清楚的明白制表的过程,每一个递归实例都可能被反复的经过。

比如: $A[n] \ne B[m]$. 那么分为两条路径: LCS(A[0, n-1], B[0,m]) 和 LCS(A[0, n],B[0, m-1]). 这两个的计算都需要计算 LCS(A[0, n-1], B[0,m-1]), 所以会造成重复计算。

所以如何制表呢?

递归公式, 用 $C[i,j]$ 来表示表格中 $[A_i, B_j]$ 处的长度。

具体填表的过程参考: https://blog.csdn.net/hrn1216/article/details/51534607

想清楚表格的物理意义: 可以看作某一个序列固定(列),然后逐渐增加另一个序列的长度(行),也就是逐渐填入行。

初始的情况也要想清楚,某一个序列长度为 0 时,公共序列肯定也为 0。

$m\times n$ 的表格

初始化, i=0 或 j=0

  • 先填入第一行,一个字符为 “3”,没有与之相同的字符,所有这一行都为 0.

  • 再填入第二行,填 [2,1] 处,都为3,C[2,1]=C[1,1]+1,然后按照递归公式走下去。

第二行其他空格 $A[i]\ne B[j]$,C[i,j]=max(C[i-1,j], C[i, j-1])

回溯构造 LCS

我们根据递归公式构建了上表,我们将从最后一个元素c[8][9]倒推出S1和S2的LCS。

  • C[8, 9] = 5,且$S_1[8] \ne S_2[9]$,所以倒推回去,C[8,9]的值来源于 C[8,8]的值(因为C[8,8] > c[7,9])

  • C[8, 8] = 5, 且 $S_1[8] = S_2[8]$, 所以倒推回去,C[8,8]的值来源于 C[7, 7]。

  • 可能会出现分歧的情况,$S_1[i] \ne S_2[j]$, 且 C[i-1,j]=C[i, j-1]. 这个时候选择一个方向。

两种结果:

分歧处选择另一个方向。

时间复杂度分析: 构建表格需要 O(mn), 回溯输出一个 LCS 需要 O(m+n)

leetcode 300. Longest increasing sequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Brute Force [Time Limit Exceeded]: recursive

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

int lenofLIS(vector<int> &nums, int prev, int curpos);



class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

return lenofLIS(nums, INT_MIN, 0);

}

};



int lenofLIS(vector<int> &nums, int prev, int curpos){

if (curpos == nums.size())

return 0;

int taken = 0;

if (nums[curpos] > prev)

taken = 1 + lenofLIS(nums, nums[curpos], curpos+1);

int notaken = lenofLIS(nums, prev, curpos+1);

return max(taken, notaken);

}

时间复杂度分析:

数组中每一个位置都可能出现或者不出现在 LIS 中,也就是说每一个递归实例的操作是 2,所以最终时间复杂度是 $O(2^n)$

空间复杂度分析:$O(n^2)$

Recursion with memorization [Memory Limit Exceeded]

解决上面这种递归实例反复调用的问题,通常有两种方法,在上面学习中也说到了。这里先采用记忆法,将所有子问题列成一张表。

Dynamic Programming [Accepted]

参考: https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

Optimal Substructure:

Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.

Then, L(i) can be recursively written as:

L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or

L(i) = 1, if no such j exists.

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.

Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

Following is a simple recursive implementation of the LIS problem. It follows the recursive structure discussed above.

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



int lenofLIS(vector<int> &nums, int prev, int curpos);



class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.size() == 0) return 0;

int dp[nums.size()];

dp[0] = 1;

for (int i=1; i< nums.size(); i++){

dp[i] = 1;

for (int j=0; j < i; j++){

if (nums[i] > nums[j] && dp[i] < dp[j]+1){

dp[i] = dp[j] + 1;

}

}

}

return *max_element(dp, dp+nums.size());

}

};

复杂度分析:

Time complexity: $O(n^2)$ Two loops of n.

Space complexity: $O(n)$ dp array size n is used.

总结

再回过头思考下动态规划的含义:

动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

对于 longest increasing subsequence 里面就存在最有子问题。对于一个序列,每增加一个元素,都可以看作一个子问题。

子问题的解是固定的,但是子问题与当前步的结合又是动态变化的。比如这里,当前 i 位置的值大于 j 的值和小于 j 的值的处理方式就不太一样。我们要做的就是找出这个规律 (递推公式),然后根据填写好的子问题的解的表格,进一步扩大问题规模。

所以如前面所说,动态规划:自顶而下递归,自底而上迭代。