#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]; //到达时间 
 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);  //调用查询函数 
}