《数据结构邓版》学习总结---第二章向量Vector
《数据结构邓版》学习总结—第二章向量
转载请注明出处，大家共同学习共同进步！
sequence序列中向量vector和列表list；
由数组至向量；向量是线性数组的一种抽象和泛化。
向量的秩rank与元素一一对应。vector[rank]。与数组下标类似
向量ADT接口，引用邓PPT；
vector模板类程序示例
typedef int Rank;
#define DEFAULT_CAPACITY 3;
tempalte<typename T>
class Vector
{
private:
Rank _size;int _capacity;T* _elem;//元素个数，向量容量，存放地址
protected:
void copyForm(T* const A,int lo,int hi);//复制数组区间A[lo,hi]
void expand();//二倍扩容
void shrink();//缩容
bool bubble(Rank lo,Rank hi);//扫描交换算法，冒泡排序内层循环
void bubbleSort(Rank lo,Rank hi);//冒泡排序算法
void merge(Rank lo,Rank mi,Rank hi);//归并算法
void mergeSort(Rank lo,Rank hi);//并归排序算法
void partition(Rank lo,Rank hi);//轴点构造算法
void quickSort(Rank lo,Rank hi);//快排算法
void headSort(Rank lo,Rank hi);//堆排序
public:
//构造函数
Vector(int c=DEFAULT_CAPACITY){_elem=new T[_capacity=c];_size=0}//默认
Vector(T* A,Rank lo,Rank hi){copyForm(T* A,lo,hi);}//数组
Vector(T* A,Rank n){copyForm(T* 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 empty()const{return _size<=0;}//判断向量是否为空
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 cosnt& e)const//有序向量 全局查找
{return (0>=_size)?-1:search(e,(Rank)0,(Rank)_size);}
Rank search(T const& e,Rank lo.Rank hi)cosnt;//有序向量 区间查找
//可写访问接口
T& operator[](int r)cosnt;//重载[]运算符
Vector<T>& operator=(Vector<T> cosnt&);//重载=
T remove(Rank r);//删除秩为r的元素
int remove(Rank lo,Rank hi);//删除区间内所有元素
Rank insert(Rank r,T const& e);//在r处插入T类型元素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);//局部置乱
void unsort(){unsort(0,_size)}//默认全局置乱
int deduplicate();//无序向量剔除重复元素
int uniquify();//有序向量剔除重复元素
//遍历
void traverse(void (*)(T&));//使用函数指针遍历，只读或局部修改
template <typename VST> void traverse(VST&); //使用函数对象遍历，可全局性修改
};//Vector
基于复制的构造方法实现示例：
template<class T>//class与typename相同
void Vector<T>::copyForm(T* const A,Rank lo.Rank hi)//复制函数
{
_elem=new T[_capacity=2*(hi-lo)];_size=0;//分配2倍空间扩容，向量元素个数清零
while(lo<hi)//
_elem[_size++]=A[lo++];//复制A数组元素至_elem地址的向量
}
由于编译器默认的运算符“=”不足以支持向量之间的相互赋值。
重载运算符“=”实现示例：
template<class T>//class与typename相同
Vector<T>& Vector<T>::operator=(Vector<T> const& V)//重载运算符“=”
{
int n=V.size();//确认V向量的规模大小
if(_capacity<n)//若当前向量的容量小于n，则需要扩展
{delete [] _elem;_elem=new T[_capacity=2*n];}//删除后重新动态分配空间
copyForm(V._elem,0,n);//调用 复制函数进行复制。
return *this;//返回当前对象的指针
}
当向量规模不足，则需要通过内部数组动态扩容算法expand()，通常都采用2倍扩容
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];//将原数据地址名更换oldElem，动态内存分配new分配新空间，给_elem，且_capacity右移一位，实现加倍扩容。
for(int i=0;i<_size;i++)
_elem[i]=oldElem[i];//复制原向量内容
delete [] oldElem;//释放oldElem空间（即原_elem空间），new与delete搭配使用哦！！！
}//expand---o(n)，分摊运行时间o(1)
分摊复杂度：在使用同一算法对同一数据结构连续实施足够多次操作过程中，总体所需的计算时间分摊至其间所有操作的平均值。
当装填因子很低时，数组发生下溢underflow，此时有必要适当的缩减内部数组的容量，shrink()算法
template <typename T>//元素类型T
void Vector<T>::shrink(){//缩容
if(_capacity<DEFAULT_CAPACITY<<1) return;//若容量减倍后 会小于默认容量，则不执行缩容。
if(_capacity<_size<<2) return;//若容量小于4倍的规模，不执行，25%界限。 size>25%capa
T* oldElem=_elem;elem=new T[_capacity>>=1];
for(int i=0;i<_size;i++)
_elem[i]=oldElem[i];//复制原向量内容
delete [] oldElem;//释放oldElem空间（即原_elem空间），new与delete搭配使用哦！！！
}//shrink() 效率略低，并不适用于对每次操作的执行速度极其敏感的应用场合
为实现与数组同样的循秩访问，重载操作符"[]"
template <typename T>
T& Vector<T>::operator[](int r) const//重载下标操作符，以便沿用数组访问方式
{return _elem[r];}//assert:0<=r<size assert是用于检验条件真假与否！！！
置乱器，置乱算法，从置乱区间末元素开始逆序向前扫描，使用rand()函数，将当前元素与rand()的任一元素交换。
template <typename T>
void permute(Vector<T>& V){//封装于ADT
for(int i=V.size(),i>0;i--)//自后向前思路很好
swap(V[i-1],V[rand()%i]);//将V[i-1]与rand()的任一元素V[0,i-1]交换
}//permute
区间置乱接口—对外
template <typename T>
void Vector<T>::unsort(Rank lo,Rank hi){//置乱区间_elem[lo,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[rand()%i]);//将V[i-1]与rand()的任一元素V[0,i-1]交换
}//unsort，调用方式Vector A;A.unsort(lo,hi)
判等器与比较器
元素的内部类型可能是指向其他对象的指针，而从外部更多关注的往往是指对象的大小。若实参为指针类型，则调用函数内的lt，取地址指向数据进行比较，若数据本身就是T类型，用引用调用就ok！！！
template <typename T> static bool lt(T* a,T* b){return lt(*a,*b);}//less than
template <typename T> static bool lt(T& a,T& b){return a<b;}//less than
template <typename T> static bool eq(T* a,T* b){return eq(*a,*b);}//equal
template <typename T> static bool eq(T& a,T& b){return a==b;}//equal
无序向量的查找算法：
顺序查找sequential search，遍历：依次逐个比对
//无序向量的顺序查找算法：返回最后一个等于e的元素的位置，失败则返回lo-1；
template <typename T>
Rank Vector<T>::find(T const& e,Rank lo,Rank hi){//assert：0<=lo<hi<=_size
while((lo<hi--)&&(_elem[hi]!=e))//自后向前依次查找
return hi;//当lo>hi，失败。
}//find 复杂度，遍历， 线性o(n)
插入算法
每插入一个元素，其后继元素都要后移一位
//将数据e插入至 秩为r的位置
template <typename T>
Rank Vector::insert(T const& e,Rank r){//
expand();//若有必要，扩容
for(int i=_size;i>r;i--)//自后向前
_elem[i]=_elem[i-1];//后继元素顺次后移一个单元
_elem[r]=e;//置入新元素
_size++;//更新规模
return r;//返回秩
}//insert O(n)
删除算法
每删除一个元素，其后继元素都要前移一位。
区间删除算法实现：
//删除区间[lo,hi)
template <typename T>
int Vector::remove(Rank lo,Rank hi){//删除区间[lo,hi)
if(lo==hi) return 0;//退化现象，无元素可删除
while(hi<_size)//以hi之后所有元素均移动完成为终止条件
_elem[lo++]=_elem[hi++];//后继元素顺次后移一个单元
_size=lo;//更新规模
return hi-lo;//返回删除区间的长度
}//remove O(n)
可根据区间删除算法，完成单个元素删除功能
//删除秩为r的元素
template <typename T>
int Vector::remove(Rank r){//
if(_elem[r]==NULL) return 0;//若不存在，不删除
T e=_elem[r];//备份
remove(r,r+1);//调用区间删除大法 删除r处元素
return e;//返回删除秩为r的元素
}//remove O(n)
在某些场合可能要对向量进行处理要求 向量元素互异，即唯一性。
唯一性算法：自前向后逐个比对，删除重复
template <typename T>
int Vector::deduplicate(){
int oldSize=_size;
Rank i=1;
while(i<_size){
Rank j=find(_elem[i],0,i)//在[0,i)区间内找与_elem[i]相同元素
(j<0)?++i:remove(j);//判断j,若<0,则无重复，否则，有重复并删除
}//while
return oldSize-_size;//返回删除个数
}//deduplicate O(n^2)
遍历接口traverse()
两种实现方式：自学补充知识体会不同！！！
//遍历向量，对各节点实施visit操作
//函数指针机制
template <typename T>
void Vector::traverse(void (*visit)(T&))//以函数指针为形参调用，只读或局部性修改
{for(int i=0;i<_size;i++) visit(_elem[i];)}//
//函数对象机制
template <typename T>
template <typename VST>
void Vector::traverse(VST& visit)//以函数对象为形参调用，全局性修改
{for(int i=0;i<_size;i++) visit(_elem[i];)}//
有序向量的接口函数实现
首先判断有序性，提出相邻逆序对概念，即在秩i<=i+1，若a[i]>=a[i+1]，则构成一对逆序对。
template <typename T>//类型
int Vector<T>::disordered() const{//有序性判断，返回相邻逆序对总对数
int n=0;//计数器
for(int i=1;i<_size;i++)//从第二个数开始遍历
if(_elem[i-1]>_elem[i]) n++;//若构成相邻逆序对。加1
return n;
}//disordered
唯一性，与无序向量意义相同。不能出现重复元素。
依次比较删除，过于低效。
采用：当识别后一个比当前元素大的元素位置时，删除之间区间。
//有序向量重复元素剔除算法
template <typename T>
int Vector<T>::uniquify(){//唯一性：剔除重复元素，一次识别，多次删除
Rank i=0,j=0;
while(++j<_size)//从1开始遍历至结束
if(_elem[i]!=_elem[j])//若发现i之后的第一个不等元素
elem[++i]=_elem[j];将i++秩的元素换为j的元素
_size=++i;//i为秩，_size为规模，规模=最后1个秩的值+1
return j-i;//返回被删除元素的个数。向量规模变化量
}//uniquify
//思路个人实现版本！！！哈哈哈
template <typename T>
int Vector<T>::uniquify(){//唯一性：剔除重复元素，一次识别，多次删除
Rank i=0,j=1;
while(j<_size)//从1开始遍历至结束
if(_elem[i]!=_elem[j])//若发现i之后的第一个不等元素
elem[++i]=_elem[j++];将i+1秩的元素换为j的元素，并将j+1
_size=++i;//i为秩，_size为规模，规模=最后1个秩的值+1
return j-i;//返回被删除元素的个数。向量规模变化量
}//uniquify
查找接口：
template <typename T>
Rank Vector<T>::search(T const& e,Rank lo,Rank hi){//
if(rand()%2)//随机选择查找方式
return binSearch(_elem,e,lo,hi);
else
return fibSearch(_elem,e,lo,hi);
}
二分法查找思路：寻找秩中点mi，比较查找值在两个区间中哪一个后，再对此区间二分，依次重复直至查找成功或失败。
成功返回当前元素的秩，失败返回不大于查找值的最大秩。
实现示例：
//二分查找A：每次迭代一次判断。但成功查找也不能提前终止。 在多个命中元素时，不能保证返回最靠后值的秩。且查找失败返回-1。
template <typename T>//元素类型
static Rank binSearch(T* A,T const& e,Rank lo,Rank hi){//在A[lo,hi)中查找e
while(lo<hi-1){//循环hi-1-lo次
Rank mi=(lo+hi)>>1;//右移一位 除2
e<A[mi]?hi==mi:lo==mi;//判断在左/右区间
}//while
return e==A[lo]?lo:-1;//成功，返回lo。失败返回-1
}//binSearch
若考虑 在多个命中元素时，返回最靠后值的秩。且查找失败返回不大于查找值的最大秩。
//二分查找B：若考虑 在多个命中元素时，返回最靠后值的秩。且查找失败返回不大于查找值的最大秩。
template <typename T>//元素类型
static Rank binSearch(T* A,T const& e,Rank lo,Rank hi){//在A[lo,hi)中查找e
while(lo<hi){//循环hi-lo次，hi=lo跳出
Rank mi=(lo+hi)>>1;//右移一位 除2
e<A[mi]?hi==mi:lo==mi+1;//判断在左[lo,mi)/右[mi+1,hi)区间;
}//while
return --lo;//成功，返回--lo。失败返回--lo;//循环结束时，lo为大于e的元素的最小秩，则lo-1为不大于e的元素的最大秩。因此 不论成功与否都返回lo-1，此返回值便于插入删除操作！！！
}//binSearch
斐波那契查找：与二分思路相同，只是分界点不是中点了，而是斐波那契对应的数。
//三个分支，可提前终止，在多个命中元素时，不能保证返回最靠后值的秩。且查找失败返回-1
template <typename T>//元素类型
static Rank fibSearch(T* A,T const& e,Rank lo,Rank hi){//在A[lo,hi)中查找e
Fib fib(hi-lo);//
while(lo<hi){//循环hi-lo次，hi=lo跳出
while(hi-lo<fib.get()) fib.pred();//当长度小于斐波那契值，不足以划分两块时，选用前一个更小的斐波那契数值。
Rank mi=lo+fib.get()-1;//(fib(k)-1)-(fib(k-1)-1)-1=(fib(k-2)-1);长度为fib(k)-1；
if(e<A[mi]) hi==mi;//判断在左[lo,mi)/右[mi+1,hi)区间;//深入前半段查找
else if(e>A[mi])lo==mi+1;//深入后半段查找
else return mi;//准确命中
}//while
return -1;//失败
}//fibSearch
向量的排序器：
向量的排序函数接口
//随机选择排序方式
template <typename T>//
void Vector::sort(Rank lo,Rank hi){//_elem[lo,hi)排序
switch(rand()%4){//随机选择
case 1: bubbleSort(lo,hi);break;//起泡排序
case 2: mergeSort(lo,hi);break;//归并排序
case 3: heapSort(lo,hi);break;//堆排序，在堆 章节讲述
default:quickSort(lo,hi);break;//快速排序，在 排序章节讲述
}//switch
}//sort
起泡排序思想：1.逐个比对相邻元素是否为逆序对，若是，交换，否则，不动。每次执行都将一个最大元素冒出。2.之后的比对不再考虑已冒出元素。逐渐缩小比对元素的区间，直至全序！
稳定排序算法，O(n2)；
//思路如上，swap交换函数此处不再示例；
template <typename T>
void Vector<T>::bubbleSort(Rank lo,Rank hi){ //起泡排序
{ while(!bubble(lo,hi--)); }//bubbleSort//每次循环后都会排序出一个当前最大元素
//起泡程序
template <typename T>
void Vector<T>::bubbleSort(Rank lo,Rank hi){//起泡
bool sorted=true;//全序标志符-默认全序
while(++lo<hi){//从1开始
if(_elem[lo-1]>_elem[lo]){
sorted=false;
swap(_elem[lo-1],_elem[lo]);
}//if
}//while
return sorted;
}//bubble
//个人思路：for循环实现，可能复杂度考虑不如上一种！
template <typename T>
void Vector<T>::bubbleSort(Rank lo,Rank hi){
int n=hi-lo;//确定排序区间长度
while(--n){//确定最大循环次数n-1次
for(int i=lo;i<--hi;i++){//每次循环比较排序，每次长度-1
if(_elem[i]>_elem[i+1]){
swap(_elem[i],_elem[i+1]);//比较与交换
}//if
}//for
}//while
}//bubbleSort
向量的归并排序：两个有序向量的合并。归并排序O(nlogn); 稳定
merge的思想：1.将向量长度均分2段，对每一段单独排序。(可递归至长度为1的向量段。) 2.对每一段的最前元素比较大小，将最小的弹出并置入有序序列。3.依次比较弹出，直至排序完成。
归并排序的主体结构属于典型的分而治之策略
//归并排序的主体结构属于典型的分而治之策略
template <typename T>//元素类型
void Vector<T>::mergeSort(Rank lo,Rank hi){//
if(hi-lo<2) return;//退化现象，单元素必然有序啊啊啊！！！
int mi=(hi+lo)>>1;//左移一位代表除2
//递归，继续实行分治策略
mergeSort(lo,mi);//左区间归并排序
mergeSort(mi,hi);//右区间归并排序
//区间归并
merge(lo,mi,hi);//归并
}//mergeSort
********************************************
//之后分析merge归并实现算法
//当前向量以mi为界，为两个有序向量[lo,mi),[mi,hi)。归并完成一个完整的有序向量[lo,hi)
template <typename T>//元素类型
void Vector<T>::merge(Rank lo,Rank mi,Rank hi){//
T* A=_elem+lo;//A[0,hi-lo)=_elem[lo,hi);将秩为lo的元素的地址赋予A。
int lb=mi-lo; T* B=new T[lb];
for(int i=0;i<lb;i++) B[i]=B[lo++];//复制A的左区间至B
int lc=hi-mi; T* C=_elem+mi; //A的右区间更名为C//不需要为右区间再分配内存存放；即C与A的右区间用同一段内存单元
//比较B,C并进行合并
Rank i,j,k;i=j=k=0;
while(j<lb&&k<lc){//反复比较
while(j<lb&&B[j]<=C[k]) A[i++]=B[j++];//将小者续在A后;//此处曾考虑过if,也可使用
while(k<lc&&C[k]<B[j]) A[i++]=C[k++];//此处对原处的=去除，个人考虑，因B在前，若有相同也是B中为先，因此出现相同就将B的元素先置于A
}//while
while(j<lb) A[i++]=B[j++];//若只剩B元素，则将其剩余元素依次续在A后。因为C与A右其实同内存单元，即使此时k<lc；也只是C的部分有序元素不会移动位置，也就是A的右区间的部分元素不移动罢了！！！不需要提出while(k<lc) A[i++]=C[k++];
delete [] B;//排序后释放分配至B的空间！new与delete形影不离~
}//merge
学习总结—第二章向量Vector！
所有程序示例截图均来自邓老师数据结构课程及教材！！！
望诸君共勉~！
投递传音控股等公司10个岗位 >
