数据结构和算法（2）：向量

抽象数据类型

数组到向量

C/C++ 中，数组A[]中的元素与[0,n)内的编号一一对应，A[0],A[1],...,A[n-1]；反之，每个元素均由（非负）编号唯一指代，并可直接访问A[i] 的物理地址 = A+i × s，s 为单个元素占用的空间量，所以也叫作线性数组。

向量是数组的抽象与泛化，由一组元素按线性次数封装而成。各元素与[0,n)内的秩（rank）一一对应。
元素的类型不限于基本类型；
操作、管理维护更加简化、统一与安全；
可更为便捷地参与复杂数据结构的定制与实现

Vector 模板类

using Rank = unsigned int; //秩
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）
template <typename T> class Vector { //向量模板类
private:Rank_size;int_capacity;T* _elem;//规模、容量、数据区
protected:
	/.../
public:
	//构造函数
	Vector ( Rank c = DEFAULT_CAPACITY, Rank s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v
	{ _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
	Vector ( T const* A, Rank n ) { copyFrom ( A, 0, n ); } //数组整体复制
	Vector ( T const* A, Rank lo, Rank hi ) { copyFrom ( A, lo, hi ); } //区间
	Vector ( Vector<T> const& V ) { copyFrom ( V._elem, 0, V._size ); } //向量整体复制
	Vector ( Vector<T> const& V, Rank lo, Rank hi ) { copyFrom ( V._elem, lo, hi ); } //区间
	// 析构函数
	~Vector() { delete [] _elem; } //释放内部空间
}; //Vector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

可扩充向量

静态空间管理

开辟内部数组_elem[]并使用一段地址连续的物理空间
_capacity ：总容量
_size：当前的实际规模n

若采用静态空间管理策略，容量_capacity固定，则有明显的不足
1.上溢( overf1ow ) : _elem[]不足以存放所有元素
尽管此时系统仍有足够的空间
2.下溢( underflow ) : _elem[]中的元素寥寥无几
装填因子(load factor) $\lambda =\_size/\_capacity<<50\%$

更糟糕的是，一般的应用环境中难以准确预测空间的需求量。

动态空间管理

在即将发生上溢时，适当地扩大内部数组的容量

template <typename T>
void Vector<T>::expand() { //向量空间不足时扩容
	if(_size < _capacity) return; //尚未满员时，不必扩容
	_capacity = max(_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; //释放原空间
}
1
2
3
4
5
6
7
8
9

得益于向量的封装，尽管扩容之后数据区的物理地址有所改变，却不致出现野指针。

容量加倍策略在时间复杂度上总体优于容量递增策略。

平均分析 vs 分摊分析

平均复杂度或期望复杂度(average/expected complexity)
根据数据结构各种操作出现概率的分布，将对应的成本加权平均
各种可能的操作，作为独立事件分别考查
割裂了操作之间的相关性和连贯性
往往不能准确地评判数据结构和算法的真实性能

分摊复杂度(amortized complexity)
对数据结构连续地实施足够多次操作，所需总体成本分摊至单次操作
从实际可行的角度，对一系列操作做整体的考量
更加忠实地刻画了可能出现的操作序列
可以更为精准地评判数据结构和算法的真实性能

分摊复杂度和平均复杂度的结果并没有必然联系。

无序向量

元素访问

通过V.get(r)和V.put(r)接口，可以对元素进行读写。
可以重载下标操作符，增加其便捷性：

template<typename T>	//0 <= _size
T & Vector<T>::operator[](Rank(r)) const {return _elem[r];}
1
2

此后，对外的V[r]即对应内部的V._elem[r]可以使用下标进行操作：

//右值
T x = V[r] + U[s] + W[t];
//左值
V[r] = T(2*x + 3);
1
2
3
4

插入

template <typename T> //将e插入至[r]
Rank Vector<T>::insert ( Rank r, T const& e ) { //0 <= r <= size
	expand(); //如必要，先扩容
	for ( Rank i = _size; r < i; i-- ) //自后向前，后继元素
		_elem[i] = _elem[i-1]; //顺次后移一个单元
	_elem[r] = e; _size++; //置入新元素并更新容量
	return r; //返回秩
}
1
2
3
4
5
6
7
8

区间删除

template <typename T> int Vector<T>::remove( Rank lo, Rank hi ) { //0 <= lo <= hi <= n
	if ( lo == hi ) return 0; //出于效率考虑，单独处理退化情况
	while ( hi < _size ) _elem[lo++] = _elem[hi++]; //后缀[hi, _size)顺次前移 hi-lo 位
	_size = lo; shrink(); //更新规模，lo=_size之后的内容无需清零；如必要，则缩容
	//若有必要，则缩容
	return hi-lo;//返回被删除元素的数目
}
1
2
3
4
5
6
7

单元素删除

可以视作区间删除的特例：[r] = [r,r+1)

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; //返回被删除元素
}
1
2
3
4
5

查找

template <typename T> //在无序向量中顺序查找e：成功则返回最靠后的出现位置，否则返回lo-1
Rank Vector<T>::find ( T const& e, Rank lo, Rank hi ) const { //0 <= lo < hi <= _size
   while ( ( lo < hi-- ) && ( e != _elem[hi] ) ); //从后向前，顺序查找
   return hi; //若hi < lo，则意味着失败；否则hi即命中元素的秩
}
1
2
3
4
5

输入敏感：最好：$\mathcal{O}(1)$ ； 最差：$\mathcal{O}(n)$

实例：去重（删除重复元素）

template <typename T> Rank Vector<T>::dedup() { //删除无序向量中重复元素（高效版）
   Rank oldSize = _size; //记录原规模
   for ( Rank i = 1; i < _size; ) //自前向后逐个考查_elem[1,_size)
      if ( -1 == find(_elem[i], 0, i) ) //在前缀[0,i)中寻找与[i]雷同者（至多一个），O(i)
         i++; //若无雷同，则继续考查其后继
      else
         remove(i); //否则删除[i]，O(_size-i)
	return oldSize - _size; //被删除元素总数
}
1
2
3
4
5
6
7
8
9

每轮迭代中 find() 和 remove（累计耗费线性时间，总体为 $\mathcal{O}(n^2)$ ）

有序向量：唯一化

有序/无序序列中，任意/总有一对相邻元素顺序/逆序因此，相邻逆序对的数目，可用以度量向量的逆序程度。

实例：有序向量去重

观察︰在有序向量中，重复的元素必然相互紧邻构成一个区间。因此，每一区间只需保留单个元素即可

低效算法

template <typename T> Rank Vector<T>::uniquify() { //有序向量重复元素剔除算法（低效版）
	Rank oldSize = _size, i = 1; //当前比对元素的秩，起始于首元素
	while ( i < _size ) //从前向后，逐一比对各对相邻元素
		_elem[i - 1] == _elem[i] ? remove ( i ) : i++; //若雷同，则删除后者；否则，转至后一元素
	return oldSize - _size; //向量规模变化量，即被删除元素总数
}
1
2
3
4
5
6

效率低，运行时间主要取决于 while 循环，次数共计：_size - 1 = n -1
最坏： $\mathcal{O}(n^2)$

高效算法
反思:低效的根源狂于，同一元素可作为被删除元素的后继多次前移
启示︰若能以重复区间为单位，成批删除雷同元素，性能必将改进

template <typename T> Rank Vector<T>::uniquify() { //有序向量重复元素剔除算法（高效版）
  Rank i = 0, j = 0; //各对互异“相邻”元素的秩
  while ( ++j < _size ) //逐一扫描，直至末元素
     if ( _elem[i] != _elem[j] ) //跳过雷同者
        _elem[++i] = _elem[j]; //发现不同元素时，向前移至紧邻于前者右侧
  _size = ++i; shrink(); //直接截除尾部多余元素
  return j - i; //向量规模变化量，即被删除元素总数
}
1
2
3
4
5
6
7
8

共计 n - 1 次迭代，每次常数时间，累计 $\mathcal{O}(n)$ 时间。

有序向量：二分查找（A）

//二分查找算法（版本A)︰在有序向量的区间[lo，hi)内查找元素e,0 <= lo <= hi <= _size
template <typename T> static Rank binSearch( T* S, T const& e， Rank lo，Rank hi ) {
	while ( lo < hi ) {	//每步迭代可能要做两次比较判断，有三个分支
	Rank mi = ( lo + hi ) >>1;	//以中点为轴点(区间宽度折半，等效于其数值表示的右移一位)
	if( e < s[mi] ) hi = mi;	//深入前半	段[ 1o， mi)继续查找
	else if ( S[mi] < e ) lo = mi + 1;	//深入后半段(mi，hi)继续查找
	else
		return mi; 	//在mi处命中
	}	//成功查找可以提前终止
	return -1;	//查找失败
}	//有多个命中元素时，不能保证返回秩最大者;查找失败时，简单地返回-1，而不能指示失败的位置
1
2
3
4
5
6
7
8
9
10
11

转向左、右分支前的关键码比较次数不等，而递归深度却相同

有序向量：Fib 查找

若能通过递归深度的不均衡，对转向成本的不均衡进行补偿平均查找长度应能进一步缩短…

#include "fibonacci/Fib.h" //引入Fib数列类
//Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template <typename T> static Rank fibSearch( T* S, T const& e, Rank lo, Rank hi ) {
   //用O(log_phi(n = hi - lo)时间创建Fib数列
   for ( Fib fib( hi - lo ); lo < hi; ) { //Fib制表备查；此后每步迭代仅一次比较、两个分支
      while ( hi - lo < fib.get() ) fib.prev(); //自后向前顺序查找（分摊O(1)）
      Rank mi = lo + fib.get() - 1; //确定形如Fib(k)-1的轴点
      if      ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找
      else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
      else                  return mi; //在mi处命中
   } //一旦找到，随即终止
   return -1; //查找失败
} //有多个命中元素时，不能保证返回秩最大者；失败时，简单地返回-1，而不能指示失败的位置
1
2
3
4
5
6
7
8
9
10
11
12
13

通用策略：对于任何的 $A[0，n)$，总是选取 $A[\lambda n]$ 作为轴点，$0\le \lambda <1$
在$[0，1)$内，$\lambda$ 如何取值才能达到最优 ? 设平均查找长度为 $\alpha (\lambda )\cdot lo{g}_{2}n$，何时 $\alpha (\lambda )$ 最小?
二分查找：$\lambda =0.5$ Fib 查找：$\mathrm{0.6180339...}$

有序向量：二分查找（B）

二分查找中左、右分支转向代价不平衡的问题，也可直接解决。将中间点包含在了右边。

//二分查找算法（版本B）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo < hi <= _size
template <typename T> static Rank binSearch( T* S, T const& e, Rank lo, Rank hi ) {
	while ( 1 < hi - lo ) { //每步迭代仅需做一次比较判断，有两个分支；成功查找不能提前终止
      Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度折半，等效于其数值表示的右移一位）
      ( e < S[mi] ) ? hi = mi : lo = mi; //经比较后确定深入[lo, mi)或[mi, hi)
   } //出口时hi = lo + 1，查找区间仅含一个元素A[lo]
   return e < S[lo] ? lo - 1 : lo; //返回位置，总是不超过e的最大者
} //有多个命中元素时，返回秩最大者；查找失败时，简单地返回-1，而不能指示失败的位置
1
2
3
4
5
6
7
8

有序向量：二分查找（C）

//二分查找算法（版本C）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template <typename T> static Rank binSearch( T* S, T const& e, Rank lo, Rank hi ) {
  while ( lo < hi ) { //每步迭代仅需做一次比较判断，有两个分支
     Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度折半，等效于其数值表示的右移一位）
     ( e < S[mi] ) ? hi = mi : lo = mi + 1; //经比较后确定深入[lo, mi)或(mi, hi)
  } //成功查找不能提前终止
  return lo - 1; //至此，[lo]为大于e的最小者，故[lo-1]即为不大于e的最大者
} //有多个命中元素时，返回最靠后者；查找失败时，返回失败的位置
1
2
3
4
5
6
7
8

