#include<stdio.h>
#include<string.h>

#define MaxSpace 100
#define keylen 7
#define RADIX_n 10
#define RADIX_c 26

typedef char KeyType;
typedef struct{
 char start[7]; //起點站 
 char end[7]; //終點站 
 char sche[12]; //航班期 
 char time1[5]; //起飛時間 
 char time2[5]; //到達(dá)時間 
 char mode1[3]; //機(jī)型 
 int price;  //票價 
}InfoType;  //航班記錄類型 

typedef struct{
 KeyType keys[keylen];//關(guān)鍵字 
 InfoType others;
 int next;
}SLNode;  //靜態(tài)鏈表結(jié)點類型

typedef struct{
 SLNode sl[MaxSpace];//靜態(tài)鏈表，s1[0]為頭結(jié)點 
 int keynum;  //記錄當(dāng)前關(guān)鍵字字符個數(shù) 
 int length;  //當(dāng)前表長 
}SLList;  //靜態(tài)鏈表類型 

typedef int ArrType_n[RADIX_n];  //十進(jìn)制數(shù)字指針數(shù)組 

typedef int ArrType_c[RADIX_c] ; //26個字母指針數(shù)組 

void Display(SLList,int i);  //聲明輸出函數(shù) 


/*一趟數(shù)字字符分配函數(shù)*/
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; //將數(shù)字字符轉(zhuǎn)換成相對應(yīng)的數(shù)值類型數(shù)字
 if(!f[j]) 
  f[j]=p;
 else
  s1[e[j]].next=p;
  e[j]=p;  //將p指向的結(jié)點輸入到第j個字表中 
 }
}


/*一趟數(shù)字字符收集函數(shù)*/
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指向第一個非空子表中的一個結(jié)點 
 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;
 }
}


/*一趟字母字符分配函數(shù)*/
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;
 }
}


/*一趟字母字符收集函數(shù)*/
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;
}


/*鏈?zhǔn)交鶖?shù)排序函數(shù)*/
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號單元僅存放指針，不儲存內(nèi)容 
 L.sl[L.length].next=0; //將普通的線性表進(jìn)行改造為靜態(tài)鏈表 
 for(i=L.keynum-1;i>=2;i--)
 {
  //按最低位優(yōu)先次序?qū)Ω麝P(guān)鍵字進(jìn)行分配和收集，先做低4位數(shù)字部分
  Distribute(L.sl,i,fn,en) ;
  Collect(L.sl,i,fn,en);
 }
 for(i=1;i>=0;i--)
 {
  //對高位的2位大寫字母進(jìn)行分配和收集
  Distribute_c(L.sl,i,fc,ec) ;
  Collect_c(L.sl,i,fc,ec);
 }
 return L;
}//RadixSort 


/*按指針鏈重新整理靜態(tài)鏈表*/
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;
}


/*查找算法的實現(xiàn)*/
int BinSearch(SLList L,KeyType key[]) //二分查找函數(shù) 
{
 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


/*順序查找函數(shù)*/
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"); 
}


/*輸入輸出函數(shù)*/
void Display(SLList L,int i)
{
 if(i==0) printf("無此航班信息，可能是輸入錯誤：\n");
 else{
 printf("航班號 起點站 終點站 航班期 起飛時間 到達(dá)時間 機(jī)型 票價\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("* 航班信息查詢系統(tǒng) *\n");
 printf("*********************************\n");
 printf("*  1.航 班 號  *\n");
 printf("*  2.起 點 站  *\n");
 printf("*  3.終 點 站  *\n");
 printf("*  4.起飛時間  *\n");
 printf("*  5.到達(dá)時間  *\n");
 printf("*  0.退出系統(tǒng)  *\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("輸入要查詢的航班到達(dá)時間："); 
  scanf("%s",k1);
  SeqSearch(L,k1,i);
  break;

  case 0:
  printf("退出程序,再見！\n");
  return ; 
 }
 }
}


/*輸入航班記錄函數(shù)*/
SLList InputData(SLList L)
{
 int i=++L.length;
 char yn='y';
 while(yn=='y' || yn=='Y')
 {
 printf("航班號 起點站 終點站 航班期 起飛時間 到達(dá)時間 機(jī)型 票價\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("繼續(xù)輸入嗎？y/n:");
 getchar();
 scanf("%c",&yn);
 }
 L.length=i-1;
 return L; 
}


/*主函數(shù)*/
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);  //基數(shù)排序 
 L=Arrange(L); 
 serachcon(L);  //調(diào)用查詢函數(shù) 
}