《数据结构-课程设计》航班查询系统实验报告

1、 TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 一、概述1 HYPERLINK l bookmark2 o Current Document 二、系统分析1.航班信息的查询与检索 1.航班信息查询与检索数据结构理论 1 HYPERLINK l bookmark8 o Current Document 三、概要设计2.系统的功能2.系统模块分析及其流程图 3四、详细设计6.各函数说明6.定义相关数据类型 81.航班信息的查询9五、运行由于测试12 HYPERLINK l bookmark62 o Current Document 五

2、、总结与心得16 HYPERLINK l bookmark64 o Current Document 参考文献16附录16概述随着信息产业的飞速发展，信息化管理及查询已经进入并应用到各行各业，影响着人们的价值观念和生活方式。因此，要提高企业信息化建设，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，从而提高企业综合实力。本次设计是针对航班的查询系统，该设计要求对飞机航班信息进行排序和查询。可按航班的航班号、起点站、终点站等信息进行航班信息的查询。系统 分析航 班 信息 的 查询 与 检 索进入系统后，首先提示输入航班的信息，包括：航班号、起点站、终点站、班期、起飞时间、到达时间、飞

3、机型号及票价等，票价为整型，其他为字符型。当输入完一个信息后会提示是否继续输入，重复以上步骤输入全部的信息。进入主菜单后会给出用户操作的界面，根据提示进行航班信息的查询。航 班 信息 查 询与 检 索 数 据结 构 理 论针对在本该类系统中的数据的处理情况，本系统采用二分查找法、基数排序法、最高位优先法。二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用 O(log n) 完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2 与欲查找的 x 作比较，如果x=an/2则找到x,算法终止。如 果xan/2,则我们只要 在数组 a 的右

4、半部继续搜索x 。对航班号的排序是采用的基数排序法。基数排序法又称“桶子法”( bucket sort )或 bin sort ，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为 O (nlog(r)m),其中r为所采取的基数，而m为堆 数，在某些时候，基数排序法的效率高于其它的比较性排序法。最高位优先(Most Significant Digit first) 法，简称 MSL&:先按 k1排序分组，同一组中记录，关键码 k1 相等，再对各组按 k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到

5、按最次位关键码 kd 对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先 (LeastSignificant Digit first) 法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1 排序后便得到一个有序序列。概要 设计. 系 统 的功 能本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综合练习。以链式基数排序为主线，用到二分查找和顺序查找等 知识，还有建立静态链表等相关概念。.系统模块分析及其流程图(1)航班排序对输入系统内的航班首先要进行排序，我们

6、采用的基数排序，从低位到高 位依次对关键字进行分配和收集，分两段实现其算法流程图。(2)时间查找根据航班的起飞时间(到达时间)查找航班的信息。(3)二分法查找功能4)显示功能显示功能是将所求单词的所有行列信息依次显示在屏幕上。、 详细 设 计各 函 数说 明. 一趟分配函数void distribute_c(slnode*sl,int i,arrtype_c f,arrtype_c e)/ 一趟字母分配字符函数int j,p;for(j=0;jradix_c;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;el

7、seslej.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(jradix_c-1)for(j=j+1;jradix_c-1&!fj;j+);if(fj)slt.next=fj;t=ej;slt.next=0;.链式基数排序void radixsort(sllist &l)/ 链式 基数排序函数int i;arrtype_n fn,en;arrtype_c fc,ec;for(i=0;i=2;i-)di

8、stribute(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);4.二分法查找函数int binsearch(sllist l,keytype 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)=1&

9、i=5)printf(n*n);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,&i);printf(n);switch(i)case1:printf(输入要查询的航班号(字母要大写):);scanf(%s,key);k=binsearch(l,key);printf(I *n)

10、;if（k=0）printf（* 无此航班信 息，可能是输入错误！ *n）;elseprintf（* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n）;printf(*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*n,l.slk.keys,l.slk.others.start,l.slk.others.end,l.slk.others.sche,l.slk.others.time1,l.slk.others.time2,l.slk.others.model,l.slk.others.price);printf(*n);break;case2:print

11、f( 输入 要查询的航班起点站名:);scanf(%s,key);seqsearch(l,key,i);break;case3:printf( 输入 要查询的航班终点站名:);scanf(%s,key);seqsearch(l,key,i);break;case4:printf( 输入 要查询的航班起飞时间:);scanf(%s,key);seqsearch(l,key,i);break;case5:printf( 输入 要查询的航班到达时间:);scanf(%s,key);seqsearch(l,key,i);break;case0:printf(nnn 再 见 nnn);航斑期起飞时间到达

12、时间肮班期起F悯到达时间3.7 H900 明领 733 40萌航班明起飞时间到达时间3.8 I0VWH HSMW ?J3 W9肮班朋起飞时间到达时间3.4 09M 1506 733 2000肮W期起飞时间到达时间3.6 0980 5白阑 733 4mmh肮班期起飞时间到达时间3.S 的嗣 1506 733 2001翻建B起飞时间到达时间 1420 115 M90 12&6肮班期起飞时间到达时间 6 0&5S 1035 733 IfilO4.5 1055 1240 733 969HU5341终点站5国1*2-S237储 1238终点站终点站 回1.2.RPW；9揄黔/r痣黔瞿客蠹站 而6,重庆

