車務管理模型算法實現如下
[cpp]
#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
