数据结构-实验报告六--航班信息查询与检索系统

实验课程名称数据结构课程设计专业班级学生姓名学号指导教师2012至2013学年第一学期第1至9周目录一、概述：.............................................................................................3二、系统分析：........................................................................................32.1输入/输出形式和输出值..............................................................32.2功能需求.......................................................................................32.3系统特点.......................................................................................3三、概要设计：........................................................................................43.1设计思路.......................................................................................43.2数据处理.......................................................................................43.3基本概念和数据处理...................................................................53.4数据流图.......................................................................................6四、详细设计：........................................................................................74.1设计说明.......................................................................................74.2算法设计与分析...........................................................................7二分查找........................................................................................74.3算法实现.......................................................................................8五、运行与测试：....................................................................................9六、总结与心得：..................................................................................11附录：程序代码..........................................................................11一、概述：设计一个航班信息查询与检索系统。可事先按要求录入航班信息、删除航班信息、查看全部航班信息及按航班的航班号、起点站、终点站、起飞时间、以及到达时间等信息进行查询。二、系统分析：2.1输入/输出形式和输出值进入系统后，首先按照要求输入航班信息，包括：航班号、起点站、终点站、航班期、起飞时间、到达时间、票价。除票价为整型外，其他均为字符型。信息完成后均以Enter结束。当输入完一个航班信息后，会提示是否继续输入，若要继续输入则重复上述步骤，否显示主菜单。根据主菜单输入功能序号选择，若用户输入的值超过给定范围，则提示错误并要求重新输入。2.2功能需求（1）输入航班信息（2）删除航班信息，可按航班号、起点站、终点站、起飞时间、到达时间等删除（3）按不同类型查询航班信息，如航班号、起点站、终点站、起飞时间、到达时间等（4）显示当前所有的航班记录（5）退出系统2.3系统特点本系统的使用者是航空公司，操作人员只需具备基本的计算机操作技巧即可。三、概要设计：3.1设计思路根据设计要求，程序必须实现航班信息的录入和查询。程序首先定义了一个用于存储航班信息的数据类型，再由用户录入航班数据路，在录入的同时并对数据进行排序，最后执行数据查询和检索。在设计过程中，使用二分查找法对航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找。3.2数据处理航班信息管理系统录入航班信息删除航班信息查询航班信息显示全部记录退出按航班号删除︵查询︶按起点站删除︵查询︶按终点站删除︵查询︶按起飞时间删除︵查询︶按到达时间删除︵查询︶3.3基本概念和数据处理开始输入航班信息信息是否合法显示主菜单用户选择查询功能，输入查询信息信息是否存在查找用户输入的信息显示航班信息提示查无信息结束异常处理否否是是3.4数据流图开始初始化信息主菜单显示输入查询序号判断序号是否合法按航班号查询按时间查询按地点查询按票价查询输出航班信息结束管理员航班信息用户业务处理航班信息查询关键字四、详细设计：4.1设计说明1）利用起点站、终点站、起飞时间、到达时间为关键字来查询航班信息。该查找算法使用最简单的顺序查找方法进行。即按照航班信息的结构体数组依次与被查找信息进行比较，若找到，则输出结构即可，若没找到，则输出相关的提示信息。2）利用航班号作为关键字进行查询由于设计内容要求使用基数排序对这组航班信息进行排序，并利用二分查找法对排好的航班记录按航班号实现快速查找，因此此算法设计包括基数排序和二分查找。4.2算法设计与分析基数排序基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法，其是通过“分配”和“收集”两种操作对相应关键字进行排序。算法思路是按照排序关键字的每一位字符进行排序。排序前，先定义一个队列数组，每个队列数组与某个关键字位对应，某队列中只能存放与该关键字位对应的元素。首先先从关键字的最后一位字符进行判断，根据关键字位，把这个元素放入相应的队列中去，这就是“分配”过程。等到所有元素均被分配到相应队列中之后，在把各个队列中的元素，按照队列数组顺序，依次重新放回原元素数组中，这就是“收集”过程。经过“分配”和“收集”后，一次排序完成。接着再以关键字的倒数第二位字符作为关键字位进行上述排序过程，直到按照关键字的所有位全部进行排序过后，整个序列就成为有序序列，排序完成。二分查找二分查找是对有序序列进行快速查找的一种有效方法。它的基本思想是，每次都与这个有序序列的中间元素进行比较，若找到，则输出元素信息，若没找到，则判断这个中间元素比待查找的元素大还是小，如果大，那么查找工作继续在该有序序列的前半段进行；反之，则继续查找该有序序列的后半段。如此一直查找，直到找到该元素或者查找到只剩下一个元素而这个元素与待查找元素不相符时，查找结束。前一种情况找到了待查找元素，输出该元素，后一种没有找到，输出相应提示信息。4.3算法实现1．定义数据类型根据设计要求，所用到的数据记录只有航班信息，因此要定义相关的数据类型。本系统采用链式存储的存储结构，分别定义三个结构体。typedefstruct//定义航班信息的结构体,静态链表类型{charterminal[6];//定义起点站charend[6];//定义终点站charflightNo[10];//定义航班期charstartTime[5];//定义起飞时间charendTime[5];//定义到达时间chartype[10];//定义机型intprice;//定义票价}infotype;typedefstruct{keytypekeys[keylen];//航班号，动态链表infotypeothers;intnext;}slnode;typedefstruct//定义存储信息的结构体{slnodesl[MAX];intkeynum;//信息数量，最大表长intlength;//信息长度，当前表长}sllist;//顺序表类型2．实现排序的各函数说明（1）显示一条航班记录函数voidDisplay(SLListL,inti)（2）删除记录函数voiddel(SLListL,keytypekey[],inti)（3）显示所有记录函数voiddisplayall(SLListL)（4）顺序查找函数voidSeqSearch(sllistl,keytypekey[],inti)（5）查询检索菜单voidserachcon(sllistl)（6）录入航班数据函数voidInputData(sllist&l)（7）主函数voidmain(){初始化;数据输入;排序处理;接受查找要求及查找关键字;查找处理;输出查找结果;}五、运行与测试：1、录入航班信息2、删除航班信息3、按起点站查询航班4、按终点站查询航班及显示全部航班信息5、退出航班信息与检索系统六、总结与心得：本设计的重点和难点在于对航班数据的排序和查找，以链式基数排序为主线，用到了二分查找和顺序查找、建立静态链表等知识。通过本次课程设计，使我对数据结构和算法设计有了新的了解和认识，以前编程只是注重如何编写函数能够完成所要求的功能，只是凭单纯的意识和简单的语句来搭配一段程序，但现在感觉不一样了，在编写一个程序之前，经过仔细考虑，挑选出最适合当前题目的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了清晰的构思了，除此之外，也让我真正理解定义数据类型的好处，这样才能用好这样一种数据结构。总之，学习它让我觉得受益匪浅！附录：程序代码#includestdio.h#includestring.h#includestdlib.hstructSLNode{charstart[10];//起点charend[10];//终点charsche[10];//班期chartime1[6];//起飞时间chartime2[6];//到达时间charmodel[4];//机型intprice;//票价charkeys[6];//关键字（航班号）};//航班记录类型//静态链表节点类型typedefstruct{SLNode*sl;//动态链表intlistsize;//最大表长intlength;//当前表长}SLList;//顺序表类型//显示一条航班记录函数voidDisplay(SLListL,inti){printf(航班号起点站终点站航班期起飞时间到达时间机型票价\n);printf(%6s%6s%6s%6s%6s%6s%4s%d\n,L.sl[i].keys,L.sl[i].start,L.sl[i].end,L.sl[i].sche,L.sl[i].time1,L.sl[i].time2,L.sl[i].model,L.sl[i].price);}//顺序查找函数voidSeqSearch(SLListL,charkey[],inti){intk,j,m=0;for(j=1;j=L.length;j++