vector.h

数据结构各种算法的比较程序

#ifndef VECTOR
#define VECTOR
//基本向量类（包含排序向量各种操作）
//-------------------------------------------------------------------------------------------
#include"iostream"
#include"assert.h"
#include"queue.h"
using namespace std;
template<class T>class vector
{
public:
	vector();
	vector(unsigned num);
	vector(unsigned num,T value);
	vector(const vector<T>& vec);
	virtual~vector();
	T& operator[](unsigned num)const;
	vector<T>& operator =(const vector<T>&);
	unsigned Setsize(unsigned num);
	unsigned Setsize(unsigned num,T value);
	unsigned length()const;
	friend ostream& operator <<(ostream& out,vector<double>& vec);
	unsigned binarySearch(T value);
	unsigned include(T value);
	void add(T value);
	void remove(T value);
	void ShowValues();
protected:
	T* data;
	unsigned size;
};
template<class T> vector<T>::vector(){};
template<class T> vector<T>::vector(unsigned num)
{
	size=num;
	data=new T[size];
	assert(data!=0);
}
template<class T> vector<T>::vector(unsigned num, T value)
{
	size=num;
	data=new T[size];
	assert(data!=0);
	for(unsigned i=0;i<=num-1;i++)
		data[i]=value;
}
template<class T> vector<T>::vector(const vector<T> &vec)
{
	size=vec.size;
	data=new T[size];
	assert(data!=0);
	for(unsigned i=0;i<size;i++)
		data[i]=vec.data[i];
}
template<class T> vector<T>::~vector()
{
	delete[]data;
	data=0;
	size=0;
}
template<class T> T& vector<T>::operator [](unsigned num)const
{
	assert(num<size);
	return data[num];
}
template<class T> vector<T>& vector<T>::operator =(const vector<T> &vec)
{
	if(size!=vec.size)
	{
		T* np=new T[vec.size];
		assert(np!=0);
		delete[]data;
		data=np;
		size=vec.size;
	}
	for(unsigned i=0;i<size;i++)
		data[i]=vec.data[i];
	return *this;
}
template<class T> unsigned vector<T>::Setsize(unsigned  num)
{
	if(num!=size)
	{
		T* np=new T[num];
		assert(np!=0);
		unsigned n=size<=num?size:num;
		for(unsigned i=0;i<n;i++)
			np[i]=data[i];
		delete[]data;
		data=np;
		size=num;
	}
	return size;
}
template<class T> unsigned vector<T>::Setsize(unsigned num, T value)
{
	if(num!=size)
	{
		T* np=new T[num];
		assert(np!=0);
		unsigned i=0;
		while(i<num)
		{
			np[i]=value;
			i++;
		}
		unsigned n=size<=num?size:num;
		for(unsigned z=0;z<n;z++)
			np[z]=data[z];
		delete[]data;
		data=np;
		size=num;
	}
	return size;
}
template<class T> unsigned vector<T>::length() const
{
	return size;
}
template<class T> ostream& operator <<(ostream &out, vector<T>& vec)
{
	for(unsigned i=0;i<vec.length();i++)
		out<<vec[i];
	return out;
}
template<class T> unsigned vector<T>::binarySearch(T value)
{	
	unsigned low=0;
	unsigned high=size;
	while(low<high)
	{
		unsigned mid=(low+high)/2;
		if(data[mid]==value)return mid;
		else if(data[mid]<value)
			low=mid+1;
		else high=mid;
	}
	return low;
}
template<class T> unsigned vector<T>::include(T value)
{
	unsigned index=binarySearch(value);
	unsigned max=length();
	if(index<max && value==data[index])
		return 1;
	else return 0;
}
template<class T> void vector<T>::add(T value)
{
	unsigned index=binarySearch(value);
	unsigned max=length();
	this->Setsize(max+1);
	for(unsigned i=max;i>index;i--)
		data[i]=data[i-1];
	data[index]=value;
}
template<class T> void vector<T>::remove(T value)
{
	unsigned index=binarySearch(value);
	unsigned max=length();
	if(index<max&&data[index]==value)
	{
		for(unsigned i=index;i<max-1;i++)
			data[i]=data[i+1];
		this->Setsize(max-1);
	}
	else cout<<"no such value";
}
template<class T>void vector<T>::ShowValues()
{
	int z=0;
	while(z<100)
	{
	cout<<"  "<<data[z]<<"  ";
	z++;
	}
}
//作业2remove函数
//----------------------------------------------------------------//模板函数
template<class T> void swap(vector<T> & vec, unsigned i, unsigned j)
{
	T temp=vec[i];
	vec[i]=vec[j];
	vec[j]=temp;
}
//----------------------------------------------------------------插入排序
template<class T> void insertionSort(vector<T> &vec)
{
	int num=0,mov=0;
	unsigned n=vec.length();
	T temp;
	for(unsigned i=1;i<n;i++)
	{
		temp=vec[i];
		for(unsigned j=i;j>0&&vec[j]<vec[j-1];j--,num++)//比较次数+1
		{
			vec[j]=vec[j-1];
			vec[j-1]=temp;
			mov+=3;//移动次数+3
		}
	}
	cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------插入排序
//----------------------------------------------------------------冒泡排序
template<class T> void bubbleSort(vector<T> &vec)
{
	int top,i,num=0,mov=0;
	for(top=vec.length()-1;top>0;top--)
	{
		for(i=0;i<top; i++,num++)//比较次数+1
			if(vec[i]>vec[i+1])
			{
				swap(vec,i,i+1);//i和i+1换
				mov+=3;//移动次数+3
			}
	}
	cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------冒泡排序
//----------------------------------------------------------------选择排序
template<class T>void selectionSort(vector<T>&vec)
{
	int largest,top,j;
	int num=0,mov=0;
	for(top=vec.length()-1;top>0;top--)
	{
	
		for(largest=0,j=1;j<=top;j++,num++)
		{
			if(vec[largest]<vec[j])
				largest=j;
			
		}
		if(top!=largest)
		{
			swap(vec,top,largest);
		    mov+=3;
		}
	}
	
    cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------选择排序
//----------------------------------------------------------------快速排序
template<class T> int partition(vector<T>& vec,int low,int high,int &qnum,int &qmov)
{
	T pivot=vec[low];
	while(low<high)
	{
		while(low<high&&vec[high]>=pivot)//找到第一个比pivot小的vec[high]赋值给vec[low],关键字移动了一次qmov+3
		{
			high--;
			qnum++;
		}
		if(low<high){
			qnum++;
		vec[low]=vec[high];
		low++;
		qmov+=3;
		}
		while(low<high&&vec[low]<=pivot)//找到比pioot大的赋值给vec[high]
		{
			low++;
			qnum++;
		}
		if(low<high){
			qnum++;
		vec[high]=vec[low];
		high--;
		qmov+=3;
		}
	}
	vec[high]=pivot;
	return high;
}//循环结束后piovt左边的比它小，右边的比他大
template<class T> void quickSort(vector<T>& vec,int low,int high,int &qnum,int &qmov)
{
	if(low>=high) return;
	int mIndex=partition(vec,low,high,qnum,qmov);
	quickSort(vec,low,mIndex-1,qnum,qmov);//将low到mIndex-1再做一次排序
	quickSort(vec,mIndex+1,high,qnum,qmov);//将mIndex+1到high再做一次排序,分成了前后两部分，如此递归下去
}
template<class T> void quickSort(vector<T> &vec)
{
	int qnum=0;
	int qmov=0;
	quickSort(vec,0,vec.length()-1,qnum,qmov);
	cout<<"关键字比较了"<<qnum<<"次"<<endl;
	cout<<"关键字移动了"<<qmov<<"次"<<endl;
}
//----------------------------------------------------------------快速排序
//----------------------------------------------------------------归并排序
template <class T> 
void  MergeSort ( vector<T> &v1 ) {
//按对象排序码非递减的顺序对表中对象排序
    vector <T> tempList( v1.length() );
	int num=0,mov=0;
	int CurrentSize=v1.length();
    int len = 1;
    while ( len < CurrentSize ) {
         MergePass ( tempList, len,v1 ,num,mov);   len *= 2;
	     MergePass ( v1, len,tempList ,num,mov);   len *= 2;
    }
	cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
template <class T> 
void MergePass ( vector<T> & mergedList,
       const int len, vector<T> &v1 ,int &num,int &mov) {
       int i = 0;
	   int CurrentSize=v1.length();
       while (i+2*len <= CurrentSize-1) {
         merge(mergedList, i, i+len-1, i+2*len-1, v1,num,mov);
         i += 2 * len;                //循环两两归并
    }
    if ( i+len <= CurrentSize-1 )
       merge(mergedList, i, i+len-1, CurrentSize-1,v1,num,mov);
    else for ( int j = i; j <= CurrentSize-1; j++)
	{
               mergedList[j] = v1[j];
			   mov++;
	}
} 
template <class T> 
void merge ( vector <T> & mergedList, const int
left,  const int mid,  const int right, vector <T> & v1,int &num,int &mov) {
    int i = left,  j = mid+1,  k = left ;		
    while ( i <= mid && j <= right )   //两两比较
        if ( v1[i] <= v1[j] ) {
			num++;
            mergedList[k] = v1[i];//mergeList=v1[]中较小的那个i，j。将较小的v1赋值给mergeList后下标++
			mov++;
	   i++;  k++;
        }
        else {
			num++;
			mov++;
            mergedList[k] = v1[j]; 
            j++;  k++;
        }
    if ( i <= mid )
        for ( int n1 = k, n2 = i; n2 <= mid; n1++, n2++ )
		{
              mergedList [n1] = v1[n2];
			  mov++;
		}
    else
       for ( int n1 = k, n2 = j;  n2 <= right; n1++, n2++)
	   {
	    mergedList[n1] = v1[n2];
		mov++;
       }
}
//----------------------------------------------------------------归并排序
//----------------------------------------------------------------堆排序
template <class T>
void heapSort(vector<T> &data)
{
	int num=0,mov=0;
     unsigned int max = data.length();
     //循环调用buildHeap构造第一个堆
     for (int i = max/2 -1; i>=0; i--)
        buildHeap(data,max,i,num,mov);
     for (int j = max-1; j>0; j--)
     { //将最小的元素与第一个交换
         swap(data,j,0);
		 mov+=3;//移动次数为三
         buildHeap(data,j,0,num,mov);//重建新的堆
     }
	 cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
template <class T>
void buildHeap(vector<T> &data, unsigned int heapsize, 
                                                                     unsigned int position,int &num,int &mov)
{  //以position 为根的二叉树进行重建
    T value = data[position];
    while (position < heapsize)
   {
       unsigned int childpos = position*2 + 1;
       if (childpos < heapsize)
       {
            if ( (childpos+1< heapsize)&& 
                              data[childpos+1]<data[childpos])
			{
				num++;
                  childpos += 1;    
			}
                  // 找出childpos子结点中较小的一个  
            if (value<data[childpos])
             {   // 找到适当的位置
                 data[position] = value; 
				 num++;mov+=3;
                 return; 
              } 
           else
            {   //找不到适当的位置则空位下移
                data[position] = data[childpos];
				mov+=3;num++;
                position = childpos;  
              }  
       } 
     else   // childpos > heapsize，说明已经到达叶子结点
      {
           data[position]  = value;
           return;
       }
   } 
 } 
//----------------------------------------------------------------堆排序
//----------------------------------------------------------------计数排序
template<class T> 
void RankSort(vector<T> & vec) 
{
	int num=0,mov=0;
	int n=vec.length();
	vector<T> count(n);//新建一个可保存的向量
		int i=0;
	while(i<n)   
	{
		int nt=0;
		for(int z=0;z<n;z++)//计数向量中有几个比vec[i]大的，记录在nt中
		{
			num++;
			if(vec[i]<vec[z])
			nt++;
		}
		while(count[nt]==vec[i])//若出现相同两个数据时存放在后面，将vec[i]存放在count的第nt位上
			nt++;
		    count[nt]=vec[i];
		    mov++;
		    i++;
	    }
	    for(int j=0;j<n;j++)//复制，将排序好的count向量复制给vec
	    {
		    vec[j]=count[j];
		    mov++;
	    }
	cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------计数排序
//----------------------------------------------------------------基数排序
template <class T>
void RadixSort(vector<T> & vec)
{
	int num=0,mov=0;
	Listqueue<int> q,q0,q1,q2,q3,q4,q5,q6,q7,q8,q9;
	int n=vec.length(),temp1,temp;
	int i=1;
	for(int k=0;k<n;k++)
	{
		q.enqueue (vec[k]);//所有元素依次进栈
		mov++;
	}
	while(i<4)//令元素不超过四位
	{
		while(!q.isEmpty())//队列不空，进行下面操作
		{
		temp1=q.dequeue();
		if(i==1) temp=temp1%10;//第一趟，比较个位
		else if(i==2) temp=(temp1/10)%10;//第二趟，比较十位
		else temp=(temp1/10/10)%10;//第三趟，比较百位
	    if(temp==0) q0.enqueue(temp1);//temp与下标相等，原元素进栈
		else if(temp==1) q1.enqueue(temp1);
		else if(temp==2) q2.enqueue(temp1);
		else if(temp==3) q3.enqueue(temp1);
		else if(temp==4) q4.enqueue(temp1);
		else if(temp==5) q5.enqueue(temp1);
		else if(temp==6) q6.enqueue(temp1);
		else if(temp==7) q7.enqueue(temp1);
		else if(temp==8) q8.enqueue(temp1);
		else q9.enqueue(temp1);
		num+=temp;
		mov+=2;
	    }
	    while(!q0.isEmpty()) q.enqueue(q0.dequeue());//q0不空，q0中元素逐一压入q中
		while(!q1.isEmpty()) q.enqueue(q1.dequeue());//q1不空，q1中元素逐一压入q中
	    while(!q2.isEmpty()) q.enqueue(q2.dequeue());//q2不空，q2中元素逐一压入q中
		while(!q3.isEmpty()) q.enqueue(q3.dequeue());//q3不空，q3中元素逐一压入q中
		while(!q4.isEmpty()) q.enqueue(q4.dequeue());//q4不空，q4中元素逐一压入q中
		while(!q5.isEmpty()) q.enqueue(q5.dequeue());//q5不空，q5中元素逐一压入q中
		while(!q6.isEmpty()) q.enqueue(q6.dequeue());//q6不空，q6中元素逐一压入q中
		while(!q7.isEmpty()) q.enqueue(q7.dequeue());//q7不空，q7中元素逐一压入q中
		while(!q8.isEmpty()) q.enqueue(q8.dequeue());//q8不空，q8中元素逐一压入q中
		while(!q9.isEmpty()) q.enqueue(q9.dequeue());//q9不空，q9中元素逐一压入q中
	    i++;
		mov+=100;
	    }
	for(int l=0;l<n;l++)
	{
		vec[l]=q.dequeue();//q中元素出栈，进入向量，排序完成
		mov++;
	}
    cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------基数排序
//----------------------------------------------------------------希尔排序
template<class T> 
void ShellSort(vector<T> & vec)
{
	int num=0,mov=0;
	int n = vec.length();
	for (int mid = n/2; mid; mid = mid/2)
	{
		for (int i = mid; i < n; i++)
		{
			int temp = vec[i];
			int j;
			for (j = i; j >= mid && temp < vec[j - mid]; j -= mid)
			{ 			
				num++;//比较一次
				vec[j] = vec[j - mid];
				mov++;//移动一次
			}
			num++;//比较一次
			vec[j] = temp;
			mov++;//移动一次
		}
	}
    cout<<"关键字比较了"<<num<<"次"<<endl;
	cout<<"关键字移动了"<<mov<<"次"<<endl;
}
//----------------------------------------------------------------希尔排序
#endif