sort_all.h

本程序是使用数据结构的算法

#include "commont.h"
/**********************************各种常量及类型定义***********************************/
char data[80];
#define MAX_NUM_OF_KEY  5			//最大关键字数
#define RADIX_n 10						//十进制整数的基数
#define RADIX_c 26						//26个字母的基数
#define MAX_SPACE 2000					//最大链表空间
#define LT(a,b) ((a)<(b))
#define EQ(a,b) ((a)==(b))
#define BG(a,b) ((a)>(b))
typedef char KeysType;					//图书号类型

typedef struct{
	char bookname[60];					//书名称		
	char author[60];				    //作者
	double price;						//书价
	char ISBN[60];					        //ISBN号
	char publishtime[30];                    //出版时间
}InfoType;							
typedef struct LNode{
	KeysType keys[MAX_NUM_OF_KEY];		//关键字
	InfoType otheritems;				//其他数据项
	int next;
}SLCell,Lnode,*LinkList;
Lnode *p,*q;
typedef struct{
	SLCell r[MAX_SPACE];				//静态链表的可利用空间,r[0]为头结点
	int keynum;							//记录的当前关键字个数
	int recnum;							//静态链表的当前长度
}SLList;								//静态链表类型	
typedef int ArrType_n[RADIX_n];			//十进制指针数组类型
typedef int ArrType_c[RADIX_c];			//26个字母的指针数组类型

/**********************************各种函数定义*****************************************/

void InitSLList(SLList &L)				
//链表初始化
{
	L.recnum=0;							
	L.keynum=MAX_NUM_OF_KEY;
}//InitSLList

bool Equal(KeysType key1[],KeysType key2[])
//判断相等
{
	for(int i=0;i<MAX_NUM_OF_KEY;i++)
	{if(!EQ(key1[i],key2[i])) return false;}
	return true;
}//Equal

void GetData(SLList &L)					
//获得数据
{   
	int j=1;
	char numstr[60];
	KeysType key='0';
	cout<<"请输入图书编码,若图书编码为'@'则结束!"<<endl;
//	cout<<"例如: 01b11(5位,若超过5位,系统会自动删除额外的数)"<<endl;
	cout<<"图书编号:";
	for(int i=0;i<MAX_NUM_OF_KEY;i++)
	{
		cin>>key;
		if(i==2&&key>'Z') key=(char)(key-'a'+'A');
		L.r[1].keys[i]=key;
	}
	printf("图书名称:");
	gets(L.r[1].otheritems.bookname);                //修改前
	while(strlen(L.r[1].otheritems.bookname)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("图书名称不能为空,请重新输入:");     //printf比cout快
		gets(L.r[1].otheritems.bookname);
	}
	printf("图书作者:");
	gets(L.r[1].otheritems.author);
	while(strlen(L.r[1].otheritems.author)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("图书作者不能为空,请重新输入:");
		gets(L.r[1].otheritems.author);
	}
	printf("出版时间:");
	gets(L.r[1].otheritems.publishtime);
	while(strlen(L.r[1].otheritems.publishtime)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("出版时间不能为空,请重新输入:");
		gets(L.r[1].otheritems.publishtime);
	}
	printf("ISBN号:");
	gets(L.r[1].otheritems.ISBN);
	while(strlen(L.r[1].otheritems.ISBN)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("ISBN号不能为空,请重新输入:");
		gets(L.r[1].otheritems.ISBN);
	}
	printf("图书单价:");
	gets(numstr);
	while(!(atof(numstr)>0.0))
	{	printf("\a");                     //声音提示
		printf("非法输入,请重新输入:");
		gets(numstr);
	}                                            //抛出输入单价为字符的异常
    L.r[1].otheritems.price=atof(numstr);
	
    
	while(key!='@')
	{	
		j++;
		cout<<endl<<"图书编号:";
		for(int i=0;i<MAX_NUM_OF_KEY;i++)
		{
			cin>>key;
			if(i==2&&key>'Z') key=(char)(key-'a'+'A');
			if(key=='@') {j--;break;}
			L.r[j].keys[i]=key;
		}
	    while(Equal(L.r[j-1].keys,L.r[j].keys))            //抛出重复的异常
		{ printf("\a");                     //声音提示
		  printf("这个图书编号已存在,请重新输入:");
		  for(int i=0;i<MAX_NUM_OF_KEY;i++)
		{
		  cin>>key;
		  if(i==2&&key>'Z') key=(char)(key-'a'+'A');
		  if(key=='@') {j--;break;}
		  L.r[j].keys[i]=key;
		}
		}
		if(key=='@') break;
		printf("图书名称:");
		gets(L.r[j].otheritems.bookname);
	while(strlen(L.r[j].otheritems.bookname)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("图书名称不能为空,请重新输入:");
		gets(L.r[j].otheritems.bookname);
	}
	printf("图书作者:");
	gets(L.r[j].otheritems.author);
	while(strlen(L.r[j].otheritems.author)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("图书作者不能为空,请重新输入:");
		gets(L.r[j].otheritems.author);
	}
	printf("出版时间:");
	gets(L.r[j].otheritems.publishtime);
	while(strlen(L.r[j].otheritems.publishtime)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("出版时间不能为空,请重新输入:");
		gets(L.r[j].otheritems.publishtime);
	}
	printf("ISBN号:");
	gets(L.r[j].otheritems.ISBN);
	while(strlen(L.r[j].otheritems.ISBN)==0)        //抛出输入为空的异常
	{	printf("\a");                     //声音提示
		printf("ISBN号不能为空,请重新输入:");
		gets(L.r[j].otheritems.ISBN);
	}
	printf("图书单价:");
	gets(numstr);
	while(!(atof(numstr)>0.0))
	{	printf("\a");                     //声音提示
		printf("非法输入,请重新输入:");
		gets(numstr);
	}                                            //抛出输入单价为字符的异常
    L.r[j].otheritems.price=atof(numstr);
	}//while
	L.recnum=j;
}//GetData

