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

　　 　 　 　　 算法与数据结构实验报告
　　 　 航班查询与检索
题目：航班查询与检索
指导老师:
组长：
成员:
一：航班信息得查询与检索
初始化信息
进行排序
主菜单显示
输入查询序号
判断序号就是否合法
按航班号查询
按时间查询
按地点查询
按票价查询
输出航班信息
结束
开始

按时间查询：
输入查询时间
Time=1

按抵达时间查询
按起飞时间查询
返回查询信息
开始
就是
否

开始
输入票价范围
判断有无符合条件票价票价
输出相应信息
返回查询信息
按票价范围查询

按站点查询:
开始
返回查询信息
输入起点终点及AD
AD=1?
按目得站查询
按起点站查询
否
就是

二分法查询：
输入航班号
开始
输入航班号对应序列号
High=mid+1
Low<=highh
Num=F[mid]、flight_number
Mid=(high+low)/2
Num<F[mid]fligt_number
Low=mid+1
返回
就是
否

二：
算法分析:程序主要采用结构体 链表　顺序表　队列
主要算法：/＊航班信息得查询与检索＊/
三：/*航班信息得查询与检索＊/
＃inｃlｕde＜ｉｏｓtｒeaｍ、h＞
＃includｅ<ｓtrinｇ、h〉
＃inｃlude<ｓtdiｏ、h〉
＃defiｎｅ N ６ 　//航班数
//航班信息
typeｄef　struct flighｔ
{
cｈar ｆlighｔ_numｂer[10］； 　//航班号
chａｒ ｓｔａrt_address［10];　　 ／/起飞站
char　arrｉveｄ_adｄｒesｓ[10］； //终点站
　ｃhar wｏrk_date［10］； 　//班期
char　start_ｔime[6]；　 　 　//起飞时间
chaｒ aｒrｉved_tｉｍe［6］；　 //到达时间
char ＦlighｔType[4]; //机型
　int fａre； 　 　 　　 //票价　
}DaｔaTypｅ；
stｒuct ｆliｇht Fliｇhｔ［N];
//---－—－－-－－—按航班号进行基数排序——-－-——---－
ｔyｐedef ｃhaｒ ＫeｙType;
＃definｅ D 7 　 　　　　 // D为排序码得最大位数
＃dｅfinｅ R 'ａ' 　　 /／ R为基数，这里为小于字母’a＇代表得整型值
struct　Nodｅ; 　 　 //单链表结点类型　
typeｄef struｃt Nｏｄe ＲadixNoｄe;
sｔrucｔ　Node
{ 　　
KeｙTyｐe　key［D];　 //关键字
DａtaTｙpe info； 　 /／数据信息
　RadiｘＮode　*next;
}；
typｅdｅf RaｄiｘNode *　RadｉｘList;
ｔｙｐedeｆ sｔruｃｔ QuｅｕeNode
｛ 　
　RａdiｘNode *ｆ； 　 　　 　//对列得头指针
RadixNoｄe *e; 　　 　／/对列得尾指针
｝Queue;
Ｑｕeｕe ｑueue[Ｒ]；／/用队列表示桶
voｉd ｒadixＳort（RadixLisｔ * plist，　int d， int ｒ)
{
ｉｎt i，j,k；
ＲadｉxNode ＊p, *heaｄ;
head=（＊pｌｉｓt）－>nexｔ;
　fｏｒ（j=d—１;　j>=0； j—-) 　 //进行d次分配与收集
｛
ｐ＝hｅaｄ;
for（i=0； i〈r;　i＋+）
　 {
queue［i]、f=NULＬ； qｕｅｕｅ［i］、e=ＮULL; //清队列
｝
wｈile(ｐ!=ＮＵＬL）
｛
k＝ｐ—〉key［j]; 　　　/／按排序码得第j个分量进行分配
　 if(ｑｕeue[k］、f==NULＬ) ｑueuｅ[k]、f=ｐ；　／/　若第k个堆为空,则当前记录为队头
　ｅlsｅ （quｅｕe[ｋ]、e）－〉nexｔ＝p； 　 ／/ 否则当前记录链接到第k队得队尾
　 ｑueue[k］、e=p；
p＝p->ｎext；
｝
i=0;
ｗhiｌe（ｑueue[i]、f==ＮULＬ)　　i++； 　 　／/　从r个队列中找出第一个非空得队列
　ｐ=qｕeuｅ[i]、ｅ; hｅad＝ｑｕeuｅ［i]、f；　 　 /／heａｄ为收集链表得头指针
　　fｏr（i+＋； i〈r;　i+＋）
　 　 if(qｕeue［i]、f!=NUＬL）
{ p-＞nexｔ=ｑueue[i]、f; 　p=quｅue［i]、e; 　} 　／/ 收集非空队列
　 p—〉ｎeｘt＝NUＬL;
}
（＊pliｓt）-＞nexｔ＝ｈead;
}
／/初始化航班信息
sｔｒucｔ Node elemeｎt［N+１]={
” 　 ”,” 　 ”,＂ ”,"　　 "，” 　",” 　 　＂，" 　 ”，" "，0，NULL，//表头
ﻩ 　＂ＣＡ1544”,＂ＣA1５４4”,"合肥”,”北京","1245 ”,"10:５５"，”12:４0＂，”７33”,９6０,NULL,
ﻩﻩ "MU5341”,”MＵ５3４1",＂上海"，"广州＂,"每日　"，”１4：20＂，”16：１5",＂M90＂,128０，NULＬ,
　 　 　 ”CＺ３８6９”,＂CＺ３８6９","重庆”，”深圳”，＂2４６　 ","08：55"，＂10:３5"，"733",1０10，NＵLL,
　 "ＭU3６８２＂，＂MU3６８2”，＂桂林＂，＂南京"，”２3４６7＂，”20:50",”2２：１5”，＂M９0",13８0，NUＬL，
＂ＨU1８３6”，"HU１836”,"上海”，"北京"，"每日　","09:40＂，＂11：20＂,"738"，12５０，NULL,
　 ”CZ３52８”，＂CZ3５28"，"成都＂,”厦门”,＂13４５7”,”15：10",＂16:50＂,"CＲJ＂,1０60,ＮＵLＬ，
｝；
//--－——-——-———信　息 显 示———-—-——－-—-
//按表得格式输出某个航班信息
/／显示头部信息
voiｄ Cｏut_inｆo１(）
{
　 　ｃouｔ〈＜”　 　 　 　 　 　 *＊＊*＊*****＊**＊＊＊＊＊**＊＊****＊＊*＊****＊＊***＊＼n＂＜〈enｄｌ；
ﻩｃout〈<”　 　 ＊　 　 　　　 欢　迎 您 使 用 　　 *\ｎ＂＜〈endl;
　　cout〈<" 　 　 　 　 　＊ 　 航　班　信　息　表 　　*\n"＜＜endl；
　 cout<<"　 　 　　 *******＊***＊*＊＊****＊＊＊***＊*＊*＊*＊*＊******\n”〈<endl;
cout〈〈"　　　航班号 　起飞时间 到达时间 起飞站　 终点站　　　班期 　 机型 　　 票价\n"<<eｎｄl；
｝
／/显示主体信息
ｖoｉd Ｃｏｕｔ＿iｎfｏ２_1（Nodｅ　p[］）//方式一
｛
ｃoｕt<＜" "<〈p-〉ｉnｆo、flight_nuｍbeｒ；
cout〈<”　　 "＜<p—〉info、ｓtａrt_time；
cout<<" 　 　”<<p—＞ｉｎfo、ａrriｖed＿ｔｉme；
　 cｏut〈＜＂ ＂〈<p－〉info、stａrｔ＿aｄdrｅss;
　　 coｕｔ＜〈” 　 ＂〈〈p—>info、ａrrivｅｄ_addｒｅｓs；
cout<〈" 　 ＂<〈p—〉info、woｒk_ｄatｅ；
coｕｔ〈<＂ 　 ”<<p->inｆo、FlｉgｈtTypｅ；
ｃouｔ〈〈” 　”<〈ｐ—>ｉnfo、ｆare<＜”元"<<eｎdl;
｝
void　Cｏut_iｎfo２_2(flight　F[]，ｉnｔ i)//方式二
{
cout〈〈” "＜<F[i］、flｉght_nuｍbeｒ;
couｔ＜〈” ”<<F［i］、start_time；
ｃoｕt<〈” 　 ＂<<Ｆ[i］、arriｖed_timｅ；
　 cout〈〈" "〈＜F[i]、ｓｔarｔ_addreｓｓ；
　ｃｏut<<" ”＜<F［i］、arｒived_address；
cout〈〈” 　＂<<Ｆ［ｉ]、woｒk_datｅ；
coｕｔ〈<" 　 ”<<F[ｉ］、FliｇhtTyｐe；
couｔ<<＂ 　 　＂＜＜F［ｉ］、ｆare〈〈"元”〈〈endl;
}
//显示所有航班信息
ｖｏｉd output_ALL_inｆｏ1（Noｄe ｅlement［］) //方式一
｛
RadixList p＝element;
　Cout_info1（);
p=ｐ->next；
　while（p!=ＮUＬＬ）
｛
　 Cout_ｉnfo２_1（p）；
p=p-＞ｎext；
}
cｏut〈〈endl；
}
ｖoid oｕtpｕt_ＡLL_info2（fliｇhｔ F[]） //方式二
｛ 　
Ｃouｔ_infｏ1（）;
for(inｔ i=0；ｉ〈N；i++）
｛
　Cｏuｔ_ｉnfｏ２_2（F,i)；
　 }
ｃouｔ〈〈enｄl；
｝
//—-—－—————-—---信 息 复 制--———－－－—-—--——-
／/将排好得序列(链表）转化成顺序表存储形式
void cｏpｙ(flight F［］，Nodｅ eｌemｅnt[])
{
　RadixＬist p=eｌemｅnt；
ｐ=p－>next；
iｎt ｉ；
for（i=０;i<Ｎ ＆& ｐ！=NULＬ;ｉ++)
　｛
strcpｙ(F［ｉ]、flｉght_nｕmbｅｒ，p->iｎfｏ、flｉght_ｎuｍber)；
sｔｒcｐy（F［i］、ｓｔaｒｔ_ｔiｍe,p—＞infｏ、start＿timｅ)；
sｔｒcpy(F[ｉ］、ａrrｉved_time，ｐ－>info、arrived_tiｍe)；
　 ｓtrｃｐｙ(F[i]、sｔart_ａddｒｅsｓ,p—〉inｆｏ、sｔaｒｔ_ａddresｓ）;
stｒｃpy(F[i]、arrｉved_addreｓs,p—>infｏ、aｒｒｉｖed_ａddresｓ）;
ｓtrｃpy(Ｆ[i]、woｒk＿date，p—〉infｏ、worｋ_ｄate）；
　　strcｐｙ（F[ｉ］、ＦlightTypｅ，p—〉iｎｆo、ＦlighｔType);
F［i］、fare=ｐ－〉info、fare;
p=p－＞ｎexｔ;
｝
｝
//-—-－—--—－－----—服 务 菜 单－—-—--－-—----－
vｏｉd　F_By_Timｅ（flｉgｈt F[］,int）;
voiｄ F＿By＿Ａｄdｒess(flight　Ｆ[］,int)；
ｖoid Ｆ_Ｂｙ_fare(fliｇhｔ Ｆ［］）;
void　F_By_FN（fligｈt F[］)；
/／主菜单
ｖoｉｄ mainmenu(） 　
{
ｃｈar　ｃh;
　 int y;
　　 cout〈＜＂　 　 　 　 　　 　 主菜单\n”<<enｄl；
cout<〈” 　　 =＝=＝＝==＝======＝=＝=＝======＝＝========＝===＝＝==========＝=======\n"〈<eｎdl；
cｏuｔ〈<" 　 　 　 Pｌｅａse choose: （ｉnput the number）（输入查询/排序命令）\n"＜〈endl；
ｃouｔ<<＂ 　 　 　 　 0、 　　shoｗ tｈe　maiｎmenｕ （显示主菜单）＼n"〈〈enｄｌ；
cout〈＜”　 　　 　　 1、　 Fiｎd by fliｇht　ｎｕmber（按航班号查询)＼n"<<endl;
couｔ〈〈” 　 　 　 　 ２、 Fｉnｄ　by staｒｔ　ｔime（按起飞时间查询）\n”＜〈ｅｎdl；
cｏut＜＜＂ 　 　 3、　　 Ｆind　by aｒrived timｅ（按到达时间查询）\ｎ＂＜<endl;
　 cout<〈＂ 　 　 　 　　 　　 4、　　　Fｉnd by start address(按起飞地点查询)\n”〈<endl；
coｕｔ<<" 　　 　 　 5、 　 Find by　arｒived aｄdress(按目得地点查询）\ｎ"<＜endl；
ｃoｕt<〈＂ 　　 　６、 　 Find ｂy the faｒe（按票价范围查询）\ｎ”〈〈endl;
cout＜＜” 　 　 　 　 　 　 　 　 　 　 　　 　 —--－其她键退出＂<＜enｄl；
　cout<〈” 　＝＝＝=＝＝=＝==＝＝====＝=======＝=====＝＝＝=================＝========\n"＜〈enｄl；
wｈile(１）
　｛
　couｔ〈〈”请输入服务命令：”;
　cin〉>y;
ｓwitch(ｙ)
　 ｛
　 ｃase　0: maiｎmenｕ（);breａｋ;
ｃase 1:Ｆ_By_FN(Flight);breａk；
　ｃasｅ ２:Ｆ_By_Time（Fliｇht,１）;break;
　　 　 cａse 3：F_Ｂｙ_Time(Flighｔ,２）;bｒeak；
　 　　 casｅ 4:F＿By_Ａddreｓs(Fｌight，1）;break;
case 5：F＿By_Ａddrｅss（Ｆlｉｇht，2)；ｂreaｋ;
　　 　　 caｓe 6:F_Bｙ_fａｒe(Fｌight）;brｅａk；
　　 　defａuｌt ：coｕt<<" 　 　　 　　 　 　 　 　　 　 谢谢惠顾！　 　 　　 "<＜ｅndl;breaｋ；
}
cｏut〈<”就是否退出?(Y/N）：";
　cin＞〉ch；
if(cｈ＝='Y'｜|cｈ=='y'）　breaｋ;
｝
}
//－-－-－－－————－-—查 询 系　统—-—－—--——-—-—－
/／通过航班号实现二分查找法查找
ｖoid Ｆ_Bｙ_FN(ｆligｈt F［]）
{
int ｌｏw＝0，high=N，mid；
char　Num［１0]；
couｔ＜<"请输入您要查询得航班号：”;
　ciｎ>＞Num；
Cout_ｉnfｏ1(）；//显示头部信息
while（ｌow＜=high)
｛
　 mid=(low+hｉgｈ）/2；
　 iｆ（ｓｔｒcmp(Nuｍ,Ｆ［miｄ］、flight_ｎumber）==0） ｛Couｔ＿info2＿2（F，mｉd）;ｂｒeak；｝
eｌｓe ｉf（strｃmp（Ｎum，F［ｍid]、flight＿nuｍbeｒ）＜0）　ｈigh=ｍid—１；
elsｅ low=mid+1；
｝
　　　 ｃout〈＜" 　 　 ＊＊*****＊＊*＊**对不起,没有您要查找得航班号＊＊＊＊*＊＊＊＊* ”〈〈endl；
}
//通过起飞/到达时间查询
void F_By_Time（ｆｌight F[］，inｔ Timｅ)　 　
｛
inｔ i；
cｈaｒ T［6］;
　　coｕt〈＜＂请输入您要查询得航班得起飞/抵达时间:＂；
　ciｎ〉〉T；
Cout_info1（);//显示头部信息 　 　 　 　 　 　 　　
　 　fｏr(i=０；ｉ<N；i++）
｛
　　if（Timｅ＝=1) //按起飞时间查询
{
if(sｔrｃmｐ（Ｔ，Ｆ［i]、ｓtart_ｔime）＝＝0) Ｃout_iｎfｏ2_２（F，i);
｝
　if（Ｔime＝＝2) ／/按抵达时间查询
　 {
if（strcmp（Ｔ，F[i]、ａｒrｉved＿timｅ）=＝0) Couｔ_inｆｏ2_2(Ｆ,ｉ）;
　｝
　}　
cout〈<”　　 　 　 ＊＊*＊＊＊＊对不起，该时间没有航班＊*＊＊＊＊＊ 　 "〈〈endl;
}
//通过站点查询
ｖoid F_By_Aｄdｒｅss（fｌｉｇｈt F［］,ｉnt　AD) 　
｛
char sｔr［１０]；
cout＜＜"请输入您要查询得航班得起飞/抵达地址：";
ｃin>＞str；
Coｕt_inｆｏ1（);
for(inｔ　i=０;i〈N；i＋＋）
｛
ﻩ if（AD=＝1） /／按起点站查询
ﻩ 　｛
ﻩ ﻩ if(sｔrcｍｐ（str,F［i]、sｔaｒｔ_addｒess）＝＝0) 　Ｃｏuｔ＿info２＿２（F，i）；
ﻩ 　 ｝
if(AD=＝2） //按目得站查询
ﻩ ｛
ﻩﻩ if(strcｍｐ（str,F[i］、arrｉveｄ_ａdｄress）==0） Ｃｏut_info2_2(F,ｉ)；
ﻩ ｝
　｝
coｕｔ<<" 　　 　 　 　 **＊*＊***对不起,该站点不存在＊＊***＊＊＊ 　 　 　 　 "＜<endl;
｝
//通过票价范围查询
vｏid F_Bｙ_ｆａre(flｉｇhｔ F［］） 　 　
｛
　int T１,T２，ｉ;
　 　coｕt＜〈”请输入您要查询得航班得最低票价(单位:元）:＂;
　 ｃin>＞T１;
　 couｔ〈＜＂请输入您要查询得航班得最高票价（单位:元）：＂；
　cin＞＞Ｔ2；
Cout_iｎｆｏ1（）； 　 　　 　　 　　
　　fｏr（i＝0；i<N；ｉ++）
｛
iｆ(Ｔ１〈＝F［i]、fａrｅ &＆ Ｔ2〉=F[ｉ]、fare)　Cout＿info2_2(F,i）；
}
ｃoｕt〈〈＂　　 　　　*＊＊＊＊＊*对不起,没有适合您得航班,请修改您得票价范围＊*＊＊***＊” <〈endl;
}
/／—---—-－-——－-——主 函　数-—－-——－-———----—
int　mａin()
{
RａdixLｉst p＝elｅment；
ｆoｒ（ｉnt i＝0;i〈N；i++)
　 element[i］、next=＆eleｍent[ｉ+1］;
　element［10］、ｎeｘt=NULL；
ｒａdixSｏrt（&p，　D， R)； //基数排序
　outｐut＿AＬＬ_info１(ｅlｅment)； //输出排序后得有序序列（航班信息）
coｐy（Ｆligｈｔ,elemｅnt）; //另存储排序后得航班信息
mainmenu（）; /／给出主菜单
　return　0；
}
测试数据及测试结果：

、
边界值处理：

四：
遇到得问题及解决策略：首先就是要实现所要得功能需用什么数据结构得问题，比如排序问题究竟用那一种，在组员得商量下与上网搜寻资料,采用对排序最符合，其次就是在时间得查询过程中，比如输入时间16:40开始只能实现输入1640，最后通过改时间得数据类型实现了时间得输入,最后就是在各个模块得组合过程中由于各个成员编程所起得名字或者其她原因，程序无法运行 ，最后在大家得努力下一起修改错误使得程序可以正常运行。
还未解决得问题：插入得订票得函数无法正常运行。
五:实验收获与心得:
通过这次次实验我们收获了很多,对数据结构这门课有了更深得了解、让我们对链表、队列、结构体得应用更娴熟,为我们更好得了解课本内容，改进不足提供了件。在这次课程设计得过程中充分说明了团队合作得重要性，组内成员共同讨论,即充分而认真得完成自己负责得模块又对组内其她成员得工作提供建议,使得这次课程设计能够按时完成。我们一定会更加努力，争取在以后得学习中能够学以致用,最后要感谢胡老师在设计过程中给我们得指导，有了胡老师得帮助,我们得流程图更加得规范、正确.再一次谢谢胡老师。
六：
人员分工:组内成员一起构思了流程图.并完成最后得整理工作