向量 | Fl0w3r

引言

本课程旨在围绕各类数据结构的设计与实现，揭示其中的规律原理与方法技巧；同时针对算法设计及其性能分析，使学生了解并掌握主要的套路与手段。本文将讲解数据结构向量及查找和排序。

抽象数据类型

接口与实现

向量属于最最基本的线性结构，我们笼统称之为线性序列。

本章我们将围绕这种数据结构展示和讨论两方面问题：

如何根据统一的接口规范来定制并实现一个数据结构
围绕这种数据结构展示如何通过更加有效的算法使得我们对外的接口能够更加高效率地工作：查找、排序

首先我们要辨析抽象数据类型和数据结构：

抽象数据类型 = 数据模型 + 定义在该模型的一组操作
数据结构 = 基于某种特定语言，实现 ADT 的一整套算法

更形象一点，我们可以将数据结构比喻成某种产品比如汽车。作为用户 Application 而言，他只关心这种产品的外在特性能够提供的功能；而实现者 Implementation 则需要对这些功能以及特性具体如何落实负责。

向量ADT

所谓向量，实际上是 C++ 等高级编程语言中数组这种数据组织形式的一个推广和泛化。

循秩访问

在这些高级程序设计语言中所谓的数组实际上就是一段连续的内存空间，它被均匀地划分为若干个单元，而每一个单元都会与一个编号彼此回应，并且可以直接访问。

而向量可以被认为是数组的抽象与泛化，它同样是由一组抽象的元素按照刚才的线性次序封装而成。不同的是原来通过下标 i 的访问方式变成了秩 rank。

另外向量中元素的类型得到了拓展，不限于是某一种特定的基本类型，它的所有操作、管理维护更加简化，可以通过统一的接口来完成。

向量ADT接口

可以通过这些操作接口对向量做各种操作，同时也只能通过这些操作接口对向量进行操作。

接口操作实例

构造与析构

SourceCode

#ifndef SRC_VECTOR_H
#define SRC_VECTOR_H

#define DEFAULT_CAPACITY 3   // 默认初始容量

namespace Vector {
    using Rank = int;       // 秩

    template<typename T> class Vector {
    protected:
        T* _elem;           // 数据
        Rank _size;         // 规模
        Rank _capacity;     // 容量

        void expand();                                      // 空间不足扩容
        void shrink();                                      // 装填过小压缩
        void copyFrom(T const* A, Rank lo, Rank hi);        // 复制数组区间

        Rank maxItem(Rank lo, Rank hi);                     // 选取最大元素
        Rank partition(Rank lo, Rank hi);                   // 轴点构造算法

        void selectionSort(Rank lo, Rank hi);               // 选择排序

        bool bubble(Rank lo, Rank hi);                      // 扫描交换
        void bubbleSort(Rank lo, Rank hi);                  // 起泡排序

        void merge(Rank lo, Rank mid, Rank hi);             // 归并算法
        void mergeSort(Rank lo, Rank hi);                   // 归并排序

        void heapSort(Rank lo, Rank hi);                    // 堆排序
        void quickSort(Rank lo, Rank hi);                   // 快速排序
        void shellSort(Rank lo, Rank hi);                   // 希尔排序

    public:
        /* 构造函数 */
        Vector(int c = DEFAULT_CAPACITY, Rank s = 0, T v = 0) {
            _elem = new T[_capacity = c];
            for (_size = 0; _size < s; ++_size)
                _elem[_size] = v;
        }

        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);                       // 无序向量区间查找

        Rank search(T const& e) const {                               // 有序向量整体查找
            return (_size <= 0)? -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);                                             // 删除单一元素
        int remove(Rank lo, Rank hi);                                 // 删除区间元素
        
        Rank insert(Rank r, T const& e);                              // 插入元素
        Rank insert(T const& e) { return insert(_size, e); }          // 插入末元素
        
        void sort(Rank lo, Rank hi);                                  // 区间排序
        void sort() { sort(0, _size); }                               // 整体排序

        void unsort(Rank lo, Rank hi);                                // 区间置乱
        void unsort() { unsort(0, _size); }                           // 整体置乱

        /* 遍历接口 */
        void traverse(void(*) (T&));                                  // 函数指针遍历
        template<typename VST> void traverse(VST&);                   // 函数对象遍历
    };
}

#endif //SRC_VECTOR_H

整个 Vector 被封装起来，来自各种用户 application 的操作接口 interface 提供在外面，相当于一个 Vector 结构的使用说明书。

/* 构造函数 */
Vector(int c = DEFAULT_CAPACITY, Rank s = 0, T v = 0) {
    _elem = new T[_capacity = c];
    for (_size = 0; _size < s; ++_size)
        _elem[_size] = v;
}

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

复制

template <typename T>
void Vector<T>::copyFrom(const T *A, Rank lo, Rank hi) {
    _elem = new T[_capacity = 2*(hi - lo)];
    _size = 0;

    while (lo < hi)
        _elem[_size++] = A[lo++];
}

复制操作将 _elem 空间扩展为原来的二倍，然后将区间元素依次复制。

可扩充向量

现在我们用 _size 表示实际规模，_capacity 表示总容量。

T* _elem;           // 数据
Rank _size;         // 规模
Rank _capacity;     // 容量

