向量-Vector

Vector.h

#ifndef ALGOTEST_VECTOR_H #define ALGOTEST_VECTOR_H typedef int Rank;//秩,为类型起别名 #define DEFAULT_CAPACITY 3 //默认的初始容量（实际应用中可设置为更大） template <class T> class Vector {//向量模板类 protected: //规模、容量、数据区 Rank _size; int _capacity; T *_elem; void copyFrom(T const *A, Rank lo, Rank hi);//复制数组区间A[lo, hi) void expand();//空间不足时扩容 void shrink();//装填因子过小时压缩 public: //构造函数 Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0);//容量为c、规模为s、所有元素初始为v Vector(T const *A, Rank lo, Rank hi);//区间复制 Vector(T const *A, Rank n);//数组整体复制 Vector(Vector<T> const &v);//向量复制 Vector(Vector<T> const &v, Rank lo, Rank hi);//向量区间复制 //析构函数 ~Vector() { delete[] _elem; } // 只读访问接口 Rank size() const { return _size; } //规模 bool empty() const { return !_size; } //判空 int disordered() const; //判断向量是否已排序,返回逆序对数 Rank find(T const &e) const { return find(e, 0, _size); } //无序向量整体查找 Rank find(T const &e, Rank lo, Rank hi) const; //无序向量区间查找 Rank search(T const &e) const //有序向量整体查找 { return (0 >= _size) ? -1 : search(e, 0, _size); } Rank search(T const &e, Rank lo, Rank hi) const; //有序向量区间查找 int deduplicate();//删除重复元素，并返回删除的个数//无序去重 int uniquify(); //有序去重 //遍历 void traverse(void (*viste)(T & v));//遍历（使用函数指针，只读或局部性修改） template <typename VST> void traverse ( VST & ); //遍历（使用函数对象，可全局性修改） // 运算符重载 T &operator[](Rank r)const;///重载下标操作符，可以类似于数组形式引用各元素 Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符，以便直接克隆向量 template <class T> struct Increase{ virtual void operator)() (T &e){e++;} }; void increase(Vector<T> & v); //可写访问接口 Rank insert(Rank r,T const &e); int remove(Rank lo,Rank hi);//区间删除【lo,hi) T remove(Rank r); //单元素删除 void sort(Rank lo,Rank hi);//排序//对[lo, hi)排序 void sort(){sort(0,_size);} void bubbleSort(Rank lo,Rank hi);//对[lo, hi)排序 void selectSrot(Rank lo,Rank hi);//选择排序 }; #endif //ALGOTEST_VECTOR_H

Vector.cpp

#include <afxres.h> #include "Vector.h" #include <iostream> using namespace std; template<typename T> Vector::Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0) { _elem = new T[_capacity = c]; _size = 0; } template<typename T> Vector::Vector(T const *A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } template<typename T> void Vector::Vector(Vector<T> const &v) { copyFrom(v._elem, 0, v._size); } template<typename T> void Vector::Vector(T const *A, Rank n) { copyFrom(A, 0, n); } template<typename T> void Vector::Vector(Vector<T> const &v, Rank lo, Rank hi) { copyFrom(v._elem, lo, hi); } template<typename T> void Vector::copyFrom(T const *A, Rank lo, Rank hi)//复制数组区间A[lo, hi) { _elem = new T[_capacity = 2 * (hi - lo)];//分配空间 //*2 扩充空间 _size = 0;//规模清零 while (lo < hi) { _elem[_size++] = A[lo++];//复制元素到_elem } } template<typename T> void Vector::expand() {//空间不足时扩容 if (_size < _capacity) return; _capacity = 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;//释放空间 } } template<typename T> T &Vector<T>::operator[](Rank r) const { return _elem[r]; } template<typename T> Vector<T> &operator=(Vector<T> const &) { } 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) {//删除[lo,hi）里的元素 if (lo == hi) return 0; if (lo < 0 || hi >= _size) { cout << "Error" << endl; return 0; } for (int i = 1; i <= (hi - lo); i++) { if (hi < _size) _elem[lo++] = _elem[hi++]; } _size -= lo; return hi - lo; } template<typename T> T Vector<T>::remove(Rank r) { T e = _elem[r]; remove(r, r + 1); return e; } template<class T> Rank Vector::find(T const &e, Rank lo, Rank hi) const {//无序向量区间查找 while ((lo < hi--) && e != _elem[hi]);//逆向查找 return hi; } template<class T> int Vector::deduplicate() {//算法时间复杂度为0(n*n) //唯一化算法 int oldsize = _size; int i = 1; while (i < _size) { (find(_elem[i], 0, i) < 0) ? i++ : remove(i); } return oldsize - _size; } template <class T> int Vector<T>:: uniquify()//有序去重 { int i=0; int j=1; for(j=1;j<_size;j++) { if(_elem[i]!=_elem[j]) _elem[++i]=_elem[j]; } _size=++i; shrink();//直接截取尾部多余的元素 return j-i; } 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<class T> void Vector<T>::traverse(void (*visit)(T &v)) {//遍历（使用函数指针，只读或局部性修改） for (int i = 0; i < _size; i++) visit(_elem[i]); } template <typename VST> template <typename T> void Vector<T>::traverse ( VST & visit){//遍历（使用函数对象，可全局性修改） for(int i=0;i<_size;i++) { visit(_elem[i]); } } template<class T> void Vector<T>::sort(Rank lo, Rank hi) {//对[lo, hi)排序 switch (rank() % 5) { // case 1:bubbleSort(lo,hi);break; // case 2:selectSort(lo,hi);break; // case 3:mergeSort(lo,hi);break; // case 4:heapSort(lo,hi);break; // case 5:quickSort(lo,hi);break; } } template<class T> int Vector<T>::disordered() const{ int n=0; for(int i=0;i<_size-1;i++){ if(_elem[i]>_elem[i+1]) n++; } return n; } //template <class T> //void Vector<T>::increase(Vector<T> & v){ // v.traverse(Increase<T>()); //} template<class T> void Vector<T>::bubbleSort(Rank lo, Rank hi) { for (int i = lo; i < hi - 1; i++) { for (int j = lo + 1; j < hi; j++) { if (_elem[j] < _elem[i]) { T temp=_elem[i]; _elem[i]=_elem[j]; _elem[j]=temp; } } } } template <class T> void Vector<T>::selectSrot(Rank lo, Rank hi) { for(int i=lo;i<hi-1;i++) { int k=lo;//记录最大下标 for(int j=lo+1;j<hi;j++) { if(_elem[j]>_elem[k]) { k=j; } } if(k!=i) { T temp=_elem[k]; _elem[k]=_elem[i]; _elem[i]=temp; } } }