邓公数据结构与算法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
#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
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
#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
#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
//加倍扩容
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
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
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
// 二分查找算法(版本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
// 二分查找算法(版本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
// 二分查找算法(版本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
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
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
// 改进后的冒泡排序
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
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
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
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 中元素始终较大。

课后习题