这里的问题是 _capacity 一旦确定按照目前的方案它就将一成不变，而这样一种策略显然存在明显的不足。这种不足体现在两个方面：

上溢(overflow)：_elem[] 不足以存放所有元素，尽管此时系统仍有足够的空间
下溢(underflow)：_elem[] 中的元素寥寥无几，装填因子 = _size/_capacity << 50%

动态空间管理

我们需要从静态管理策略改编为动态管理策略，模仿蝉的做法在即将发生上溢时适当地扩大内部数组容量。

向量的生命周期：

(a) 最开始虽然元素很多但不至于出现上溢的情况
(b) 但剩余空间有可能会逐步地占用，在某一时刻内部数组饱和
(c) 模仿蝉退掉外壳，动态申请另一个外壳：另一段存放空间，它的大小应该比原来的有所增长
(d) 把原先存放好的有效元素逐一按次序复制过来，使得它们对外界而言依旧保持原貌
(e) 新多出的空间足以存放新需要插入的元素，原来占用的空间在此之后被释放并且归还给系统

template <typename T>
void Vector<T>::expand() {
    if (_size < _capacity) return;
    _capacity = std::max(_capacity, DEFAULT_CAPACITY);

    T* oldElem = _elem;
    _elem = new T[_capacity <<= 1];

    for (int i = 0; i < _size; ++i)
        _elem[i] = oldElem[i];
    delete[] oldElem;
}

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

递增式扩容

每当发现当前的内部数组即将发生上溢，我们并不是对它进行容量的加倍而只是在原来的容量的基础上追加一个固定的数额：

T* oldElem = _elem;
_elem = new T[_capacity += INCREMENT];

对于这种策略而言，每经过 I 次插入操作它都需要进行一次扩容，每次分摊成本为 O(n)。

加倍式扩容

T* oldElem = _elem;
_elem = new T[_capacity <<= 1];

每次的分摊成本为 O(1) 常数时间。

倍增策略通过在空间的效率上做了一个适当的牺牲换取在时间方面的巨大收益。

无序向量

循秩访问

首先讨论向量元素的访问。表面上看这并不是什么问题，因为在向量 ADT 中已经定义了两个标准的接口 V.get(r) 和 V.put(r, e)。通过它们我们已经可以自如地来写或者是读向量中特定的元素，但这两种接口在形式上还不是那么简洁直观。

我们期望数组那种直接地访问方式：A[r]，为此需要重载下标操作符 []：

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

插入

再来考察向量的插入算法，如何讲某一个特定的元素插入到向量的特定位置。

因为原有向量所有元素都是紧邻排列的，所以为了能够插入新的元素我们需要将对应位置之后的所有元素称作它的后继，进行一个整体的右移操作。

template <typename T>
Rank Vector<T>::insert(Rank r, T const& e) {
    expand();
    for (int i = _size; i > r; --i)
        _elem[i] = _elem[i - 1];
    
    _elem[r] = e;
    _size++;
    
    return r;
}

区间删除

template <typename T>
int Vector<T>::remove(Rank lo, Rank hi) {
    if (lo == hi) return 0;

    while(hi < _size)
        _elem[lo++] = _elem[hi++];

    shrink();
    return hi - lo;
}

单元素删除

template <typename T>
T Vector<T>::remove(Rank r) {
    T e = _elem[r];
    remove(r, r + 1);
    return e;
}

查找

无序向量只支持判等操作，有序向量还需要支持其中的元素相互比较大小。

template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi) {
    while ((lo < hi--) && (_elem[hi] != e));
    return hi;
}

从 hi 出发逆向逐一取出向量中的各个元素，与目标元素进行比对。如果不相等，就忽略它并且考察它的前驱，整个工作会遍历向量中的所有元素。

去重/唯一化

向量的唯一化需要把其中重复的元素都剔除掉，只保留一个拷贝。

template <typename T>
int Vector<T>::deduplicate() {
    int oldSize = _size;
    Rank i = 1;
    while (i < _size) {                                      
        (find(_elem[i], 0, i) < 0)?                           
            i++:                                             
            remove(i);                                       
    }
    
    return oldSize - _size;                                 
}

遍历

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>
struct Increase {
    virtual void operator()(T& e) { e++; }
}

......

template <typename T>
void increase(Vector<T>& V) {
    v.traverse(Increase<T>());
}

有序向量

唯一化

与起泡排序算法的理解相同，有序/无序序列中，任意/总有一对相邻元素顺序/逆序。

因此，相邻逆序对的数目，可用以度量向量的逆序程度。

template <typename T>
int Vector<T>::disordered() const {
    int n = 0;
    for (int i = 1; i < _size; i++)
        n += (_elem[i - 1] > _e);
    return n;    
}

Fl0w3r

向量

引言

抽象数据类型

接口与实现

向量ADT

循秩访问

向量ADT接口

接口操作实例

构造与析构

复制

可扩充向量

可扩充向量

动态空间管理

递增式扩容

加倍式扩容

无序向量

循秩访问

插入

区间删除

单元素删除

查找

去重/唯一化

遍历

有序向量

唯一化

二分查找

Fib查找

插值查找

起泡排序

归并排序

位图