与版本B的差异
1)待查找区间宽度缩短至e而非1时，算法才结束
2)转入右侧子向量时，左边界取作mi + 1而非mi——A[mi]会被遗漏?
3)无论成功与否，返回的秩严格符合接口的语义约定…

冒泡排序

向量元素若有序排列，计算效率将大大提升

template <typename T> void vector<T>::bubbleSort(Rank lo，Rank h1)
{ 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; l/返回有序标志
}//乱序限于[0，√n)时，仍需O(n^{3/2})时间——按理，O(n)应已足矣
1
2
3
4
5
6
7
8
9
10
11
12

改进：

template <typename T> void vector<1>::bubbleSort(Rank lo，Rank h1)
{ while (lo < (hi = bubble(lo，hi)));}//逐趟扫描交换，直至全序
template <typename T> Rank Vector<T> : :bubble(Rank lo，Rank hi) {
	Rank last = lo;//最右侧的逆序对初始化为[lo - 1，1o]
	while (++lo < hi)//自左向右，逐一检查各对相邻元素
		if(_elem[lo - 1] > _elem[lo])//若逆序,则
			last = lo;//更新最右侧逆序对位置记录，并
			swap(_elem[lo - 1]，_elem[lo]);//交换
		}
	return last;//返回最右侧的逆序对位置
}//前一版本中的逻辑型标志sorted，改为秩last
1
2
3
4
5
6
7
8
9
10
11

