算法与数据结构实验报告航班查询与检索题目:航班查询与检索指导老师:组长:成员:一:航班信息的查询与检索按时间查询:按站点查询:二分法查询:二:算法分析:程序主要采用结构体链表顺序表队列主要算法:/*航班信息的查询与检索*/三:/*航班信息的查询与检索*/#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,最后通过改时间的数据类型实现了时间的输入,最后就是在各个模块的组合过程中由于各个成员编程所起的名字或者其她原因,程序无法运行,最后在大家的努力下一起修改错误使得程序可以正常运行。
