数据结构课程设计-航班查询与检索(含代码、流程图、输出结果)

算法与数据结构实验报告航班查询与检索题目：航班查询与检索指导老师：组长：成员：一：航班信息的查询与检索按时间查询：按站点查询：二分法查询：二：算法分析：程序主要采用结构体链表顺序表队列主要算法：/*航班信息的查询与检索*/三：/*航班信息的查询与检索*/#include<iostream.h>#include<string.h>#include<stdio.h>#define N 6 //航班数//航班信息typedef struct flight{char flight_number[10]; //航班号char start_address[10]; //起飞站char arrived_address[10]; //终点站char work_date[10]; //班期char start_time[6]; //起飞时间char arrived_time[6]; //到达时间char FlightType[4]; //机型int fare; //票价}DataType;struct flight Flight[N];//-----------按航班号进行基数排序-----------typedef char KeyType;#define D 7 // D为排序码的最大位数#define R 'a' // R为基数,这里为小于字母'a'代表的整型值struct Node; //单链表结点类型typedef struct Node RadixNode;struct Node{KeyType key[D]; //关键字DataType info; //数据信息RadixNode *next;};typedef RadixNode * RadixList;typedef struct QueueNode{RadixNode *f; //对列的头指针RadixNode *e; //对列的尾指针}Queue;Queue queue[R];//用队列表示桶void radixSort(RadixList * plist, int d, int r){int i,j,k;RadixNode *p, *head;head=(*plist)->next;for(j=d-1; j>=0; j--) //进行d次分配和收集{p=head;for(i=0; i<r; i++){queue[i].f=NULL; queue[i].e=NULL; //清队列}while(p!=NULL){k=p->key[j]; //按排序码的第j个分量进行分配if(queue[k].f==NULL) queue[k].f=p; // 若第k个堆为空，则当前记录为队头else (queue[k].e)->next=p; // 否则当前记录链接到第k队的队尾queue[k].e=p;p=p->next;}i=0;while(queue[i].f==NULL) i++; // 从r个队列中找出第一个非空的队列p=queue[i].e; head=queue[i].f; //head为收集链表的头指针for(i++; i<r; i++)if(queue[i].f!=NULL){ p->next=queue[i].f; p=queue[i].e; } // 收集非空队列p->next=NULL;}(*plist)->next=head;}//初始化航班信息struct Node element[N+1]={" "," "," "," "," "," "," "," ",0,NULL,//表头"CA1544","CA1544","合肥","北京","1245 ","10:55","12:40","733",960,NULL,"MU5341","MU5341","上海","广州","每日","14:20","16:15","M90",1280,NULL, "CZ3869","CZ3869","重庆","深圳","246 ","08:55","10:35","733",1010,NULL, "MU3682","MU3682","桂林","南京","23467","20:50","22:15","M90",1380,NULL,"HU1836","HU1836","上海","北京","每日","09:40","11:20","738",1250,NULL,"CZ3528","CZ3528","成都","厦门","13457","15:10","16:50","CRJ",1060,NULL,};//------------信息显示------------//按表的格式输出某个航班信息//显示头部信息void Cout_info1(){cout<<" ****************************************\n"<<endl;cout<<" * 欢迎您使用*\n"<<endl;cout<<" * 航班信息表*\n"<<endl;cout<<" ****************************************\n"<<endl;cout<<" 航班号起飞时间到达时间起飞站终点站班期机型票价\n"<<endl;}//显示主体信息void Cout_info2_1(Node p[])//方式一{cout<<" "<<p->info.flight_number;cout<<" "<<p->info.start_time;cout<<" "<<p->info.arrived_time;cout<<" "<<p->info.start_address;cout<<" "<<p->info.arrived_address; cout<<" "<<p->info.work_date;cout<<" "<<p->info.FlightType;cout<<" "<<p->info.fare<<"元"<<endl;}void Cout_info2_2(flight F[],int i)//方式二{cout<<" "<<F[i].flight_number;cout<<" "<<F[i].start_time;cout<<" "<<F[i].arrived_time;cout<<" "<<F[i].start_address;cout<<" "<<F[i].arrived_address; cout<<" "<<F[i].work_date;cout<<" "<<F[i].FlightType;cout<<" "<<F[i].fare<<"元"<<endl;}//显示所有航班信息void output_ALL_info1(Node element[]) //方式一{RadixList p=element;Cout_info1();p=p->next;while(p!=NULL){Cout_info2_1(p);p=p->next;}cout<<endl;}void output_ALL_info2(flight F[]) //方式二{Cout_info1();for(int i=0;i<N;i++){Cout_info2_2(F,i);}cout<<endl;}//--------------信息复制----------------//将排好的序列(链表)转化成顺序表存储形式void copy(flight F[],Node element[]){RadixList p=element;p=p->next;int i;for(i=0;i<N && p!=NULL;i++){strcpy(F[i].flight_number,p->info.flight_number);strcpy(F[i].start_time,p->info.start_time);strcpy(F[i].arrived_time,p->info.arrived_time);strcpy(F[i].start_address,p->info.start_address);strcpy(F[i].arrived_address,p->info.arrived_address);strcpy(F[i].work_date,p->info.work_date);strcpy(F[i].FlightType,p->info.FlightType);F[i].fare=p->info.fare;p=p->next;}}//---------------服务菜单--------------void F_By_Time(flight F[],int);void F_By_Address(flight F[],int);void F_By_fare(flight F[]);void F_By_FN(flight F[]);//主菜单void mainmenu(){char ch;int y;cout<<" 主菜单\n"<<endl;cout<<"===========================================================\n"<<endl;cout<<" Please choose: (input the number)(输入查询/排序命令)\n"<<endl; cout<<" 0. show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1. Find by flight number(按航班号查询)\n"<<endl;cout<<" 2. Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3. Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4. Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5. Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6. Find by the fare(按票价范围查询)\n"<<endl;cout<<" ----其他键退出"<<endl;cout<<"===========================================================\n"<<endl;while(1){cout<<"请输入服务命令：";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 谢谢惠顾！"<<endl;break;}cout<<"是否退出?(Y/N)：";cin>>ch;if(ch=='Y'||ch=='y') break;}}//--------------查询系统--------------//通过航班号实现二分查找法查找void F_By_FN(flight F[]){int low=0,high=N,mid;char Num[10];cout<<"请输入您要查询的航班号：";cin>>Num;Cout_info1();//显示头部信息while(low<=high){mid=(low+high)/2;if(strcmp(Num,F[mid].flight_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid].flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起，没有您要查找的航班号********** "<<endl;}//通过起飞/到达时间查询void F_By_Time(flight F[],int Time){int i;char T[6];cout<<"请输入您要查询的航班的起飞/抵达时间:";cin>>T;Cout_info1();//显示头部信息for(i=0;i<N;i++){if(Time==1) //按起飞时间查询{if(strcmp(T,F[i].start_time)==0) Cout_info2_2(F,i);}if(Time==2) //按抵达时间查询{if(strcmp(T,F[i].arrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起，该时间没有航班******* "<<endl;}//通过站点查询void F_By_Address(flight F[],int AD){char str[10];cout<<"请输入您要查询的航班的起飞/抵达地址:";cin>>str;Cout_info1();for(int i=0;i<N;i++){if(AD==1) //按起点站查询{if(strcmp(str,F[i].start_address)==0) Cout_info2_2(F,i);}if(AD==2) //按目的站查询{if(strcmp(str,F[i].arrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起，该站点不存在******** "<<endl; }//通过票价范围查询void F_By_fare(flight F[]){int T1,T2,i;cout<<"请输入您要查询的航班的最低票价(单位：元):";cin>>T1;cout<<"请输入您要查询的航班的最高票价(单位：元):";cin>>T2;Cout_info1();for(i=0;i<N;i++){if(T1<=F[i].fare && T2>=F[i].fare) Cout_info2_2(F,i);}cout<<" *******对不起，没有适合您的航班，请修改您的票价范围********" <<endl; }//--------------主函数----------------int main(){RadixList p=element;for(int i=0;i<N;i++)element[i].next=&element[i+1];element[10].next=NULL;radixSort(&p, D, R); //基数排序output_ALL_info1(element); //输出排序后的有序序列(航班信息)copy(Flight,element); //另存储排序后的航班信息mainmenu(); //给出主菜单return 0;}测试数据及测试结果：、边界值处理：四：遇到的问题及解决策略：首先是要实现所要的功能需用什么数据结构的问题，比如排序问题究竟用那一种，在组员的商量下和上网搜寻资料，采用对排序最符合，其次是在时间的查询过程中，比如输入时间16：40开始只能实现输入1640，最后通过改时间的数据类型实现了时间的输入，最后是在各个模块的组合过程中由于各个成员编程所起的名字或者其他原因，程序无法运行，最后在大家的努力下一起修改错误使得程序可以正常运行。

