main.cpp

清华文件 考研用. Distribution of this memo is unlimite

#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
	类名称：Node
	类功能：将输入的string以node形式组织起来，便于在LSD时进行分和收的操作
	与其它类的继承和调用关系：无
*/
class Node{
public:
	string key;		//输入的英文单词
	int next;		//指向排序后该单词的后一个单词在数组的位置
};
/*
	类名称：StaticQueue
	类功能：定义出在收集时每个桶的数据结构
	与其它类的继承和调用关系：无
*/
class StaticQueue{
public:
	int head;	//指向当前关键码所对应桶的第一个元素在数组中的下标，-1标记为无
	int tail;	//指向当前关键码所对应桶的最后一个元素在数组中的下标，-1标记为无
};
/*
	类名称：RadixSorter
	类功能：将所有解决英文单词按基数排序的函数，数据封装在一个类中
	与其它类的继承和调用关系：调用Node类，将Node类作为所输入的英文单词在vector中的组织形式
*/
class RadixSorter{
public:
	RadixSorter():size(53){init();};	//构造函数
	void init();		//对输入进行初始化的函数
	void DoSort();		//对输入的数据进行基数排序的函数
	void PrintString(int );		//输出数组中排序的结果
private:
	void Setlength();		//将所有的输入的字母调整为定长
	void Distribute(int  , int  ,StaticQueue * );	//LSD中分的函数
	void Collect(int & , StaticQueue *);		//LSD中收的函数
	inline int GetKeynumber(char);		//返回当前字符对应关键码的桶的位置
	const int size;			//桶的多少
	int stringnumber;		//记录所输入数据的总数
	int length;				//记录给定的最长的字符
	vector<Node> Myvector;	//存储所有输入的数据
};
/*
	函数名：init
	函数功能：处理给定的输入，并且将输入的string以Node的形式组织在数组里，便于处理
*/
void RadixSorter::init (){
	cout<<"please enter the max length of the string"<<endl;
	cin>>length;	//最大的单词长度
	string tempstring;	
	Node tempnode ;
	cout<<"please enter the number of the string"<<endl;
	cin>>stringnumber;
	int i=0;
	while(i++<stringnumber){
		cin>>tempstring;
		tempnode.key=tempstring;
		tempnode.next=i;
		Myvector.push_back (tempnode);
	}
}
/*
	函数名：GetKeynumber
	函数功能：根据传入字符，返回其所对应的桶的编号，其对应原则是
	如果是结束符，那么在第0个桶，其余字母按顺序，A-Z在1-26，a-z在27-52
	参量意义：所传入，当前需要做排序处理的字符
*/
inline int RadixSorter::GetKeynumber(char a){
	if(a=='\0')
		return 0;
	else
		if(a>='A'&&a<='Z')
			return a-'A'+1;
		else
			if(a>='a'&&a<='z')
				return a-'a'+27;
}
/*
	函数名：PrintString
	函数功能：根据排序后的顺序输出序列
	参量意义：从某个给定的位置first开始打印数组
*/
void RadixSorter::PrintString (int first){
	int i=first;
	while(i!=-1){
		cout<<Myvector[i].key <<" ";
		i=Myvector[i].next ;
	}
	cout<<endl;
}
/*
	函数名：Distribute
	函数功能：实现LSD中分的功能，将当前序列分到桶中
	参数意义：first：当前序列起始元素的在数组中的序号
			  step：当前排序的字符串的位数
			  queue：用于实现这些桶的静态链
*/
void RadixSorter::Distribute (int first , int step , StaticQueue * queue){
	for(int i=0;i<size;i++)
		queue[i].head =-1;		//对静态链中元素的初始化
	int begin=first;			//begin为当前处理元素在数组中的下标
	while(begin!=-1){
		string temp=Myvector[begin].key ;
		int position=GetKeynumber(temp[step]);	//position为当前第step位关键字所在桶的序号
		if(queue[position].head ==-1)
			queue[position].head =begin;		//子序列为空，则当前记录为第一个记录
		else
			Myvector[queue[position].tail].next=begin;	//否则加到子序列尾部
		queue[position].tail=begin;			//当前记录为序列的尾部
		begin=Myvector[begin].next ;		//继续分配下一个记录
	}
}
/*
	函数名：Collect
	函数功能：实现LSD中收的功能，将分好的桶合在一块成为整个序列
	参数意义：first:合并完成后，序列的首元素
			  queue:用于实现桶的静态链
*/
void RadixSorter::Collect (int & first  , StaticQueue * queue){
	int k=0;
	while(queue[k].head ==-1)	//找到第一个非空的桶
		k++;
	first=queue[k].head ;		//第一个非空的桶的首元素为新序列的首元素
	int last=queue[k].tail ;
	while(k<size-1){			
		k++;
		while(k<size-1&&queue[k].head==-1) k++;		//继续收集下一个非空的桶
		if(queue[k].head !=-1)
		{
			Myvector[last].next =queue[k].head ;	//将这个序列与上一个非空的序列连接起来
			last=queue[k].tail ;
		}
	}
	Myvector[last].next =-1;		//对最后一个元素作标记
}
/*
	函数名：SetLength
	函数功能：将所有输入的单词调整成为给定的最长长度的单词的长度，多出的部分补\0
*/
void RadixSorter::Setlength (){
	vector<Node>::iterator i=Myvector.begin ();
	for(;i!=Myvector.end ();i++)
	{
		if((*i).key.length()<length)
		{
			string::iterator i_string=(*i).key.end ();
			for(int j=0;j<length-(*i).key.length() ;j++)
			{
				(*i_string)='\0';		//对多余部分补\0
				i_string++;}
		}
	}
}
/*
	函数名：DoSort
	函数功能：用LSD的基数排序处理输入的所有单词
*/
void RadixSorter::DoSort (){
	Setlength();	//预处理，将当前所有的单词调成给定的长度
	StaticQueue  * queue=new StaticQueue[size];		//申请实现桶的静态链
	Myvector[stringnumber-1].next =-1;		//对序列最后一个元素进行标记
	cout<<"before sorting"<<endl;
	PrintString(0);
	int first=0;
	for(int j=length-1;j>=0;j--)	//一共处理n布
	{
		Distribute(first , j , queue);
		Collect(first  ,queue);
	}
	PrintString(first);
	delete []queue;		

}
int main(){
	RadixSorter mysort;
	mysort.DoSort ();
	return 1;
}