?? 航班.cpp
字號:
#include <stdio.h>
#include <string.h>
#define MaxSpace 100
#define keylen 6
#define Radix_n 10
#define Radix_c 26
typedef char KeyType;
typedef struct
{
char start[6]; /*起點*/
char end[6]; /*終點*/
char sche[10]; /*斑期*/
char time1[5]; /*起飛時間*/
char time2[5]; /*到達時間*/
char model[4]; /*機型*/
int price; /*標價*/
}InfoType; /*航班記錄類型*/
typedef struct
{
KeyType keys[keylen]; /*航班號*/
InfoType others;
int next;
}SLNode; /*靜態鏈表接點類型*/
typedef struct
{
SLNode sl[MaxSpace];
int keynum; /*靜態鏈表，sl[0]為頭結點*/
int length; /*當前表長*/
}SLList; /*靜態鏈表類型*/
typedef int ArrType_n[Radix_n]; /*十進制數字指針數組*/
typedef int ArrType_c[Radix_c]; /*26個字母指針數組*/
/*一趟數字字符分配函數*/
void Distribute(SLNode *sl,int i,ArrType_n f,ArrType_n e)
{
int j,p;
for(j=0;j<Radix_n;j++)
{ /*各子表置為空表*/
f[j]=e[j]=0;
}
for(p=sl[0].next;p;p=sl[p].next)
{
j=sl[p].keys[i]%48; /*將數字字符轉換成相對應的數值型數字*/
if(!f[j])
f[j]=p;
else
sl[e[j]].next=p;
e[j]=p; /*將p指向的結點插入到第j個子表中*/
}
}
/*一趟數字字符的收集函數*/
void Collect(SLNode *sl,int i,ArrType_n f,ArrType_n e)
{
int j,t;
for(j=0;!f[j];j++); /*找第一個非空子表*/
sl[0].next=f[j];
t=e[j];
while(j<Radix_n-1)
{
for(j=j+1;j<Radix_n-1 && !f[j];j++); /*找下一個非空子表*/
if(f[j])
{
sl[t].next=f[j];
t=e[j]; /*鏈接兩個非空子表*/
}
}
sl[t].next=0; /*t指向最后一個非空子表中的最后一個結點*/
}
/*一趟字母字符分配函數*/
void Distribute_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)
{
int j,p;
for(j=0;j<Radix_c;j++)
{ /*各子表置為空表*/
f[j]=e[j]=0;
}
for(p=sl[0].next;p;p=sl[p].next)
{
j=sl[p].keys[i]%65; /*將字母字符轉換成在字母集中相應的序號（0－25）*/
if(!f[j])
f[j]=p;
else
sl[e[j]].next=p;
e[j]=p;
}
}
/*一趟字母字符收集*/
void Collect_c(SLNode *sl,int i,ArrType_c f,ArrType_c e)
{
int j,t;
for(j=0;!f[j];j++);
sl[0].next=f[j];
t=e[j];
while(j<Radix_c-1)
{
for(j=j+1;j<Radix_c-1&&!f[j];j++);
if(f[j])
{ sl[t].next=f[j]; t=e[j]; }
}
sl[t].next=0;
}
/*鏈式基數排序函數*/
void RadixSort(SLList &L)
{
int i;
ArrType_n fn,en;
ArrType_c fc,ec;
for(i=0;i<L.length;i++)
L.sl[i].next=i+1; /*0號單元公存放指針，不存儲內容*/
L.sl[L.length].next=0; /*將普通的線性表改造為靜態鏈表*/
for(i=L.keynum-1;i>=2;i--)
{ /*按最低優先次序對各關鍵字進行分配和收集，先做低4位數字部分*/
Distribute(L.sl,i,fn,en);
Collect(L.sl,i,fn,en);
}
for(i=1;i>=0;i--)
{ /*對高位的2位大寫字母進行分配和收集*/
Distribute_c(L.sl,i,fc,ec);
Collect_c(L.sl,i,fc,ec);
}
}/*RadixSort*/
/*按指針鏈重新整理靜態鏈表*/
void Arrange(SLList &L)
{
int p,q,i;
SLNode temp;
p=L.sl[0].next; /*p指向第一個記錄的當前位置*/
for(i=1;i<L.length;i++) /*L.sl[1..i-1]已按關鍵字有序化*/
{
while(p<i)
p=L.sl[p].next; /*找到第i個記錄，并用p指向其在L中當前位置*/
q=L.sl[p].next; /*q指向尚未調整的表尾*/
if(p!=i)
{
temp=L.sl[p]; L.sl[p]=L.sl[i]; L.sl[i]=temp; /*交換記錄*/
L.sl[i].next=p;
}
p=q; /*p指向尚未調整的表尾，為找第i+1個記錄做準備*/
}
}/*Arrange*/
/*二分查找函數*/
int BinSearch(SLList L,KeyType key[])
{
int low,high,mid;
low=1;
high=L.length;
while(low<=high)
{
mid=(low+high)/2;
if(strcmp(key,L.sl[mid].keys)==0)
return mid;
else
if(strcmp(key,L.sl[mid].keys)<0)
high=mid-1;
else
low=mid+1;
}
return 0;
}/*BinSearch*/
/*順序查找函數*/
void SeqSearch(SLList L,KeyType key[],int i)
{
int j,k,m=0;
printf("***********************************************************\n");
printf("* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *\n");
for(j=1;j<=L.length;j++)
{
switch(i)
{
case 2:k=strcmp(key,L.sl[j].others.start);break;
case 3:k=strcmp(key,L.sl[j].others.end);break;
case 4:k=strcmp(key,L.sl[j].others.time1);break;
case 5:k=strcmp(key,L.sl[j].others.time2);break;
}
if(k==0)
{ m=1;
printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",L.sl[j].keys,L.sl[j].others.start,L.sl[j].others.end,L.sl[j].others.sche,L.sl[j].others.time1,L.sl[j].others.time2,L.sl[j].others.model,L.sl[j].others.price);
}
}
if(m==0)
printf("* 無此航班信息，可能是輸入錯誤！ *\n");
printf("***********************************************************\n");
}
/*查詢檢索菜單控制程序*/
void searchcon(SLList L)
{
KeyType key[keylen];
int i=1,k;
while(i>=1&&i<=5)
{
printf("\n **********************\n");
printf(" * 航班信息查詢系統 *\n");
printf(" **********************\n");
printf(" * 1.航 班 號 *\n");
printf(" * 2.起 點 站 *\n");
printf(" * 3.終 點 站 *\n");
printf(" * 4.起飛時間 *\n");
printf(" * 5.到達時間 *\n");
printf(" * 0.退出系統 *\n");
printf(" **********************\n");
printf(" 請選擇(0-5):");
scanf("%d",&i);
printf("\n");
switch(i)
{
case 1: printf("輸入要查詢的航班號(字母要大寫):");
scanf("%s",key);
k=BinSearch(L,key);
printf("*************************************************************\n");
if(k==0)
printf("* 無此航班信息，可能是輸入錯誤！ *\n");
else
{
printf("* 航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價 *\n");
printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *\n",L.sl[k].keys,L.sl[k].others.start,L.sl[k].others.end,L.sl[k].others.sche,L.sl[k].others.time1,L.sl[k].others.time2,L.sl[k].others.model,L.sl[k].others.price);
}
printf("*************************************************************\n");
break;
case 2: printf("輸入要查詢的航班起點站名:");
scanf("%s",key);
SeqSearch(L,key,i);
break;
case 3: printf("輸入要查詢的航班終點站名:");
scanf("%s",key);
SeqSearch(L,key,i);
break;
case 4: printf("輸入要查詢的航班起飛時間:");
scanf("%s",key);
SeqSearch(L,key,i);
break;
case 5: printf("輸入要查詢的航班到達時間:");
scanf("%s",key);
SeqSearch(L,key,i);
break;
case 0: printf("\n\n\n 再 見\n\n\n");
}
}
}
/*輸入航班記錄函數*/
void InputData(SLList &L)
{
int i=++L.length;
char yn='y';
while(yn=='y'||yn=='Y')
{
printf("航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價\n");
scanf("%s%s%s%s%s%s%s%d",L.sl[i].keys,L.sl[i].others.start,L.sl[i].others.end,L.sl[i].others.sche,L.sl[i].others.time1,L.sl[i].others.time2,L.sl[i].others.model,&L.sl[i].others.price);
++i; getchar();
RadixSort(L); /*基數排序*/
Arrange(L); /*重新整理靜態鏈表*/
printf("繼續輸入嗎?y/n:");
scanf("%c",&yn);
}
L.length=i-1;
}
void main()
{
SLList L;
L.keynum=6; /*初始化及輸入數據*/
L.length=0;
InputData(L); /*輸入航班記錄*/
printf("排序之后:\n");
for(int i=1;i<=L.length;i++)
{
printf("航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價\n");
printf("%-8s%-7s%-6s%-11s%-9s%-7s%-5s%d\n",L.sl[i].keys,L.sl[i].others.start,L.sl[i].others.end,L.sl[i].others.sche,L.sl[i].others.time1,L.sl[i].others.time2,L.sl[i].others.model,L.sl[i].others.price);
}
printf("總共:%d",i-1);
searchcon(L); /*查詢菜單控制程序*/
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -