航班信息查询与检索系统

1、课程设计报告课程设计报告 课程设计名称：数据结构课程设计课程设计名称：数据结构课程设计 题目：设计并实现一个航班信息查询与检索系统题目：设计并实现一个航班信息查询与检索系统 院系：计算机学院院系：计算机学院 专业：专业： 班级：班级： 学号：学号： 姓名：姓名： 指导教师：指导教师： 学术诚信声明 本人声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师 指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中 特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己 经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。 与我一同工作的同学对本研究所做的任何贡献均己在报告

2、中做了明 确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人 愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承 担相关一切后果。 本人签名: 日期： 年 月 日 课程设计名称数数据据结结构构课课程程设设计计专业 学生姓名班级学号 题目名称设计并实现一个航班信息查询与检索系统设计并实现一个航班信息查询与检索系统 起止日期2016年12月18日起至2017年1月4日止 课设内容和要求： 对飞机航班信息进行排序和查找，可按照航班号、起点站、到达站、起飞时对飞机航班信息进行排序和查找，可按照航班号、起点站、到达站、起飞时 间间 和到达时间等信息进行查询。和到达时间等信息进行查询。 要

3、求：要求： 1.1. 设计数据结构设计数据结构 2.2. 选择合适的排序和查找算法选择合适的排序和查找算法 3.3. 设计软件的功能结构设计软件的功能结构 4.4. 采用模块化编程采用模块化编程 5.5. 给出现实方法和算法给出现实方法和算法 6.6. 按课程设计规范撰写课程设计报告按课程设计规范撰写课程设计报告 参考资料： 1 严蔚敏、陈文博，数据结构及应用算法教程m.北京：清华大学出版社，2011.5 2 张小莉、王苗、罗文劼，数据结构与算法m.北京：机械工业出版社，2014.4 教教研研室室审审核核意意见见： 教教研研室室主主任任签签字字： 指导教师（签名）指导教师（签名） 年月日 学学

4、 生（签名）生（签名）年月日 课程设计总结：课程设计总结： 本设计的重点和难点是在于对航班数据的排序和查找，以链式基数排序为 主线，用到了二分查找和顺序查找等知识，还有建立静态链表等。通过这次课程 设计，使我对 c 语言编程有了新的认识。以前编程只是注重如何编写函数能够 完成所需要的功能，只是凭单纯的意识和简单的语句来堆砌出一段程序。但现在 编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，选取 自己需要的数据结构，在编写每一个函数之前，可以仔细斟酌比对，挑选出最适 合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经 有了明确的原图了。这样无形中就提高了自己

5、编写的程序的质量。另外，我还体 会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能 用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写 程序的关键。 目目 录录 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、题目介绍、题目介绍 设计一个航班信息查询与检索系统。

6、可按航班的航班号、起点站、终点站、起飞时间 以及到达时间等信息进行查询。 2 2、课程设计要求、课程设计要求 1、每个航班记录包括八项：航班号、起始站、终点站、班期、起飞时间、到达时间、 飞机型号、票价。如下表所示： 航班号起点站终点站班期起飞时间到达时间机型票价 ca1544 合肥北京 1.2.4.510551240733960 mu5341 上海广州每日 14201615m901280 cz3869 重庆深圳 2.4.6085510357331010 2、对航班信息进行排序与查找。 3 3、概要设计、概要设计 3.1、设计思路、设计思路 根据题目所要求，程序必须实现航班信息的录入和查询。程

7、序首先定义了 一个储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数 据进行排序，最后执行数据查询和检索。在查询设计中，使用折半查找法对排 好序的航班号数据实现快速查找，按起点站、终点站、起飞时间、到达时间查 找的则采用顺序查询方法。 3.2、流程图、流程图 数据输入、排序 接受查找条件、查 找关键字 定义数据类型 显示输出 开开 始始 录入信息提示录入信息提示 信息录入信息录入 查询菜单显示查询菜单显示 输入查询序号输入查询序号 判断符号是否判断符号是否 合法合法 按航班号按航班号 查询查询 按起飞时间按起飞时间 查询查询 按到达时间查按到达时间查 询询 按起点站查按起点站查

8、询询 按终点站按终点站 查询查询 输出查询结果输出查询结果 结结 束束 4、算法实现、算法实现 4.1 . 定义数据类型定义数据类型 根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关 的数据类型： typedef struct char start6; /起点站 char end6; /终点站 char sche10; /班期 char time15; /起飞时间 char time25; /到达时间 char model4; /机型 int price; /票价 info; /航班记录类型 typedef struct char keyskeylen; /关键字 info o

9、thers; int next; slnode; /表结点 typedef struct slnode slmaxspace; int keynum; /关键字长 int length; /当前表长 sllist; /静态链表类型 为了进行基数排序，需要定义在分配和收集操作时用到的指针数组： typedef int arrtype_n10; /十进制数字指针数组 typedef int arrtype_c26; /26 个字母指针数组 4.2 . 函数描述函数描述 void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e) int j,p

10、; for(j=0;j10;j+) fj=ej=0; for(p=sl0.next;p;p=slp.next) j=slp.keysi%48; /将数字字符转化为对应的数值型数字 if(!fj) fj=p; else slej.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(j10-1) for(j=j+1;j10-1j+); /找下一个非空子

11、表 if(fj) slt.next=fj; t=ej; /链接两个非空子表 slt.next=0; 链式基数排序算法链式基数排序算法 void radixsort(sllist 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

12、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,char key) int low,high,mid; low=1; high=l.length; while(low=high) mid=(low+high)/2; if(strcmp(key,l.sl

13、mid.keys)=0) return mid; else if(strcmp(key,l.slmid.keys)0) high=mid-1; else low=mid+1; return 0; 5、测试数据、测试数据 编译后运行，显示： 录入信息_ 航班号起点站终点站班期起飞时间到达时间机型票价 录入：ca1544 合肥 北京 1.2.4.5 1055 1240 733960 显示：是否继续？y/n: 录入：y 显示：航班号 起点站 终点站 班期起飞时间到达时间机型票价 录入：mu5341上海 广州 每日 1420 1615 m901280 显示：是否继续？y/n: 录入：y 显示：航班号

14、起点站终点站班期起飞时间到达时间机型票 价 录入：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 录入：

15、2 显示：输入要查询的航班起点站: 录入：合肥 显示：航班号起点站终点站 班期起飞时间到达时间机型票 价 显示：ca1544 合肥 北京 1.2.4.5 1055 1240 733960 录入：2 显示：输入要查询的航班起点站: 录入：广州 显示： 附录附录 源程序：源程序： #include #include #define max 100 #define keylen 7 typedef struct char start6; char end6; char sche10; char time15; char time25; char model4; int price; info; ty

16、pedef struct char keyskeylen; info others; int next; slnode; typedef struct slnode slmax; int keynum; int length; sllist; typedef int arrtype_n10; typedef int arrtype_c26; void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e) int j,p; for(j=0;j10;j+) fj=ej=0; for(p=sl0.next;p;p=slp.next) j=slp.k

17、eysi%48; if(!fj) fj=p; else slej.next=p; ej=p; 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(j10-1) for(j=j+1;j10-1j+); if(fj) slt.next=fj; t=ej; slt.next=0; void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e) int j,p; for(j=0;j26;j

18、+) fj=ej=0; for(p=sl0.next;p;p=slp.next) j=slp.keysi%65; if(!fj) fj=p; else slej.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(j26-1) for(j=j+1;j26-1j+); if(fj) slt.next=fj; t=ej; slt.next=0; void radixsort(sllist arrtype_n

19、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 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

20、.sli=temp; l.sli.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.slmid.keys)=0) return mid; else if(strcmp(key,l.slmid.keys)0) high=mid-1; else low=mid+1; return 0; void seqsearch(sllist l,char key,int i) int j,k

21、,m=0; printf(-n); printf( 航班号 起点站 终点站 班期 起飞时间 到达时间 机型 票价 n); for(j=1;j=1 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, printf(n); sw

22、itch(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.slk.keys,l.slk.others.start,l.slk.others.end,l.slk.others.sche,l.slk.others.time1,l.slk.oth ers.time2,l.slk.others.model,l.slk.others.price); printf(-n)