学院名称《数据结构》课程设计报告题目——航班信息查询与检索班级：姓名：时间：2012/12/29---2013/1/5二○一二年十二月二十九日课程设计任务书及成绩评定航班信息查询与检索课题名称Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。

可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一三年一月五日目录一、概述 (6)二、系统分析 (6)三、概要设计 (6)四、详细设计 (7)1.定义数据类型 (7)2.算法实现 (8)五、测试数据 (10)六、收获与体会 (13)七、参考文献 (13)八、附录 (14)5一、概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

目录第1章概述 (1)第2章设计要求与分析 (2)2.1设计要求 (2)2.2设计分析 (2)2.2.1定义数据类型 (2)2.2.2实现排序的个函数说明 (3)第3章算法实现 (4)3.1 一趟分配算法 (4)3.2 一趟收集算法 (4)3.3 链式基数排序算法 (11)3.4 二分查找的函数定义 (12)第4章程序代码 (12)第5章运行与测试 (20)第6章实验反思 (23)参考文献 (23)第1章概述排序和查找是在数据信息处理中使用频度极高的操作。

为了加快查找的速度，需要先对数据记录按关键字排序。

当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。

在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。

因为航班号是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。

第2章设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：其中k0和k14位为航班表号，这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串型即可。

2.2设计分析2.2.1定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef struct{Char start[7];Char end[7];Char sche[12];Char time1[5];Char time2[5];Char model[4];Int price;}InfoType;Typedef struct{KeyType keys[keylen];InfoType others;Int next;}SLNode;Typedef struct{SLNode s1[MaxSpace];Int keylen;Int length;}SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n[10];Typedef int ArrType_.c[26];2.2.2实现排序的个函数说明（1）一趟分配函数：Void Distribute(SLNode *s1,int I,ArrType f,ArrType e);//本算法是按关键字keys[i]建立RADIX个子集，是同一个子集中记录的keys[i]相同，//f[0..RADIX]和e[0..RADIX]分别指向各自表中的第一个和最后一个记录（2）一趟搜集函数：Void Collect(SLNode *s1,int i,ArrType f,ArrType e);//本算法是按关键字keys[i]从小到大将[0..RADIX]所指的各子表一次连接成一个链表（3）链式基数排序函数：Void RadixSort(SLList &L);//本算法是按关键字从低位到高位依次对各关键字进行分配和收集，分两端实现（4）二分查找函数：Int BinSerach(SLList L,KeyType key[]);//L为待查找的表，key[]为待查找的关键字，按二分查找的思想实现查找（5）主控函数：Void main(){初始化；数据输入；排序处理；接受查找要求及查找关键字；查找处理；输出查找结果；}第3章算法实现3.1 一趟分配算法Void Distribute(SLNode *s1,int I,ArrType f,ArrType e) {Int j,p;For(j=0;j<RADIX;j++){//分子表初始化为空表F[j]=0;E[j]=0;}For(p=s1[0].next;p;p=s1[p].next){J=s1[p].keys[i]%48;If(!f[j])F[j]=p;ElseS1[e[j]].next=p;E[j]=p;}}3.2 一趟收集算法Void Colect(SLNode *s1,int I,ARRType f,ArrType e) {Int j,t;For(j=0;!f[j];j++);S1[0].next=f[j];t=e[j];While(j<RSDIX-1){For(j=j+1;j<RADIX-1&&!f[j];j++);If(f[j]){s1[t].next=f[j];t=e[j];}}S1[t].next=0;}//主函数程序#include<stdio.h>#include<string.h>#define MaxSpace 100#define keylen 6#define RADIX_n 10#define RADIX_c 26#define SHOW_MSG_ERROR "\n错误信息：航班号须由2位大写字母和4位数字组成。

算法与数据结构实验报告航班查询与检索题目：航班查询与检索指导老师：组长：成员：一：航班信息的查询与检索按时间查询：按站点查询：二分法查询：二：算法分析：程序主要采用结构体链表顺序表队列主要算法：/*航班信息的查询与检索*/三：/*航班信息的查询与检索*/#include<>#include<>#include<>#define N 6 =NULL; queue[i].e=NULL; ==NULL) queue[k].f=p; ->next=p; =p;p=p->next;}i=0;while(queue[i].f==NULL) i++; ; head=queue[i].f; !=NULL){ p->next=queue[i].f; p=queue[i].e; } light_number;cout<<" "<<F[i].start_time;cout<<" "<<F[i].arrived_time;cout<<" "<<F[i].start_address;cout<<" "<<F[i].arrived_address;cout<<" "<<F[i].work_date;cout<<" "<<F[i].FlightType;cout<<" "<<F[i].fare<<"元"<<endl;}light_number,p->;strcpy(F[i].start_time,p->;strcpy(F[i].arrived_time,p->;strcpy(F[i].start_address,p->;strcpy(F[i].arrived_address,p->;strcpy(F[i].work_date,p->;strcpy(F[i].FlightType,p->;F[i].fare=p->;p=p->next;}}show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1. Find by flight number(按航班号查询)\n"<<endl;cout<<" 2. Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3. Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4. Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5. Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6. Find by the fare(按票价范围查询)\n"<<endl;cout<<" ----其他键退出"<<endl;cout<<"===========================================================\n"< <endl;while(1){cout<<"请输入服务命令：";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 谢谢惠顾！ "<<endl;break;}cout<<"是否退出(Y/N)：";cin>>ch;if(ch=='Y'||ch=='y') break;}}light_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid].flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起，没有您要查找的航班号********** "<<endl;}tart_time)==0) Cout_info2_2(F,i);}if(Time==2) rrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起，该时间没有航班******* "<<endl;}tart_address)==0) Cout_info2_2(F,i);}if(AD==2) rrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起，该站点不存在******** "<<endl;}are && T2>=F[i].fare) Cout_info2_2(F,i);}cout<<" *******对不起，没有适合您的航班，请修改您的票价范围********" <<endl;}ext=&element[i+1];element[10].next=NULL;radixSort(&p, D, R);我们对链表、队列、结构体的应用更娴熟，为我们更好的了解课本内容，改进不足提供了件。

目录第1章概述 (1)第2章设计要求与分析 (2)2。

1设计要求 (2)2。

2设计分析 (3)2.2.1定义数据类型 (3)2.2.2实现排序的个函数说明 (3)第3章算法实现 (4)3。

1 一趟分配算法 (4)3.2 一趟收集算法 (4)3。

3 链式基数排序算法 (12)3.4 二分查找的函数定义 (12)第4章程序代码 (13)第5章运行与测试 (21)第6章实验反思 (24)参考文献 (24)第1章概述排序和查找是在数据信息处理中使用频度极高的操作.为了加快查找的速度，需要先对数据记录按关键字排序.当今乘飞机旅行的人越来越多，人们需要关心了解各类航班的班次、时间、价格及机型等信息。

