#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,%dn",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);
//调用查询函数 }