#include<stdio.h>#include<string.h>#define MaxSpace 100#define keylen 7#define RADIX_n 10#define RADIX_c 26typedef char KeyType;typedef struct{ char start[7]; //起點站  char end[7]; //終點站  char sche[12]; //航班期  char time1[5]; //起飛時間  char time2[5]; //到達時間  char mode1[3]; //機型  int price;  //票價 }InfoType;  //航班記錄類型 typedef struct{ KeyType keys[keylen];//關鍵字  InfoType others; int next;}SLNode;  //靜態鏈表結點類型typedef struct{ SLNode sl[MaxSpace];//靜態鏈表，s1[0]為頭結點  int keynum;  //記錄當前關鍵字字符個數  int length;  //當前表長 }SLList;  //靜態鏈表類型 typedef int ArrType_n[RADIX_n];  //十進制數字指針數組 typedef int ArrType_c[RADIX_c] ; //26個字母指針數組 void Display(SLList,int i);  //聲明輸出函數 /*一趟數字字符分配函數*/void Distribute(SLNode *s1,int i,ArrType_n f,ArrType_n e) { int j,p; for(j=0 ; j<RADIX_n ; j++) { //各子表置為空表 f[j] =0; e[j]=0; } for(p=s1[0].next;p;p=s1[p].next) { j=s1[p].keys[i]%48; //將數字字符轉換成相對應的數值類型數字 if(!f[j])   f[j]=p; else  s1[e[j]].next=p;  e[j]=p;  //將p指向的結點輸入到第j個字表中  }}/*一趟數字字符收集函數*/void Collect(SLNode *s1,int i,ArrType_n f,ArrType_n e){ int j,t; for(j=0;!f[j];j++);  //找第一個非空子集  s1[0].next=f[j]; //s1[0].next指向第一個非空子表中的一個結點  t=e[j]; while(j<RADIX_n-1) { for(j=j+1;j<RADIX_n-1 && !f[j];j++); //找下一個非空子表  if(f[j]) {  s1[t].next=f[j]; //連接兩個非空子表   t=e[j]; } s1[t].next=0; }}/*一趟字母字符分配函數*/void Distribute_c(SLNode *s1,int i,ArrType_c f,ArrType_c e){ int j,p; for(j=0;j<RADIX_c;j++) { //各子類表置為空 f[j]=0; e[j]=0; } for(p=s1[0].next;p!=0;p=s1[p].next) { j=s1[p].keys[i] % 65; if(!f[j])  f[j]=p; else  s1[e[j]].next=p; e[j]=p; }}/*一趟字母字符收集函數*/void Collect_c(SLNode *s1,int i,ArrType_c f,ArrType_c e){ int j,t; for(j=0;!f[j];j++); s1[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])  {  s1[t].next=f[j];  t=e[j];  } } s1[t].next=0;}/*鏈式基數排序函數*/SLList 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); } return L;}//RadixSort /*按指針鏈重新整理靜態鏈表*/SLList Arrange(SLList L){ int p,q,i; SLNode temp; p=L.sl[0].next; for(i=1;i<=L.length;i++) { while(p<i)   //************此處有問題*************   p=L.sl[p].next;  q=L.sl[p].next;  if(p!=i)  {  temp=L.sl[p]; //交換記錄  L.sl[p]=L.sl[i]; //交換記錄  L.sl[i]=temp; //交換記錄  L.sl[i].next=p;  } p=q; } return L;}/*查找算法的實現*/int BinSearch(SLList L,KeyType key[]) //二分查找函數 { int low,high,mid; low=1; high=L.length-1; 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; 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; Display(L,j); } } if(m==0) printf("無此航班信息，可能是輸入錯誤：/n"); }/*輸入輸出函數*/void Display(SLList L,int i){ if(i==0) printf("無此航班信息，可能是輸入錯誤：/n"); else{ printf("航班號 起點站 終點站 航班期 起飛時間 到達時間 機型 票價/n"); printf("%s,%s,%s,%s,%s,%s,%s,%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.mode1, L.sl[i].others.price); } }/*查詢檢索菜單控制程序*/void serachcon(SLList L){ int i=1,k; KeyType key[keylen],k1[4]; while(i>=1 && i<=5){ printf("*********************************/n"); printf(""); 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("  請選擇(1-5)  /n"); scanf("%d",&i); switch(i){  case 1:  printf("輸入要查詢的航班號（字母要大寫）：");  scanf("%s",key);  k=BinSearch(L,key);  Display(L,k);  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",k1);  SeqSearch(L,k1,i);  break;  case 5:  printf("輸入要查詢的航班到達時間：");   scanf("%s",k1);  SeqSearch(L,k1,i);  break;  case 0:  printf("退出程序,再見！/n");  return ;  } }}/*輸入航班記錄函數*/SLList 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.mode1, &L.sl[i].others.price); ++i; printf("繼續輸入嗎？y/n:"); getchar(); scanf("%c",&yn); } L.length=i-1; return L; }/*主函數*/int main(void){ int i; SLList L; L.keynum=6; L.length=0; for(i=1;i<=L.length;i++) Display(L,i); L=InputData(L);  //輸入航班記錄  L=RadixSort(L);  //基數排序  L=Arrange(L);  serachcon(L);  //調用查詢函數 }