目录
Vector.h
Vector.hpp
Vector.h
#define DEFAULT_CAPACITY 3 //默认初始容量(实际应用中可设置为更大)
template <typename T> class Vector //向量模板
{
protected:
int _size;int _capacity;T *_elem; //规模,容量,数据区
void copyFrom(T const*A,int lo,int hi); //复制数组区间
void expand(); //空间不足时扩容
void shrink(); //装填因子过小时压缩
bool bubble(int lo,int hi); //扫描交换
void bubbleSort(int lo,int hi); //起泡(冒泡)排序算法
int max(int lo,int hi); //选取最大元素
void seletcionSort(int lo,int hi); //选择排序算法
void mergeSort(int lo,int hi); //归并算法
void merge(int lo,int mi,int hi); //归并排序算法
int partition(int lo,int hi); //轴点构造算法
void quickSort(int lo,int hi); //快速排序算法
void heapSort(int lo,int hi); //堆排序(稍后结合完全堆讲解)
public:
//构造函数
Vector(int c=DEFAULT_CAPACITY,int s=0,T v=0);//容量为c，规模为s，所有元素初始为v
Vector(T const*A,int n); //数组整体复制
Vector(T const*A,int lo,int hi); //区间
Vector(Vector <T>const& V); //向量整体复制
Vector(Vector <T>const& V,int lo,int hi); //区间
//析构函数
~Vector(); //释放内部空间
//只读访问接口
int size()const; //规模
bool empty()const; //判空
int disordered()const; //判断向量是否已排序
int find(T const& e)const; //无序向量整体查找
int find(T const& e,int lo,int hi)const; //无序向量区间查找
int search(T const& e)const; //有序向量整体查找
int search(T const& e,int lo,int hi)const;//有序向量区间查找
int binsearch(T* A,T const& e,int lo,int hi)const;//二分查找
//可写访问接口
T& operator[](int r)const; //重载下标操作符,可以类似于数组形式引用各元素
Vector<T> &operator=(Vector<T> const&);//重载赋值操作符,以便直接克隆向量
T remove(int r); //删除秩为r的元素
int remove(int lo,int hi); //删除秩在区间[ho,hi)之内的元素
int insert(int r,T const& e); //插入元素
int insert(T const& e);//默认作为末元素插入
void sort(int lo,int hi); //对[lo，hi)排序
void sort(); //整体排序
void unsort(int lo,int hi); //对[lo，hi）置乱
void unsort(); //整体置乱
int deduplicate(); //无序去重
int uniquify(); //有序去重
//遍历
void traverse(void(*visit)(T&));//遍历（使用函数指针,只读或局部性修改）
//template<typename VST>void traverse(VST& );//遍历（使用函数对象，可全局性修改）
void display();
};
Vector.hpp
#include <iostream>
#include "Vector.h"
using namespace std ;
template <typename T>
void Vector<T>::copyFrom(T const*A,int lo,int hi) //复制数组区间(未开辟空间情况下，给构造函数使用)
{
_elem=new T[_capacity=2*(hi-lo)]; //开辟复制俩倍的空间。
for(_size=0;lo<hi;_size++,lo++)
{
_elem[_size]=A[lo];
}
}
template <typename T>
void Vector<T>::expand() //空间不足时扩容
{
T *another=_elem;
if(_size<_capacity)return; //容器尚未装满
if(_capacity<DEFAULT_CAPACITY)_capacity=DEFAULT_CAPACITY
_elem=new T[_capacity<<=1]; //开辟翻一倍的空间
for(int i=0;i<_size;i++)
{
_elem=another[i];
}
delete[]another;
}
template <typename T>
void Vector<T>::shrink() //装填因子过小时压缩
{
if(_capacity<DEFAULT_CAPACITY<<1)return ;//不致收缩到DEFAULT_CAPACITY以下,《小于<优先级,《n表示乘以n*2
//我:if((_capacity>>1)<DEFAULT_CAPACITY)return;//容量缩小一倍后不能低于初始值
if(_size<<2>_capacity)return; //以容量的25%为限
//我:if(_size>(_capacity>>2))return; //以25%为例，规模要大于容量的25%
T* another=_elem;
_elem=new T[_capacity>>=1] //容量减半
for(int i=0;i<_size;i++)
{
_elem[i]=another[i];
}
delete[]another;
}
template <typename T>
bool Vector<T>::bubble(int lo,int hi) //扫描交换
{
bool sort=true; //整体有序标志(作用:若循环一遍发现整体有序后可不实现交换)
while (++lo<hi)
{
if(_elem[lo]<_elem[lo-1])
{
sort=false;
swap(_elem[lo],_elem[lo-1]);
}
}
return sort;
}
template <typename T>
void Vector<T>::bubbleSort(int lo,int hi) //起泡(冒泡)排序算法
{
while (!bubble(lo,hi--)) //hi--每一次确定最后一个元素后将hi前移
{
}
}
template <typename T>
int Vector<T>::max(int lo,int hi) //选取最大元素(在[lo,hi]里选取最大元素)
{
T max=_elem[hi];
while(lo<=hi--)
{
if(_elem[hi]<max)max=hi;
}
return hi;
}
template <typename T>
void Vector<T>::seletcionSort(int lo,int hi) //选择排序算法
{
for(int i=0;i<hi-lo;i++)
{
int k=i;
for(int j=i+1;j<hi-lo;j++)
{
if(_elem[j]<_elem[k])k=j;
}
if(k!=i)swap(_elem[i],_elem[k]);
}
}
template <typename T>
void Vector<T>::mergeSort(int lo,int hi) //归并算法
{
if(hi-lo<2)return ; //当区间为单个数时自然有序
int mi=(lo+hi)>>1;
merge(lo,mi);merge(mi,hi); //无序序列不停分割成俩个区间直至一个自然数
mergeSort(lo,mi,hi); //当返回至俩个自然数这层进行归并排序
}
template <typename T>
void Vector<T>::merge(int lo,int mi,int hi) //归并排序算法
{
T* A=_elem+lo; //设置合并后的向量[0,hi-lo)
int lb=mi-lo; //设置前部分向量大小
T* B=new T[lb];
for(int i=0;i<lb;i++)
{
B[i]=A[i];
}
int lc=hi-mi;
T* C=_elem+mi;
int i,j,k;
for(i=j=k=0;j<lb||k<lc;)
{
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=NULL;
}
template <typename T>
int Vector<T>::partition(int lo,int hi) //轴点构造算法
{
}
template <typename T>
void Vector<T>::quickSort(int lo,int hi) //快速排序算法
{
}
template <typename T>
void Vector<T>::heapSort(int lo,int hi) //堆排序(稍后结合完全堆讲解)
{
}
//构造函数
template <typename T>
Vector<T>::Vector(int c=DEFAULT_CAPACITY,int s=0,T v=0)//容量为c，规模为s，所有元素初始为v
{
_elem=new T[_capacity=c];
for(_size=0;_size<s;_size++)_elem[_size]=v;
}
template <typename T>
Vector<T>::Vector(T const*A,int n) //数组整体复制
{
copyFrom(A,0,n);
}
template <typename T>
Vector<T>::Vector(T const*A,int lo,int hi) //区间
{
copyFrom(A,lo,hi);
}
template <typename T>
Vector<T>::Vector(Vector <T>const& V) //向量整体复制
{
copyFrom(V._elem,0,V._size);
}
template <typename T>
Vector<T>::Vector(Vector <T>const& V,int lo,int hi) //区间
{
copyFrom(V._elem,lo,hi);
}
//析构函数
template <typename T>
Vector<T>::~Vector() //释放内部空间
{
if(_elem)delete []_elem;
_elem=NULL;
_capacity=_size=0;
}
//只读访问接口
template <typename T>
int Vector<T>::size()const //规模
{
return _size;
}
template <typename T>
bool Vector<T>::empty()const
{
return !_size;
}
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++;
}
return n;
}
template <typename T>
int Vector<T>::find(T const& e)const //无序向量整体查找
{
return find(e,0,_size);
}
template <typename T>
int Vector<T>::find(T const& e,int lo,int hi)const //无序向量区间查找
{
while p((lo<hi--)&&(e!=_elem[hi])) //逆序查找，默认返回秩最大的元素。
return hi;
/*我：正序查找，默认返回秩最小的元素
for(;lo<hi;lo++)
{
if(e==_elem[lo])break;
}
return lo;
*/
}
template <typename T>
int Vector<T>::search(T const& e)const //有序向量整体查找
{
return (0>=_size)?-1:search(e,0,_size);
}
template <typename T>
int Vector<T>::search(T const& e,int lo,int hi)const //有序向量区间查找
{
return binsearch(_elem,e,lo,hi);
}
template <typename T>
int Vector<T>::binsearch(T* A,T const& e,int lo,int hi)const//二分查找
{
/*int mi;
while (lo<hi)
{
mi=(lo+hi)>>1;
if(e<A[mi])hi=mi;
else if(e>[mi])lo=mi;
else return mi;
}
return -1; //未找到变量*/
//更新版
int mi;
while (lo<hi)
{
mi=(lo+hi)>>1;
(e<_elem[mi])?hi=mi:lo=mi+1;
}
return --lo;
}
//可写访问接口
template <typename T>
T& Vector<T>::operator[](int r)const //重载下标操作符,可以类似于数组形式引用各元素
{
return _elem[r];
//我:if（r<0||r>=_size）exit(1);应增加此句判断数组越界问题。
}
template <typename T>
Vector<T>& Vector<T>::operator=(Vector<T>const& V) //重载赋值操作符,以便直接克隆向量
{
if(_elem)delete[]_elem;
_elem=new T[_capacity=V._capacity];
for(_size=0;_size<V._size;_size++)
{
_elem[_size]=V._elem[_size];
}
//邓:copyFrom(V._elem,0,V.size()); 意见：copyFrom（）函数是给构造函数使用，如若在这使用，可能会使被赋值容量数值与复制容量数值不同。
return*this;
}
template <typename T>
T Vector<T>::remove(int r) //删除秩为r的元素
{
T e=_elem[r]; //备份被删除元素
remove(r,r+1); //[r,r+1)相等于删除r
return e;
/*
T e=_elem[r];
for(int i=r;i<_size;i++)
{
_elem[i]=_elem[i+1];
}
_size--;
return _elem[r];
*/
}
template <typename T>
int Vector<T>::remove(int lo,int hi) //删除秩在区间[ho,hi)之内的元素
{
if(lo==hi)return 0; //优化效率。
while (hi<_size) //将[hi,size)的元素依次往前移动
{
_elem[lo++]=_elem[hi++];
}
_size=lo; //更新规模
shrink(); //若有必要缩容,shrink（）函数已包含判断是否缩容语句。
return hi-lo //返回被删除元素数目
}
template <typename T>
int Vector<T>::insert(int r,T const& e) //插入元素
{
//邓：按秩插入
expand(); //若有必要扩容,expand（）函数已包含判断是否扩容语句。
for(int i=_size;i>r;i--)
{
_elem[i]=_elem[i-1];
}
_elem[r]=e;
_size++;
return r; //返回插入元素的秩
/*我：按位置插入，增添位置插入片段
if(r>_size||r<1)return;
for(int i=_size;i>=r;i--)
{
_elem[i]=_elem[i-1];
}
_elem[r-1]=e;
_size++;
*/
}
template <typename T>
int Vector<T>::insert(T const& e)//默认作为末元素插入
{
return insert(_size,e);
}
template <typename T>
void Vector<T>::sort(int lo,int hi) //对[lo，hi)排序
{
merge(lo,hi);
}
template <typename T>
void Vector<T>::sort() //整体排序
{
sort(0,_size);
}
template <typename T>
void Vector<T>::unsort(int lo,int hi) //对[lo，hi）置乱
{
T *V=_elem+lo; //将置乱区间向量看成另一向量V[0,hi-lo)
for(int i=hi-lo;i>0;i--) //rand()%n:表示从0到n-1个数里取随机数,因为从0开始，所以要取逆序。
{
swap(V[i-1],V[rand()%i]);
}
}
template <typename T>
void Vector<T>::unsort() //整体置乱
{
unsort(0,size());
}
template <typename T>
int Vector<T>::deduplicate() //无序去重
{
int old_size=_size;
int i=1; //重复是在第二个元素开始
while (i<_size)
{
(find(_elem[i],0,i)<0)?i++:remove(i); //remove里已更新规模，此处不用。
}
return old_size-_size; //返回重复元素个数。
}
template <typename T>
int Vector<T>::uniquify() //有序去重
{
int i=j=0;
while (++j<_size)
{
if(_elem[i]!=_elem[j]) //跳过重复元素，根据重复有序元素相邻的特性
_elem[++i]=_elem[j];
}
_size=++i; //更新规模
shrink(); //若有必要缩容
return j-i; //返回删除元素个数
}
//遍历
template <typename T>
void Vector<T>::traverse(void(*visit)(T&)) //遍历（使用函数指针,只读或局部性修改）
{
for(int i=0;i<_size;i++)visit(_elem[i]);
}
template <typename T>
void Vector<T>::display()
{
for(int i=0;i<_size;i++)
{
cout<<_elem[i]<<" ";
}
cout<<endl;
}
/*template<typename VST>void Vector<VST>::traverse(VST&) //遍历（使用函数对象，可全局性修改）
{
for(int i=0;i<_size;i++)visit(_elem[i]);
}*/