int ord_n(KeysType key)					
//将记录中第key个关键字映射到[0..RADIX_n]
{
	return ((int)(key-'0'));
}//ord_n

int ord_c(KeysType key)					
//将记录中第key个关键字映射到[0..RADIX_c]
{
	return ((int)((int)key-'A'));
}//ord_c

int succ(int j)							
//求j的后继函数
{
	return (j+1);
}//succ

void Distribute_n(SLCell* r,int i,ArrType_n &f,ArrType_n &e)
//静态链表L的r域中记录已按(keys[0],...keys[i-1])有序
//本算法按第i个关键字keys[i]建立RADIX_n个子表,使同一子表中记录的keys[i]相同
//f[0..RADIX_n]和e[0..RADIX_n]分别指向各自表中的一个和最后一个记录
{
	int j,p;
	for(j=0;j<RADIX_n;j++)			//各子表初始化为空表
	{
		f[j]=0;
		e[j]=0;
	}
	for(p=r[0].next;p;p=r[p].next)
	{
		j=ord_n(r[p].keys[i]);
		if(!f[j]) f[j]=p;
		else r[e[j]].next=p;
		e[j]=p;						//将p所指的结点插入第j个子表中
	}
}//Distribute_n

void Collect_n(SLCell* r,int i,ArrType_n f,ArrType_n e)
//本算法按keys[i]自小至大地将f[0..RADIX_n]所指各子表依次链接成一个链表
//e[0..RADIX_n-1]为各子表的尾指针
{
	int j,t;
	for(j=0;!f[j];j=succ(j));		//找第一个非空子表		
	r[0].next=f[j];t=e[j];			//r[0].next指向第一个非空子表中的一个结点
	while(j<RADIX_n-1)
	{
		for(j=succ(j);j<RADIX_n-1&&!f[j];j=succ(j));	//找下一个非空子表
		if(f[j]) {r[t].next=f[j];t=e[j];}				//链接两个非空子表
	}
	r[t].next=0;										//t指向最后一个非空子表中的最后一个结点
}//Collect_n

void Distribute_c(SLCell* r,int i,ArrType_c &f,ArrType_c &e)
//静态链表L的r域中记录已按(keys[0],...keys[i-1])有序
//本算法按第i个关键字keys[i]建立RADIX_c个子表,使同一子表中记录的keys[i]相同
//f[0..RADIX_c]和e[0..RADIX_c]分别指向各自表中的一个和最后一个记录
{
	int j,p;
	for(j=0;j<RADIX_c;j++)				//各子表初始化为空表
	{
		f[j]=0;
		e[j]=0;
	}
	for(p=r[0].next;p;p=r[p].next)
	{
		j=ord_c(r[p].keys[i]);
		if(!f[j]) f[j]=p;
		else r[e[j]].next=p;
		e[j]=p;							//将p所指的结点插入第j个子表中
	}
}//Distribute_c

