向量与列表¶

主要的基础线性数据结构是向量与列表。在本合集中，向量指以数组方式组合并封装通用抽象接口的数据类型；列表指以链表方式组合并封装通用抽象接口的数据类型。

较为高级的数据结构——栈与队列建立在向量与列表的基础上。提供了一些受限制的操作接口。

线性数据结构¶

对于基础的线性数据结构，以下的接口可以视为通用：

操作	描述	通用性
`size()`	获取对象中元素的数目
`get()`	获取对象中某个元素的值
`set()`	修改对象中某个元素的值
`insert()`	向对象中的某个位置插入元素
`remove()`	移除对象中的某个元素
`traverse()`	遍历对象中的所有元素，并执行某操作
`find()`	在对象中查找某个元素的位置
`search()`	在有序的结构中查找某个元素的位置	要求有序
`sort()`	排序对象中的元素	要求重载`<`和`>`运算符

向量¶

在向量中，数据在内存中连续存储，即下标相邻的数据在内存中相邻。C/C++语言中的数组数据结构可以视为简单的向量。但数组不提供插入、删除等具体的操作接口，需要在程序代码中手动实现。将数组封装成类可以提供更多的操作接口，并且保证数据被合法地访问及修改。

向量是数组的抽象泛化、支持所有数组的功能，对于不同类型的元素提供了统一的操作接口。

C++提供了模板类的功能用来针对不同类型的元素提供相同的功能。对于某个ADT（以向量为例），其属性和接口的组织方式可遵循如下规则：

template <typename T> class Vector { //向量模板类
private: Rank _size; int _capacity; T* _elem; //规模、容量、数据区
protected:
/* ... 内部函数 */
public:
/* ... 构造函数 */
/* ... 析构函数 */
/* ... 只读接口 */
/* ... 可写接口 */
/* ... 遍历接口 */
};

通过对[]运算符进行重载，向量和列表支持数组风格的访问方式。

具体代码可以参见：

向量模板类声明

/******************************************************************************************
* Data Structures in C++
* ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
* Junhui DENG, deng@tsinghua.edu.cn
* Computer Science & Technology, Tsinghua University
* Copyright (c) 2003-2020. All rights reserved.
******************************************************************************************/

typedef int Rank; //秩
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）

template <typename T> class Vector { //向量模板类
protected:
   Rank _size; int _capacity;  T* _elem; //规模、容量、数据区
   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 ); //归并排序算法
   void heapSort ( Rank lo, Rank hi ); //堆排序（稍后结合完全堆讲解）
   Rank partition ( Rank lo, Rank hi ); //轴点构造算法
   void quickSort ( Rank lo, Rank hi ); //快速排序算法
   void shellSort ( Rank lo, Rank hi ); //希尔排序算法
public:
// 构造函数
   Vector ( 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
   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; } //释放内部空间
// 只读访问接口
   Rank size() const { return _size; } //规模
   bool empty() const { return !_size; } //判空
   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 ); }
   Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量区间查找
// 可写访问接口
   T& operator[] ( Rank r ); //重载下标操作符，可以类似于数组形式引用各元素
   const T& operator[] ( Rank r ) const; //仅限于做右值的重载版本
   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& ); //遍历（使用函数对象，可全局性修改）
}; //Vector

Reference

插入¶

向量的插入操作分为三步：

检查向量空间与输入下标的合法性，必要时改变向量的长度以容纳该元素
当输入下标不是向量的末尾时，移动向量中的元素，在对应位置腾出空间
将数据写入向量中

在长度为\(n\)的向量中的随机位置插入一个元素，改变向量长度所需的时间为\(\mathcal O(n)\)，移动元素以腾出空间的期望时间复杂度为\(\mathcal O(n)\)，写入数据的时间复杂度为\(\mathcal O(1)\)，总的时间复杂度为\(\mathcal O(n)\)

可扩充向量¶