13、深圳2.4.皓?y/m = y起点站终点站 GZ1236费用巴西12. 人呜才/口一*断辩信息查询系统与站昌统一一 班点点一 后起”起目 一一继续输i北厅 1*2*屿？星舟退筮点站工林广州每日筵续航 鲁GZ234除了GZ1235 继续输/ 成班牙:吗？n” 匕南站羹点站 PWt 1-2- 吗？“口 = v机型 机型 机型 机型 机型 机型 机型 机型录iii票你票你票价票价票价票价票价GZ1239 山东 巴西 1.E.3.H 9900 0RP0 733 钿的恨续输入诙 J M： M；帙 HEM W”注注制衽 * * M * M” “ML 亡6,玳玛文件夹 Dwbug CppZ.ese1juF

14、ua -ur ivf ub tjj- ur im u- _ kf u J kJ- u- -u u, FkJ*肮班信息查询系统*麻MMJt* H(lr统犬点点现点占飞达出展终起是( 一12 3 4 5 0潮&附ii.人要查恂的航班号字母要大写AS l如4无此航班信息可能是输入懵误！ “u Hl Ji M T 一 1 1 J j j-航班信息查询系统京站间间统B7HT案 空点飞蓄 1 S 3 4 S 0 *航班号踪:苗GZ1235 贵州航班期起飞时间到达时间机型票检1.2.3.50908150B733 2061 *清选择I入要查询的肮班起点站名;北京*肮班信息查询系统*ntriSS身统 现占点飞日

15、 12 3 4 5 0M M M M M M M M M MM*航班信息查询系统-航班号GZ12371.2.3.7航班期起飞时间到达时间机型票价-0960M NHM N M M NHM N N. H M M M MIA N. N. K H M M Nlfl M. MdM M M M N M M. MdM M .M H M My * 胁* M M V itt W M M： MdM H* W 幡注伏,二 二二 京站鸟竺 狂耳号7Ht肘一予一一 初点占八飞诙出 , 睢 岳 *- 二 12 3 4 5 0 K二MA 二* * 情修杵弄二俞人要查询的航班终点站名;北京航班号超卢站终的解好期起飞时间到达时

16、间机型票价-81544合肥北京 1.2,4,5 1B5S 1240733960 *W. M. M1cM.M, -J :. M. M i 航班信息查询系统wMiw w-Mriv vA-htMtm ” -Mi ri请选择g-h4航班号 CZ1394 GZ1S3& GZ123& GZ123? GZ123B GZ123B|1 北里 11 iL上09萌7332 g的B9HBiB07332日U1酎腼典陋73340W的加隔的733钠阙的削鸵）幽7334小H?00随的?33的姗V X要查询的航班起飞时间:号鞭终点站航班期起飞B寸间到达时间机型早价， 天津 1.3.3.41.2,3.6 C71.2,3.81.2

17、,3,8一 -12 3 15 8班占百飞达出时时系三沿砧闫闰.汽埼人要查询的航班到诊时间=8RHR航班号马总站终点站航班期 至州 西西1-2-3.1_2.3.1-2-3-GZ123&GZ123?GZ1238GZ1238山布起飞时间 E 090H ?M09UQK萌羽7334000M幽阙7334000*防勾画浮7334000丽曲7334厮H* M X * * * * M-出正时间机型票价，杭班仁定查询军统*六、 总结 与心得在本次试验中，遇到了很多的问题。首先，按照书上的代码输入后，有很多错误，发现里面的代码有顺序不对的，有没有定义的等问题，经过修改解决了这些问题。其次，就是在输入时遇到了输入不当

18、得问题，修改输入方法后得到了修改。最后，便是对几个算法的理解不是很透彻，对算法的具体实现了解 不深。针对以上问题，对各个算法解读了还几次，对算法的理解有了一定的理解，对整个系统运行有了全面的了解。参考文献1严蔚敏 吴伟民.数据结构（C语言版）.北京：清华大学出版社.2007.谭浩强 .C 程序设计 . 北京 : 清华大学出版社.1999.12.苏仕华 . 数据结构 课程设计 . 机械工业出版社#include #include #define maxspace 100#define keylen 7#define radix_n 10#define radix_c 26typedef char

19、 keytype;typedef structchar start6;char end6;char sche10;char time15;char time25;char model4;int price;infotype;typedef structkeytype keyskeylen;infotype others;int next;slnode;typedef structslnode slmaxspace;int keynum;int length;sllist;typedef int arrtype_nradix_n;typedef int arrtype_cradix_c;void

20、 distribute(slnode *sl,int i,arrtype_n f,arrtype_n e) int j,p;for(j=0;jradix_n;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;if(!fj)fj=p;elseslej.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(jradix_n-1)for(j=j+1;jradix_n-1&

21、!fj;j+);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;jradix_c;j+)fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.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.n

22、ext=fj;t=ej;while(jradix_c-1)for(j=j+1;jradix_c-1&!fj;j+);if(fj)slt.next=fj;t=ej;slt.next=0;void radixsort(sllist &l)/ 链 式int i;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

23、(sllist &l)/重新整理int p,q,i;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,keytype key)int low,high,mid;low=1;high=l.length;while(low=high)mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0)

24、return mid;else if(strcmp(key,l.slmid.keys)0) high=mid-1;elselow=mid+1;return 0;void seqsearch(sllist l,keytype key,int i)int j,k,m=0;printf(*n);printf（* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n）;for(j=1;j=1&i=5)printf(*n);printf（ * 航班信息查询系统*n）;printf(*n);printf(*1.航班号*n);printf(*2.起点站*n);printf(*3.终点站*n)

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