数据结构与算法之-----向量（Vector)

 前言

写在前面的话：数据结构与算法。

1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

 向量构建

本章的主要内容：数据结构之-----向量

数据结构中最基础也是最重要的一个数据结构----向量。笔者大学所学的数据结构貌似与当前流行的学习内容有些不同，如果将数据按逻辑结构来简单划分的话，可以分为线性结构和非线性结构，线性结构里有一个顺序表的概念，其实，您可以把向量看成是顺序表的实例。

下面我们来看向量的C++实现：

先来看头文件，头文件中的内容非常之多，基本囊括了向量中大部分的知识，包括多种查询算法，插入算法，删除算法等等。

为了代码的高可用性，笔者使用了模版类，如果您对于某段代码不太理解，可以先放一放，去查询一下相关资料，此外，如果代码中有错误之处，敬请指出，谢谢！

/*
 * 作者：易果啥笔
 * 时间：2021.8.18
 * 内容：向量模板类的头文件
 *
 */

#ifndef VECTOR_VECTOR_H
#define VECTOR_VECTOR_H
#include <cstdlib>
#include "Vector.h"
#include <iostream>
using namespace std;

typedef int Rank;  //秩
#define DEFAULT_CAPACITY 3   //默认的初始容量

template <typename T>
class Vector    {   //向量模板类
    protected:
        Rank _size{} ; int _capacity{} ; T* _elem ; //规模，容量，数据区
        void copyForm(T const* A , Rank lo , Rank hi) ; //复制数组区间A[lo,hi)
    	void expand() ; //空间不足时扩容
        void shrink() ; //装填因子过小时压缩
        bool bubble(Rank lo , Rank hi) ; //扫描交换
        void swap(T& e1,T& e2) ; //交换元素
        void bubbleSort(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 insertionSort(Rank lo , Rank hi) ; //插入排序算法
    public:
        //构造函数
        explicit Vector(int c = DEFAULT_CAPACITY , int s = 0 , T v = 0){
            _elem = new T[_capacity  = c] ;
            for (_size = 0 ; _size < s ; _elem[_size++] = v);
            
        } //容量为c,规模为s,所有元素初始为v
        Vector(T const* A , Rank lo , Rank hi){
            copyForm(A,lo,hi) ; //数组区间复制
        }
        Vector(T const* A , Rank n){
            copyForm(A,0,n) ; //数组整体复制
        }
        Vector(Vector<T> const* V , Rank lo , Rank hi){
            copyForm(V->_elem,lo,hi) ; //向量区间复制
        }
        Vector(Vector<T> const* V){
            copyForm(V->_elem,0,V->_size) ; //向量整体复制
        }

        //析构函数
        ~Vector(){ delete [] _elem ; } //释放内部空间

        //只读访问接口
        Rank size() const {return _size ; } //规模
        bool isEmpty() const {return _size;} //判空
        int disordered() const ; //判断向量是否已排序
        Rank find(T const& e) const {return find(e,0,(Rank)_size) ; } //无序向量整体查找
        Rank find(T const& e , Rank lo , Rank hi) const ; //无序向量区间查找
        Rank search(T const& e ) const {return (0 >= _size) ? -1 : search(e,(Rank)0,(Rank)_size) ; } //有序向量整体查找
        Rank search(T const& e , Rank lo , Rank hi) const ; //有序向量区间查找

        //可写访问接口
        T& operator[](Rank r) const ; //重载[]运算符，可以类似数组形式引用各元素
        Vector<T> & operator=(Vector<T> const&) ; //重载赋值操作符，以便直接克隆向量
        T remove(Rank r) ; //删除秩为r的元素
        Rank 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 (* visit)(T&)); //遍历(使用函数指针，只读或局部性修改)
        //template<typename VST> void traverse(VST &) ; //遍历(使用函数对象，可全局性修改)


}; // Vector

/*
 *
 * 静态方法
 *
 *
 */



//Fibonacci数列的构造
template <typename T> static void fibonacci(T *f,int MAXSIZE)
{
    f[0] = 0;
    f[1] = 1;
    for(int i = 2;i < MAXSIZE;++i)
        f[i] = f[i - 2] + f[i - 1];
}

/*
 *
 * protected方法
 *
 */

template <typename T>  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 ; //成功查找不能提前终止
    }
    return --lo ;
} //查找失败时，能指示失败的位置