向量的空间是有限的（即为向量本身的长度），若当向量空间不足时为向量重新分配一块更长的内存，将原数据复制到新的内存空间中以实现容量的扩增，则向量的空间可以近似视为无限。一般存在两种扩充算法：

当向量空间不足时，向量空间增加一个常量\(I\)
当向量空间不足时，向量空间乘以一定倍数\(k\)（通常情况下，\(k=2\)）

对于初始长度为\(0\)的向量，考察插入\(n\gg 2\)个元素下两种扩充算法的调用次数。递增策略下插入第\(mI+1, (m\in \mathbb N)\)个元素时需要进行扩充，总的调用次数为\(\frac{n}{I}\)，即\(\mathcal O(n)\)。倍增策略下插入第\(1, 2, 3, 5\dots 2^m+1, (m\in \mathbb N)\)个元素时需要进行扩充，总的调用次数为\(\mathcal O(\log n)\)。

复制数据的时间复杂度为\(\mathcal O(n)\)，因此递增策略每次扩容所需的时间为\(0, I, 2I, \dots\)，共需要扩容\(\frac nI\)次，扩容操作的总时间复杂度为\(\mathcal O(n^2)\)。每次插入操作分摊\(\mathcal O(n)\)。倍增策略每次扩容所需的时间为\(0, 1, 2, \dots n\)，共需要扩容\(\log n\)次。扩容操作的总时间复杂度为\(\mathcal O(n)\)，每次插入操作分摊\(\mathcal O(1)\)。

但倍增策略会导致更多的空间浪费，具体表现为向量的装载因子较低。插入大量元素时，倍增策略的装载因子只能保证\(> 50\)，而递增策略的装载因子可以保证在\(1\)左右。

删除¶

向量的删除操作主要为区间删除与单个元素的删除。其中后者可以视为前者的特殊情况。删除操作不需要执行额外的操作，只需要将删除区间后的元素向前移动，覆盖删除区间内的数据并更新操作结束后向量的长度即可。对于可扩充向量，删除后应对向量的装填因子进行检查，在必要时收缩向量。

如果多次调用删除单个元素的接口实现区间删除，由于每次删除都会导致一次数据的移动，总的时间复杂度为\(\mathcal O(n^2)\)

删除操作需要对删除位置的合法性进行检验。

查找¶

无序向量与有序向量的查找方法不同，所需的时间复杂度也不同。具体而言，有序向量的顺序提供了额外的信息，从而使得有序向量中的查找操作能够在\(\log n\)的时间复杂度内完成。

顺序查找¶

顺序查找操作假设向量中的元素类型定义了==运算符与!=运算符。

无序向量查找只需要从向量的开头依次对比向量中的元素与待查元素，当元素相同时返回即可。平均时间复杂度为\(\mathcal O(n)\)

二分查找¶

有序向量的查找操作假设向量中的元素类型定义类==运算符、!=运算符，因此有序向量可以按照无序向量的查找方法线性查找。若有序向量的元素类型定义了比较运算符<与>，则基于比较的二分查找可以将时间复杂度降至\(\mathcal O(\log n)\)。

减而治之是二分查找的核心思想。考虑更一般的通用算法，对于长度为\(n\)的数组，在\(\lambda \cdot n (0\leq \lambda\leq 1)\)处设为轴点。每次比较当前待查区间的轴点\(B\)与待查元素\(A\)。每一次对轴点的比较有三种可能的结果，假设向量中的元素按照升序排序，则：

\(A<B\)，表示待查元素只可能出现在轴点左侧，将待查区间缩小至左半部分，继续查找过程；
\(A=B\)，表示轴点处出现待查元素，直接返回中点的下标即可；
\(B<A\)，表示待查元素只可能出现在轴点右侧，将待查区间缩小至右半部分，继续查找过程。

对于二分查找，轴点为待查区间的中点，即\(\lambda = 0.5\)。

但该版本的二分查找有多种意外情形，如：

向量中找不到待查元素；
向量中待查元素存在多个。