在这个飞机航班数据的信息模型中，航班号是关键字，而且是具有结构特点的一类关键字。

因为航班号是字母数字混变的，例如CZ3869，这种记录集合是一个适合与多关键字排序的例子。

第2章设计要求与分析2.1设计要求该设计要求对飞机航班信息进行排序和查找.可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询.对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他词关键字的查找可采用最简单的顺序查找方法进行，因为他们用的较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表如下表所示：其中航班号一项的格式为：k0 k1 k3 k4 k5 k6其中k0和k1的输入值是航空公司的别称，用两个大写字母表示，后4位为航班表号,这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外,均定义为字符串型即可。

2.2设计分析2.2。

1定义数据类型根据设计要求，我们知道设计中所用到的数据记录只有航班信息，因此要定义行管的数据类型：Typedef struct{Char start[7］；Char end[7];Char sche［12］;Char time1［5];Char time2[5];Char model[4];Int price;｝InfoType;Typedef struct｛KeyType keys［keylen];InfoType others;Int next；｝SLNode；Typedef struct｛SLNode s1［MaxSpace］;Int keylen;Int length；}SLList;为了进行基数排列，需要定义在分配和手机操作使用到的指针数组：Typedef int ArrType_n［10］；Typedef int ArrType_。

目录第１章概述ﻩ错误!未定义书签。

第2章设计要求与分析ﻩ错误!未定义书签。

2、1设计要求 ..............................................错误!未定义书签。

2、2设计分析 ..............................................错误!未定义书签。

２、2、1定义数据类型ﻩ错误!未定义书签。

2、2、2实现排序得个函数说明ﻩ错误!未定义书签。

第3章算法实现ﻩ错误!未定义书签。

3、1 一趟分配算法 .....................................错误!未定义书签。

3、２一趟收集算法ﻩ错误!未定义书签。

3、3 链式基数排序算法 .............................错误!未定义书签。

３、4 二分查找得函数定义ﻩ错误!未定义书签。

第４章程序代码 ...............................................错误!未定义书签。

第5章运行与测试...........................................错误!未定义书签。

第6章实验反思 ...............................................错误!未定义书签。

参考文献ﻩ错误!未定义书签。

第1章概述排序与查找就是在数据信息处理中使用频度极高得操作.为了加快查找得速度，需要先对数据记录按关键字排序。

当今乘飞机旅行得人越来越多，人们需要关心了解各类航班得班次、时间、价格及机型等信息。

在这个飞机航班数据得信息模型中,航班号就是关键字，而且就是具有结构特点得一类关键字。

因为航班号就是字母数字混变得，例如CZ3８69,这种记录集合就是一个适合与多关键字排序得例子。

第２章设计要求与分析2、1设计要求该设计要求对飞机航班信息进行排序与查找、可按航班得航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

学院名称《数据结构》课程设计报告题目——航班信息查询与检索班级：姓名：时间：2012/12/29---2013/1/5二○一二年十二月二十九日课程设计任务书与成绩评定课题名称航班信息查询与检索Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。

可按航班的航班号、起点站、到达站、起飞时间以与到达时间等信息进行查询。

任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以与票价等，假设航班信息表（8条记录）位为航班号，这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉与本设计的核心，因此除了票价为数值型外，均定义为字符串即可。

Ⅱ、设计进度与完成情况Ⅲ、主要参考文献与资料[1] 严蔚敏数据结构（C语言版）清华大学出版社1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社1999[3] 谭浩强C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一三年一月五日目录一、概述 (6)二、系统分析 (6)三、概要设计 (6)四、详细设计 (7)1.定义数据类型 (7)2.算法实现 (8)五、测试数据 (10)六、收获与体会 (13)七、参考文献 (13)八、附录 (14)5 / 24一、概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉与和课程相关的各个方面，是一门独立于课程之外的特殊课程。

实验课程名称数据结构课程设计专业班级学生姓名学号指导教师2012至 2013学年第一学期第 1 至 9 周目录一、概述： (3)二、系统分析： (3)2.1 输入/输出形式和输出值 (3)2.2 功能需求 (3)2.3 系统特点 (3)三、概要设计： (4)3.1 设计思路 (4)3.2 数据处理 (4)3.3 基本概念和数据处理 (5)3.4 数据流图 (6)四、详细设计： (7)4.1 设计说明 (7)4.2 算法设计与分析 (7)二分查找 (7)4.3 算法实现 (8)五、运行与测试： (9)六、总结与心得： (11)附录：程序代码 (11)一、概述：设计一个航班信息查询与检索系统。

可事先按要求录入航班信息、删除航班信息、查看全部航班信息及按航班的航班号、起点站、终点站、起飞时间、以及到达时间等信息进行查询。

二、系统分析：2.1 输入/输出形式和输出值进入系统后，首先按照要求输入航班信息，包括：航班号、起点站、终点站、航班期、起飞时间、到达时间、票价。

除票价为整型外，其他均为字符型。

信息完成后均以Enter结束。

当输入完一个航班信息后，会提示是否继续输入，若要继续输入则重复上述步骤，否显示主菜单。

根据主菜单输入功能序号选择，若用户输入的值超过给定范围，则提示错误并要求重新输入。

2.2 功能需求（1）输入航班信息（2）删除航班信息，可按航班号、起点站、终点站、起飞时间、到达时间等删除（3）按不同类型查询航班信息，如航班号、起点站、终点站、起飞时间、到达时间等（4）显示当前所有的航班记录（5）退出系统2.3 系统特点本系统的使用者是航空公司，操作人员只需具备基本的计算机操作技巧即可。

三、概要设计：3.1 设计思路根据设计要求，程序必须实现航班信息的录入和查询。

程序首先定义了一个用于存储航班信息的数据类型，再由用户录入航班数据路，在录入的同时并对数据进行排序，最后执行数据查询和检索。

在设计过程中，使用二分查找法对航班数据按航班号实现快速查找，按起点站、终点站、起飞时间、到达时间查找。

课程设计报告课程设计名称：数据结构课程设计题目：设计并实现一个航班信息查询与检索系统院系：计算机学院专业：班级：学号：姓名：指导教师：学术诚信声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。

尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。

报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名: 日期：年月日目录1 题目介绍 (5)2 课程设计要求 (5)2.1课程设计内容 (5)2.2课程设计目标 (5)3 概要设计 (5)3.1设计思路 (5)3.2流程图 (5)4 算法概述 (6)4.1定义数据类型 (6)4.2函数描述 (7)5 测试数据 (10)附录（关键部分程序清单） (12)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;elsesl[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.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);}}void arrange(sllist &l) //按指针链表整理静态链表{int p,q,i;slnode temp;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;}}折半查找函数定义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;elselow=mid+1;}return 0;}5、测试数据编译后运行，显示：录入信息^_^航班号起点站终点站班期起飞时间到达时间机型票价录入：CA1544合肥北京 1.2.4.5 10551240 733960显示：是否继续？y/n:录入：y显示：航班号起点站终点站班期起飞时间到达时间机型票价录入：MU5341上海广州每日14201615 M901280显示：是否继续？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 10551240 733960录入：2显示：输入要查询的航班起点站:录入：合肥显示：航班号起点站终点站班期起飞时间到达时间机型票价显示：CA1544合肥北京 1.2.4.5 10551240 733960录入：2显示：输入要查询的航班起点站: 录入：广州显示：附录源程序：#include <stdio.h>#include <string.h>#define max 100#define keylen 7typedef 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;elsesl[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;elsesl[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.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);}}void arrange(sllist &l){int p,q,i;slnode temp;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;}}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;elselow=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].oth ers.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.e nd,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);}毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。

