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

.PAGE.学院名称《数据结构》课程设计报告题目——航班信息查询与检索班级：__时间：2012/12/292013/1/5二○一二年十二月二十九日课程设计任务书及成绩评定课题名称航班信息查询与检索Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解,通过上机实验、调试程序,加深对课本知识的理解,最终使学生能够熟练应用数据结构的知识写程序。〔1通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。〔2能针对给定题目,选择相应的数据结构,分析并设计算法,进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。任务要求:对于本设计,可采用基数排序法对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他次关键字的查找可采用最简单的顺序查找方法进行,因此他们用得较少。每个航班记录包括八项,分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等,假设航班信息表〔8条记录航班号起点站终点站班期起飞时间到达时间机型票价CA1544XX北京.510551240733960MU5341上海XX每日14201615M901280CZ3869XXXX085510357331010MU3682XXXX.6.720502215M901380HU1836上海北京每日094011207381250CZ3528XXXX.5.715101650CRJ1060MU4594XXXX.6101511403281160SC7425XXXX19202120DH41630其中航班号一项的格式为：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++相关的资料Ⅳ、成绩评定：设计成绩：〔教师填写指导〔签字二○一三..目录6211一、概述……………610268二、系统分析………6三、概要设计………6四、详细设计………71.定义数据类型…………………72.算法实现………8五、测试数据………10六、收获与体会……………………13七、参考文献………13八、附录……………14一、概述课程设计是实践性教学中的一个重要环节,它以某一课程为基础,可以涉及和课程相关的各个方面,是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用,理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课,是计算机理论和应用的核心基础课程。数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面,加深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本课程设计主要是对排序及查找等进行练习,以链式基数排序为主线,利用二分查找和顺序查找等知识,并建立静态链表,完成对航班信息的查询与检索。我们可以利用航班的这些信息,通过其中的任意一个信息,找出我们所需要的查找的航班的所有信息,所以,我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排序好的航班记录按航班号实现快速查找,并按其他关键字的查找可以采用最简单的顺序查找方法进行。二、系统分析1设计要求<1>提供对航班信息的排序功能<2>提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息<3提供按关键字〔航班号快速查询或顺序查询功能2设计分析对于本设计,可采用基数排序法对一组具有结构特点的飞机航班号进行排序,利用二分查找法对排好序的航班记录按航班号实现快速查找,按其他次关键字的查找可采用最简单的顺序查找方法进行,因为它们用得比较少。每个航班记录包括八项,分别是：航班号,起点站,终点站,班期,起飞时间,到达时间,飞机型号以及票价等。其中航班号一项的格式为：K0k1k2k3k4k5CZ3869CZ3869航班关键字可分为两段,即字母和数字。其中k0和k1是航空公司的别称,用两个大写字母表示,后4位为航班编号。三、概要设计1、设计思路根据题目所要求,程序必须实现航班信息的录入和查询。程序首先定义了一个用于储存航班信息的数据类型,再由用户录入航班数据,在录入的同时并对数据进行排序,最后执行数据查询和检索。在查询设计中,使用二分查找法对排好序的航班数据按航班号实现快速查找,按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。定义数据类型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;j<radix_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<j<radix_n-1>{for<j=j+1;j<radix_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;i<l.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;i<l.length;i++>{while<p<i>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;}五、测试数据航班信息输入如图：按航班号查询：输入航班号错误则显示如下图：按航班起点站查询：按航班起点查询：按起飞时间查询：显示查询主菜单,退出查询系统：六、收获与体会通过本实验,我了解了基数排序是作为一种内部排序方法,当关键字位数较少而排序序列较长时,该排序算法有一定的优越性。而对于有序序列的查找算法,二分查找是一种效率比较高的方法。在本实验中,对这两种算法的应用,我加深了对他们的理解,掌握了他们的实现方法。在本次实验过程中,输入错误还是存在的问题,但能很快的通过编译解决,一些编译不能发现的问题,在组建过程中也能发现并解决。这次实验的过程中遇到了很多问题,定义的过程中存在定义不清楚的问题,还有一些模糊定义和重定义的问题出现。在程序的定义过程中,存在着函数的调用失败的问题,在调用过程中不能正常调用,通过把调用的函数直接用在程序中,不通过调用的方法,使得程序正常运行。本次实验的问题只要通过调试和对整个程序的理解,便可以解决所有的发现的问题本次实验利用二分查找法很快的完成了对航班信息的查找,使我们对二分查找有了一个很好的掌握。其查找过程是先确定待查记录所在的范围〔区间,然后逐步缩小范围直到找到或找不到该记录为止。在实验过程中,程序中许多定义需要我们有一个很仔细的了解,比如上述的对字符长度的定义,这需要对所定义的对象给一个合理的字符长度,在输入的过程中才不会出现因输入的字符长度过长而不能识别。本次实验中用到了静态链表,定义静态链表的过程中,需要有一个很熟悉的了解,知道静态链表是如何定义以及如何实现。通过这次实验,使得对于查找以及检索有了一个很好的掌握,让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。七、参考文献[1]徐孝凯,魏荣《数据结构》,机械工程出版社[2]谭浩强《程序设计》,北京大学出版社[3]杨路明《C语言程序设计教程》,北京邮电大学出版社.[4]耿国华《数据结构-C语言描述》,高等教育出版社八、附录源程序清单：#include<stdio.h>#include<string.h>#defineMaxSpace100#definekeylen7#defineRADIX_n10#defineRADIX_c26typedefcharKeyType;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[RADIX_n];//十进制数字指针数组typedefintArrType_c[RADIX_c];//26个字母指针数组//一趟数字字符分配函数voidDistribute<SLNode*sl,inti,ArrType_nf,ArrType_ne>{intj,p;for<j=0;j<RADIX_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个子表中}}//一趟数字字符的收集函数voidCollect<SLNode*sl,inti,ArrType_nf,ArrType_ne>{intj,t;for<j=0;!f[j];j++>//找第一个非空子表sl[0].next=f[j];//s1[0].next指向第一个非空子表中的一个结点t=e[j];while<j<RADIX_n-1>{for<j=j+1;j<RADIX_n-1&&!f[j];j++>//找下一个非空子表if<f[j]>{sl[t].next=f[j];t=e[j];}//链接两个非空子表}sl[t].next=0;//t指向最后一个非空子表中的最后一个结点}//一趟字母字符分配函数voidDistribute_c<SLNode*sl,inti,ArrType_cf,ArrType_ce>{intj,p;for<j=0;j<RADIX_c;j++>{//各子表置为空表f[j]=e[j]=0;}for<p=sl[0].next;p;p=sl[p].next>{j=sl[p].keys[i]%65;//将字母字符转换成在字母集中相应的序号〔0-25if<!f[j]>f[j]=p;elsesl[e[j]].next=p;e[j]=p;}}//一趟字母字符收集voidCollect_c<SLNode*sl,inti,ArrType_cf,ArrType_ce>{intj,t;for<j=0;!f[j];j++>;sl[0].next=f[j];t=e[j];while<j<RADIX_c-1>{for<j=j+1;j<RADIX_c-1&&!f[j];j++>;if<f[j]>{sl[t].next=f[j];t=e[j];}}sl[t].next=0;}//链式基数排序函数voidRadixSort<SLList&L>//链式{inti;ArrType_nfn,en;ArrType_cfc,ec;for<i=0;i<L.length;i++>L.sl[i].next=i+1;//0号单元仅存放指针,不存储内容L.sl[L.length].next=0;//将普通的线性表改造为静态链表for<i=L.keynum-1;i>=2;i-->{//按最低位优先次序对各关键字进行分配和收集,先做低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.sl[0].next;//p指向第一个记录的当前位置for<i=1;i<L.length;i++>//l.s1[1…i-1]已按关键字有序化{while<p<i>p=L.sl[p].next;//找到第i个记录,并用p指向其在L中当前位置q=L.sl[p].next;//q指向尚未调整的表尾if<p!=i>{temp=L.sl[p];L.sl[p]=L.sl[i];L.sl[i]=temp;L.sl[i].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.sl[mid].keys>==0>returnmid;elseif<strcmp<key,L.sl[mid].keys><0>high=mid-1;elselow=mid+1;}return0;}//顺序查找函数voidSeqSearch<SLListL,KeyTypekey[],inti>{intj,k,m=0;printf<"*************************************************************\n">;printf<"*航班号起点站终点站航班期起飞时间到达时间机型票价*\n">;for<j=1;j<=L.length;j++>{switch<i>{case2:k=strcmp<key,L.sl[j].others.start>;break;case3:k=strcmp<key,L.sl[j].others.end>;break;case4:k=strcmp<key,L.sl[j].others.time1>;break;case5:k=strcmp<key,L.sl[j].others.time2>;break;}if<k==0>{m=1;printf<"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",L.sl[j].keys,L.sl[j].others.start,L.sl[j].others.end,L.sl[j].others.sche,L.sl[j].others.time1,L.sl[j].others.time2,L.sl[j].others.model,L.sl[j].others.price>;}}if<m==0>printf<"*无此航班信息,可能是输入错误！*\n">;printf<"*************************************************************\n">;}//查询检索菜单控制程序voidsearchcon<SLListL>{KeyTypekey[keylen];inti=1,k;while<i>=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>:\n">;scanf<"%d",&i>;switch<i>{case1:printf<"输入要查询的航班号<字母要大写>:">;scanf<"%s",key>;k=BinSearch<L,key>;printf<"*************************************************************\n">;if<k==0>printf<"无此航班信息,可能是输入错误！\n">;else{printf<"*航班号起点站终点站航班期起飞时间到达时间机型票价*\n">;printf<"*%-8s%-7s%-6s%-11s%-9s%-7s%-5s%4d*\n",L.sl[k].keys,L.sl[k].