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

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

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

3、3682桂林南京2.3.4.6.7205022151M901380HU1836上海北京每日094011207381250CZ3528成都厦门1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.611015114013281160SC7425青岛海口1.3.619202120DH41630其中航班号一项的格式为：K0K1K2K3K4K5CZ3869教育资料其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号,这种航班号关键字可分成两段，即字母和数字。其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。n、设计进度及

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

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

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

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

8、先定义了一个教育资料用于储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。在查询设计中，使用二分查找法对排好序的航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。2、流程图起点站终点站航班期起飞时间到达时间机型票价航班记录类型关键字表结点静态链表，s10为头结关键字长四、详细设计1,定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：1typedefstructcharstart6;/charend6;/charsche10;/chartime15;/chartime

9、25;/charmodel4;/intprice;/infotype;/typedefstructkeytypekeyskeylen;/infotypeothers;intnext;slnode;/typedefstructslnodeslmaxspace;/八、intkeynum;/教育资料intlength;/当前表长sllist;/静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedefintarrtype_n10;/十进制数字指针数组typedefintarrtype_c26;/26个字母指针数组2.算法实现(1) 一趟分配算法2voiddistribut

10、e(slnode*sl,inti,arrtype_nf,arrtype_ne)intj,p;for(j=0;j<radix_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;/将p指向的结点插入到第j个结点(2) 一趟收集算法voidcollect(slnode*sl,inti,arrtype_nf,arrtype_ne)intj,t;for(j=0;!fj;j+);/找第一个非空子表s10.next=fj;t=ej;whil

11、e(j<radix_n-1)for(j=j+1;j<radix_n-1&&!fj;j+);/找下一个非空子表if(fj)s1t.next=fj;t=ej;/链接两个非空子表教育资料将普通的线性表改为静态按最低位优先依次对各关键字收集按指针链表整理静态链)slt.next=0;)(3)链式基数排序算法3voidradixsort(sllist&l)(inti;arrtype_nfn,en;arrtype_cfc,ec;for(i=0;i<l.length;i+)l.sli.next=i+1;l.sll.length.next=0;/链表for(i=l.k

12、eynum-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.sl0.next;for(i=1;i<l.length;i+)(while(p<i)p=l.slp.next;q=l.slp.next;if(p!=i)(temp=l.slp;l.slp=l.sli

13、;教育资料l.sli=temp;/交换记录l.sli.next=p;)p=q；)(4)二分查找函数定义4intbinsearch(sllistl,keytypekey)(intlow,high,mid;low=1;high=l.length;while(low<=high)(mid=(low+high)/2;if(strcmp(key,l.slmid.keys)=0)returnmid;elseif(strcmp(key,l.slmid.keys)<0)high=mid-1;elselow=mid+1;)return0;)五、测试数据航班信息输入如图：教育资料按航班号查询:输入航班

14、号错误则显示如下图:按航班起点站查询:教育资料航班信息查询系统-*M-K-*Fm三间间沅班点点航远终一-一123450请选择£0T”曾入要查询的航班起点站名;上海*航班号起点站终点站随班期起飞时间到达时间机型票价*MU5341上海广州每日14201615M901280*MM8923上海南宁1.3.51201512877400*按航班起点查询:*C：WindovsVsysteiii3ZDebiigBH.exe*航班信息查询系统*口京站昌统朝点只飞达出冬123450请选择,旧-SX翁人要查询的航班起点站等南昌按起飞时间查询:教育资料显示查询主菜单，退出查询系统:*航班信息查询系统*-ia

15、|x|n冢站间间啰班点点需终起患123450M-请选择:p见Pressanykeytocontinue六、收获与体会通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。而对于有序序列的查找算法，二分查找是一种效率比较高的方法。在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。在程序的定义过程中

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

17、表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。七、参考文献1徐孝凯，魏荣数据结构，机械工程出版社2谭浩强程序设计，北京大学出版社3杨路明C语言程序设计教程，北京邮电大学出版社4耿国华数据结构-C语言描述，高等教育出版社八、附录源程序清单：#include<stdio.h>#include<string.h>#defineMaxSpace100#definekeylen7#defineRADIX_n10#defineRA

18、DIX_c26typedefcharKeyType;typedefstruct(charstart6;/起点charend6;/终点charsche10;/班期教育资料chartime15;/chartime25;/charmodel4;/intprice;/InfoType;/typedefstruct起飞时间到达时间机型票价航班记录类型KeyTypekeyskeylen;/关键字（航班号）intnext;SLNode;/typedefstructSLNodeslMaxSpace;/intkeynum;/intlength;/SLList;/静态链表结点类型静态链表，s10为头结点记录当前关

19、键字字符个数当前表长静态链表类型InfoTypeothers;typedefintArrType_nRADIX_n;/十进制数字指针数组typedefintArrType_cRADIX_c;/26个字母指针数组/一趟数字字符加己函数一voidDistribute(SLNode*sl,inti,ArrType_nf,ArrType_ne)intj,p;for(j=0;j<RADIX_n;j+)/各子表置为空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%48;/将数字字符转换成相对应的数值型数字if(!fj)fj=p;elseslej.ne

20、xt=p;ej=p;/将p指向的结点插入到第j个子表中/一趟数字字符的收集函数voidCollect(SLNode*sl,inti,ArrType_nf,ArrType_ne)intj,t;教育资料for(j=0;!fj;j+)/找第一个非空子表sl0.next=fj;/s10.next指向第一个非空子表中的一个结点t=ej;while(j<RADIX_n-1)找下一个非空子表(for(j=j+1;j<RADIX_n-1&&!fj;j+)/if(fj)/链接两个非空子表指向最后一个非空子表中的最后一个结点(slt.next=fj;t=ej;slt.next=0;/t

21、/一趟字母字符分配函数voidDistribute_c(SLNode*sl,inti,ArrType_cf,ArrType_ce)(-intj,p;for(j=0;j<RADIX_c;j+)/各子表置为空表fj=ej=0;for(p=sl0.next;p;p=slp.next)j=slp.keysi%65;/将字母字符转换成在字母集中相应的序号(0-25)if(!fj)fj=p;elseslej.next=p;ej=p;/一趟字母字符收集voidCollect_c(SLNode*sl,inti,ArrType_cf,ArrType_ce)intj,t;for(j=0;!fj;j+);sl

22、0.next=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;/链式基数排序函数voidRadixSort(SLList&L)/inti;ArrType_nfn,en;ArrType_cfc,ec;for(i=0;i<L.length;i+)L.sli.next=i+1;/0L.slL.length.next=0;/for(i=L.keynum-1;i>=2;i-)链式号单兀仅存放指针，不存储内容将普通的线

23、性表改造为静态链表/按最低位优先次序对各关键字进行分配和收集，先做低4位数字部分Distribute(L.sl,i,fn,en);Collect(L.sl,i,fn,en);for(i=1;i>=0;i-)/对高位的2位大写字母进行分配和收集Distribute_c(L.sl,i,fc,ec);Collect_c(L.sl,i,fc,ec);/按指针链重新整理静态链表voidArrange(SLList&L)/intp,q,i;SLNodetemp;p=L.sl0.next;/pfor(i=1;i<L.length;i+)/l.s11重新整理指向第一个记录的当前位置i-1已

24、按关键字有序化while(p<i)p=L.slp.next;q=L.slp.next;if(p!=i)/q找到第i个记录，并用p指向其在L中当前位置指向尚未调整的表尾教育资料temp=L.slp;L.slp=L.sli;L.sli=temp;L.sli.next=p;/交换记录p=q;/p指向尚未调整的表尾，为找第i+1个记录做准备/二分查找函数intBinSearch(SLListL,KeyTypekey)(intlow,high,mid;low=1;high=L.length;while(low<=high)(mid=(low+high)/2;if(strcmp(key,L.s

25、lmid.keys)=0)returnmid;elseif(strcmp(key,L.slmid.keys)<0)high=mid-1;elselow=mid+1;return0;/顺序查找函数voidSeqSearch(SLListL,KeyTypekey,inti)(intj,k,m=0;prnfS*N');printf("*航班号起点站终点站航班期起飞时间到达时间机型票价*n");for(j=1;j<=L.length;j+)(switch(i)(case2:k=strcmp(key,L.slj.others.start);break;case3:

26、k=strcmp(key,L.slj.others.end);break;case4:k=strcmp(key,L.slj.others.time1);break;case5:k=strcmp(key,L.slj.others.time2);break;if(k=0)(教育资料m=1;printf("*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*n",L.slj.keys,L.slj.others.start,L.slj.others.end,L.slj.others.sche,L.slj.others.time1,L.slj.others.time2

27、,L.slj.others.model,L.slj.others.price);if(m=0)printf("*无此航班信息，可能是输入错误！*n");prnfS*N');/查询检索菜单控制程序voidsearchcon(SLListL)KeyTypekeykeylen;inti=1,k;while(i>=1&&i<=5)printf("*n");printf("*航班信息查询系统*n");printf("*号站站即班点点2航起终4.*n")*n")*n")起

28、飞时间*n")printf("*5.printf("*0.到达时间*n")退出系统*n")printf("*n");printf("请选择(0-5):n");scanf("%d",&i);switch(i)case1: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);prnfS*N');break