算法与数据结构课程设计-航班信息的查询与检索系统.doc

计算机科学与技术教研室课程设计说明书（2014-2015学年 第1学期）课程名称算法与数据结构课程设计设计题目航班信息的查询与检索系统学号姓名小组成员起止时间： 2015年 1 月 7 日 至 2015 年 1 月 19 日 课程设计评 语在为期两周的课程设计中，该生按时到课，课堂表现良好，参与了课程设计的整个过程，实现了航班信息查询与检索系统的以下功能：对关键字、次关键字进行各种排序（选择排序、快速排序等）和查找（二分法查找等）。其课程设计说明书填写正确，条理清楚，课题设计方案合理，符号较统一；图表基本符合规范要求；能对整个设计过程进行自己的总结。对于课程设计过程介绍详细，代码正确，可见对于数据结构程序有了一定的独立编程能力并且对课本知识掌握较熟练。作品演示较熟练，能按照设计要求完成指定的功能。答辩过程中回答问题较流利，对数据结构中的顺序结构掌握熟练。但不足之处是在程序中只运用了顺序存储结构，结构较简单，没有涉及到链表，即链式存储结构。平时成绩报告成绩演示与答辩成绩成绩总评指导教师（签字）年 月 日注：成绩均用百分制。总成绩=平时成绩*20%+报告成绩*40%+演示与答辩成绩*40%第 17 页设计题目：航班信息的查询与检索系统1、课程设计目的（1）数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C+语言），自行实现一个较为完整的应用系统。（2）通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。（3）学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。 掌握顺序存储结构及其相应的操作； 熟练运用各种排序和查找学会自己调试程序并掌握了一定的技巧； 通过温习旧的知识，学习新知识，并提高分析和解决问题的能力等。2、课程设计正文2.1概要设计2.1.1 系统分析该设计是对飞机航班信息进行排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。对于本设计，可采用排序方法对一组具有结构特征的飞机航班号进行排序，利用二分查找的方法对排好序的航班记录按航班号实现快速查找，按其他次关键字找采用最简单的顺序查找方法进行，它们用的较少。 每个航班记录包括八项，分别为：航班号、起点号、终点站、航班期、起飞时间、到达时间、机型以及票价，假设航班信息表（8条记录）如表1所示 表1 航班信息表航班号起点站终点站航班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU1836昆明西安1.3.5.7101511403281160SC7425青岛海口1.3.619202120DH41630该系统主要功能包括：对航班信息进行排序和查找。分析：（1）给数组初始化，然后用C+语言对航班信息表进行相应的排序和查找； （2）排序功能：利用快速排序、冒泡排序、选择排序、希尔排序、直接插入排序和归并排序对各个关键字进行排序；（3）查找功能：利用顺序查找和二分法查找对各个关键字进行查找；2.1.2系统结构图系统要实现的功能：（1）排序；（2）查找。系统结构图如图1所示。图1 系统结构图2.2详细设计2.2.1数据类型定义 struct hangban hMaxSize; typedef struct Node RadixNode;struct Node DataType info; /数据信息 RadixNode *next; ;typedef RadixNode *RadixList;2.2.2 存储结构：（1）航班的信息：为了便于查找，航班情况的存储结构采用数组格式，每个元素表示一个航班的情况，包括航班号、起始站、终点站、票价、起飞时间、到达时间、机型、班期 ，共八个数据项：航班号起始站终点站票价 起飞时间到达时间机型班期结构体的声明如下：typedef struct hangban char num10;/航班号 char start10;/起始站 char finalstop10;/终点站 int price;/票价 char starttime10;/起飞时间 char finaltime10;/到达时间 char type10;/机型 char data10;/班期 DataType;（2）其中航班号一项的格式为：K0 K1 K2 K3 K4 K5 C Z 3 8 6 9其中K0和K1的输入值是航空公司的别称，用两个大写字母表示，后4位航班编号，可将这种航班关键字分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，除票价可以定义为数值型外，均定义为字符串型即可。2.2.3 函数声明 （1）复制函数 函数名：void copy(hangban h,Node element) 操作结果：将Node的结构体变量element中的记录复制给hangban的结构体变量h 分析：定义一个指针指向element的首地址，然后将头结点中的记录复制给h0,用一个for循环，在每一次循环的最后让指针下移指向下一个地址，依次把记录复制给h1,h2,.,hMaxSize-1。 （2）选择排序函数 函数名：void sort_num() 操作结果：对航班号进行从小到大排序 分析：用两个for循环和一个if语句进行排序，排序的每一趟在n-i+1（i=1，2，.，n-i），个记录中选取航班号最小的记录作为有序序列中第i个记录。 （3）冒泡排序函数 函数名：void sort_starttime() 操作结果：对起飞时间进行从早到晚排序 分析：用一个while语句，一个for语句，一个if语句进行排序，第i趟起泡排序是从第1到n-i+1个记录依次比较相邻的两个记录的起飞时间，并在“逆序”时交换相邻记录。 （4）直接插入排序 函数名：void sort_finaltime() 操作结果：对到达时间进行从早到晚排序 分析：运用了两个for循环和if语句进行排序，先将序列中的第i个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按到达时间非递减有序序列为止。 （5）快速排序函数 函数名：void sort_type(int low,int high) 操作结果：对机型进行从小到大排序 分析：先用while语句进行一趟排序，然后经过递归调用在分别对分成的两部分进行快速排序，也就是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的机型均比另一部分的机型小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序。 （6）希尔排序函数 函数名：void sort_price() 操作结果：对票价进行从小到大排序 分析：即先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，在整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 （7）归并排序函数 函数名：void sort_price(int，int) 操作结果：对票价进行从大到小排序 分析：将数组中的前后相邻的两个有序序列归并为一个有序序列 （8）二分法查找函数 函数名：void search_num() 操作结果：对航班号进行查找 分析：用while语句和if语句进行查找，先确定待查记录所在范围，然后逐步缩小范围直到找到或找不到该记录为止 （9）顺序查找函数 函数名：void search_start() 操作结果：对起始站进行查找 分析：用一个for语句和一个if语句进行查找，从表中第一个记录开始，逐个进行记录的起始站和给定值进行比较，若某个记录的起始站和给定值比较相等，则查找成功，找到所查记录，反之，若直至最后一个记录，其起始站和给定值比较都不相等，则表明表中没有所查记录，查找不成功。 （10）航班信息表函数 函数名：void chart_message() 操作结果：显示航班信息表 （11）输出函数 函数名：void output() 操作结果：输出排序后的航班信息表 （12）主菜单函数 函数名：int menu() 操作结果：显示总菜单：排序，查找，退出 （13）排序菜单函数 函数名：int sort() 操作结果：显示排序关键字：航班号，起始时间，到达时间，机型，票价（从小到大），票价（从大到小） （14）查找菜单函数 函数名：int search() 操作结果：显示查找关键字：航班号，起始站，终点站2.2.4函数流程图（1） 冒泡排序流程图如图2所示。图2 冒泡排序流程图（2）选择排序流程图如图3所示。图3 选择排序流程图（3）直接插入排序的流程图如图4所示。图4 直接插入排序流程图（4）二分法查找流程图如图5所示。图5 二分法查找流程图（5） 顺序查找流程图如图6所示。图6 顺序查找流程图2.3程序测试结果（1）主菜单界面如图7所示。图7 主菜单界面（2） 排序总菜单及按航班号排序执行结果如图8所示。图8 排序总菜单及按航班号排序执行结果（3） 排序总菜单及按起始时间排序执行结果如图9所示。图9 排序总菜单及按起始时间排序执行结果（4） 排序总菜单及按到达时间排序执行结果如图10所示。图10 排序总菜单及按到达时间排序执行结果（5） 排序总菜单及按机型排序执行结果如图11所示。图11 排序总菜单及按机型排序执行结果（6） 排序总菜单及按票价（从小到大）排序执行结果如图12所示。图12 排序总菜单及按票价（从小到大）排序执行结果（7） 排序总菜单及按票价（从大到小）排序执行结果如图13所示。图13 排序总菜单及按票价（从小到大）排序执行结果（8） 查找总菜单和按航班号查找的执行结果如图14所示。图14 查找总菜单和按航班号查找的执行结果（9） 查找总菜单及按起始站查找的执行结果如图15所示。图15 查找总菜单及按起始站查找的执行结果（10） 查找总菜单及按终点站查找的执行结果如图16所示。图16 查找总菜单及按起始站查找的执行结果3、课程设计总结到现在为止我们已经学习了一学期的数据结构，再加上如今通过算法与数据结构的课程设计，让我对数据结构这门课有了比较深的了解。当然，在学习过程中也遇到各种各样的困难，不过已经通过各种途径解决了。在解决这些问题的过程中让我也学到了许多课本上没有的知识以及团队合作的重要性。主界面的编写对现在的我们来说很容易，我们课程设计的题目是航班信息的查找及检索；主要的操作就是对航班信息进行排序和查找；在排序这一部分，我用了选择排序、冒泡排序、直接插入排序、快速排序、希尔排序、归并排序6种排序方法；选择排序和冒泡排序我们之前接触过，没什么问题，其余四种排序是在这学期刚学的，所以在刚开始用的时候还是有些陌生，通过看课本上的算法，再加上不会的时候问问同学和老师，也都成功的完成了编写并且能正确的执行；在查找这一部分，我用了顺序查找和二分法查找（折半查找）2种查找方法；顺序查找在之前用过，不陌生，二分法查找是新接触的在看书上的算法后成功编写程序并能正确执行。在进行这些操作之前我先建立了一个单链表，把航班信息表初始化入单链表中，然后通过一个复制函数把单链表中的记录依次复制到一个数组中，因为数组中的元素是顺序存储，在进行一些操作时简便一些，所以我选择了这种做法。和每次的课程设计一样，通过这次的课程设计我也有了很大的进步，也学到了很多，比如团队的力量永远大于个人的力量，细节决定成败，无论做什么事情都要有耐心等等。通过这一次的编写程序不但重新温习了以前学到的知识，还学习到许多的新的知识，也认识到了自己的许多的不足。例如耐心不够，有时侯调试程序时，发现了一个错误，但是总是解决不了，心里就会感到厌烦，不想继续做下去。还有不够细心，每一次改写完程序后，检查了一遍，自己认为没有错了，结果一调试发现又有错误等等。不过也发现了自己的一些优点，比如善于听取他人意见，虚心求教等。最后，通过全组人的齐心协力，最终将程序编写了出来，并且使之得到实现我们的预期目的。通过此次课程设计，从一定成度上提高了我们对数据结构的熟悉度，也提高了我们独立编程的能力，同时也体会到在程序设计过程中团体合作，共同解决问题的重要性。4、 参考文献1谭浩强.C程序设计题解与上机指导（第二版）M.北京：清华大学出版社.2000年9月.2严蔚敏.吴伟民.数据结构M.北京：清华大学出版社.2004年6月.3朱战立.张选平.数据结构学习指导与典型题解M.西安：西安交通大学出版社.2002年7月.答辩记录答辩小组教师：刘璐，郭双乐提问与答辩情况记录如下：1、怎样对航班信息的查询与检索系统进行设计分析的？答：由于题目为航班信息的查询与检索。其中应包括航班的各种信息，包括航班号、起飞站、终点站、票价、起飞时间、到