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

1、学院名称数据结构课程设计报告题目一一航班信息查询与检索班 级：姓 名：时 间：2012/12/29-2013/1/5二。一二年十二月二十九日课程设计任务书及成绩评定课题航班信息查询与检索名称I、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解， 最终使学生能够熟练应用数据结构的知识写程序。(1)通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。(2)能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正 确求解过程并编写代码实现。2、设计题目要求：问题描述：该设计要求对飞机航班信息进行排序和查找。 可按航班的航班号、起点

2、站、 到达站、起飞时间以及到达时间等信息进行查询。任务要求：对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排 序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查 找可采用最简单的顺序查找方法进行，因此他们用得较少。每个航班记录包括八项，分 别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等， 假设航班信息表(8条记录)航 班号起 点站终 点站班期起飞时 问到达 时间机 型票 价CA1544合 肥北 京1.2.4 .51055124073396 0MU5341上 海广 州每日14201615M901280CZ3869重 庆深 圳2

3、.4.6085510357331010MU3682桂 林南 京2.3.4 .20502215M901380HU1836上 海北 京每日094011207381250CZ3528都成门厦1.3.4 .15101650RJC6010594MU4明昆安西.61.3.5101511402836011425SC7岛青口海1.3.619202120H4D3016其中航班号一项的格式为：K0 K1 K2 K3 K4 K5CZ3869其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后 4位为航班号, 这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的 核心，因此除了票价为

4、数值型外，均定义为字符串即可。n、设计进度及完成情况日 期内容选取参考书，查阅有关文献资料，完成资料搜集和系统分 析工作。创建相关数据结构，录入源程序。调试程序并记录调试中的问题，初步完成课程设计报告。上交课程设计报告打印版并进行课程设计答辩，要求每个 同学针对自己的设计回答指导教师 3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统 一刻光盘上交。田、主要参考文献及资料1严蔚敏 数据结构（C语言版）清华大学出版社19992严蔚敏数据结构题集（C语言版）清华大学出版社19993谭浩强C语言程序设计 清华大学出版社4与所用编程环境相配套的C语言或C+#目关的资料IV、成绩评定：设计成

5、绩： （教师填写）指导老师： （签字）17目录一、概述 6二、系统分析 6三、概要设计 6四、详细设计 71,定义数据类型72.算法实现 8五、测试数据 10六、收获与体会 13七、参考文献 13八、附录 14概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和 课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对 所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一 门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的 选择和应用、算法的设计及其实现等方面，加深对课程

6、基本内容的理解。同时，在 程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训 练。本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二 分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。我们 可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航 班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号 进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他 关键字的查找可以采用最简单的顺序查找方法进行。二、系统分析1设计要求(1)提供对航班信息的排序功能(2)提供对航班信息的输入输出记录

7、功能找出我们所需要的查找的航班的所有 信息(3)提供按关键字(航班号)快速查询或顺序查询功能2设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排 序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字 的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间, 到达时间，飞机型号以及票价等。其中航班号一项的格式为：K0 k1 k2 k3 k4 k5C-9Z386航班关键字可分为两段，即字母和数字。其中 k0和k1是航空公司的别称，用 两个大写字母表示，后4位为航班编号。三、概要设计1、

8、设计思路根据题目所要求，程序必须实现航班信息的录入和查询。程序首先定义了一个用于储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。在查询设计中，使用二分查找法对排好序的航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。2、流程图木四、详细设计1 .定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关 的数据类型：1typedef struct char start6;算法实现(1) 一趟分配算法2void distribute(slnode *sl,int i,arrtype_n

9、 f,arrtype_n e)一一int j,p;for(j=0;j<radix_n;j+).fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48; ext=p;ej=p;ext=fj;t=ej;while(j<radix_n-1).for(j=j+1;j<radix_n-1&&!fj;j+); ext=fj;t=ej;ext=0;( 3)链式基数排序算法3void radixsort(sllist &l)int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i<

10、;i+)1 .next=i+1;.next=0; ext;for(i=1;i<i+)while(p<i)p=p.next;q=p.next;if(p!=i)temp=p;p=i;i=temp;ext=p;p=q;( 4)二分查找函数定义4int binsearch(sllist l,keytype key)int low,high,mid;low=1;high=;while(low<=high)mid=(low+high)/2;if(strcmp(key,mid.keys)=0)return mid;else if(strcmp(key,mid.keys)<0)high