此时函数返回的结果不一定唯一。约定二分查找算法返回不大于待查元素的最后一个元素的位置。

二分查找通过尽可能减少递归深度的方式减少时间复杂度，由此，每一次递归的不同分支应有相同的期望时间消耗（即转向成本）。此处的“二分”只是在数组区间的意义上二等分，若对于如下条件语句：

if (A > B)
    // statement
else if (A < B)
    // statement
else
    // statement

左右两个跳转位于不同的分支，需要进行比较的次数不同，因此所需的时间在严格意义上是不同的。可以通过改变轴点位置，将同一递归深度下比较的期望次数调整为相同，从而降低平均查找长度，在常系数程度上对算法进行优化。

设算法的时间复杂度为\(\alpha(\lambda) \log n\)，则：

左侧子问题消耗的时间等于判断消耗的时间及解决子问题消耗的时间，即：\(\lambda (1 + \alpha(\lambda) \log (\lambda n))\)
同理，右侧子问题的时间复杂度：\((1 - \lambda)(2+\alpha(\lambda)\log((1-\lambda)n))\)

得\(\alpha(\lambda) = \frac{\ln 2(\lambda - 2)}{\lambda \cdot\ln\lambda+(1-\lambda)\cdot\ln(1-\lambda)}\)

当\(\lambda=\frac{\sqrt 5-1}{2}\approx 0.618\)时，\(\alpha(\lambda)\)取最小值。

消除不对称的另一种方式是将三种比较结果变为两种，从而一次比较即可进行划分。记待查元素为\(A\)，轴点为\(B\)，则：

\(A<B\)：在轴点左侧的区间中查找
\(A\geq B\)：在轴点右侧 （包含轴点） 的区间中查找
当区间长度缩减为1时，表示查找过程结束。

二分查找的最终实现代码如下所示：

二分查找

/******************************************************************************************
* Data Structures in C++
* ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
* Junhui DENG, deng@tsinghua.edu.cn
* Computer Science & Technology, Tsinghua University
* Copyright (c) 2003-2020. All rights reserved.
******************************************************************************************/

// 二分查找算法（版本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的元素的最大秩
} //有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置

Reference

插值查找¶

假设区间内元素分布的规律已知，根据待查元素在该分布中的位置推断待查元素在区间的位置，以此确定划分的轴点位置。

假设区间内元素服从独立的平均分布，则每次查找平均使得区间缩减至原来的\(\sqrt n\)，平均时间复杂度为\(\mathcal O(\log\log n)\)。

去重¶

对于有序向量，去重操作可以在线性时间复杂度内完成，无序向量去重的时间复杂度为\(\mathcal O(n^2)\)

无序向量¶

使用指针标记无序向量已经完成去重的部分。对于无序向量未去重部分的每个元素，在未去重部分的后半部分中查找是否存在相同的元素，如果找到相同的元素则删除。完成查找后指针后移，将当前元素标记为已经完成去重。

有序向量¶

使用双指针算法，一个指针\(P\)标记已去重部分的结尾，另一个指针\(Q\)标记未去重部分的开头，初始情况下，\(P\)位于向量第一个元素且\(P+1=Q\)。当\(P\)指向的对象与\(Q\)指向的对象相同时，\(Q\)递增而\(P\)不移动，否则将\(Q\)处的元素复制到\(P+1\)处，两指针同时递增。

排序¶

此处介绍对向量的冒泡排序与归并排序，其他排序方式将在以后进行介绍。

冒泡排序¶

对于数列\(\{a_1, \cdots, a_n\}\)，若\(a_i>a_{i+1}\)，称\((a_i, a_{i+1})\)为一对逆序对。否则称为顺序对。则有序数列中不存在逆序对，无序数列中至少有一个逆序对。如果能够通过逆序对的交换使得数列中所有的逆序对转为顺序，即可完成对数组的排序。这是冒泡排序算法的核心思想。

设向量（数组）长度为\(n\)，待排序区段下标为\([0,n)\)