三种冒泡排序算法效率相同，最好o(n)，最坏o(n^2)
在冒泡排序中，元素 a 和 b 的相对位置发生变化，只有一种可能；
1.经分别与其它元素的交换，二者相互接近直至相邻
2.在接下来一轮扫描交换中，二者因逆序而交换位置

归并排序

分治策略，向量与列表通用
序列一分为二$(\mathcal{O}(1))$，子序列递归排序$(2\times T(n/2))$，合并有序子序列$(\mathcal{O}(n))$
总体复杂度为 $(\mathcal{O}(n\log n))$

template <typename T> //向量归并排序
void Vector<T>::mergeSort( Rank lo, Rank hi ) { // 0 <= lo < hi <= size
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   Rank mi = ( lo + hi ) / 2; //以中点为界
   mergeSort( lo, mi ); mergeSort( mi, hi ); //前缀、后缀分别排序
   merge( lo, mi, hi ); //归并
}

template <typename T> //对各自有序的[lo, mi)和[mi, hi)做归并
void Vector<T>::merge( Rank lo, Rank mi, Rank hi ) { // lo < mi < hi
   Rank i = 0; T* A = _elem + lo; //合并后的有序向量A[0, hi - lo) = _elem[lo, hi)
   Rank j = 0, 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]; //复制出A的前缀
   Rank k = 0, lc = hi - mi; T* C = _elem + mi; //后缀C[0, lc) = _elem[mi, hi)就地
   while ( ( j < lb ) && ( k < lc ) ) //反复地比较B、C的首元素
      A[i++] = ( B[j] <= C[k] ) ? B[j++] : C[k++]; //将更小者归入A中
   while ( j < lb ) //若C先耗尽，则
      A[i++] = B[j++]; //将B残余的后缀归入A中——若B先耗尽呢？
   delete[] B; //释放临时空间：mergeSort()过程中，如何避免此类反复的new/delete？
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法的运行时间主要在于 for 循环，merge() 总体迭代不超过 $\mathcal{O}(n)$ 次，累计只需线性时间。$T(n)=2T(n/2)+\mathcal{O}(n)$

位图

位图（Bitmap）是一种数据结构，用于表示一组位或二进制值的集合。在计算机科学中，位图通常用于存储和操作大量的二进制数据，其中每个位都表示某种状态或信息。
位图中的每个位（或者可以理解为数组的元素）代表一个元素是否存在于集合中。当元素存在时，对应位的值为1；不存在时，对应位的值为0。