课程设计题目：城市交通咨询系统一、课程设计的原始资料及依据在交通网络非常发达，交通工具和交通方式不断更新的今天，人们的出差、旅游或做其他的出行时，不仅关心节省交通运费问题，而且对里程和所需要时间等问题感兴趣。

可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。

图中顶点表示城市，边表示城市之间的交通关系。

这个交通咨询系统可用回答旅客提出的各种问题。

二、课程设计主要内容及要求1. 建立交通网络图的存储结构。

2. 画出主要的功能结构图和主要模块的流程图。

3. 使用迪杰斯特拉算法：求一个城市到其它所有城市最短路径。

4. 使用弗洛伊德算法：求任意两个城市间最短路径。

三、对课程设计说明书撰写内容、格式、字数的要求1．课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。

一般不应少于3000字。

2．在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。

应做到文理通顺，内容正确完整，书写工整，装订整齐。

3．设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。

设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。

4．课程设计说明书手写或打印均可。

手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。

文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。

5．课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。

四、设计完成后应提交成果的种类、数量、质量等方面的要求1．完成“任务书”中指定的操作功能，运行稳定。

算法与数据结构实验报告航班查询与检索题目：航班查询与检索指导老师：组长：成员：一：航班信息的查询与检索按时间查询：按站点查询：二分法查询：二：算法分析：程序主要采用结构体链表顺序表队列主要算法：/*航班信息的查询与检索*/三：/*航班信息的查询与检索*/#include<iostream.h>#include<string.h>#include<stdio.h>#define N 6 //航班数//航班信息typedef struct flight{char flight_number[10]; //航班号char start_address[10]; //起飞站char arrived_address[10]; //终点站char work_date[10]; //班期char start_time[6]; //起飞时间char arrived_time[6]; //到达时间char FlightType[4]; //机型int fare; //票价}DataType;struct flight Flight[N];//-----------按航班号进行基数排序-----------typedef char KeyType;#define D 7 // D为排序码的最大位数#define R 'a' // R为基数,这里为小于字母'a'代表的整型值struct Node; //单链表结点类型typedef struct Node RadixNode;struct Node{KeyType key[D]; //关键字DataType info; //数据信息RadixNode *next;};typedef RadixNode * RadixList;typedef struct QueueNode{RadixNode *f; //对列的头指针RadixNode *e; //对列的尾指针}Queue;Queue queue[R];//用队列表示桶void radixSort(RadixList * plist, int d, int r){int i,j,k;RadixNode *p, *head;head=(*plist)->next;for(j=d-1; j>=0; j--) //进行d次分配和收集{for(i=0; i<r; i++){queue[i].f=NULL; queue[i].e=NULL; //清队列}while(p!=NULL){k=p->key[j]; //按排序码的第j个分量进行分配if(queue[k].f==NULL) queue[k].f=p; // 若第k个堆为空，则当前记录为队头else (queue[k].e)->next=p; // 否则当前记录链接到第k队的队尾queue[k].e=p;p=p->next;}i=0;while(queue[i].f==NULL) i++; // 从r个队列中找出第一个非空的队列p=queue[i].e; head=queue[i].f; //head为收集链表的头指针for(i++; i<r; i++)if(queue[i].f!=NULL){ p->next=queue[i].f; p=queue[i].e; } // 收集非空队列p->next=NULL;}(*plist)->next=head;}//初始化航班信息struct Node element[N+1]={" "," "," "," "," "," "," "," ",0,NULL,//表头"CA1544","CA1544","合肥","北京","1245 ","10:55","12:40","733",960,NULL,"MU5341","MU5341","上海","广州","每日","14:20","16:15","M90",1280,NULL,"CZ3869","CZ3869","重庆","深圳","246 ","08:55","10:35","733",1010,NULL, "MU3682","MU3682","桂林","南京","23467","20:50","22:15","M90",1380,NULL,"HU1836","HU1836","上海","北京","每日","09:40","11:20","738",1250,NULL,"CZ3528","CZ3528","成都","厦门","13457","15:10","16:50","CRJ",1060,NULL,};//------------信息显示------------//按表的格式输出某个航班信息//显示头部信息void Cout_info1(){cout<<" ****************************************\n"<<endl;cout<<" * 欢迎您使用*\n"<<endl;cout<<" * 航班信息表*\n"<<endl;cout<<" ****************************************\n"<<endl;cout<<" 航班号起飞时间到达时间起飞站终点站班期机型票价}//显示主体信息void Cout_info2_1(Node p[])//方式一{cout<<" "<<p->info.flight_number;cout<<" "<<p->info.start_time;cout<<" "<<p->info.arrived_time;cout<<" "<<p->info.start_address;cout<<" "<<p->info.arrived_address; cout<<" "<<p->info.work_date;cout<<" "<<p->info.FlightType;cout<<" "<<p->info.fare<<"元"<<endl;}void Cout_info2_2(flight F[],int i)//方式二{cout<<" "<<F[i].flight_number;cout<<" "<<F[i].start_time;cout<<" "<<F[i].arrived_time;cout<<" "<<F[i].start_address;cout<<" "<<F[i].arrived_address;cout<<" "<<F[i].work_date;cout<<" "<<F[i].FlightType;cout<<" "<<F[i].fare<<"元"<<endl;}//显示所有航班信息void output_ALL_info1(Node element[]) //方式一{RadixList p=element;Cout_info1();p=p->next;while(p!=NULL){Cout_info2_1(p);p=p->next;}cout<<endl;}void output_ALL_info2(flight F[]) //方式二{Cout_info1();for(int i=0;i<N;i++){Cout_info2_2(F,i);}cout<<endl;}//--------------信息复制----------------//将排好的序列(链表)转化成顺序表存储形式void copy(flight F[],Node element[]){RadixList p=element;p=p->next;int i;for(i=0;i<N && p!=NULL;i++){strcpy(F[i].flight_number,p->info.flight_number);strcpy(F[i].start_time,p->info.start_time);strcpy(F[i].arrived_time,p->info.arrived_time);strcpy(F[i].start_address,p->info.start_address);strcpy(F[i].arrived_address,p->info.arrived_address);strcpy(F[i].work_date,p->info.work_date);strcpy(F[i].FlightType,p->info.FlightType);F[i].fare=p->info.fare;p=p->next;}}//---------------服务菜单--------------void F_By_Time(flight F[],int);void F_By_Address(flight F[],int);void F_By_fare(flight F[]);void F_By_FN(flight F[]);//主菜单void mainmenu(){char ch;int y;cout<<" 主菜单\n"<<endl;cout<<"===========================================================\n"<<endl;cout<<" Please choose: (input the number)(输入查询/排序命令)\n"<<endl; cout<<" 0. show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1. Find by flight number(按航班号查询)\n"<<endl;cout<<" 2. Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3. Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4. Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5. Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6. Find by the fare(按票价范围查询)\n"<<endl;cout<<" ----其他键退出"<<endl;cout<<"===========================================================\n"<<endl;while(1){cout<<"请输入服务命令：";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 谢谢惠顾！"<<endl;break;}cout<<"是否退出?(Y/N)：";cin>>ch;if(ch=='Y'||ch=='y') break;}}//--------------查询系统--------------//通过航班号实现二分查找法查找void F_By_FN(flight F[]){int low=0,high=N,mid;char Num[10];cout<<"请输入您要查询的航班号：";cin>>Num;Cout_info1();//显示头部信息while(low<=high){mid=(low+high)/2;if(strcmp(Num,F[mid].flight_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid].flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起，没有您要查找的航班号********** "<<endl; }//通过起飞/到达时间查询void F_By_Time(flight F[],int Time){int i;char T[6];cout<<"请输入您要查询的航班的起飞/抵达时间:";cin>>T;Cout_info1();//显示头部信息for(i=0;i<N;i++){if(Time==1) //按起飞时间查询{if(strcmp(T,F[i].start_time)==0) Cout_info2_2(F,i);}if(Time==2) //按抵达时间查询{if(strcmp(T,F[i].arrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起，该时间没有航班******* "<<endl;}//通过站点查询void F_By_Address(flight F[],int AD){char str[10];cout<<"请输入您要查询的航班的起飞/抵达地址:";cin>>str;Cout_info1();for(int i=0;i<N;i++){if(AD==1) //按起点站查询{if(strcmp(str,F[i].start_address)==0) Cout_info2_2(F,i);}if(AD==2) //按目的站查询{if(strcmp(str,F[i].arrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起，该站点不存在******** "<<endl; }//通过票价范围查询void F_By_fare(flight F[]){int T1,T2,i;cout<<"请输入您要查询的航班的最低票价(单位：元):";cin>>T1;cout<<"请输入您要查询的航班的最高票价(单位：元):";cin>>T2;Cout_info1();for(i=0;i<N;i++){if(T1<=F[i].fare && T2>=F[i].fare) Cout_info2_2(F,i);}cout<<" *******对不起，没有适合您的航班，请修改您的票价范围********" <<endl; }//--------------主函数----------------int main(){RadixList p=element;for(int i=0;i<N;i++)element[i].next=&element[i+1];element[10].next=NULL;radixSort(&p, D, R); //基数排序output_ALL_info1(element); //输出排序后的有序序列(航班信息)copy(Flight,element); //另存储排序后的航班信息mainmenu(); //给出主菜单return 0;}测试数据及测试结果：、边界值处理：四：遇到的问题及解决策略：首先是要实现所要的功能需用什么数据结构的问题，比如排序问题究竟用那一种，在组员的商量下和上网搜寻资料，采用对排序最符合，其次是在时间的查询过程中，比如输入时间16：40开始只能实现输入1640，最后通过改时间的数据类型实现了时间的输入，最后是在各个模块的组合过程中由于各个成员编程所起的名字或者其他原因，程序无法运行，最后在大家的努力下一起修改错误使得程序可以正常运行。