每一次扫描待排序区段中的相邻数据，若为逆序对则交换之

扫描结束后，数组中的最大元素移动到待排序区段末尾，即为已排序

一趟扫描后将待排序区段末尾元素划入已排序区段。

重复扫描，直到待排序区段长度缩小为0，即完成排序。

提前终止：若某次扫描过程中没有发生交换，说明待排序区段已经有序，可以提前结束算法

由于提前终止的存在，冒泡排序在最好情况下的时间复杂度为\(\mathcal O(n)\)，对应输入数据已经有序的情况。平均情况下冒泡排序的时间复杂度为\(\mathcal O(n^2)\)。

在冒泡排序中，相等的元素不被视为逆序对。如果将相等的元素视为逆序对，冒泡排序将失去稳定性。

归并排序¶

归并排序采用分而治之的方法对数组进行排序，其核心思想是递归。归并排序的算法过程主要分为三步：

“分”：将向量划分为两个（近似）等长的部分，时间复杂度为\(\mathcal O(1)\)
“治”：对两部分分别进行归并排序（已知长度为\(1\)的向量是有序向量），时间复杂度为\(2\times T(n/2)\)
“合”：将排序后的两部分合并为一个有序的整体，时间复杂度为\(\mathcal O(n)\)
算法整体的时间复杂度为\(\mathcal O(n\log n)\)，即使是在输入数组有序或接近有序的情况下。归并过程的空间复杂度为\(\mathcal O(n)\)

归并排序

template <typename T> void Vector<T>::mergeSort( Rank lo, Rank hi ) {
   if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
   int mi = (lo + hi) >> 1; //以中点为界
   mergeSort( lo, mi ); //对前半段排序
   mergeSort( mi, hi ); //对后半段排序
   merge( lo, mi, hi ); //归并
}

Reference

归并过程的核心思想即按顺序遍历两部分，将最小的写入目标数组中。

实际执行过程中，只需将数组的前半部分复制一份，然后进行合并即可。

若前半部分提前结束，由于目标数组的后半部分与原数组的后半部分重合，目标数组自动成为有序
若后半部分提前结束，将前半部分剩余的数据复制到目标数组后半部分对应位置即可

如下图：

若在归并过程中出现相同元素，左侧的元素优先归入目标数组，则可以保证归并排序的稳定性。

位图¶

位图是其中元素只能取0/1的向量。对于一个有限的整数集合\(U\)，位图构建了\(U\)的子集\(S\)，其中\(k\in S\)等价于位图中下标为\(k\)的元素的取值为\(1\)。位图提供了set()、get()、clear()三个接口，分别对应于位图的写入、查询、清除操作。

基于位运算的实现如下：

位图方法实现

bool test( int k ) { return M[ k >> 3 ] & ( 0x80 >> (k & 0x07) ); }
void set( int k ) { expand( k ); M[ k >> 3 ] |= ( 0x80 >> (k & 0x07) ); }
void clear( int k ) { expand( k ); M[ k >> 3 ] &= ~( 0x80 >> (k & 0x07) ); }

Reference

读取字节中的某个位可以使用&运算符实现，向字节中设置某个位为\(1\)可以使用|=运算符实现。

位图的应用场景：

整数数组去重操作，借助位图可以在\(O(n)\)时间复杂度内完成，同时也可以完成相应的排序操作。
质数计算：Eratosthenes筛

快速初始化¶

在严格意义上讲，即使调用memset()函数，位图的初始化（清空）也需要\(\mathcal O(n)\)的时间。借助校验环结构可以将位图的初始化复杂度由\(\mathcal O(n)\)提高到\(\mathcal O(1)\)（但相应地，位图中的一个位需要两个int类型即64字节进行存储，造成空间的大量浪费）。

将位图的数组拆分为A[]、B[]两个数组，对于第k位，满足：

A[B[k]] = k
B[A[k]] = k

两个数组构成了相互校验的关系，按照下标查询，符合校验条件的下标存储的位为1，否则为0。

