课程设计报告

课程设计名称：数据结构课程设计

题目：设计并实现一个航班信息查询与检索系统

院系：计算机学院

专业：

班级：

学号：

姓名：

指导教师：

学术诚信声明

本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名: 日期： 年 月 日

1、题目介绍

设计一个航班信息查询与检索系统。可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进行查询。

2、课程设计要求

1、每个航班记录包括八项：航班号、起始站、终点站、班期、起飞时间、到达时间、飞机型号、票价。如下表所示：

2、对航班信息进行排序与查找。

3、概要设计

3.1、设计思路

根据题目所要求，程序必须实现航班信息的录入和查询。程序首先定义了一个储存航班信息的数据类型，再由用户录入航班数据，在录入的同时并对数据进行排序，最后执行数据查询和检索。在查询设计中，使用折半查找法对排好序的航班号数据实现快速查找，按起点站、终点站、起飞时间、到达时间查找的则采用顺序查询方法。

3.2、流程图

4、算法实现

4.1 . 定义数据类型

根据设计要求，设计中所用到的数据记录只有航班信息，因此要定义相关的数据类型：

typedef struct {

char start[6]; //起点站

char end[6]; //终点站

char sche[10]; //班期

char time1[5]; //起飞时间

char time2[5]; //到达时间

char model[4]; //机型

int price; //票价

}info; //航班记录类型

typedef struct{

char keys[keylen]; //关键字

info others;

int next;

}slnode; //表结点

typedef struct{

slnode sl[maxspace];

int keynum; //关键字长

int length; //当前表长

}sllist; //静态链表类型

为了进行基数排序，需要定义在分配和收集操作时用到的指针数组：

typedef int arrtype_n[10]; //十进制数字指针数组

typedef int arrtype_c[26]; //26个字母指针数组

4.2 . 函数描述

void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)

{

int j,p;

for(j=0;j<10;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;

else

sl[e[j]].next=p;

e[j]=p; //将p指向的结点插入到第j个结点

}

}

void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)

{

int j,t;

for(j=0;!f[j];j++); //找第一个非空子表

sl[0].next=f[j];

t=e[j];

while(j<10-1)

{

for(j=j+1;j<10-1&&!f[j];j++); //找下一个非空子表

if(f[j])

{

sl[t].next=f[j];

t=e[j];

} //链接两个非空子表

}

sl[t].next=0;

}

链式基数排序算法

void radixsort(sllist &l)

{

int i;

arrtype_n fn,en;

arrtype_c fc,ec;

for(i=0;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);

}

}

void arrange(sllist &l) //按指针链表整理静态链表

{

int p,q,i;

slnode temp;

p=l.sl[0].next;

for(i=1;i

{

while(p

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;

}

}

折半查找函数定义

int binsearch(sllist l,char key[])

{

int low,high,mid;

low=1;

high=l.length;

while(low<=high)

{

mid=(low+high)/2;

if(strcmp(key,l.sl[mid].keys)==0)

return mid;

else if(strcmp(key,l.sl[mid].keys)<0)

high=mid-1;

else

low=mid+1;

}

return 0;

}

5、测试数据

编译后运行，显示：

录入信息^_^

航班号　起点站　终点站　班期　起飞时间　到达时间　机型　票价

录入：CA1544合肥 北京 1.2.4.5 　1055　 1240 　733　960

显示：是否继续？y/n:

录入：y

显示：航班号 起点站 终点站 班期　起飞时间　到达时间　机型　票价

录入：MU5341　上海 广州 每日 　1420　 1615 　M90　1280

显示：是否继续？y/n:

录入：y

显示：航班号 起点站　终点站　班期　起飞时间　到达时间　机型　票价

录入：CZ3869 重庆 深圳 2.4.6 0855 1035 733 1010

显示：是否继续？y/n:

录入：n

录入航班信息后，屏幕显示：

-------------------------------

* 航班信息查询系统 *

-------------------------------

* 1.航 班 号 *

* 2.起 点 站 *

* 3.终 点 站 *

* 4.起飞时间 *

* 5.到达时间 *

* 0.退出 *

-----------------------------

(0-5)号服务项目:

录入：1

显示：输入要查询的航班号(字母要大写):

录入：CA1544

显示：航班号　起点站　终点站 班期　起飞时间　到达时间　机型　票价

CA1544合肥 北京 1.2.4.5 　 1055　 1240 　 733　 960

录入：2

显示：输入要查询的航班起点站:

录入：合肥

显示：航班号　起点站　终点站 班期　起飞时间　到达时间　机型　票价

显示：CA1544合肥 北京 1.2.4.5 　1055　 1240 　733　960

录入：2

显示：输入要查询的航班起点站:

录入：广州

显示：

附录

源程序：

#include

#include

#define max 100

#define keylen 7

typedef struct

{

char start[6];

char end[6];

char sche[10];

char time1[5];

char time2[5];

char model[4];

int price;

}info;

typedef struct

{

char keys[keylen];

info others;

int next;

}slnode;

typedef struct

{

slnode sl[max];

int keynum;

int length;

}sllist;

typedef int arrtype_n[10];

typedef int arrtype_c[26];

void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e)

{

int j,p;

for(j=0;j<10;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;

else

sl[e[j]].next=p;

e[j]=p;

}

}

void collect(slnode *sl,int i,arrtype_n f,arrtype_n e)

{

int j,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];

t=e[j];

while(j<10-1)

{

for(j=j+1;j<10-1&&!f[j];j++);

if(f[j])

{

sl[t].next=f[j];

t=e[j];

}

}

sl[t].next=0;

}

