数据结构与算法分析

C++STL中的vector模板类非常好用，有效解决了数组大小固定的问题。

而vector本身是封装好的，一般使用时只需要知道vector提供的接口即可，而它的内部是怎样实现的一直没有去了解。

1.秩：一个元素的秩就是它的前驱元的个数（它的前面的元素的个数），各元素的秩互异。

通过秩（记为r）可以唯一确定向量中的一个元素，这是向量独有的元素访问方式，称为循秩访问。

2.向量中的元素：向量中的元素不必为基本类型，也不必是可以比较大小的数值型。

可以是更具一般性的某一类的对象。（在C++中可以理解为，向量的元素可以是一个结构体或者类）

3.向量支持的ADT接口

图片来源：《数据结构（C++语言版）第三版》邓俊辉

了解过C++vector就知道，上面的大部分接口，C++提供的模板类都是支持的。

4.向量内部结构的本质

描述：向量结构在内部维护一个元素类型为T的私有数组，其容量由私有变量capacity指示，其有效元素数量（即当前向量的实际规模）由变量size指示。

//注意区别capacity和size，capacity可以理解为一个水桶的容量，而size相当于装在水桶中的水的体积，所以恒有size<=capacity

意思是，在向量这个结构内部，系统创建了一个数组，这个数组的元素不必是基本类型（C++template实现），描述其大小的数值储存在私有变量capacity中。

数组的大小是固定的，而一直以来vector都是作为变长数组来使用的，所以向量结构的核心在于，能对数组进行扩容。

扩容的方法很简单，在向向量中添加元素时，将当前的size+1，与capacity进行比较，如果size+1<=capacity，那么该元素成功添加到向量中（水桶不满），

如果size+1>capacity，也就是即将发生数组越界时（水桶满了），向量将new一个容量更大的数组，将原来数组中的元素复制到新的更大的数组中去，然后销毁原数组，释放空间。

通俗一点讲就是，小水桶装满了，就买一个更大的水桶，把小水桶中的水倒进去，然后把小水桶扔了防止占空间。

这就是向量实现数组扩容的基本思路，然而，怎样扩容，扩容多大合适，是有讲究的。

5.构造与析构

默认构造方法：向量被系统创建，然后借助构造函数初始化。默认构造方法为，根据创建者指定的容量向系统申请储存空间，创建数组_elem[]。若容量没有指定，则使用容量默认值DEFAULT_CAPACITY。_size初始化为0。

重载构造函数：

基于复制的构造方法：

 1 //基于数组A的区间[lo,hi]构造
 2 template <typename T>
 3 void Vector<T>::copyFrom(T const*A, Rank lo, Rank hi)
 4 {
 5     //分配空间
 6     _elem = new T[_capacity = 2 * (hi - lo)];
 7     _size = 0;
 8     //逐一复制  
 9     while (lo < hi)
10         _elem[_size++] = A[lo++];
11 }

析构方法：析构函数不能重载

1 ~Vector(){delete []_elem;}

忽略分配和回收空间的时间，构造与析构的时间复杂度均为O(1)

6.动态空间管理

装填因子：向量实际规模与其内部数组容量的比值（size/capacity），它是衡量空间利用率的指标

静态空间管理：比如数组，数组在其生命周期内大小固定，一方面，数组容量过小，很容易出现溢出，而另一方面，数组容量过大，导致空间利用率低

动态空间管理的目的就是，使得空间既能足够大以致不会溢出，也不会太大使得空间浪费，归纳起来就是，使得装填因子始终在（0，1）这个区间上

向量扩容：

 1 template <typename T> void Vector<T>::expand()
 2 {
 3     //尚未满，不必扩容
 4     if(_size<_capacity)
 5         return;
 6     //不得低于最小容量
 7     if(_capacity<DEFAULT_CAPACITY)
 8         _capacity=DEFAULT_CAPACITY;
 9     T* oldElem=_elem;
10     //容量加倍
11     _elem=new T[_capacity<<1];
12     //复制原向量内容
13     for(int i=0;i<_size;i++)
14         _elem[i]=oldElem[i];
15     //释放原空间
16     delete [] oldElem;
17 }

这里选择容量加倍是很有讲究的，在这之前需要先了解分摊分析。

分摊分析：

对于一个操作的序列来讲，平摊分析得出的是在特定问题中这个序列下每个操作的平摊开销。一个操作序列中可能存在一、两个开销比较大的操作，在一般地分析下，如果割裂了各个操作的相关性或忽视问题的具体条件，那么操作序列的开销分析结果就可能会不够紧确，导致对于操作序列的性能做出不准确的判断。用平摊分析就可以得出更好的、更有实践指导意义的结果。因为这个操作序列中各个操作可能会是相互制约的，所以开销很大的那一两个操作，在操作序列总开销中的贡献也会被削弱和限制。所以最终会发现，对于序列来讲，每个操作平摊的开销是比较小的。
换句话说，对于一个操作序列来讲，平摊分析得出的是这个序列下每个操作的平摊开销。