课程设计报告课程设计名称：数据结构课程设计题目：设计并实现一个航班信息查询与检索系统院系：计算机学院专业：班级：学号：姓名：指导教师：学术诚信声明本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。

尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。

报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名: 日期：年月日目录1 题目介绍 (5)2 课程设计要求 (5)2.1课程设计内容 (5)2.2课程设计目标 (5)3 概要设计 (5)3.1设计思路 (5)3.2流程图 (5)4 算法概述 (6)4.1定义数据类型 (6)4.2函数描述 (7)5 测试数据 (10)附录（关键部分程序清单） (12)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;elsesl[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.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);}}void arrange(sllist &l) //按指针链表整理静态链表{int p,q,i;slnode temp;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;}}折半查找函数定义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;elselow=mid+1;}return 0;}5、测试数据编译后运行，显示：录入信息^_^航班号起点站终点站班期起飞时间到达时间机型票价录入：CA1544合肥北京 1.2.4.5 10551240 733960显示：是否继续？y/n:录入：y显示：航班号起点站终点站班期起飞时间到达时间机型票价录入：MU5341上海广州每日14201615 M901280显示：是否继续？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 10551240 733960录入：2显示：输入要查询的航班起点站:录入：合肥显示：航班号起点站终点站班期起飞时间到达时间机型票价显示：CA1544合肥北京 1.2.4.5 10551240 733960录入：2显示：输入要查询的航班起点站: 录入：广州显示：附录源程序：#include <stdio.h>#include <string.h>#define max 100#define keylen 7typedef 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;elsesl[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;elsesl[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.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);}}void arrange(sllist &l){int p,q,i;slnode temp;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;}}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;elselow=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].oth ers.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.e nd,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);}。

目录一、概述 0二、系统分析 (1)1.航班信息的查询与检索 (1)2.航班信息查询与检索数据结构理论 (1)三、概要设计 (2)1.系统的功能 (2)2.系统模块分析及其流程图 (3)四、详细设计 (6)1.各函数说明 (6)2.定义相关数据类型 (8)3. 航班信息的查询 (9)五、运行由于测试 (11)六、总结与心得 (16)参考文献 (16)附录 (16)一、概述随着信息产业的飞速发展，信息化管理及查询已经进入并应用到各行各业，影响着人们的价值观念和生活方式。

因此，要提高企业信息化建设，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，从而提高企业综合实力。

本次设计是针对航班的查询系统，该设计要求对飞机航班信息进行排序和查询。

可按航班的航班号、起点站、终点站等信息进行航班信息的查询。

二、系统分析1.航班信息的查询与检索进入系统后，首先提示输入航班的信息，包括：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号及票价等，票价为整型，其他为字符型。

当输入完一个信息后会提示是否继续输入，重复以上步骤输入全部的信息。

进入主菜单后会给出用户操作的界面，根据提示进行航班信息的查询。

2.航班信息查询与检索数据结构理论针对在本该类系统中的数据的处理情况，本系统采用二分查找法、基数排序法、最高位优先法。

二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。

它的基本思想是，将n 个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。

如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。

如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

对航班号的排序是采用的基数排序法。

基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

算法与数据结构实验报告航班查询与检索题目：航班查询与检索指导老师：组长：成员：一：航班信息的查询与检索按时间查询：按站点查询：二分法查询：二：算法分析：程序主要采用结构体链表顺序表队列主要算法：/*航班信息的查询与检索*/三：/*航班信息的查询与检索*/#include<>#include<>#include<>#define N 6 =NULL; queue[i].e=NULL; ==NULL) queue[k].f=p; ->next=p; =p;p=p->next;}i=0;while(queue[i].f==NULL) i++; ; head=queue[i].f; !=NULL){ p->next=queue[i].f; p=queue[i].e; } light_number;cout<<" "<<F[i].start_time;cout<<" "<<F[i].arrived_time;cout<<" "<<F[i].start_address;cout<<" "<<F[i].arrived_address;cout<<" "<<F[i].work_date;cout<<" "<<F[i].FlightType;cout<<" "<<F[i].fare<<"元"<<endl;}light_number,p->;strcpy(F[i].start_time,p->;strcpy(F[i].arrived_time,p->;strcpy(F[i].start_address,p->;strcpy(F[i].arrived_address,p->;strcpy(F[i].work_date,p->;strcpy(F[i].FlightType,p->;F[i].fare=p->;p=p->next;}}show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1. Find by flight number(按航班号查询)\n"<<endl;cout<<" 2. Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3. Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4. Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5. Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6. Find by the fare(按票价范围查询)\n"<<endl;cout<<" ----其他键退出"<<endl;cout<<"===========================================================\n"<<endl;while(1){cout<<"请输入服务命令：";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 谢谢惠顾！"<<endl;break;}cout<<"是否退出(Y/N)：";cin>>ch;if(ch=='Y'||ch=='y') break;}}light_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid].flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起，没有您要查找的航班号********** "<<endl;}tart_time)==0) Cout_info2_2(F,i);}if(Time==2) rrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起，该时间没有航班******* "<<endl;}tart_address)==0) Cout_info2_2(F,i);}if(AD==2) rrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起，该站点不存在******** "<<endl;}are && T2>=F[i].fare) Cout_info2_2(F,i);}cout<<" *******对不起，没有适合您的航班，请修改您的票价范围********" <<endl;}ext=&element[i+1];element[10].next=NULL;radixSort(&p, D, R);我们对链表、队列、结构体的应用更娴熟，为我们更好的了解课本内容，改进不足提供了件。

