车务管理模型算法实现如下
#include "common.h"
/**********************************各种常量及类型定义***********************************/
#define MAX_NUM_OF_KEY 7 //最大关键字数
#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 carname[15]; //车名
char color[10]; //颜色
char date[10]; //购买日期
char ownername[15]; //车主
}InfoType;
typedef struct{
KeysType keys[MAX_NUM_OF_KEY]; //关键字
InfoType otheritems; //其他数据项
int next;
}SLCell;
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
void GetData(SLList &L)
//获得数据
{
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个关键字映射到[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<<"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)
//显示一个记录
{
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)
//得到需要查找的关键字
{
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)
//随机生成车牌号,这里将随机生成200个车牌号
{
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)
//遍历随机生成的静态表
{
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