每次扩容，系统都要将原向量中的元素进行复制，这需要花费额外的时间，那么，扩容一倍的策略时间复杂度即为O(2n)=O(n)，这种策略的效率貌似很低，但O(n)仅仅是相对单次扩容而言。可以知道，经过一次扩容后，至少要再经过n次操作，才需要再一次扩容，而随着向量规模逐渐增大，n也越来越大，那么需要进行扩容操作的概率也就越来越小，平均而言，加倍扩容的成本并不很高。

缩容：一般情况下，下溢并不常见，需要用到缩容的场合很少，但不排除某些场合对空间利用率要求较高

 1 template <typename T> void Vector<T>::shrink()
 2 {
 3     if(_capacity<DEFAULT_CAPACITY<<1)
 4         return;
 5     if(_size<<2>_capacity)   //以25%为界
 6         return;
 7     T* oldElem=_elem;
 8     //容量减半
 9     _elem=new T[_capacity>>=1];
10     //复制原向量内容
11     for(int i=0;i<_size;i++)
12         _elem[i]=oldElem[i];
13     //释放原空间
14     delete [] oldElem;
15 }

这里选取25%为界，一旦空间利用率降至25%以下，将执行缩容操作。

实际应用中，为避免频繁缩容，可使用更低阀值，取0时即为禁止缩容。

7.引用元素

向量ADT为我们提供了get操作，实际应用中，可以像数组一样用下标运算符获取元素。

但向量中的元素并不一定是基本类型，这时需要对下标运算符“[]”进行重载。

1 template <typename T> T& Vector<T>::operaator[](Rank r) const
2 {return _elem[r];}

8.向量置乱算法

1 template <typename T> void permute(Vector<T>& V)
2 {
3     for(int i=V.size();i>0;i--)
4         swap(V[i-1],V[rand()%i]);
5 }

应用于软件测试，仿真模拟等方面，保证测试的覆盖面和仿真的真实性

封装置乱算法

1 template <typename T> void Vector<T>::unsort(Rank lo, Rank hi)
2 {
3     T* V = _elem + lo;
4     for (int i = V.size(); i > 0; i--)
5         swap(V[i - 1], V[rand() % i]);
6 }

这样封装以后，就可以对外提供一个置乱接口，可置乱任意区间[lo,hi]之间的元素

9.判等器和比较器

系统提供的比较符号包括“==”，“<=”，">="都是仅适用于数值类型的数据的，而向量的元素类型并不局限于基本类型，所以，要实现判等器和比较器，核心在于实现它们的通用性。

通常采用对比较操作进行封装形成比较器或在定义相应的数据类型时重载“==”，“>=”等运算符

10.查找

无序向量：

1 template <typename T>
2 Rank Vector<T>::find(T const& e,Rank lo,Rank hi)
3 {
4     //从前往后，顺序查找
5     while((lo<hi--)&&(e!=_elem[hi]));
6     return hi;
7 }

查找区间为[lo,hi]，时间最好为O(1)，最坏为O(n)，这种对于规模相同，内部组成不同的输入，渐进运行时间有本质区别的算法，叫作输入敏感的算法

有序向量：

相对于无序向量而言，有序向量的雷同元素集中在各个区间内且有序排列，由此特性，向量的查找算法可以得到优化

二分查找：

 1 template <typename T> static Rank binSearch(T* A,T const& e,Rank lo,Rank hi)
 2 {
 3     while(lo<hi)
 4     {
 5         //从中点二分
 6         Rank mi=(lo+hi)>>1;
 7         //查找前半段
 8         if(e<A[mi])
 9             hi=mi;
10         //查找后半段
11         if(e>A[mi])
12             lo=mi+1;
13         //中点命中
14         else
15             return mi;
16     }
17     //查找失败，向量中没有目标值
18     return -1;
19 }

注意，该算法不能保证返回目标元素的秩最大者

有效地查找区间以1/2的比例缩小，所以至多经过log2（hi-lo）次迭代后，算法必将终止，所以整体时间复杂度为O(logn)<O(n²)，显然优于上一种算法

查找长度：即查找过程中执行元素比较操作的次数，是衡量查找算法整体效率的标准

Fibonacci查找：

事实上，减治算法并不限定必须对半分，二分的点可以不为中点。Fibonacci查找就是以斐波那契数列为分割来减治的。

随着斐波那契数列项数的增加，前一项与后一项之比趋向于0.618（黄金分割）

 1 template <typename T> static Rank FibSearch(T* A,T const& e,Rank lo,Rank hi)
 2 {
 3     while(lo<hi)
 4     {
 5         while(lo<hi)
 6         {
 7             while(hi-lo<fib.get())
 8                 fib.prev();
 9             Rank mi=lo+fib.get()-1;
10             if(e<A[mi])
11                 hi=mi;
12             if(e>A[mi])
13                 lo=mi+1;
14             else
15                 return mi;
16         }
17     }
18     //查找失败，向量中没有目标值
19     return -1;
20 }

