发表更新数据结构与算法32 分钟读完 (大约4803个字)

邓公数据结构与算法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 中元素始终较大。

课后习题

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

http://www.panxiaoxie.cn/2018/12/20/邓公数据结构与算法2-向量/

作者

Xie Pan

发布于

2018-12-20

更新于

2021-06-29

许可协议

#

评论

关注我

链接

分类

×