template <typename T>  Rank fibSearch(T* A,T const& e,Rank lo,Rank hi){
    Rank n = hi-lo , k = 0 , *array;
    array = new T[n] ;
    fibonacci(array,n) ;
    while(n > array[k] - 1) //计算出n在斐波那契中的数列
        ++k;
    for(int i = n ; i < array[k] - 1 ; ++i) //把数组补全
        array[i] = array[n-1];
    while(lo < hi){
        Rank mi = lo + array[k-1] - 1 ; //找轴点
        if(e <A[mi]) hi = mi ;
        else if(A[mi] < e) lo = mi + 1 ;
        else return mi ;
    }
    return -1 ; //查找失败返回-1
}

template <typename T> void Vector<T>::copyForm(const T *A, Rank lo, Rank hi) {
    _elem = new T[_capacity = (hi-lo)<<1] ; _size = 0 ;//分配空间，规模清零
    while(lo < hi)
        _elem[_size++] = A[lo++] ; //复制至_elem[0,hi-lo)
}

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 ; //释放原空间
}

template <typename T> void Vector<T>::shrink() { //装填因子过小时压缩向量所占空间
    if(_capacity < DEFAULT_CAPACITY << 1) return; //不至于收缩到DEFAULT_CAPACITY以下
    if(_size << 2 > _capacity) return; //以25%为界
    T* oldElem = _elem ; _elem = new T[_capacity >>= 1] ; //容量减半
    for(int i = 0 ; i< _size ; i++) {_elem[i] = oldElem[i];}//复制原向量内容
    delete [] oldElem ;
}

template<typename T> void Vector<T>::swap(T &e1, T &e2) {
    int temp ;
    temp = e1 ;
    e1 = e2 ;
    e2 = temp ;

}


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>::bubbleSort(Rank lo, Rank hi) {
    while (!bubble(lo,hi--)) ; //逐趟做扫描交换，直至全序
}

template<typename T> void Vector<T>::selectionSort(Rank lo, Rank hi) {
    while(lo < hi){
        Rank temp = lo ;
        for(Rank i = lo+1 ; i < hi ; i++){
            if(_elem[temp] > _elem[i]) temp = i ;
        }
        swap(_elem[lo++],_elem[temp]) ;
    }
}

template<typename T> void Vector<T>::insertionSort(Rank lo , Rank hi) {
    for(int i = 0 ; i < hi - lo ; i++){
        insert(binSearch(_elem,_elem[lo],lo-i,lo)+1,_elem[lo]);
        lo++ ; remove(lo--) ;
    }
}

template<typename T> void Vector<T>::merge(Rank lo, Rank mi, Rank hi) { //有序向量的归并，以mi为界，各自有序的子向量[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)
    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 ;
}

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) ; //分别对前后半段排序，然后归并
}

template<typename T> Rank Vector<T>::partition(Rank lo, Rank hi) { //轴点构造算法：通过调整元素位置构造区间[lo,hi]的轴点，并返回其秩
    swap(_elem[lo],_elem[lo + rand() % (hi -lo +1)]) ; //任意一个元素与首元素交换
    T pivot = _elem[lo] ; //以首元素为候选轴点-----经以上交换，等效于随机选取
    while(lo < hi){ //以向量的两端交替地向中间扫描
        while((lo < hi))
            if(pivot < _elem[hi]) //在大于的pivot前提下
                hi--; //向左扩展右端子向量
            else //直至遇到不大于pivot者
            {_elem[lo++] = _elem[hi] ; break ;} //将其归入左端子向量
        while ((lo < hi))
            if(_elem[lo] < pivot)
                lo++;
            else
                {_elem[hi--] = _elem[lo] ; break ;}
    }
    _elem[lo] = pivot ; //将备份的轴点记录置于前，后子向量之间
    return lo ; //返回轴点的秩

}
template<typename T> void Vector<T>::quickSort(Rank lo, Rank hi) {
    if(hi - lo < 2) return ;
    Rank mi = partition(lo,hi - 1) ;
    quickSort(lo,mi) ;
    quickSort(mi + 1,hi) ;
}

/*
 *
 * public方法
 *
 */

template <typename T> Vector<T>& Vector<T>::operator=(const Vector<T> & V) {
    if(_elem) delete [] _elem ; //释放原有内容
    copyForm(V._elem,0,V.size()) ; //整体复制
    return *this ; //返回当前对象的引用，以便链式赋值
}

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