二分查找优化：

优化比较次数

 1 template <typename T> static Rank binSearch(T* A,T const& e,Rank lo,Rank hi)
 2 {
 3     while(1<hi-lo)
 4     {
 5         Rank mi=(lo+hi)>>1;
 6         //仅需经过一次比较即可更新查找边界
 7         (e<A[mi])?hi=mi:lo=mi;
 8     }
 9     return (e==A[lo])?lo:-1;
10 }

思路与原二分查找思路类似，区别在于在分割点处比较的次数。原版本的二分查找最多需要比较三次，而优化后仅需比较一次。

11.插入

 1 template <typename T>
 2 Rank Vector<T>::insert(Rank r,T const& e)
 3 {
 4     expand();
 5     for(int i=_size;i>r;i--)
 6         _elem[i]=_elem[i-1];
 7     _elem[r]=e;
 8     _size++;
 9     return r;;
10 }

自后向前搬迁，否则会导致一部分数据被覆盖。

时间复杂度为O(_size)=O(n)

12.删除

向量ADT提供了两个remove接口，分别是remove(lo,hi)和remove(r)

前者删除指定区间内的元素，后者删除指定秩的单个元素

一般思路，前者可以通过反复调用后者来实现，其实不然。

删除单个元素时，必须将该元素的所有后继全部向前搬迁一个单元，那么对区间(lo,hi)内的所有元素调用remove(r)时，意味着该区间内的每个元素的所有后继元素都将要向前移动一格，若后继元素有m个，则累计需要移动m*（hi-lo）次，无疑，这种方法是不可行的。

实际思路相反，将删除单个元素看作是删除区间元素的特殊情况

区间删除：

 1 template <typename T> int Vector<T>::remove(Rank lo,Rank hi)
 2 {
 3     if(lo==hi)
 4         return 0;
 5     while(hi<_size)
 6         _elem[lo++]=_elem[hi++];
 7     _size=lo;
 8     //如有必要，缩容
 9     shrink();
10     return hi-lo;
11 }

单个元素删除：

1 template <typename T> int Vector<T>::remove(Rank r)
2 {
3     //备份删除元素
4     T e=_elem;
5     //调用区间删除，等价于删除区间[r,r+1)上的元素
6     remove(r,r+1);
7     //返回删除的元素
8     return e;
9 }

13.去重

无序向量：

1 template <typename T> int Vector<T>::deduplicate()
2 {
3     int oldSize = _size;
4     Rank i = 1;
5     while (i < _size)
6         (find(_elem[i], 0, 1) < 0) ? i++ : remove(i);
7     retrun oldSize - _size;
8 }

在当前元素的前缀中寻找相同的元素，如找到，删除该元素，如没有找到，转到该元素的后继。

时间复杂度O(n²)

有序向量：

有序向量相比于无序向量的特点是，它的相同元素都是集中在一起的

一般思路，检查每个元素两边的元素是否相同，相同删除，不同转到下一个：

1 template <typename T> int Vector<T>::uniquify()
2 {
3     int oldSize=_size;
4     int i=1;
5     while(i<_size)
6         _elem[i-1]==_elem[i]?remove(i):i++;
7     return oldSize-_size;
8 }

然而分析时间复杂度可以得知，该算法的时间复杂度为O(n²)，和无序向量的去重算法没有区别

优化思路：以上算法的主要开销是调用remove(r)的次数太多，由前面可知，remove(lo,hi)的效率更高，那么办法就是，把重复的元素集中到一个区间里，一次性删除

 1 template <typename T> int Vector<T>::uniquify()
 2 {
 3     Rnak i=0,j=0;
 4     while(++j<_size)
 5         //跳过雷同的元素
 6         if(_elem[i]!=_elem[j])
 7         //发现不同元素时，向前移至紧邻于前者右侧
 8             _elem[i]=_elem[j];
 9     _size=++i;
10     //将末尾多余元素直接截除
11     shrink();
12     return j-i;
13 }

复杂度为O(n)

14.遍历

函数指针：

通过函数指针机制，只读或局部修改向量

1 template <typename T> void Vector<T>::traverse(void(*visit)(T&))
2 {
3     for(int i=0;i<_size;i++)
4         visit(_elem[i]);
5 }

函数对象：

通过重载运算符“()”来遍历向量并实现相关操作，功能更多，适用范围更广

1 template <typename T> template <typename VST>
2 void Vector<T>::traverse(VST& visit)
3 {
4     for(int i=0;i<_size;i++)
5         visit(_elem[i]);
6 }

15.排序

归并排序，略。

参考资料：《数据结构（C++语言版）》邓俊辉