双数组模式下，数组B为类似于栈的结构，从开头逐渐向后延伸，维护一个变量top记录B中元素的数量。数组A随机访问。

set(k)：在数组B中追加一个值为k的元素，在A[k]中存储B中对应元素的下标；
get(k)：若B[A[k]] == k且A[k]小于栈顶位置则为真，否则为假；
clear()：清空数组B，即将top置0。
remove(k)：先将A-B校验环中的最后一对（对应B[top - 1]）复制到B[A[k]]的位置，再top--删除最后一个元素。

“校验环”位图的实现：

位图

void set(int k)
{
   A[k] = top;
   B[top++] = A[k];
}
int get(int k)
{
   return B[A[k]] == k && A[k] < top;
}
void remove(int k)
{
   A[B[--top]] = k;
   B[k] = B[top];
}
void clear(int k)
{
   top = 0;
}

列表¶

向量是静态的数据结构，一次只能分配固定长度的空间，向量的扩增需要分配一块新的空间，然后将向量中的元素复制到新的向量中。而列表与之不同，列表的元素可以动态分配，列表的扩增只需要分配扩增所需的空间即可。

列表中元素的排列与列表元素在内存中的排列顺序没有必然的关系，这些元素在逻辑上形成一个序列。列表的元素又称节点，相邻的节点互称前驱与后继。没有前驱的节点称为首节点，没有后继的节点称为尾节点。节点需要额外的空间记录相邻节点的地址以构建逻辑上的顺序关系。

这种方法的缺点在于列表中的元素不能直接按照下标进行访问，只能从列表的第一个节点开始，依序访问节点直到访问到对应下标的节点，时间复杂度为\(\mathcal O(n)\)

节点类型¶

为实现列表的各项操作，节点类型需要实现以下接口：

获取与设置当前节点的前驱
获取与设置当前节点的后继
获取与设置当前节点的取值
插入前驱节点
插入后继节点

注意： 双向链表在实现时有潜在的数据不一致的风险。（前驱节点的后继不等于后继节点的前驱）

如下提供了一个节点类的示例接口，没有包含接口的具体实现。

列表节点类

/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2003-2020. All rights reserved.
 ******************************************************************************************/

typedef int Rank; //秩
#define ListNodePosi(T) ListNode<T>* //列表节点位置

template <typename T> struct ListNode { //列表节点模板类（以双向链表形式实现）
// 成员
   T data; ListNodePosi(T) pred; ListNodePosi(T) succ; //数值、前驱、后继
// 构造函数
   ListNode() {} //针对header和trailer的构造
   ListNode ( T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s = NULL )
      : data ( e ), pred ( p ), succ ( s ) {} //默认构造器
// 操作接口
   ListNodePosi(T) insertAsPred ( T const& e ); //紧靠当前节点之前插入新节点
   ListNodePosi(T) insertAsSucc ( T const& e ); //紧随当前节点之后插入新节点
};

Reference

插入与删除¶

向列表中插入数据需要如下过程：

定位到节点
分配一个新的节点
更新节点之间的指针，将新节点与其他节点相连接

删除过程是插入过程的反向过程，更新节点之间指针，将删除节点排除在外即可。

查找与去重¶

无序列表的查找与去重操作与无序向量的查找与去重操作的基本思路相同，此处不再赘述。

有序列表的查找不能使用二分查找而只能顺序查找。

有序列表的去重：反复考察相邻的节点，若节点相同，则删除后边的节点，继续考察，否则当前节点向后移动，重复考察过程。直到列表到达结尾，算法结束。

向量与列表¶

线性数据结构¶

向量¶

插入¶

可扩充向量¶

删除¶

查找¶

顺序查找¶

二分查找¶

插值查找¶

去重¶

无序向量¶

有序向量¶

排序¶

冒泡排序¶

归并排序¶

位图¶

快速初始化¶

列表¶

节点类型¶

插入与删除¶

查找与去重¶

评论