《数据结构邓版》学习总结—第二章向量

转载请注明出处，大家共同学习共同进步！
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(n²)；

//思路如上，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！
所有程序示例截图均来自邓老师数据结构课程及教材！！！
望诸君共勉~！