算法与数据结构实验报告航班查询与检索题目:航班查询与检索指导老师:组长:成员:一:航班信息的查询与检索按时间查询:按站点查询:二分法查询:二:算法分析:程序主要采用结构体链表顺序表队列主要算法:/*航班信息的查询与检索*/三:/*航班信息的查询与检索*/#include<iostream、h>#include<string、h>#include<stdio、h>#define N 6 //航班数//航班信息typedef struct flight{char flight_number[10]; //航班号char start_address[10]; //起飞站char arrived_address[10]; //终点站char work_date[10]; //班期char start_time[6]; //起飞时间char arrived_time[6]; //到达时间char FlightType[4]; //机型int fare; //票价}DataType;struct flight Flight[N];//-----------按航班号进行基数排序-----------typedef char KeyType;#define D 7 // D为排序码的最大位数#define R 'a' // R为基数,这里为小于字母'a'代表的整型值struct Node; //单链表结点类型typedef struct Node RadixNode;struct Node{KeyType key[D]; //关键字DataType info; //数据信息RadixNode *next;};typedef RadixNode * RadixList;typedef struct QueueNode{RadixNode *f; //对列的头指针RadixNode *e; //对列的尾指针}Queue;Queue queue[R];//用队列表示桶void radixSort(RadixList * plist, int d, int r){int i,j,k;RadixNode *p, *head;head=(*plist)->next;for(j=d-1; j>=0; j--) //进行d次分配与收集{p=head;for(i=0; i<r; i++){queue[i]、f=NULL; queue[i]、e=NULL; //清队列}while(p!=NULL){k=p->key[j]; //按排序码的第j个分量进行分配if(queue[k]、f==NULL) queue[k]、f=p; // 若第k个堆为空,则当前记录为队头else (queue[k]、e)->next=p; // 否则当前记录链接到第k队的队尾queue[k]、e=p;p=p->next;}i=0;while(queue[i]、f==NULL) i++; // 从r个队列中找出第一个非空的队列p=queue[i]、e; head=queue[i]、f; //head为收集链表的头指针for(i++; i<r; i++)if(queue[i]、f!=NULL){ p->next=queue[i]、f; p=queue[i]、e; } // 收集非空队列p->next=NULL;}(*plist)->next=head;}//初始化航班信息struct Node element[N+1]={" "," "," "," "," "," "," "," ",0,NULL,//表头"CA1544","CA1544","合肥","北京","1245 ","10:55","12:40","733",960,NULL,"MU5341","MU5341","上海","广州","每日","14:20","16:15","M90",1280,NULL, "CZ3869","CZ3869","重庆","深圳","246 ","08:55","10:35","733",1010,NULL, "MU3682","MU3682","桂林","南京","23467","20:50","22:15","M90",1380,NULL,"HU1836","HU1836","上海","北京","每日","09:40","11:20","738",1250,NULL,"CZ3528","CZ3528","成都","厦门","13457","15:10","16:50","CRJ",1060,NULL,};//------------信息显示------------//按表的格式输出某个航班信息//显示头部信息void Cout_info1(){cout<<" ****************************************\n"<<endl;cout<<" * 欢迎您使用*\n"<<endl;cout<<" * 航班信息表*\n"<<endl;cout<<" ****************************************\n"<<endl;cout<<" 航班号起飞时间到达时间起飞站终点站班期机型票价\n"<<endl;}//显示主体信息void Cout_info2_1(Node p[])//方式一{cout<<" "<<p->info、flight_number;cout<<" "<<p->info、start_time;cout<<" "<<p->info、arrived_time;cout<<" "<<p->info、start_address;cout<<" "<<p->info、arrived_address;cout<<" "<<p->info、work_date;cout<<" "<<p->info、FlightType;cout<<" "<<p->info、fare<<"元"<<endl; }void Cout_info2_2(flight F[],int i)//方式二{cout<<" "<<F[i]、flight_number;cout<<" "<<F[i]、start_time;cout<<" "<<F[i]、arrived_time;cout<<" "<<F[i]、start_address;cout<<" "<<F[i]、arrived_address; cout<<" "<<F[i]、work_date;cout<<" "<<F[i]、FlightType;cout<<" "<<F[i]、fare<<"元"<<endl;}//显示所有航班信息void output_ALL_info1(Node element[]) //方式一{RadixList p=element;Cout_info1();p=p->next;while(p!=NULL){Cout_info2_1(p);p=p->next;}cout<<endl;}void output_ALL_info2(flight F[]) //方式二{Cout_info1();for(int i=0;i<N;i++){Cout_info2_2(F,i);}cout<<endl;}//--------------信息复制----------------//将排好的序列(链表)转化成顺序表存储形式void copy(flight F[],Node element[]){RadixList p=element;p=p->next;int i;for(i=0;i<N && p!=NULL;i++){strcpy(F[i]、flight_number,p->info、flight_number);strcpy(F[i]、start_time,p->info、start_time);strcpy(F[i]、arrived_time,p->info、arrived_time);strcpy(F[i]、start_address,p->info、start_address);strcpy(F[i]、arrived_address,p->info、arrived_address);strcpy(F[i]、work_date,p->info、work_date);strcpy(F[i]、FlightType,p->info、FlightType);F[i]、fare=p->info、fare;p=p->next;}}//---------------服务菜单--------------void F_By_Time(flight F[],int);void F_By_Address(flight F[],int);void F_By_fare(flight F[]);void F_By_FN(flight F[]);//主菜单void mainmenu(){char ch;int y;cout<<" 主菜单\n"<<endl;cout<<"===========================================================\n"<<endl;cout<<" Please choose: (input the number)(输入查询/排序命令)\n"<<endl; cout<<" 0、show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1、Find by flight number(按航班号查询)\n"<<endl;cout<<" 2、Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3、Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4、Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5、Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6、Find by the fare(按票价范围查询)\n"<<endl;cout<<" ----其她键退出"<<endl;cout<<"===========================================================\n"<<endl; while(1){cout<<"请输入服务命令:";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 谢谢惠顾！"<<endl;break;}cout<<"就是否退出?(Y/N):";cin>>ch;if(ch=='Y'||ch=='y') break;}}//--------------查询系统--------------//通过航班号实现二分查找法查找void F_By_FN(flight F[]){int low=0,high=N,mid;char Num[10];cout<<"请输入您要查询的航班号:";cin>>Num;Cout_info1();//显示头部信息while(low<=high){mid=(low+high)/2;if(strcmp(Num,F[mid]、flight_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid]、flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起,没有您要查找的航班号********** "<<endl;}//通过起飞/到达时间查询void F_By_Time(flight F[],int Time){int i;char T[6];cout<<"请输入您要查询的航班的起飞/抵达时间:";cin>>T;Cout_info1();//显示头部信息for(i=0;i<N;i++){if(Time==1) //按起飞时间查询{if(strcmp(T,F[i]、start_time)==0) Cout_info2_2(F,i);}if(Time==2) //按抵达时间查询{if(strcmp(T,F[i]、arrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起,该时间没有航班******* "<<endl;}//通过站点查询void F_By_Address(flight F[],int AD){char str[10];cout<<"请输入您要查询的航班的起飞/抵达地址:";cin>>str;Cout_info1();for(int i=0;i<N;i++){if(AD==1) //按起点站查询{if(strcmp(str,F[i]、start_address)==0) Cout_info2_2(F,i);}if(AD==2) //按目的站查询{if(strcmp(str,F[i]、arrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起,该站点不存在******** "<<endl; }//通过票价范围查询void F_By_fare(flight F[]){int T1,T2,i;cout<<"请输入您要查询的航班的最低票价(单位:元):";cin>>T1;cout<<"请输入您要查询的航班的最高票价(单位:元):";cin>>T2;Cout_info1();for(i=0;i<N;i++){if(T1<=F[i]、fare && T2>=F[i]、fare) Cout_info2_2(F,i);}cout<<" *******对不起,没有适合您的航班,请修改您的票价范围********" <<endl; }//--------------主函数----------------int main(){RadixList p=element;for(int i=0;i<N;i++)element[i]、next=&element[i+1];element[10]、next=NULL;radixSort(&p, D, R); //基数排序output_ALL_info1(element); //输出排序后的有序序列(航班信息) copy(Flight,element); //另存储排序后的航班信息mainmenu(); //给出主菜单return 0;}测试数据及测试结果:、边界值处理:四:遇到的问题及解决策略:首先就是要实现所要的功能需用什么数据结构的问题,比如排序问题究竟用那一种,在组员的商量下与上网搜寻资料,采用对排序最符合,其次就是在时间的查询过程中,比如输入时间16:40开始只能实现输入1640,最后通过改时间的数据类型实现了时间的输入,最后就是在各个模块的组合过程中由于各个成员编程所起的名字或者其她原因,程序无法运行,最后在大家的努力下一起修改错误使得程序可以正常运行。