template <typename T> void Vector<T>::unsort(Rank lo, Rank hi) {
    T* V = _elem + lo ; //将子向量_elem[lo,hi)视作另一向量V[0,hi-lo)
    for(Rank i = hi - lo ; i > 0 ; i--) //自后向前
        swap(V[i-1],V[random() % i]) ; //V[i - 1]与V[0 , i]中某一随机元素交换
}

template <typename T> Rank Vector<T>::find(const T &e, Rank lo, Rank hi) const {
    while((lo < hi--) && (e != _elem[hi])) ; //从后向前，顺序查找
    return hi ; //若hi < lo，则意味着失败，否则将返回hi即为命中元素的秩
}

template <typename T> Rank Vector<T>::insert(Rank r, const T &e) {
    expand() ; //若有必要，扩容
    for(int i = _size ; i > r ; i--) _elem[i] = _elem[i-1] ; //自后向前，后继元素顺次后移一个单元
    _elem[r] = e ; _size++ ; //置入新元素并更新容量
    return r ; //返回秩
}

template <typename T> Rank Vector<T>::remove(Rank lo, Rank 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)区间
    shrink() ; //若有必要，则缩容
    return hi - lo ; //返回被删除的元素个数
}

template <typename T> T Vector<T>::remove(Rank r) {
    T e = _elem[r] ; //备份被删除元素
    remove(r,r+1) ; //调用区间删除算法，等效于对区间[r,r+1)的删除
    return e ; //返回被删除的元素
}

template <typename T> Rank Vector<T>::deduplicate() {
    int oldSize = _size ; //记录原规模
    Rank i = 1 ; //从_elem[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>
//Rank Vector<T>::traverse(VST & visit) {
   //for(int i = 0 ; i < _size ; i++) visit(_elem[i]) ; //利用函数对象机制的遍历
//}

template <typename T> int Vector<T>::disordered() const {
    int n = 0 ; //计数器
    for(int i = 1 ; i < _size ; i++) //逐一检查_size-1对相邻元素
        if(_elem[i-1] > _elem[i]) n++ ; //逆序则计数
    return n ; //向量有序但且仅当n=0
}

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-1 ; //返回被删除元素总数
}

template <typename T> Rank Vector<T>::search(const T &e, Rank lo, Rank hi) const {
    return (random()%2) ?
        binSearch(_elem,e,lo,hi) : fibSearch(_elem,e,lo,hi) ; //Fibonacci查找
}

template<typename T> void Vector<T>::sort(Rank lo, Rank hi) {

    switch (random() % 4) { //随机选择排序算法，可根据问题的特点灵活选取或扩充
        case 1 : bubbleSort(lo,hi) ; break ; //起泡排序
        case 2 : selectionSort(lo,hi) ; break ; //选择排序
        case 3 : mergeSort(lo,hi) ; break ; //归并排序
        case 4 : insertionSort(lo,hi); //插入排序
        default: quickSort(lo,hi) ; break ; //快速排序
    }
}

#endif //VECTOR_VECTOR_H

 向量测试

在头文件里，我们定义了向量的一些基本运算，下面，我们以一个main文件来展示向量的基本操作：

/*
 * 作者：易果啥笔
 * 时间：2021.8.18
 * 内容：Vector模版类的应用
 *
 */

#include <iostream>
#include "Vector.h"
#include <ctime>
#include <string>

#define CAPACITY 10
#define SIZE 5
#define VALUE 0

using namespace std;

template<typename T> void print(T a){
    std::cout<<a<<"  ";
}

int main(){
    clock_t start,finish; //clock_t为CPU时钟计时单元数

    start = clock();

    Vector<int> vector(CAPACITY,SIZE,VALUE);
    vector[0] = 1 ;
    vector[1] = 2 ;
    vector.insert(2,3);
    vector.insert(3,7);
    vector[4] = 1 ;
    //遍历
    vector.traverse(print);
    
    vector.sort();cout<<endl;
    //遍历
    vector.traverse(print);

    finish = clock();
    cout<<endl<<"进程耗时："<<double (finish - start)/CLOCKS_PER_SEC<<'s'<<endl;
    cout<<vector.isEmpty()<<endl;
    return 0;
}

main文件中，笔者使用了C++中的ctime库中的clock_t对象来测试向量的一些基本操作的耗时，读者可以忽略。