#include "common.h"
/**********************************各種常量及類型定義***********************************/

#define MAX_NUM_OF_KEY 7				//最大關(guān)鍵字?jǐn)?shù)
#define RADIX_n 10						//十進(jìn)制整數(shù)的基數(shù)
#define RADIX_c 26						//26個(gè)字母的基數(shù)
#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;					//關(guān)鍵字類型

typedef struct{
	char carname[15];					//車名		
	char color[10];						//顏色
	char date[10];						//購買日期
	char ownername[15];					//車主
}InfoType;								
typedef struct{
	KeysType keys[MAX_NUM_OF_KEY];		//關(guān)鍵字
	InfoType otheritems;				//其他數(shù)據(jù)項(xiàng)
	int next;							
}SLCell;
typedef struct{
	SLCell r[MAX_SPACE];				//靜態(tài)鏈表的可利用空間,r[0]為頭結(jié)點(diǎn)
	int keynum;							//記錄的當(dāng)前關(guān)鍵字個(gè)數(shù)
	int recnum;							//靜態(tài)鏈表的當(dāng)前長(zhǎng)度
}SLList;								//靜態(tài)鏈表類型	
typedef int ArrType_n[RADIX_n];			//十進(jìn)制指針數(shù)組類型
typedef int ArrType_c[RADIX_c];			//26個(gè)字母的指針數(shù)組類型

/**********************************各種函數(shù)定義*****************************************/

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

void GetData(SLList &L)					
//獲得數(shù)據(jù)
{
	KeysType key='0';
	int j=1;
	cout<<"please input the car number with key='#' to end"<<endl;
	cout<<"Example: 01B3456"<<endl;
	cout<<"car number=";
	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("carname:");
	gets(L.r[1].otheritems.carname);
	printf("color:");
	gets(L.r[1].otheritems.color);
	printf("date:");
	gets(L.r[1].otheritems.date);
	printf("ownername:");
	gets(L.r[1].otheritems.ownername);
	while(key!='#')
	{	
		j++;
		cout<<endl<<"car number=";
		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("carname:");
		gets(L.r[j].otheritems.carname);
		printf("color:");
		gets(L.r[j].otheritems.color);
		printf("date:");
		gets(L.r[j].otheritems.date);
		printf("ownername:");
		gets(L.r[j].otheritems.ownername);
	}//while
	L.recnum=j;
}//GetData

int ord_n(KeysType key)					
//將記錄中第key個(gè)關(guān)鍵字映射到[0..RADIX_n]
{
	return ((int)(key-'0'));
}//ord_n

int ord_c(KeysType key)					
//將記錄中第key個(gè)關(guān)鍵字映射到[0..RADIX_c]
{
	return ((int)((int)key-'A'));
}//ord_c

int succ(int j)							
//求j的后繼函數(shù)
{
	return (j+1);
}//succ

void Distribute_n(SLCell* r,int i,ArrType_n &f,ArrType_n &e)
//靜態(tài)鏈表L的r域中記錄已按(keys[0],...keys[i-1])有序
//本算法按第i個(gè)關(guān)鍵字keys[i]建立RADIX_n個(gè)子表,使同一子表中記錄的keys[i]相同
//f[0..RADIX_n]和e[0..RADIX_n]分別指向各自表中的一個(gè)和最后一個(gè)記錄
{
	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所指的結(jié)點(diǎn)插入第j個(gè)子表中
	}
}//Distribute_n

void Collect_n(SLCell* r,int i,ArrType_n f,ArrType_n e)
//本算法按keys[i]自小至大地將f[0..RADIX_n]所指各子表依次鏈接成一個(gè)鏈表
//e[0..RADIX_n-1]為各子表的尾指針
{
	int j,t;
	for(j=0;!f[j];j=succ(j));		//找第一個(gè)非空子表		
	r[0].next=f[j];t=e[j];			//r[0].next指向第一個(gè)非空子表中的一個(gè)結(jié)點(diǎn)
	while(j<RADIX_n-1)
	{
		for(j=succ(j);j<RADIX_n-1&&!f[j];j=succ(j));	//找下一個(gè)非空子表
		if(f[j]) {r[t].next=f[j];t=e[j];}				//鏈接兩個(gè)非空子表
	}
	r[t].next=0;										//t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn)
}//Collect_n

void Distribute_c(SLCell* r,int i,ArrType_c &f,ArrType_c &e)
//靜態(tài)鏈表L的r域中記錄已按(keys[0],...keys[i-1])有序
//本算法按第i個(gè)關(guān)鍵字keys[i]建立RADIX_c個(gè)子表,使同一子表中記錄的keys[i]相同
//f[0..RADIX_c]和e[0..RADIX_c]分別指向各自表中的一個(gè)和最后一個(gè)記錄
{
	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所指的結(jié)點(diǎn)插入第j個(gè)子表中
	}
}//Distribute_c

void Collect_c(SLCell* r,int i,ArrType_c f,ArrType_c e)
//本算法按keys[i]自小至大地將f[0..RADIX_c]所指各子表依次鏈接成一個(gè)鏈表
//e[0..RADIX_c-1]為各子表的尾指針
{
	int j,t;
	for(j=0;!f[j];j=succ(j));			//找第一個(gè)非空子表
	r[0].next=f[j];t=e[j];				//r[0].next指向第一個(gè)非空子表中的一個(gè)結(jié)點(diǎn)
	while(j<RADIX_c-1)
	{
		for(j=succ(j);j<RADIX_c-1&&!f[j];j=succ(j));	//找下一個(gè)非空子表
		if(f[j]) {r[t].next=f[j];t=e[j];}				//鏈接兩個(gè)非空子表
	}
	r[t].next=0;										//t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn)
}//Collect_c