数据结构课程设计--航班信息查询与检索系统《数据结构》课程设计报告题⽬：航班信息查询与检索专业：班级：学号：姓名：任课⽼师：2010年12⽉26⽇⽬录⼀、设计题⽬ (1)⼆、设计要求 (2)三、概要设计 (2)1.设计思路 (2)2.流程图 (2)四、详细设计 (3)1.定义数据类型 (3)2.算法实现 (3)五、测试数据 (6)1.录⼊航班信息 (6)2.航班信息查询 (7)六、收获与体会 (8)⼀、设计题⽬设计⼀个航班信息查询与检索系统。

可按航班的航班号、起点站、终点站、起飞时间以及到达时间等信息进⾏查询。

⼆、设计要求1、每个航班记录包括⼋项：航班号、起始站、终点站、班期、起飞时间、到达时间、飞机型号、票价。

如下表所⽰：航班信息表航班号起点站终点站航班期起飞时机到达时间机型票价CA1544 合肥北京 1.2.5 1055 1240 733 9602、要有输⼊模块。

3、对航班信息进⾏排序与查找。

三、概要设计1、设计思路根据题⽬所要求，程序必须实现航班信息的录⼊和查询。

程序⾸先定义了⼀个⽤于储存航班信息的数据类型，再由⽤户录⼊航班数据，在录⼊的同时并对数据进⾏排序，最后执⾏数据查询和检索。