void distribute_c(slnode *sl,int i,arrtype_c f,arrtype_c e)

{

int j,p;

for(j=0;j<26;j++)

{

f[j]=e[j]=0;

}

for(p=sl[0].next;p;p=sl[p].next)

{

j=sl[p].keys[i]%65;

if(!f[j])

f[j]=p;

else

sl[e[j]].next=p;

e[j]=p;

}

}

void collect_c(slnode *sl,int i,arrtype_c f,arrtype_c e)

{

int j,t;

for(j=0;!f[j];j++);

sl[0].next=f[j];

t=e[j];

while(j<26-1)

{

for(j=j+1;j<26-1&&!f[j];j++);

if(f[j])

{

sl[t].next=f[j];

t=e[j];

}

}

sl[t].next=0;

}

void radixsort(sllist &l)

{

int i;

arrtype_n fn,en;

arrtype_c fc,ec;

for(i=0;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);

}

}

void arrange(sllist &l)

{

int p,q,i;

slnode temp;

p=l.sl[0].next;

for(i=1;i

{

while(p

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;

}

}

int binsearch(sllist l,char key[])

{

int low,high,mid;

low=1;

high=l.length;

while(low<=high)

{

mid=(low+high)/2;

if(strcmp(key,l.sl[mid].keys)==0)

return mid;

else if(strcmp(key,l.sl[mid].keys)<0)

high=mid-1;

else

low=mid+1;

}

return 0;

}

void seqsearch(sllist l,char key[],int i)

{

int j,k,m=0;

printf("------------------------------------------------------------\n");

printf(" 航班号 起点站 终点站 班期 起飞时间 到达时间 机型 票价 \n");

for(j=1;j<=l.length;j++)

{

switch(i)

{

case 2:k=strcmp(key,l.sl[j].others.start);break;

case 3:k=strcmp(key,l.sl[j].others.end);break;

case 4:k=strcmp(key,l.sl[j].others.time1);break;

case 5:k=strcmp(key,l.sl[j].others.time2);break;

}

if(k==0)

{

m=1;

printf(" %-8s%-7s%-7s%-11s%-6s%-6s%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");

}

void searchcon(sllist l)

{

char key[keylen];

int i=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)号服务项目:");

scanf("%d",&i);

printf("\n");

switch(i)

{

case 1:printf("输入要查询的航班号(字母要大写):");

scanf("%s",key);

k=binsearch(l,key);

printf("--------------------------------------------------------------\n");

if(k==0)

printf(" 无此航班信息，可能是输入错误！ \n");

else

{

printf(" 航班号 起点站 终点站 班期 起飞时间 到达时间 机型 票价 \n");

printf(" %-8s%-7s%-7s%-11s%-6s%-6s%-5s%4d \n",l.sl[k].keys,l.sl[k].others.start,l.sl[k].others.end,l.sl[k].others.sche,l.sl[k].others.time1,l.sl[k].others.time2,l.sl[k].others.model,l.sl[k].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);

break;

case 0:printf("\n\n宝宝走了\n\n");

}

}

}

void inputdata(sllist &l)

{

int i=++l.length;

char yn='y';

while(yn=='y'||yn=='Y')

{

printf("信息录入^_^\n\n");

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.time1,l.sl[i].others.time2,l.sl[i].others.model,&l.sl[i].others.price);

++i;

getchar();

radixsort(l);

arrange(l);

printf("是否继续?\ny/n:");

scanf("%c",&yn);

}

l.length=i-1;

}

void main()

{

sllist l;

l.keynum=6;

l.length=0;

inputdata(l);

searchcon(l);

}

欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语； 1、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！ 2、现在你不玩命的学，以后命玩你。3、我不知道年少轻狂，我只知道胜者为王。4、不要做金钱、权利的奴隶；应学会做“金钱、权利”的主人。5、什么时候离光明最近？那就是你觉得黑暗太黑的时候。6、最值得欣赏的风景，是自己奋斗的足迹。 7、压力不是有人比你努力，而是那些比你牛×几倍的人依然比你努力。

航班信息查询与检索系统方案