航班信息的查询与检索

目录21概述21.1课程设计名称21.2课程设计目的21.3课程设计内容22系统分析22.1设计要求22.2设计分析23概要设计33.1系统总流程图33.2定义数据类型33.3实现排序的各函数的说明44详细设计44.1数据类型的定义44.2链式基数排序54.2.1一趟数字字符分配函数错误!未定义书签。4.2.2一趟数字字符的收集函数错误!未定义书签。4.2.3一趟字母字符分配函数错误!未定义书签。4.2.4一趟字母字符收集错误!未定义书签。4.2.6链式基数排序函数错误!未定义书签。4.3重新整理静态链表64.4查找算法实现64.4.1二分查找函数64.4.2顺序查找函数74.5输入输出函数75运行与测试86总结与心得117参考文献118附录（程序源代码）11目录1概述1.1课程设计名称航班信息的查询与检索1.2课程设计目的通过本次实验，掌握数据结构中的几种排序算法和查找算法，了解静态链表的运用，利用上述的算法完成航班信息的查询与检索。2系统分析2.1课程设计内容本课程设计主要是对排序及查找等进行练习，以链式基数排序为主线，利用二分查找和顺序查找等知识，并建立静态链表，完成对航班信息的查询与检索。我们可以利用航班的这些信息，通过其中的任意一个信息，找出我们所需要的查找的航班的所有信息，所以，我们可以采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排序好的航班记录按航班号实现快速查找，并按其他关键字的查找可以采用最简单的顺序查找方法进行。2.2设计要求1） 提供对航班信息的排序功能2提供对航班信息的输入输出记录功能找出我们所需要的查找的航班的所有信息3）提供按关键字（航班号）快速查询或顺序查询功能2.3设计分析对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因为它们用得比较少。每个航班记录包括八项，分别是：航班号，起点站，终点站，班期，起飞时间，到达时间，飞机型号以及票价等。其中航班号一项的格式为：K0k1k2k3k4k5CZ3869航班关键字可分为两段，即字母和数字。其中kO和k1是航空公司的别称，用两个大写字母表

示，后4位为航班编号。3概要设计3.1系统总流程图航班信息的查询与检索系统航班信息的查询与检索系统按航班号查询按起飞时间查询按到达时间查询按起点站查询按终点站查询按航班号查询按起飞时间查询按到达时间查询按起点站查询按终点站查询//起点//起点//终点IIk、八、、//班期//起飞时间//到达时间//机型//票价//航班记录类型//关键字//表结点〃静态链表，s1[0]为头结点//关键字长//当前表长3.2定义数据类型根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型typedefstruct{charstart[7];charend[7];charsche[12];chartime1[5];chartime2[5];charmodel[4];intprice;}InfoType;typedefstruct{KeyTypekeys[keylen];InfoTypeothers;intnext;}slnode;typedefstruct{SLNodesl[MaxSpace];intkeylen;intlength;}SLList; 〃静态链表类型为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：typedefintArrType_n[10]; 〃十进制数字指针数组typedefintArrType_c[26]; 〃26个字母指针数组3.3实现排序的各函数的说明一趟分配函数：voidDistribute(SLNode*s1,inti,ArrTypef,ArrTypee);〃本算法是按关键字key[i]建立RADIX个子表，使同一个子表中记录的keys[i]〃相同，f[0..RADIX]和e[0..RADIX]分别指向各子表中的第一个和最后一个记录一趟搜集函数：voidCollect(SLNode*s1,inti,ArrTypef,ArrTypee);〃本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表依次成一个链表链式基数排序函数：voidRadixSort(SLList&L);〃本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两段实现二分查找函数：intBinSearch(SLListL,KeyTypekey[]);//L为待查找的表，key□为待查找的关键字，按二分查找的思想实现查找主控函数voidmain(){初始化；数据输入；排序处理；接受查找要求及查找关键字；查找处理；输出查找结果；}4详细设计4.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];〃静态链表sl[0]为头结点intkeynum;intlength;}sllist;〃记录当前关键字字符个数〃当前表长〃静态链表类型typedefintarrtype_n[radix_n];〃十进制数字指针typedefintarrtype_c[radix_c];//26个字母指针4.2链式基数排序