在查询设计中，使⽤⼆分查找法对排好序的航班数据按2、流程图四、详细设计1 . 定义数据类型根据设计要求，设计中所⽤到的数据记录只有航班信息，因此要定义相关的数据类型：typedef struct {char start[6]; //起点站char end[6]; //终点站char sche[10]; //航班期char time1[5]; //起飞时间char time2[5]; //到达时间char model[4]; //机型int price; //票价}infotype; //航班记录类型typedef struct{keytype keys[keylen]; //关键字infotype others;int next;}slnode; //表结点typedef struct{slnode sl[maxspace]; //静态链表，s1[0]为头结点int keynum; //关键字长int length; //当前表长}sllist; //静态链表类型为了进⾏基数排序，需要定义在分配和收集操作时⽤到的指针数组：typedef int arrtype_n[10]; //⼗进制数字指针数组typedef int arrtype_c[26]; //26个字母指针数组2 . 算法实现（1）⼀趟分配算法void distribute(slnode *sl,int i,arrtype_n f,arrtype_n e){int j,p;for(j=0;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）⼀趟收集算法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{for(j=j+1;jif(f[j]){sl[t].next=f[j];t=e[j];} //链接两个⾮空⼦表}sl[t].next=0;}（3）链式基数排序算法void radixsort(sllist &l){int i;arrtype_n fn,en;arrtype_c fc,ec;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(pp=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,keytype 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;elselow=mid+1;}return 0;}五、测试数据1、录⼊航班信息编译后运⾏，显⽰：航班号起点站终点站航班期起飞时间到达时间机型录⼊：MU4594昆明西安 1.3.5.6 10151140 328 1160↙显⽰：继续输⼊吗?y/n:录⼊：y↙显⽰：航班号起点站终点站航班期起飞时间到达时间机型票价录⼊：SC7425青岛海⼝ 1.3.6 19202120 DH4 1630↙显⽰：继续输⼊吗?y/n:录⼊：n↙2、航班信息查询录⼊航班信息后，屏幕显⽰：********************* 航班信息查询系统********************** 1.航班号** 4.起飞时间** 5.到达时间** 0.退出系统*********************请选择(0-5):录⼊：1↙显⽰：输⼊要查询的航班号(字母要⼤写):录⼊：MU4594↙显⽰：航班号起点站终点站航班期起飞时间到达时间机型票价MU4594-昆明-西安-1.3.5.6 -1015 -1140 -328 -1160录⼊：2↙显⽰：输⼊要查询的航班起点站名:录⼊：青岛↙显⽰：航班号起点站终点站航班期起飞时间到达时间机型SC7425-青岛-海⼝-1.3.6 -1920-2120 -DH4 -1630↙录⼊：2↙显⽰：输⼊要查询的航班起点站名:录⼊：⼴州↙显⽰：* ⽆此航班信息，可能是输⼊错误！*六、收获与体会本设计的重点和难点是在于对航班数据的排序和查找，以链式基数排序为主线，⽤到了⼆分查找和顺序查找等知识，还有建⽴静态链表等。

算法与数据结构实验报告航班查询与检索题目：航班查询与检索指导老师：组长：成员：一：航班信息的查询与检索按时间查询：按站点查询：二分法查询：二：算法分析：程序主要采用结构体链表顺序表队列主要算法：/*航班信息的查询与检索*/三：/*航班信息的查询与检索*/#include<iostream.h>#include<string.h>#include<stdio.h>#define N 6 //航班数//航班信息typedef struct flight{char flight_number[10]; //航班号char start_address[10]; //起飞站char arrived_address[10]; //终点站char work_date[10]; //班期char start_time[6]; //起飞时间char arrived_time[6]; //到达时间char FlightType[4]; //机型int fare; //票价}DataType;struct flight Flight[N];//-----------按航班号进行基数排序-----------typedef char KeyType;#define D 7 // D为排序码的最大位数#define R 'a' // R为基数,这里为小于字母'a'代表的整型值struct Node; //单链表结点类型typedef struct Node RadixNode;struct Node{KeyType key[D]; //关键字DataType info; //数据信息RadixNode *next;};typedef RadixNode * RadixList;typedef struct QueueNode{RadixNode *f; //对列的头指针RadixNode *e; //对列的尾指针}Queue;Queue queue[R];//用队列表示桶void radixSort(RadixList * plist, int d, int r){int i,j,k;RadixNode *p, *head;head=(*plist)->next;for(j=d-1; j>=0; j--) //进行d次分配和收集{p=head;for(i=0; i<r; i++){queue[i].f=NULL; queue[i].e=NULL; //清队列}while(p!=NULL){k=p->key[j]; //按排序码的第j个分量进行分配if(queue[k].f==NULL) queue[k].f=p; // 若第k个堆为空，则当前记录为队头else (queue[k].e)->next=p; // 否则当前记录到第k队的队尾queue[k].e=p;p=p->next;}i=0;while(queue[i].f==NULL) i++; // 从r个队列中找出第一个非空的队列p=queue[i].e; head=queue[i].f; //head为收集链表的头指针for(i++; i<r; i++)if(queue[i].f!=NULL){ p->next=queue[i].f; p=queue[i].e; } // 收集非空队列p->next=NULL;}(*plist)->next=head;}//初始化航班信息struct Node element[N+1]={" "," "," "," "," "," "," "," ",0,NULL,//表头"CA1544","CA1544","","","1245 ","10:55","12:40","733",960,NULL,"MU5341","MU5341","","","每日","14:20","16:15","M90",1280,NULL,"CZ3869","CZ3869","","","246 ","08:55","10:35","733",1010,NULL,"MU3682","MU3682","","","23467","20:50","22:15","M90",1380,NULL,"HU1836","HU1836","","","每日","09:40","11:20","738",1250,NULL,"CZ3528","CZ3528","","","13457","15:10","16:50","CRJ",1060,NULL,};//------------信息显示------------//按表的格式输出某个航班信息//显示头部信息void Cout_info1(){cout<<" ****************************************\n"<<endl;cout<<" * 欢迎您使用*\n"<<endl;cout<<" * 航班信息表*\n"<<endl;cout<<" ****************************************\n"<<endl;cout<<" 航班号起飞时间到达时间起飞站终点站班期机型票价\n"<<endl;}//显示主体信息void Cout_info2_1(Node p[])//方式一{cout<<" "<<p->info.flight_number;cout<<" "<<p->info.start_time;cout<<" "<<p->info.arrived_time;cout<<" "<<p->info.start_address;cout<<" "<<p->info.arrived_address; cout<<" "<<p->info.work_date;cout<<" "<<p->info.FlightType;cout<<" "<<p->info.fare<<"元"<<endl;}void Cout_info2_2(flight F[],int i)//方式二{cout<<" "<<F[i].flight_number;cout<<" "<<F[i].start_time;cout<<" "<<F[i].arrived_time;cout<<" "<<F[i].start_address;cout<<" "<<F[i].arrived_address; cout<<" "<<F[i].work_date;cout<<" "<<F[i].FlightType;cout<<" "<<F[i].fare<<"元"<<endl;}//显示所有航班信息void output_ALL_info1(Node element[]) //方式一{RadixList p=element;Cout_info1();p=p->next;while(p!=NULL){Cout_info2_1(p);p=p->next;}cout<<endl;}void output_ALL_info2(flight F[]) //方式二{Cout_info1();for(int i=0;i<N;i++){Cout_info2_2(F,i);}cout<<endl;}//--------------信息复制----------------//将排好的序列(链表)转化成顺序表存储形式void copy(flight F[],Node element[]){RadixList p=element;p=p->next;int i;for(i=0;i<N && p!=NULL;i++){strcpy(F[i].flight_number,p->info.flight_number);strcpy(F[i].start_time,p->info.start_time);strcpy(F[i].arrived_time,p->info.arrived_time);strcpy(F[i].start_address,p->info.start_address);strcpy(F[i].arrived_address,p->info.arrived_address);strcpy(F[i].work_date,p->info.work_date);strcpy(F[i].FlightType,p->info.FlightType);F[i].fare=p->info.fare;p=p->next;}}//---------------服务菜单--------------void F_By_Time(flight F[],int);void F_By_Address(flight F[],int);void F_By_fare(flight F[]);void F_By_FN(flight F[]);//主菜单void mainmenu(){char ch;int y;cout<<" 主菜单\n"<<endl;cout<<"===========================================================\n"<<endl;cout<<" Please choose: (input the number)(输入查询/排序命令)\n"<<endl; cout<<" 0. show the mainmenu (显示主菜单)\n"<<endl;cout<<" 1. Find by flight number(按航班号查询)\n"<<endl;cout<<" 2. Find by start time(按起飞时间查询)\n"<<endl;cout<<" 3. Find by arrived time(按到达时间查询)\n"<<endl;cout<<" 4. Find by start address(按起飞地点查询)\n"<<endl;cout<<" 5. Find by arrived address(按目的地点查询)\n"<<endl;cout<<" 6. Find by the fare(按票价围查询)\n"<<endl;cout<<" ----其他键退出"<<endl;cout<<"===========================================================\n"<<endl;while(1){cout<<"请输入服务命令：";cin>>y;switch(y){case 0: mainmenu();break;case 1:F_By_FN(Flight);break;case 2:F_By_Time(Flight,1);break;case 3:F_By_Time(Flight,2);break;case 4:F_By_Address(Flight,1);break;case 5:F_By_Address(Flight,2);break;case 6:F_By_fare(Flight);break;default :cout<<" 惠顾！"<<endl;break;}cout<<"是否退出?(Y/N)：";cin>>ch;if(ch=='Y'||ch=='y') break;}}//--------------查询系统--------------//通过航班号实现二分查找法查找void F_By_FN(flight F[]){int low=0,high=N,mid;char Num[10];cout<<"请输入您要查询的航班号：";cin>>Num;Cout_info1();//显示头部信息while(low<=high){mid=(low+high)/2;if(strcmp(Num,F[mid].flight_number)==0) {Cout_info2_2(F,mid);break;}else if(strcmp(Num,F[mid].flight_number)<0) high=mid-1;else low=mid+1;}cout<<" *************对不起，没有您要查找的航班号********** "<<endl;}//通过起飞/到达时间查询void F_By_Time(flight F[],int Time){int i;char T[6];cout<<"请输入您要查询的航班的起飞/抵达时间:";cin>>T;Cout_info1();//显示头部信息for(i=0;i<N;i++){if(Time==1) //按起飞时间查询{if(strcmp(T,F[i].start_time)==0) Cout_info2_2(F,i);}if(Time==2) //按抵达时间查询{if(strcmp(T,F[i].arrived_time)==0) Cout_info2_2(F,i);}}cout<<" *******对不起，该时间没有航班******* "<<endl;}//通过站点查询void F_By_Address(flight F[],int AD){char str[10];cout<<"请输入您要查询的航班的起飞/抵达地址:";cin>>str;Cout_info1();for(int i=0;i<N;i++){if(AD==1) //按起点站查询{if(strcmp(str,F[i].start_address)==0) Cout_info2_2(F,i);}if(AD==2) //按目的站查询{if(strcmp(str,F[i].arrived_address)==0) Cout_info2_2(F,i);}}cout<<" ********对不起，该站点不存在******** "<<endl; }//通过票价围查询void F_By_fare(flight F[]){int T1,T2,i;cout<<"请输入您要查询的航班的最低票价(单位：元):";cin>>T1;cout<<"请输入您要查询的航班的最高票价(单位：元):";cin>>T2;Cout_info1();for(i=0;i<N;i++){if(T1<=F[i].fare && T2>=F[i].fare) Cout_info2_2(F,i);}cout<<" *******对不起，没有适合您的航班，请修改您的票价围********" <<endl; }//--------------主函数----------------int main(){RadixList p=element;for(int i=0;i<N;i++)element[i].next=&element[i+1];element[10].next=NULL;radixSort(&p, D, R); //基数排序output_ALL_info1(element); //输出排序后的有序序列(航班信息)copy(Flight,element); //另存储排序后的航班信息mainmenu(); //给出主菜单return 0;}测试数据及测试结果：、边界值处理：四：遇到的问题及解决策略：首先是要实现所要的功能需用什么数据结构的问题，比如排序问题究竟用那一种，在组员的商量下和上网搜寻资料，采用对排序最符合，其次是在时间的查询过程中，比如输入时间16：40开始只能实现输入1640，最后通过改时间的数据类型实现了时间的输入，最后是在各个模块的组合过程中由于各个成员编程所起的名字或者其他原因，程序无法运行，最后在大家的努力下一起修改错误使得程序可以正常运行。

学院名称《数据结构》课程设计报告题目——航班信息查询与检索班级：姓名：时间：2012/12/29---2013/1/5二○一二年十二月二十九日课程设计任务书及成绩评定课题名称航班信息查询与检索Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求：问题描述:该设计要求对飞机航班信息进行排序和查找。

可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。

任务要求:对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。

每个航班记录包括八项，分别是：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，K0 K1 K2 K3 K4 K5这种航班号关键字可分成两段，即字母和数字。

其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社1999[3] 谭浩强C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一三年一月五日目录一、概述 (6)二、系统分析 (6)三、概要设计 (6)四、详细设计 (7)1.定义数据类型 (7)2.算法实现 (8)五、测试数据 (10)六、收获与体会 (13)七、参考文献 (13)八、附录 (14)教育资料一、概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。