void RadixSort(SLList &L)
//對(duì)作基數(shù)排序,使得L成為按關(guān)鍵字自小到大的有序靜態(tài)鏈表
{
	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;					//將改造為靜態(tài)鏈表
	for(i=L.keynum-1;i>2;i--)				//按最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配和收集
	{										//分為三段,因?yàn)轫殞⒆址哪莻€(gè)關(guān)鍵字單獨(dú)做
		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)
//根據(jù)靜態(tài)鏈表L中各結(jié)點(diǎn)的指針值調(diào)整記錄位置,使得L中記錄按關(guān)鍵字非遞減
{
	int i,p,q;
	SLCell buf;
	p=L.r[0].next;						//p指示第一個(gè)記錄的當(dāng)前位置
	for(i=1;i<L.recnum;i++)				//L.r[1..i-1]已按關(guān)鍵字有序排列
	{									//第i個(gè)記錄在L中的當(dāng)前位置應(yīng)不小于i
		while(p<i) p=L.r[p].next;		//找到第i個(gè)記錄,并用p指示其在L中的當(dāng)前位置
		q=L.r[p].next;					//q指示尚未調(diào)整的表尾
		if(p!=i)
		{			
			buf=L.r[p];L.r[p]=L.r[i];L.r[i]=buf;	//交換記錄
			L.r[i].next=p;							//指向被移走的記錄,使得以后可由while循環(huán)找回
		}
		p=q;							//p指向尚未調(diào)整的表尾,為找第i+1個(gè)記錄做準(zhǔn)備		
	}
}//Arrange


void SLListTraverse(SLList L)
//遍歷靜態(tài)表
{
	int i,j;
	cout<<endl;
	cout<<"CARNUM"<<'\t'<<"CARNAME"<<'\t'<<"COLOR"<<'\t'<<"DATA"<<'\t'<<"OWNERNAME"<<endl<<endl;
	if(L.recnum)
		for(i=1;i<=L.recnum;i++)
		{
			for(j=0;j<MAX_NUM_OF_KEY;j++) cout<<L.r[i].keys[j];
			cout<<'\t'<<L.r[i].otheritems.carname<<'\t'<<L.r[i].otheritems.color<<'\t';
			cout<<L.r[i].otheritems.date<<'\t'<<L.r[i].otheritems.ownername<<endl;
		}//for
}//SLListTraverse

void DataTraverse(SLList L,int num)
//顯示一個(gè)記錄
{
	int j;
	cout<<"(Note:other data term is peculiarity character)"<<endl;
	cout<<"CARNUM"<<'\t'<<"CARNAME"<<'\t'<<"COLOR"<<'\t'<<"DATA"<<'\t'<<"OWNERNAME"<<endl<<endl;
	for(j=0;j<MAX_NUM_OF_KEY;j++) cout<<L.r[num].keys[j];
	cout<<'\t'<<L.r[num].otheritems.carname<<'\t'<<L.r[num].otheritems.carname<<'\t';
	cout<<L.r[num].otheritems.date<<'\t'<<L.r[num].otheritems.ownername<<endl;
}//DataTraverse

void GetSearchKey(KeysType *key)
//得到需要查找的關(guān)鍵字
{
	cout<<"Please input the key you want to search:";
	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 RandData(SLList &L)
//隨機(jī)生成車牌號(hào),這里將隨機(jī)生成200個(gè)車牌號(hào)
{
	int i,j;
	for(i=1;i<=200;i++)
	{
		for(j=0;j<MAX_NUM_OF_KEY;j++)
		{
			if(j==0) L.r[i].keys[0]=(char)(rand()*4/32768+'0');
			else
			{
				if(j==1&&L.r[i].keys[0]=='3') L.r[i].keys[1]='1';
				else
				{
					if(j==2)
					L.r[i].keys[2]=(char)(rand()*26/32768+'A');
					else L.r[i].keys[j]=(char)(rand()*10/32768+'0');
				}
			}
		}
	}
	L.keynum=7;
	L.recnum=200;
}//RandData

void SLListTraRand(SLList L)
//遍歷隨機(jī)生成的靜態(tài)表
{
	int i,j;
	if(L.recnum)
		for(i=1;i<=L.recnum;i++)
		{
			for(j=0;j<MAX_NUM_OF_KEY;j++) cout<<L.r[i].keys[j];
			cout<<'\t';
		}//for
}//SLListTraRand

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

bool Little(KeysType key1[],KeysType key2[])
//判斷較小
{
	for(int i=0;i<MAX_NUM_OF_KEY;i++)
	{
		if(LT(key1[i],key2[i])) return true;
		else if(BG(key1[i],key2[i])) return false;
	}
	return false;
}//Little

int Search_Bin(SLList L,KeysType key[])
{//二分查找
	int low=1,high=L.recnum,mid;
	while(low<=high){
		mid=(low+high)/2;
		if(Equal(key,L.r[mid].keys)) return mid;
		else if(Little(key,L.r[mid].keys)) high=mid-1;
		else low=mid+1;
	}
	return 0;
}//Search_Bin