《数据结构课程设计航班信息查询与检索系统.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计航班信息查询与检索系统.doc(15页珍藏版)》请在三一办公上搜索。
1、数据结构课程设计报告题目:航班信息查询与检索专业:班级:学号:姓名:任课老师:2010年12月26日目录一、设计题目.1二、设计要求.2三、概要设计.21.设计思路22.流程图2四、详细设计.3 1.定义数据类型.3 2.算法实现.3五、测试数据.6 1.录入航班信息6 2.航班信息查询7六、收获与体会.8一、设计题目 设计一个航班信息查询与检索系统。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。二、设计要求1、每个航班记录包括八项:航班号、起始站、终点站、班期、起飞时间、到达时间、飞机型号、票价。如下表所示:航班信息表航班号 起点站 终点站 航班期 起飞时机 到达时间
2、 机型 票价 CA1544 合肥 北京 1.2.5 1055 1240 733 9602、要有输入模块。3、对航班信息进行排序与查找。三、概要设计1、设计思路根据题目所要求,程序必须实现航班信息的录入和查询。程序首先定义了一个用于储存航班信息的数据类型,再由用户录入航班数据,在录入的同时并对数据进行排序,最后执行数据查询和检索。在查询设计中,使用二分查找法对排好序的航班数据按航班号实现快速查找,按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。2、流程图定义数据类型 输出查找结果接受查找条件、查找关键字数据输入、排序四、详细设计 1 . 定义数据类型 根据设计要求,设计中所用到的数
3、据记录只有航班信息,因此要定义相关的数据类型:typedef struct char 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; /静态链表,s10为头结点int keynu
4、m; /关键字长int length; /当前表长sllist; /静态链表类型为了进行基数排序,需要定义在分配和收集操作时用到的指针数组:typedef int arrtype_n10; /十进制数字指针数组typedef int arrtype_c26; /26个字母指针数组2 . 算法实现 (1)一趟分配算法 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; /将数字
5、字符转化为对应的数值型数字if(!fj)fj=p;elseslej.next=p;ej=p; /将p指向的结点插入到第j个结点(2)一趟收集算法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;(3)链式基数排序算法 void radixs
6、ort(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(sllist &l) /按指针链表整理静态链表int p,q,i;slnode temp;p=l.sl0.next;for(i=1;il.length;i+)while(
7、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;(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)0)high=mid-1;elsel
8、ow=mid+1;return 0;五、测试数据1、录入航班信息编译后运行,显示:航班号起点站终点站航班期起飞时间到达时间机型票价录入:MU4594昆明西安 1.3.5.6 1015 1140 3281160显示:继续输入吗?y/n:录入:y显示:航班号起点站终点站航班期起飞时间到达时间机型票价录入:SC7425青岛海口 1.3.6 1920 2120 DH41630显示:继续输入吗?y/n:录入:n2、航班信息查询录入航班信息后,屏幕显示:* 航班信息查询系统 * 1.航 班 号 * 2.起 点 站 * 3.终 点 站 * 4.起飞时间 * 5.到达时间 * 0.退出系统 *请选择(0-5)
9、:录入:1显示:输入要查询的航班号(字母要大写):录入:MU4594显示:航班号起点站终点站航班期起飞时间到达时间机型票价MU4594-昆明 -西安 -1.3.5.6 -1015 -1140 -328 -1160录入:2显示:输入要查询的航班起点站名:录入:青岛显示:航班号起点站终点站航班期起飞时间到达时间机型票价SC7425-青岛-海口 -1.3.6 -1920 -2120 -DH4-1630录入:2显示:输入要查询的航班起点站名:录入:广州显示:* 无此航班信息,可能是输入错误! *六、收获与体会本设计的重点和难点是在于对航班数据的排序和查找,以链式基数排序为主线,用到了二分查找和顺序查找
10、等知识,还有建立静态链表等。通过这次课程设计,使我对C语言编程有了新的认识。以前编程只是注重如何编写函数能够完成所需要的功能,只是凭单纯的意识和简单的语句来堆砌出一段程序。但现在编程感觉完全不同了。在编写一个程序之前,自己能够综合考虑各种因素,选取自己需要的数据结构,在编写每一个函数之前,可以仔细斟酌比对,挑选出最适合当前状况的算法。这样,即使在完整的程序还没有写出来之前,自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外,我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处,才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的,它往往是编写程
11、序的关键。附录源程序清单:#include stdafx.h#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;infotype others;int ne
12、xt;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;elseslej.next=p;ej=p;vo
13、id 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.next;p;p=slp.next)j=s
14、lp.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;arrtype_c fc,ec;for(i=0;i=2;i-
15、)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;l.sli.next=p;p=q;int binsearc
16、h(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);printf(* 航班号 起点站 终点站 航班期 起飞时间 到达时间
17、 机型 票价 *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:printf(输入要查询的航班号(字母要大写):);sc
18、anf(%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.
19、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(%s,key);seqsearch(l,key,i);bre
20、ak;case 0:printf(nnn 再 见nnn);void inputdata(sllist &l)int i=+l.length;char yn=y;while(yn=y|yn=Y)printf(航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价n);scanf(%s%s%s%s%s%s%s%d,l.sli.keys,l.sli.others.start,l.sli.others.end,l.sli.others.sche,l.sli.others.time1,l.sli.others.time2,l.sli.others.model,&l.sli.others.price);+i; getchar(); radixsort(l);arrange(l);printf(继续输入吗?y/n:);scanf(%c,&yn);l.length=i-1;void main()sllist l;l.keynum=6;l.length=0;inputdata(l);searchcon(l);