数据结构课程设计航班信息的查询与检索实验参考代码.doc

数据结构课程设计航班信息的查询与检索实验参考代码#include #include #define Maxspace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26typedef char keytype;typedef struct char start6; /起点char end6; /终点char sche6; /班期char time15; /起飞时间 char time25; /到达时间char model4; /机型int price; /票价infotype; /航班记录类型typedef struct keytype keyskeylen; /关键字（航班号）infotype others;int next;slnode;typedef structslnode slMaxspace;int keynum; /记录当前关键字字符个数int length; /当前表长sllist; /静态链表类型typedef int arrtype_nRADIX_n;/十进制数字指针数组typedef int arrtype_cRADIX_c;/26个字母指针数组/*链式基数排序 */void Distribute(slnode *sl,int i,arrtype_n f,arrtype_n e) /一趟数字字符分配函数int j,p;for(j=0;jRADIX_n;j+)/各子表置为空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;/将数字字符转化成相对应的数值数字if(!fj)fj=p;elseslej.next=p;ej=p; /将P指向的结点插入到第J个子表中void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)/一趟数字字符的收集函数int j,t;for(j=0;!fj;j+);/找出第一非空子表sl0.next=fj;/指向第一个非空子表中的一个结点t=ej;while(jRADIX_n-1)for(j=j+1;jRADIX_n-1 & !fj;j+); /找出下一个非空子表if(fj)slt.next=fj;/链接两个非空子表t=ej; slt.next=0;/t指向最后一个非空子表中的最后一个结点void Distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)/一趟字母字符分配函数int j,p;for(j=0;jRADIX_c;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)/一趟字母字符收集函数int j,t;for(j=0;!fj;j+);sl0.next=fj;t=ej;while(jRADIX_c-1)for(j=j+1;jRADIX_c-1&!fj;j+);if(fj)slt.next=fj;t=ej; slt.next=0;void Radixsort(sllist &l)/链式基数排序int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-)Distribute(l.sl,i,fn,en);collect(l.sl,i,fn,en);for(i=1;i=0;i-)Distribute_c(l.sl,i,fc,ec);collect_c(l.sl,i,fc,ec);void Arrange(sllist &l) /按指针链重新整理静态链表int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i+)while(pi)p=l.slp.next;q=l.slp.next;if(p!=i)temp=l.slp;l.slp=l.sli;l.sli=temp;l.sli.next=p;p=q;/*查找算法实现*/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.slmid.keys)=0)return mid;else if(strcmp(key,l.slmid.keys)0)high=mid-1;elselow=mid+1;return 0;void Seqsearch(sllist l,keytype key,int i)/顺序查找函数int j,k,m=0;printf(* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n);for(j=1;j=1&i=5)printf(*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);if(k=0) printf(* 无此航班信息，可能是输入错误！ *n);else printf(* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n); printf(*%6s,%6s,%6s,%6s,%8s,%6s,%6s,%4d*n,l.slk.keys,l.slk.others.start,l.sl k.others.end,l.slk.others.sche,l.slk.others.time1,l.slk.others.time2,l.sl k.others.model,l.slk.others.price);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);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.sli.keys,l.sli.others.start,l.sli.others.end,l.sl i.others.sche,l.sli.others.time1,l.sli.others.time2,l.sli.others.model,&l.sl i.others.price);+i; getcha