06010203.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist";
		exit(1);
	}
	ofstream out("output.txt");
//////////////////////////////////////////////////////
//冒泡排序
template<class T>
void BubbleSort(T a[],int n)
{
	for(int i=n;i>1;i--)
		for(int j=0;j<i-1;j++)
			if(a[j]>a[j+1])
				Swap(a[j],a[j+1])
}

template<class T>
inline void Swap(T&a,T&b)
{
	//交换a与b的值
	T temp=a;
	a=b;
	b=temp;
}

//////////////////////////////////////////////////////
//插入排序
template<class T>
void Insert(T a[],int n,const T&x)
{
    //元素插入数组
	int i;
	for(i=n-1;i>=0&&x<a[i];i--)
		a[i+1]=a[i];
	a[i+1]=x;
}

template<class T>
void InsertionSort(T a[],int n)
{
    //插入排序算法
	for(int i=1;i<n;i++)
	{
		T t=a[i];
	    Insert(a,i,t);
	}
}
////////////////////////////////////////////////////////
//选择排序
template<class T>
int Max(T a[],int n)
{
    //确定中最大元素下标
	int pos=0;
	for(int i=1;i<n;i++)
		if(a[pos]<a[i])
			pos=i;
    return pos;
}

template<class T>
void SelectionSort(T a[],int n)
{
    //选择排序算法
	for(int size=n;size>1;size--)
	{
		int j=Max(a,size);
		Swap(a[j],a[size-1]);
	}
}

////////////////////////////////////////////////////////
//快速排序算法
template<class T>
void QuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);//对左半段排序
		QuickSort(a,q+1,r);//对右半段排序
	}
}

template<class T>
int Partition(T a[],int p,int r)
{
	int i=p,
		j=r+1;
	T x=a[p];
    //将<=x的元素交换到左边区域
    //将>=x的元素交换到右边区域
	while(true)
	{
		while(a[++i]<x&&i<r);
		while(a[--j]>x);
		if(i>=j) break;
		Swap(a[i],a[j]);
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}

/////////////////////////////////////////////////////////////
//随机快速排序算法
template<class T>
int RandomizePartition(T a[],int p,int r)
{
	int i=Random(p,r);
	Swap(a[i],a[p]);
	return Partition(a,p,r);
}
template<class T>
void RandomizedQuickSort(T a[],int p,int r)
{
	if(p<r)
	{
		int q=RandomizePartition(a,p,r);//对左半段排序
		RandomizedQuickSort(a,p,q-1);//对右半段排序
	}
}

/////////////////////////////////////////////////////////////
//合并排序算法
template<class T>
void MergeSort(T a[],int left,int right)
{
	if(left<right)
	{
         //至少有2个元素
		int i=(left+right)/2;//取中点
		MergeSort(a,left,i);
		MergeSort(a,i+1,right);
		Merge(a,b,left,i,right);//合并到数组b
		Copy(a,b,left,right);//复制回数组a
	}
}

////////////////////////////////////////////////////////////////////
//消除递归
template<class T>
void MergeSort(T a[],int n)
{
	T*b=new T[n];
	int s=1;
	while(s<n)
	{
		MergePass(a,b,s,n);//合并到数组b
		s+=s;
		MergePass(b,a,s,n);//合并到数组a
		s+=s;
	}
}

template<class T>
void MergePass(T x[],T y[],int s,int n)
{ 
	//合并大小为s的相邻子数组
	int i=0;
	while(i<=n-2*s)
	{
		//合并大小为s的相邻2段子数组
		Merge(x,y,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}

	//剩下的元素个数少于2s
	if(i+s<n)
		Merge(x,y,i,i+s-1,n-1);
	else for(int j=i;j<=n-1;j++)
		y[j]=x[j];
}


template<class T>
void Merge(T c[],T d[],int l,int m,int r)
{ 
	//合并c[l:m]和c[m+1:r]到d[l:r]
	int i=l,
		j=m+l,
		k=l;
	
	while((i<=m)&&(j<=r))
		if(c[i]<=c[j])
			d[k++]=c[i++];
		else  d[k++]=c[j++];
		if(i>m)
			for(int q=j;q<=r;q++)
				d[k++]=c[q];
		else for(int q=i;q<=m;q++)
			d[k++]=c[q];
}

///////////////////////////////////////////////////////////////////
//计数排序
void CountingSort(int a[],int n,int m,int b[])//m为a[]中那个最大的值
{
	//计数排序算法
	int c[m+1];
	for(int i=0;i<=m;i++)
		c[i]=0;
	for(i=0;i<n;i++)
		c[a[i]]+=1;
    //c[i]中存放的是a中键值等于i的元素个数
	for(i=1;i<=m;i++)
		c[i]+=c[i-1];
    //c[i]中存放的是a中键值小于或等于i的元素个数
	for(i=n;i>0;i--)
	{
		b[c[a[i-1]]-1]=a[i-1];
		c[a[i-1]]-=1;
	}
}

//////////////////////////////////////////////////////////////////
//桶排序
template<class T>
void List<T>::BinSort(int m)
{
    //桶排序算法
	int b;//桶下标
	Node<T> **bottom,**top;
    //桶初始化
	bottom=new Node<T> *[m+1];
	top=new Node<T> *[m+1];
	for(b=0;b<=m;b++)
		bottom[b]=0;
    //将元素装入桶中
	for(;first;first=first->next)
	{
		b=first->element;
		if(bottom[b])
		{
			//桶非空
			top[b]->next=first;
			top[b]=first;
		}
		else//桶空
			bottom[b]=top[b]=first;
	}
    //按桶的顺序将桶中元素顺序连接在一起
	Node<T> *p=0;
	for(b=0;b<=m;b++)
		if(bottom[b])
		{
			//桶非空
			if(p)//不是第一个非空桶
				p->next=bottom[b];
			else//第一个非空桶
				first=bottom[b];
			p=top[b];
		}
	if(p) 
		p->next=0;
	delete [] bottom;
	delete [] top;
}

/////////////////////////////////////////////////////
//平均情况下的线性时间选择算法
template<class T>
T RandomizedSelect(T a[],int p,int r,int k)
{
	if(p==r) return a[p];
	int i=RandomizedPartition(a,p,r),
		j=i-p+1;
	if(k<=j) return RandomizedSelect(a,p,i,k);
	else return RandomizedSelect(a,i+1,r,k-j);
}

////////////////////////////////////////////////////////
//最坏情况下的线性时间选择算法
template<class T>
T Select(T a[],int p,int r,int k)
{
	if(r-p<75)
	{
		//用某个简单排序算法对数组排序；
		return a[p+k-1];
	}
	for(int i=0;i<=(r-p-4)/5;i++)
		//将a[p+5*i]至a[p+5*i-4]的第3小元素与a[p+i]交换位置
		//找中位数的中位数，r-p-4即上面所说的n-5
	T x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);
	int i=Partition(a,p,r,x),
		j=i-p+1;
	if(k<=j) return Select(a,p,i,k);
	else return Select(a,i+1,r,k-j);
}