课程设计报告课程设计名称：数据结构课程设计题目：设计并实现一个航班信息查询与检索系统院系：计算机学院专业：班级：学号：姓名：指导教师：学术诚信声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。

尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。

报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名: 日期：年月日目录1 题目介绍 (5)2 课程设计要求 (5)2.1课程设计内容 (5)2.2课程设计目标 (5)3 概要设计 (5)3.1设计思路 (5)3.2流程图 (5)4 算法概述 (6)4.1定义数据类型 (6)4.2函数描述 (7)5 测试数据 (10)附录（关键部分程序清单） (12)1、题目介绍设计一个航班信息查询与检索系统。

可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。

2、课程设计要求1、每个航班记录包括八项：航班号、起始站、终点站、班期、起飞时间、到达时间、飞机型号、票价。

如下表所示：2、对航班信息进行排序与查找。

3、概要设计3.1、设计思路根据题目所要求，程序必须实现航班信息的录入和查询。

程序首先定义了一个储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。

在查询设计中，使用折半查找法对排好序的航班号数据实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。

3.2、流程图4、算法实现4.1 . 定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：typedef struct {char start[6]; //起点站char end[6]; //终点站char sche[10]; //班期char time1[5]; //起飞时间char time2[5]; //到达时间char model[4]; //机型int price; //票价}info; //航班记录类型typedef struct{char keys[keylen]; //关键字info others;int next;}slnode; //表结点typedef struct{slnode sl[maxspace];int keynum; //关键字长int length; //当前表长}sllist; //静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedef int arrtype_n[10]; //十进制数字指针数组typedef int arrtype_c[26]; //26个字母指针数组4.2 . 函数描述void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e){int j,p;for(j=0;j<10;j++){f[j]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%48; //将数字字符转化为对应的数值型数字if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p; //将p指向的结点插入到第j个结点}}void collect(slnode *sl,int i,arrtype_n f,arrtype_n e){int j,t;for(j=0;!f[j];j++); //找第一个非空子表sl[0].next=f[j];t=e[j];while(j<10-1){for(j=j+1;j<10-1&&!f[j];j++); //找下一个非空子表if(f[j]){sl[t].next=f[j];t=e[j];} //链接两个非空子表}sl[t].next=0;}链式基数排序算法void 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;l.sl[l.length].next=0; //将普通的线性表改为静态链表for(i=l.keynum-1;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.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;}}折半查找函数定义int binsearch(sllist l,char key[]){int low,high,mid;low=1;high=l.length;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;elselow=mid+1;}return 0;}5、测试数据编译后运行，显示：录入信息^_^航班号起点站终点站班期起飞时间到达时间机型票价录入：CA1544合肥北京 1.2.4.5 1055 1240 733 960显示：是否继续？y/n:录入：y显示：航班号起点站终点站班期起飞时间到达时间机型票价录入：MU5341 上海广州每日1420 1615 M90 1280显示：是否继续？y/n:录入：y显示：航班号起点站终点站班期起飞时间到达时间机型票价录入：CZ3869 重庆深圳 2.4.6 0855 1035 733 1010显示：是否继续？y/n:录入：n录入航班信息后，屏幕显示：-------------------------------* 航班信息查询系统 *-------------------------------* 1.航班号 ** 2.起点站 ** 3.终点站 ** 4.起飞时间 ** 5.到达时间 ** 0.退出 *-----------------------------(0-5)号服务项目:录入：1显示：输入要查询的航班号(字母要大写):录入：CA1544显示：航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京 1.2.4.5 1055 1240 733 960录入：2显示：输入要查询的航班起点站:录入：合肥显示：航班号起点站终点站班期起飞时间到达时间机型票价显示：CA1544合肥北京 1.2.4.5 1055 1240 733 960录入：2显示：输入要查询的航班起点站:录入：广州显示：附录源程序：#include <stdio.h>#include <string.h>#define max 100#define keylen 7typedef struct{char start[6];char end[6];char sche[10];char time1[5];char time2[5];char model[4];int price;}info;typedef struct{char keys[keylen];info others;int next;}slnode;typedef struct{slnode sl[max];int keynum;int length;}sllist;typedef int arrtype_n[10];typedef int arrtype_c[26];void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e) {int j,p;for(j=0;j<10;j++){f[j]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%48;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}void collect(slnode *sl,int i,arrtype_n f,arrtype_n e){int j,t;for(j=0;!f[j];j++);sl[0].next=f[j];t=e[j];while(j<10-1){for(j=j+1;j<10-1&&!f[j];j++);if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e) {int j,p;for(j=0;j<26;j++){f[j]=e[j]=0;}for(p=sl[0].next;p;p=sl[p].next){j=sl[p].keys[i]%65;if(!f[j])f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e) {int j,t;for(j=0;!f[j];j++);sl[0].next=f[j];t=e[j];while(j<26-1){for(j=j+1;j<26-1&&!f[j];j++);if(f[j]){sl[t].next=f[j];t=e[j];}}sl[t].next=0;}void 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;l.sl[l.length].next=0;for(i=l.keynum-1;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.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;}}int binsearch(sllist l,char key[]){int low,high,mid;low=1;high=l.length;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;elselow=mid+1;}return 0;}void seqsearch(sllist l,char key[],int i){int j,k,m=0;printf("------------------------------------------------------------\n");printf(" 航班号起点站终点站班期起飞时间到达时间机型票价 \n");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;printf(" %-8s%-7s%-7s%-11s%-6s%-6s%5s%4d\n",l.sl[j].keys,l.sl[j].others.start,l.sl[j].others.end,l.sl[j].others.sche,l. sl[j].others.time1,l.sl[j].others.time2,l.sl[j].others.model,l.sl[j].others.pri ce);}}if(m==0)printf(" 无此航班信息，可能是输入错误！ \n");printf("-------------------------------------------------------\n");}void searchcon(sllist l){char key[keylen];int i=1,k;while(i>=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);printf("--------------------------------------------------------------\n");if(k==0)printf(" 无此航班信息，可能是输入错误！ \n");else{printf(" 航班号起点站终点站班期起飞时间到达时间机型票价 \n");printf(" %-8s%-7s%-7s%-11s%-6s%-6s%-5s%4d\n",l.sl[k].keys,l.sl[k].others.start,l.sl[k].others.end,l.sl[k].others.sche,l. sl[k].others.time1,l.sl[k].others.time2,l.sl[k].others.model,l.sl[k].others.pri ce);}printf("--------------------------------------------------------------\n");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\n宝宝走了\n\n");}}}void inputdata(sllist &l){int i=++l.length;char yn='y';while(yn=='y'||yn=='Y'){printf("信息录入^_^\n\n");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.model,&l.sl[i].others.price);++i;getchar();radixsort(l);arrange(l);printf("是否继续?\ny/n:");scanf("%c",&yn);}l.length=i-1;}void main(){sllist l;l.keynum=6;l.length=0;inputdata(l);searchcon(l);}。