数据结构课程设计航班信息查询与检索

此文档收集于网络，如有侵权请联系网站删除只供学习与交流学院名称《数据结构》课程设计报告题目——航班信息查询与检索班级：姓名：时间：2012/12/29---2013/1/5此文档收集于网络，如有侵权请联系网站删除只供学习与交流二○一二年十二月二十九日课程设计任务书及成绩评定课题名称航班信息查询与检索Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8条记录）航班号起点站终点站班期起飞时间到达时间机型票价CA1544合肥北京1.2.4.510551240733960MU5341上海广州每日14201615M901280CZ3869重庆深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为：K0K1K2K3K4K5CZ3869其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号，这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。此文档收集于网络，如有侵权请联系网站删除只供学习与交流Ⅱ、设计进度及完成情况日期内容12.29选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。12.30创建相关数据结构,录入源程序。12.31调试程序并记录调试中的问题，初步完成课程设计报告。1.4上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。1.5考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料此文档收集于网络，如有侵权请联系网站删除只供学习与交流Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一三年一月五日此文档收集于网络，如有侵权请联系网站删除只供学习与交流目录一、概述……………………………………………………………6二、系统分析………………………………………………………6三、概要设计………………………………………………………6四、详细设计………………………………………………………71.定义数据类型…………………………………………………72.算法实现………………………………………………………8五、测试数据………………………………………………………10六、收获与体会……………………………………………………13七、参考文献………………………………………………………13八、附录……………………………………………………………14此文档收集于网络，如有侵权请联系网站删除只供学习与交流一、概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。我们可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他关键字的查找可以采用最简单的顺序查找方法进行。二、系统分析1设计要求(1)提供对航班信息的排序功能(2)提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息(3）提供按关键字（航班号）快速查询或顺序查询功能2设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。其中航班号一项的格式为：K0k1k2k3k4k5航班关键字可分为两段，即字母和数字。其中k0和k1是航空公司的别称，用两个大写字母表示，后4位为航班编号。三、概要设计1、设计思路根据题目所要求，程序必须实现航班信息的录入和查询。程序首先定义了一个用于储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进CZ3869此文档收集于网络，如有侵权请联系网站删除只供学习与交流行排序，最后执行数据查询和检索。在查询设计中，使用二分查找法对排好序的航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。2、流程图四、详细设计1.定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：[1]typedefstruct{charstart[6];//起点站charend[6];//终点站charsche[10];//航班期chartime1[5];//起飞时间chartime2[5];//到达时间charmodel[4];//机型intprice;//票价}infotype;//航班记录类型typedefstruct{keytypekeys[keylen];//关键字infotypeothers;intnext;}slnode;//表结点typedefstruct{slnodesl[maxspace];//静态链表，s1[0]为头结点intkeynum;//关键字长intlength;//当前表长}sllist;//静态链表类型数据输入、排序接受查找条件、查找关键字输出查找结果定义数据类型此文档收集于网络，如有侵权请联系网站删除只供学习与交流为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedefintarrtype_n[10];//十进制数字指针数组typedefintarrtype_c[26];//26个字母指针数组2.算法实现（1）一趟分配算法[2]voiddistribute(slnode*sl,inti,arrtype_nf,arrtype_ne){intj,p;for(j=0;jradix_n;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个结点}}（2）一趟收集算法voidcollect(slnode*sl,inti,arrtype_nf,arrtype_ne){intj,t;for(j=0;!f[j];j++);//找第一个非空子表s1[0].next=f[j];t=e[j];while(jradix_n-1){for(j=j+1;jradix_n-1&&!f[j];j++);//找下一个非空子表if(f[j]){s1[t].next=f[j];t=e[j];}//链接两个非空子表}sl[t].next=0;}此文档收集于网络，如有侵权请联系网站删除只供学习与交流（3）链式基数排序算法[3]voidradixsort(sllist&l){inti;arrtype_nfn,en;arrtype_cfc,ec;for(i=0;il.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);}}voidarrange(sllist&l)//按指针链表整理静态链表{intp,q,i;slnodetemp;p=l.sl[0].next;for(i=1;il.length;i++){while(pi)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;}}此文档收集于网络，如有侵权请联系网站删除只供学习与交流（4）二分查找函数定义[4]intbinsearch(sllistl,keytypekey[]){intlow,high,mid;low=1;high=l.length;while(low=high){mid=(low+high)/2;if(strcmp(key,l.sl[mid].keys)==0)returnmid;elseif(strcmp(key,l.sl[mid].keys)0)high=mid-1;elselow=mid+1;}return0;}五、测试数据航班信息输入如图：此文档收集于网络，如有侵权请联系网站删除只供学习与交流按航班号查询：输入航班号错误则显示如下图：按航班起点站查询：此文档收集于网络，如有侵权请联系网站删除只供学习与交流按航班起点查询：按起飞时间查询：显示查询主菜单，退出查询系统：此文档收集于网络，如有侵权请联系网站删除只供学习与交流六、收获与体会通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。而对于有序序列的查找算法，二分查找是一种效率比较高的方法。在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。本次实验的问题只要通过调试和对整个程序的理解，便可以解决所有的发现的问题本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查