邓公数据结构与算法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" 头文件，主要是对各种成员数据、成员函数的声明

#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)，如下所示：

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""

#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"

#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()

通过算法分析得：加倍扩容～

//加倍扩容
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 不是内置数据类型，那么就需要对下标操作符进行重载。

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()

• 删除单个元素和删除区间
  
• 删除区间时，需要注意删除顺序，从左到右逐个复制

有序向量的去重

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

二分查找

// 二分查找算法（版本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\) 选在何处时，复杂度最小。

二分查找改进版

二分查找的改进版： 使得向左右两侧深入的代价平衡，不能及时命中轴点所在的元素。牺牲了最好情况，但整体性能更趋于稳定。

// 二分查找算法（版本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]）

// 二分查找算法（版本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]}\]

这样可以更快的接近所需查找的元素。但是在小范围内，却容易被恶性分布所干扰，比如不满足均匀分布的情况下。

最好的查找方式是：插值查找 -> 二分查找 -> 顺序查找

排序

前面的查找算法都是对应于有序向量的，所以我们需要用排序算法先把向量变得有序起来，这样才能更高效的 查找 或 去重。

冒泡排序

冒泡排序：从后向前逐渐有序

其改进
- 改进一：如果在某一趟循环之后，已经完全有序了，后面的循环也就不需要了。所以需要设置设否有序的标志
- 改进二： 如果数据只是在前缀的一小部分乱序，后缀很多一部分已经有序了。这个时候我们是否还需要亦步亦趋的从后往前一步步的有序呢？ 所以可以在一趟交换走完之后，标记出交换的最后位置。然后只需要考虑前缀无序的部分即可。

改进一

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; //返回有序标志
}

自己动手实现一个整体的形式。。

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--;
    }
}

改进二

// 改进后的冒泡排序
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; //返回最右侧的逆序对位置
}

归并排序

分治策略：
- 一分为二
- 子序列递归排序
- 合并两个子序列

代码形式就是这样：

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 子序列不需要复制。

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 中。所以这里也是可以改进的。

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 中元素始终较大。

课后习题