11、=mid-1;elselow=mid+1;return 0;五、测试数据航班信息输入如图：起飞时间晅飞口洞配飞时I日I起飞时间 130S起飞时间 t 42F1起飞时间INWM起飞时间1与土旧至11达时间索价机型 b M2早什 1HUH4HM日达时间 133S到达时间1 512机型 52O机型 H77到达时间 21412鳖站站站施丁良言占武北岸广祺&葭遵彭南屋童泼若S:nin 技 Mg型航HII批M(:K能YM维航MH魅舸¥¥班MHH缗航XM然期,±4 航a.皆 航每 站更坳 f1210733到达时间机型早沛1 hl S1刖修到达时间矶型票价1 M：l!&g

12、t;7331 H1M票价 1SB2030877120到达时间 201机型 744票价机型nrilnmNmnln站U站货整M站"站VS踞":寇凯矗T第点晶点需期点鼐 1-上触至槊贸铀上An 后瑞专籁急输号薪荔®皤号8粤23籁按航班号查询:输入航班号错误则显示如下图:按航班起点站查询:V±nlovs sjF51cb32IDebxigBB. exe *H航班信息查询系统-基站® 班点点 航远终远襄 1-一 12 2 4 5 0请选择工0 T”曾入要查询的航班起点站名;上海 *航班号起点茸终点站艇班期起飞时间到达时间机型票价* MU5341上海广州每日

13、14201615M901280 * MM8923上海南宁1.3512001512877400 *按航班起点查询:按起飞时间查询:Jnl xK犍片蕤*注京站EE统理户八飞达出翁终起翦工 2 34.S0.M M *请世择旧-5”输入要查询的航班起飞寸间:1360iMMME M M理时戴N菁苍若MUM 航班信息查询系统*>1*»* iMMItMJffMJtMiM：* KKJfiMMME M HMM：* 3« = >6iMMME MX算 HMM Mi HEX*航班号击己点站 终息站施班期起飞时间到访时间机型 票价* VH2022 贵阳 遵义每日 13Q0133Q52目1

14、00 *-lai x|s显示查询主菜单，退出查询系统：，： Vi ndoivsV EpsteBSZlDebugViBB. exev请选择=0再见Pres any key to continue六、收获与体会通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。而对于有序序列的查找算法，二分查找是一种效率比较高的方法。在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。这次实验的过程中遇到了很多问题

15、，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。本次实验的问题只要通过调试和对整个程序的理解，便可以解决所有的发现的问题本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查找有了一个很好的掌握。其查找过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。在实验过程中，程序中许多定义需要我们有一个很仔细的了解，比如上述的对字符长度的定义，这需要对所定义的对象给一个合理的字符长度，在输入的过

16、程中才不会出现因输入的字符长度过长而不能识别。本次实验中用到了静态链表，定义静态链表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。七、参考文献1 徐孝凯，魏荣数据结构，机械工程出版社2 谭浩强程序设计，北京大学出版社3杨路明C语言程序设计教程，北京邮电大学出版社4 耿国华数据结构-C 语言描述，高等教育出版社八、附录源程序清单：#include <>#include <>#define MaxSpace 100#defi

17、ne keylen 7#define RADIX_n 10#define RADIX_c 26typedef char KeyType;typedef structchar start6; ext;p;p=slp.next)j=slp.keysi%48; ext=p;ej=p; ext=fj; ext指向第一个非空子表中的一个结点t=ej;while(j<RADIX_n-1)for(j=j+1;j<RADIX_n-1&&!fj;j+) ext=fj; t=ej; ext=0; ext;p;p=slp.next)j=slp.keysi%65; ext=p; ej=p;

18、 ext=fj; t=ej;while(j<RADIX_c-1)for(j=j+1;j<RADIX_c-1&&!fj;j+);if(fj)slt.next=fj;t=ej;slt.next=0;ext=i+1; ext=0; ext; ext; ext;ext=p; eys)=0)return mid;else if(strcmp(key,mid.keys)<0)high=mid-1;elselow=mid+1;return 0;break;case 3:k=strcmp(key,j.;break;case 4:k=strcmp(key,j.;break;ca

19、se 5:k=strcmp(key,j.;break;if(k=0)m=1;printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n",j.keys,j.,j.,j.,j.,j.,j.,j.;if(m=0)printf("* 无此航班信息，可能是输入错误！*n");printf("*n");班 号 *n");printf(" *2.printf(" *3.printf(" *4.printf(" *5.printf(" *0.起点站*n&qu

20、ot;)终点站*n")起飞时间*n")到达时间*n")退出系统*n")*n");printf("printf(" 请选择 (0-5): n");scanf("%d",&i);switch(i)case 1:printf(" 输入要查询的航班号(字母要大写):");scanf("%s",key);k=BinSearch(L,key);printf("*n");if(k=0)printf(" 无此航班信息，可能是输入错误！n");elseprintf("* 航班号 起点站 终点站 航班期 起飞时间到达时间机型 票价*n");printf("* %-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d *n",k.keys,k.,k.,k.,k.,k.,k.,k.;printf("*n