4.3重新整理静态链表重新整理静态链表，P指示第一个记录的当前位置，L.sl[l..i-1]已按关键字有序排列，第一个记录在L中的当前位置应不小于i,使用while循环，找到第i个记录，并用p指示其在L中的当前位置，而q指示尚未调整的表尾，若if(p!=i)则p指向被移走的记录，使得以后可由while循环找回，当p=q时，p指向尚未调整的表尾，为找到第i+个记录做准备4.4查找算法实现4.4.1二分查找函数输入航班号对应序列号4.4.2顺序查找函数voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;for(j=1;j<L.length;j++){switch(i){case2:k=strcmp(key,L.s1[j].others.start);break;case3:k=strcmp(key,L.s1[j].others.end);break;case4:k=strcmp(key,L.s1[j].others.time1);break;case5:k=strcmp(key,L.s1[j].others.time2);break;}if(k==0){m=1;Display(L,j);}}if(m==0)printf(”无此航班信息，可能是输入错误！\n");}4.5输入输出函数serachcon(SLListL){inti=1,k,k1;while(i>=1&&i<=5){printf("*****************************\n");printf("*航班信息查询系统*\n");printf("*1航班号*\n");printf("*2起点站*\n");printf("*3终点站*\n");printf("*4起飞时间*\n");printf("*5到达时间*\n");printf("*0退出系统*\n");*J「11 \ff\-**%1--1-f11 \-**%11•printf("请选择0-5：\n");scanf("%d",&i);switch(i){case1:printf("输入要查的航班号(字母要大写)：”);scanf("%s",key);k=BinSearch(L,key);Display(L,k);break;case2:printf(”输入要查询的航班起点站名：");scanf("%s",key);SeqSearch(L,key,i);break;case3:printf(”输入要查询的航班终点站点：");scanf("%s",key);SeqSearch(L,key,i);break;case4:printf(”输入要查询的航班起飞时间：");scanf("%s",k1);SeqSearch(L,k1,i);break;case5:printf(”输入要查询的航班到达时间：");scanf("%s",k1);SeqSearch(L,k1,i);