void Collect_c(SLCell* r,int i,ArrType_c f,ArrType_c e)
//本算法按keys[i]自小至大地将f[0..RADIX_c]所指各子表依次链接成一个链表
//e[0..RADIX_c-1]为各子表的尾指针
{
	int j,t;
	for(j=0;!f[j];j=succ(j));			//找第一个非空子表
	r[0].next=f[j];t=e[j];				//r[0].next指向第一个非空子表中的一个结点
	while(j<RADIX_c-1)
	{
		for(j=succ(j);j<RADIX_c-1&&!f[j];j=succ(j));	//找下一个非空子表
		if(f[j]) {r[t].next=f[j];t=e[j];}				//链接两个非空子表
	}
	r[t].next=0;										//t指向最后一个非空子表中的最后一个结点
}//Collect_c

void RadixSort(SLList &L)
//对作基数排序,使得L成为按关键字自小到大的有序静态链表
{
	int i;
	ArrType_n fn,en;
	ArrType_c fc,ec;
	for(i=0;i<L.recnum;i++) L.r[i].next=i+1;
	L.r[L.recnum].next=0;					//将改造为静态链表
	for(i=L.keynum-1;i>2;i--)				//按最低位优先依次对各关键字进行分配和收集
	{										//分为三段,因为须将字符的那个关键字单独做
		Distribute_n(L.r,i,fn,en);
		Collect_n(L.r,i,fn,en);
	}
	Distribute_c(L.r,2,fc,ec);
	Collect_c(L.r,2,fc,ec);
	for(i=1;i>=0;i--)
	{
		Distribute_n(L.r,i,fn,en);
		Collect_n(L.r,i,fn,en);
	}
}//RadixSort

void Arrange(SLList &L)
//根据静态链表L中各结点的指针值调整记录位置,使得L中记录按关键字非递减
{
	int i,p,q;
	SLCell buf;
	p=L.r[0].next;						//p指示第一个记录的当前位置
	for(i=1;i<L.recnum;i++)				//L.r[1..i-1]已按关键字有序排列
	{									//第i个记录在L中的当前位置应不小于i
		while(p<i) p=L.r[p].next;		//找到第i个记录,并用p指示其在L中的当前位置
		q=L.r[p].next;					//q指示尚未调整的表尾
		if(p!=i)
		{			
			buf=L.r[p];L.r[p]=L.r[i];L.r[i]=buf;	//交换记录
			L.r[i].next=p;							//指向被移走的记录,使得以后可由while循环找回
		}
		p=q;							//p指向尚未调整的表尾,为找第i+1个记录做准备		
	}
}//Arrange
	
void SLListTraverse(SLList L)
//遍历静态表
{
	int i,j;
	cout<<endl;
	cout<<"图书编码"<<'\t'<<"图书名称"<<'\t'<<"图书作者"<<'\t'<<"出版时间"<<'\t'<<"ISBN号"<<'\t'<<"书价"<<endl;
 
	if(L.recnum)
		for(i=1;i<=L.recnum;i++)
		{	cout<<"──────────────────────────────────────"<<endl;
			for(j=0;j<MAX_NUM_OF_KEY;j++) cout<<L.r[i].keys[j];
			cout<<'\t'<<'\t'<<L.r[i].otheritems.bookname<<'\t'<<'\t'<<L.r[i].otheritems.author<<'\t'<<'\t';
			cout<<L.r[i].otheritems.publishtime<<'\t'<<'\t'<<L.r[i].otheritems.ISBN<<'\t'<<L.r[i].otheritems.price<<endl;
		}//for
}//SLListTraverse

void DataTraverse(SLList L,int num)
//显示一个记录
{
	int j;
    cout<<"图书编码"<<'\t'<<"名称"<<'\t'<<"     作者"<<'\t'<<"   出版时间"<<'\t'<<"    ISBN号"<<'\t'<<"   书价"<<endl;
    cout<<"──────────────────────────────────────"<<endl;
	for(j=0;j<MAX_NUM_OF_KEY;j++) cout<<L.r[num].keys[j];
	cout<<'\t'<<'\t'<<L.r[num].otheritems.bookname<<'\t'<<'\t'<<L.r[num].otheritems.author<<'\t'<<'\t';
			cout<<L.r[num].otheritems.publishtime<<'\t'<<'\t'<<L.r[num].otheritems.ISBN<<'\t'<<L.r[num].otheritems.price<<endl;
}//DataTraverse

void GetSearchKey(KeysType *key)
//得到需要查找的图书号
{
	cout<<"请输入你要的图书的图书编码(5位):";
	for(int i=0;i<MAX_NUM_OF_KEY;i++) cin>>key[i];
	if(key[2]>'Z') key[2]=(char)(key[2]-'a'+'A');
}//GetSearchKey

void GetSearchEquiname(SLList L,KeysType *key)