2022年数据结构课程设计航班查询系统实验报告

1、目 录TOC o 1-3 h u HYPERLINK l _Toc32144 一、概述 PAGEREF _Toc32144 1 HYPERLINK l _Toc13871 二、系统分析 PAGEREF _Toc13871 1 HYPERLINK l _Toc7774 1.航班信息的查询与检索 PAGEREF _Toc7774 1 HYPERLINK l _Toc24534 2.航班信息查询与检索数据结构理论 PAGEREF _Toc24534 1 HYPERLINK l _Toc23760 三、概要设计 PAGEREF _Toc23760 2 HYPERLINK l _Toc21361 1.系

2、统的功能 PAGEREF _Toc21361 2 HYPERLINK l _Toc20948 2.系统模块分析及其流程图 PAGEREF _Toc20948 3 HYPERLINK l _Toc28424 四、详细设计 PAGEREF _Toc28424 6 HYPERLINK l _Toc20675 1.各函数说明 PAGEREF _Toc20675 6 HYPERLINK l _Toc14398 2.定义相关数据类型 PAGEREF _Toc14398 8 HYPERLINK l _Toc29112 3. 航班信息的查询 PAGEREF _Toc29112 9 HYPERLINK l _T

3、oc29628 五、 运行由于测试 PAGEREF _Toc29628 12 HYPERLINK l _Toc10185 六、总结与心得 PAGEREF _Toc10185 16 HYPERLINK l _Toc19719 参考文献 PAGEREF _Toc19719 16 HYPERLINK l _Toc2567 附录 PAGEREF _Toc2567 16一、概述 随着信息产业的飞速发展，信息化管理及查询已经进入并应用到各行各业，影响着人们的价值观念和生活方式。因此，要提高企业信息化建设，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，从而提高企业综合实力。 本次设计是针对航班

4、的查询系统，该设计要求对飞机航班信息进行排序和查询。可按航班的航班号、起点站、终点站等信息进行航班信息的查询。二、系统分析1.航班信息的查询与检索进入系统后，首先提示输入航班的信息，包括：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价等，票价为整型，其他为字符型。当输入完一个信息后会提示是否继续输入，重复以上步骤输入全部的信息。进入主菜单后会给出用户操作的界面，根据提示进行航班信息的查询。2.航班信息查询与检索数据结构理论针对在本该类系统中的数据的处理情况，本系统采用二分查找法、基数排序法、最高位优先法。二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，

5、可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果xan/2，则我们只要在数组a的右 半部继续搜索x。对航班号的排序是采用的基数排序法。基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。最高位优先(Most Sign

6、ificant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。三、概要设计1.系统的功能本任务要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。本设计主要是对排序以及查找等概念进行综

7、合练习。以链式基数排序为主线，用到二分查找和顺序查找等知识，还有建立静态链表等相关概念。航班信息查询系统航班信息查询系统按航班号查询退出系统输入航班信息按起点站查询按终点站查询按到达时间查询按起飞时间查询2.系统模块分析及其流程图（1）航班排序对输入系统内的航班首先要进行排序，我们采用的基数排序，从低位到高位依次对关键字进行分配和收集，分两段实现其算法流程图。NN每段进行串式基数排序Y开始输入数据数组，基数n,长度Max分配收集操作轮数nT=0将数据分成P段每段n/p个nT+=1nT=Max结束 （2)时间查找根据航班的起飞时间（到达时间）查找航班的信息。开始开始输入查询时间Time=1按抵达

8、时间查询按起飞时间查询返回查询信息否是（3)二分法查找功能开始开始输入航班号输入航班号对应序号Low=highMid=(high+low)/2Low=mid+1Num=midfight numberNummidfight number返回High=mid+1否是（4)显示功能显示功能是将所求单词的所有行列信息依次显示在屏幕上。四、详细设计1.各函数说明1.一趟分配函数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

9、.next;p;p=slp.next)j=slp.keysi%65;if(!fj)fj=p;elseslej.next=p;ej=p;2.一趟收集函数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;3.链式基数排序void radixsort(sllist &l)/链式基数排序函数int i

10、;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);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

11、)=0)return mid;else if(strcmp(key,l.slmid.keys)=1&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)case 1

12、: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,l.slk.keys,l.slk.others.start,l.slk.others.end,l.slk.others.sche,l.slk.others.time1,l.slk.others.ti

13、me2,l.slk.others.model,l.slk.others.price);printf(*n);break;case 2:printf(输入要查询的航班起点站名:);scanf(%s,key);seqsearch(l,key,i);break;case 3:printf(输入要查询的航班终点站名:);scanf(%s,key);seqsearch(l,key,i);break;case 4:printf(输入要查询的航班起飞时间:);scanf(%s,key);seqsearch(l,key,i);break;case 5:printf(输入要查询的航班到达时间:);scanf(%

14、s,key);seqsearch(l,key,i);break;case 0:printf(nnn 再 见nnn);运行由于测试六、总结与心得在本次试验中，遇到了很多的问题。首先，按照书上的代码输入后，有很多错误，发现里面的代码有顺序不对的，有没有定义的等问题，经过修改解决了这些问题。其次，就是在输入时遇到了输入不当得问题，修改输入方法后得到了修改。最后，便是对几个算法的理解不是很透彻，对算法的具体实现了解不深。针对以上问题，对各个算法解读了还几次，对算法的理解有了一定的理解，对整个系统运行有了全面的了解。参考文献1严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.2007.2谭浩

15、强.C程序设计.北京:清华大学出版社.1999.12.3苏仕华.数据结构 课程设计.机械工业出版社附录#include #include #define maxspace 100#define keylen 7#define radix_n 10#define radix_c 26typedef char keytype;typedef struct char start6;char end6;char sche10;char time15;char time25;char model4;int price;infotype;typedef structkeytype keyskeylen;i

16、nfotype others;int next;slnode;typedef structslnode slmaxspace;int keynum;int length;sllist;typedef int arrtype_nradix_n;typedef int arrtype_cradix_c;void 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;el

17、seslej.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&!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.

18、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.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;arrtyp

19、e_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(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;

20、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)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);print

21、f(* 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 *n);for(j=1;j=1&i=5)printf(*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)case 1

22、: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,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);prin