break;case0:printf("再见！\n");return0;}}}voidInputData(SLList&L){inti=++L.length;charyn='y';while(yn=='y'IIyn=='Y'){printf("航班号起点站终点站航班期起飞时间到达时间机型票价\n");scanf("%s%s%s%s%s%s%s%d",L.sl[i].keys,L.sl[i].others.start,L.sl[i].others.end,L.sl[i].others.sche,L.sl[i].others.timel,L.s1[i].others.time2,L.s1[i].others.model,&L.s1[i].others.price);++i;printf("继续输入吗？y/n:\n");scanf("%c",&yn);}L.length=i-1;}5运行与测试航班信息输入如图ILHP:S.V± s.%.s.yet. SJ)eihn bm.pseo*起飞时间到达旳间叽刑票价51B55 1246 733966起飞时间到达时间机型芋价14^0 1615 H¥B12BB起飞时间到达时间机型幕价0055 1B35 7331B1B起飞时间到达日寸间机型票价130© ±330 528±00起飞时间到达旳间机型票价1200 1512 8??4BEI起飞时间到达旳间机型票倚1520 2012 SB2100B起飞时间到达日寸间机型票价1306 2033 877±230起飞时间到达时司机型票价123@ 2@13 7441@2@n"^■m~>月w理MfMf其班2.wn普班日航班期丄.3■占航班期±_5航班期1=3.4航班期2=4站站〔實斗州占和H.r-y'-■占衍—1-lcluZI占几占《IU川占几占"点肥旺点海歹点莽点阳即点海站g点京旺点欝己'I-1.-匕oTn&H己「-口nd,DLkH己4「口丿"—%走上A-Tk^AJNLA、衣上，幣一Aj寸h、才14-匚\号44输号41轡！P“输号22输号239“输号53输号23输J'lI炜藩沙怨煎:IH纹J'li爼掰沁注Jill"缰J'll畀落II承庇狀惟.1JLIU崔亢愆M崔.yL-lm崔二几童H崔.IJL'X崔McM士-■知cM±l.田WPEZHX±_-按航班号查询:-!□!x|Hj-!□!x|HjlnlxlCN卜航班号起点站终点姑航班期起飞时间到达时间机空克仆**MU5341上;每 .1：卜航班号起点站终点姑航班期起飞时间到达时间机空克仆**MU5341上;每 .1：1,|,|吗日 1420 1615 lltiti*输入航班号错误则显示如下图:*C:\.T±ndjove\syet«b32VDehn@：\.bb.aza*航班信息査询系统*I二肮期忙息色询系轨X^BC"3BC"3Bi^BC"3BC"3BC"3Bt!lBtB3BC"3BC"3BtB3|C"3BC"3BC"3BC"3Bfr3BC"3BtB3BC"3BtTOC\o"1-5"\h\zX 1 妙:灵 Xm H_iEH 占站 m芒站 *4-ti E吋間 *—列达II寸冋 ***************卅********请览扌平5-9》：输人妾査向的航班号■:字勺^A^^MU5341〕話站硕嚟豐w钢-----123450in览捋-5-恥=输几旻鱼向的航班号■:宁®^AH＞：MU5431儿此航班恬思.nJ能是输人钳ix!按航班起点站查询:管戸站终石辰班朗起飞时间到达时'可机型票价管戸站终石辰班朗起飞时间到达时'可机型票价*LB航班信息查询系统*JOOCKJOOOCJCJOOOCKJOOOCKJCC:\TiQdoTE\EysteB321Deb-u航班信息查询系统*JOOCKJOOOCJCJOOOCKJOOOCKJC耳耳JOCKXK耳耳>O<K>OCKK>O<KK*航班信息直询貝统*XXJ(M：KXKKKJOCXKKKJCKKX1•肌班2•起点TOC\o"1-5"\h\z3.4.5.0.XXJCJOO<XJOO<XXXJOOO<XXK请选择<0-5>：输入要查询的航玖［起点站名;南匡按起飞时间查询:显示查询主菜单，退出查询系统:EB :\Tind9VEYsyEteB32YDebng\BB.exen_石站间间统Is123450请选择<0-5>：0再见Pressanykeytocontinue总结与心得通过本实验，我了解了基数排序是作为一种内部排序方法，当关键字位数较少而排序序列较长时，该排序算法有一定的优越性。而对于有序序列的查找算法，二分查找是一种效率比较高的方法。在本实验中，对这两种算法的应用，我加深了对他们的理解，掌握了他们的实现方法。在本次实验过程中，输入错误还是存在的问题，但能很快的通过编译解决，一些编译不能发现的问题，在组建过程中也能发现并解决。这次实验的过程中遇到了很多问题，定义的过程中存在定义不清楚的问题，还有一些模糊定义和重定义的问题出现。在程序的定义过程中，存在着函数的调用失败的问题，在调用过程中不能正常调用，通过把调用的函数直接用在程序中，不通过调用的方法，使得程序正常运行。本次实验的问题只要通过调试和对整个程序的理解，便可以解决所有的发现的问题本次实验利用二分查找法很快的完成了对航班信息的查找，使我们对二分查找有了一个很好的掌握。其查找过程是先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。在实验过程中，程序中许多定义需要我们有一个很仔细的了解，比如上述的对字符长度的定义，这需要对所定义的对象给一个合理的字符长度，在输入的过程中才不会出现因输入的字符长度过长而不能识别。本次实验中用到了静态链表，定义静态链表的过程中，需要有一个很熟悉的了解，知道静态链表是如何定义以及如何实现。通过这次实验，使得对于查找以及检索有了一个很好的掌握，让我们在以后的程序设计过程中对于类似的函数定义有一个很清晰的过程以及了解。参考文献1）X孝凯，魏荣《数据结构》，机械工程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];intkeynum;intlength;}SLList;//关键字（航班号）//静态链表结点类型〃静态链表，s1[0]为头结点//记录当前关键字字符个数//当前表长//静态链表类型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]; 〃sl[0].next指向第一个非空子表中的一个结点t=e[j];while(j<RADIX_n-l){for(j=j+l;j<RADIX_n-l&&!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-25)if(!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=l;ivL.length;i++)〃l.sl[l・・・i-l]已按关键字有序化{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=l;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-l;elselow=mid+l;}return0;}//顺序查找函数voidSeqSearch(SLListL,KeyTypekey[],inti){intj,k,m=0;「printf("*航班号起点站终点站航班期起飞时间到达时间机型票价*\n");for(j=l;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.timel);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");「//查询检索菜单控制程序voidsearchcon(SLListL){KeyTypekey[keylen];inti=1,k;while(i>=1&&i<=5){printf("printf("*航班信息查询系统*\n"）;printf("printf("printf("printf("printf("printf("printf("printf("printf("*航班信息查询系统*\n"）;printf("printf("printf("printf("printf("printf("printf("********************\n");*1.航班号*\n");*2.起点站*\n");*3.终点站*\n");*4.起飞时间*\n");*5.到达时间*\n");*0.退出系统*\n");printf("printf("请选择(0-5):printf("printf("请选择(0-5):\n");scanf("%d",&i);switch(i){case1:printf("输入要查询的航班号(字母要大写):");scanf("%s",key);k=BinSearch(L,key);「if（k==0）printf（"无此航