(最新整理)应用数据结构课设最短航空路线求解报告

1、(完整)应用数据结构课设最短航空路线求解报告(完整)应用数据结构课设最短航空路线求解报告 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)应用数据结构课设最短航空路线求解报告）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)应用数据结构课设最短航空路线求解报告的全部内容。0120803490426课 程 设

2、计题 目航空线路最短路径求解学 院管理学院专 业信息管理与信息系统班 级0804班姓 名祝黎指导教师施亚能2010年07月09日 学 号： 课程设计任务书学生姓名: 祝黎 专业班级： 信管0804 指导教师： 施亚能 工作单位： 管理学院 题 目：航空线路最短路径求解初始条件:定义10个城市（自行选择）和至少20条航线（不含中转)，要求任意两城市间都可达且至少有2条可选飞行路线。预先定义每条航线的最高定价,航线票价每季度都会有折扣机会,但并非必须，每季度的折扣率由随机函数产生,范围是0.3、0。4、0.5、0。9、1.0。用户从键盘上输入年份，确定该年各季度各航线票价的折扣情况以后,输入月份、

3、起始城市和目的城市名称，程序能显示出最经济的路线选择方案。要求完成的主要任务： （包括课程设计工作量及其技术要求、说明书撰写等具体要求）依题意可知每个结点的度不小于2，航线最高票价可参考实际情况，从网上直接搜索。本程序不考虑机场建设费和燃油附加费，只计算机票价格，将其作为路径上的权值处理，耗费矩阵存储结构自行选择。时间安排：序号设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0。5天3编码实现和静态检查3天4上机准备和上机调试2天5总结和整理设计报告1天合 计7天指导教师签名： 施亚能 2010年 07月03日系主任（或责任教师）签名: 2010年 07月09日1. 需求分析该

4、程序是一个航空最短路径求解的程序，其中程序中定义10个城市和24条航线（不含中转），任意两城市间都可达且至少有2条可选飞行路线。程序预先用邻接表定义并存储了每条航线的最高定价，航线票价每季度都会有折扣机会，每季度的折扣率由随机函数产生，范围是0。3、0。4、0.5、0.9、1。0。用户从键盘上输入年份,确定该年各季度各航线票价的折扣情况以后,输入月份，系统就输出相应的折扣,用户再输入起始城市和目的城市名称,程序能显示出最经济的路线选择方案。程序拥有很清晰的人机界面，其中包括1.查看城市：将预先存储和管理员后来添加的城市一一输出。 2.选择最短时间路线：每一条航线都对应一个预先定义的时间，该操作

5、会为用户选择花时最短的路线,并附带该路线所需费用。3。选择最节约费用路线：每一天航线都预先定义存储了对应的费用，当用户选择对应的月份后，系统会输出相应的折扣，该操作会为用户选择花费最少的航线，并附带该路线所需时间.4.管理员程序:当然一个好的程序肯定不是一个死程序,也就是它可以随时修改，该操作又包含了4个子操作：（1）添加城市 （2）添加或编辑飞机费用 （3）添加或编辑飞机时间 （4)返回主菜单。5.退出程序。本程序运用了图的知识，构造了无向带权费用图和无向带权时间图。（如图1，图2所示） 图1 无向带权费用图 图2 无向带权时间图 部分截图1.主菜单截图2。查看城市3。最低费用查询4.最短时

6、间查询5。添加城市6。飞机花费编辑2. 概要设计1。数据结构本程序运用了关于图这种数据结构，它的抽象数据类型定义如下:typedef struct undigraph int numverts; /结点 costadj cost; /邻接矩阵undigraph,*ung;基本操作：undigraph* createcostg()操作结果：构造带权(费用）图.undigraph createtimeg（）操作结果：构造带权（时间)图.pathmat *floyed（undigraph *d）操作结果：floyed函数 求任意两点的最短路径。2主程序流程main函数查看城市pri()选择折扣yea

7、r_month()最短时间f_time()year_month()选择折扣year_month()最低花费f_money()管理员程序administrator() floyed(） pr(i，0) add_city(） floyed()pr（bcity,0） edit_fline（） pr(bcity，0） prn_pass（bcity，ecity） edit_fhour（） prn_pass（bcity,ecity） pr(ecity，0) pr（ecity，0）3. 详细设计1。程序模块1 程序是用dos 版做的界面.2 主界面包括1。查看城市 2。选择飞机最短时间路线 3。选择飞机最节

8、约费用路线4。管理员程序确 5。退出本程序3 程序的模块为include windows。hinclude stdio.h # include stdlib。h include iwhile ihg=（undigraph ）malloc(sizeof(undigraph）if ！g then null1=iwhile ic_number+1 while j gcostij 初始化使gcostij为无穷。c_number =gnumverts 为各条航线赋权值（时间值）if （o) then while(h=1) t+1=t调用pri(）函数print飞机时间编辑print请输入开始城市的代码i

9、nput aprint请输入结尾城市的代码input bprintf请输入你的两地时间input mt。f_timea =nt。f_timeb=xt.f_timeprint请选择print 1：继续更改城市时间print 0:返回上一级菜单input h switch（h） case 1： 1=hbreak;case 0: 0=hbreak；default：print选择出错t+1 =fwhile (t-)mt+1.f_time =g-costnt+1.f_timext+1。f_timef=treturn（g)；end(4) floyed(undigraph d，undigraph *m) 函

10、数 floyed函数求任意两点的最短路径beginc_number=n1=iwhile（i=n)1=jwhile(jcostij=aij 初始化矩阵a。mcostij=cij1=pathij 初始化矩阵p, 置1. for(k=1;k=n;k+) 为逐步加入的中间结点 for(i=1;i=n;i+) i为a中行号for(j=1;j=n；j+)if(aik+akjaijcik+ckj=cij k= pathij 若i经过k到j比i到j小，则令aij=aik+akj。aij=bijcij=lij elseaij=bijcij=lij print最短路径为：end(5) prn_pass（int i

11、,int j) 输出最短路径所经过的点begin if （ pathij！=-1）递归调用prn_pass(i,pathij）调用pr（pathij,0)end(6） f_time(int m） 飞机最短时间路径函数begin1=hwhile(h=1) print请输入起始城市和目的城市的代码,中间以空格隔开，范围（1- d）”,c_numberinput bcityinput ecity 输入起始城市和终点城市的代码。 if （!（0bcity&bcityc_number+1)（0ecity&ecityc_number+1）&bcity！=ecity)） then print出错啦!！! f

12、loyed（createtimef(0),createcostf(0）) 调用floyed函数. pr(bcity,0) 显示起始城市. prn_pass(bcity，ecity) 调用prn_pass函数，显示最短路径经过的城市. pr(ecity,0） 显示终点城市。 if （bbcityecity5000|lbcityecity10000）then print两地间还没有线路通过else (float)m/10lbcityecity= moneyprint“打折前的费用是%d元n”，lbcityecityprint ”飞机花的费用是%d元n”,(int）money print 飞机花的最

13、短时间是d小时n,bbcityecity print 1.继续最少花费查找n 2.返回主菜单n 清选择.。. input l 输入1或2选择是否继续. 1=h end(7) year_month(）函数 选择折扣begin srand(（unsigned）time（null） 随机种子调用 pri(） 输出城市列表及相应代码. print请输入年份: input year for(i=1;idiscounti1 产生310之间的随机数 print 2d月的折扣是： ”,i printf %2d折n，discounti-1 print 请选择月份。.(请在1-12之间选择) input mont

14、h if(1=month# include time。h /需引用的头文件*/srand(（unsigned)time(null); /随机种子/n=rand(）（xy+1)+y； /产生yx之间的随机数/然后我就借用此函数构造了随机打折的函数，但是在构造的过程中，我又忽略了一个问题，那就是随机函数只能产生整数随机数,我最开始的目的是构造0.31之间的随机数,所以定义的变量时float型，后来运行不通过，仔细思考之后才知道该随机函数只能产生310之间的数，修改变量定义之后就可以运行成功了。2.时间复杂度1。构造带权图createflyg createcostg和createtimeg:t（ma

15、x）=o（(max)2)2。 floyed函数 floyed : t(n）=o（n2+n3)3。显示路径函数 prn_pass : t(n）=o（n)3。空间复杂度 本程序的空间复杂度均为s(n）=（n2); 即存放n2个节点数据辅助空间。4.经验和体会自学习c语言以来，我们就没怎么练习上机实践能力,所以对于代码的敏感度不够，一个错误出现了，不是很容易发现.在这次课程设计中,我就犯了很多高手认为很基础的错误,比如说：printf函数的用法，变量声明的位置，还有就是指针数组的用法。犯错误是不可避免的，但是我们要认真地去发现错误和修改错误.我在运行后,知道自己的程序有错误，我首先一步一步慢慢看，慢

16、慢分析，在整个程序中找不出来就将该部分分离出去进行测试，这样，就很容易找到问题所在了。当然请教别人也是一个学习的方法，如果自己很长时间也找不出错误,何不请教高年级的学长呢。在这次的课程设计中，我也请教过大三的学长还有老师，虽然他们只是给了提示，但真的是我懂了不少。5. 用户使用说明运行程序，用户会看到该程序的主界面。由用户输入数字，选择相应的操作.1.查看城市 输出所有的城市及其代码。2。选择最短时间路线输出所有的城市及其代码请输入年份输出每月对应的折扣 请选择月份.。.（请在1-12之间选择）请输入起始城市和目的城市的代码,中间以空格隔开，范围（1- %d） 输出最短路径和飞机最短时间及花费

17、3. 选择最低花费路线输出所有的城市及其代码请输入年份输出每月对应的折扣 请选择月份。.（请在112之间选择）请输入起始城市和目的城市的代码，中间以空格隔开,范围(1- d） 输出最短路径和飞机最低花费及时间4。 管理员程序 输出管理员程序子菜单 请选择 （1）增加城市 请输入要增加的个数 请输入你要增加的城市名 城市增加完毕 （2）添加或编辑飞机费用 输出所有的城市及其代码 飞机花费编辑 请输入开始和结尾城市代码 请输入两地花费 （3)添加或编辑飞机时间 输出所有的城市及其代码 飞机时间编辑 请输入开始和结尾城市代码 请输入两地时间 （4）返回主菜单5。退出程序6. 测试结果1。开始界面2。

18、查看城市（这是原始存储的城市）3。最短时间查询.以输入年份2009为例,选择1月，对应的折扣是4折，起始城市是1,目的城市是2最短路径是 成都 西安 打折前的费用是840元，打折后336元，最短时间是2个小时4。选择2,返回主菜单，选择3.选择最节约费用路线，以输入2010年为例，对应的折扣如下图，选择2月份,折扣是6折，起始城市是1,目的城市是2，最短路径是 成都 西安 打折前的费用是840元，打折后的最少费用是336元,花费的时间是2小时.5。返回主菜单，4。添加城市.界面如下.6.添加或编辑飞机费用7。添加城市后,进行最少费用查询7. 附录include windows。h#includ

19、e # include stdlib.h include /需引用的头文件*/define inf 65535 /定义一个最大数定为无穷值define max 23static int c_number=10;static int k=0;staticint v=0,z=0,r=0,t=0；typedef struct zhuint f_cost；int f_time；zhu；zhu m20,x20，n20；typedef int costadjmax+1max+1；/图邻接矩阵从1开始记数int pathmax+1max+1；/图邻接矩阵从1开始记数typedef struct undigr

20、aphint numverts; /结点costadj cost； /邻接矩阵undigraph,ung； /图的定义typedef struct c_editchar a10;c_edit;c_edit add10;costadj b，l;int pr(int i，int j) int h=0；if （j=0) h=i;else if （j=1）scanf(”s，&addi。a)；switch(h）/运用switch语句。 case(0）：printf(”）;break;case（1） ： printf（成都 ）； break； case(2) ： printf（”西安 ）；break; c

21、ase(3) : printf(”郑州 );break; case(4） : printf(”武汉 );break; case(5) : printf(株洲 ”）；break； case(6） ： printf（贵阳 ”）;break； case(7） ： printf(北京 ”);break; case(8） : printf（”天津 );break； case(9） ： printf（上海 ）；break; case(10) : printf(徐州 ）；break;default： printf(s ”，addi-10.a）;return 1;/输出城市列表及相应代码void pri()i

22、nt i； printf( 城市及其代码 nnn”); printf（*n）; for （i=1；icostij=inf;/初始化使g-costij为无穷。g-numverts=c_number；g-cost16=gcost61=3;gcost12=gcost21=2;gcost23=gcost32=1;gcost34=g-cost43=2；gcost45=gcost54=4；g-cost56=g-cost65=3;gcost37=g-cost73=6;g-cost78=gcost87=1;gcost810=g-cost108=2;g-cost310=gcost103=3;g-cost910=

23、g-cost109=6;gcost95=g-cost59=1；if (o） while(h=1）t=t+1;pri()； printf（”飞机时间编辑n”);printf(请输入开始城市的代码n”）;scanf（”d”,&a）；printf（请输入结尾城市的代码n”）；scanf(”%d”，b)；printf(请输入你的两地时间n）；scanf（”%d，mt。f_time）；nt.f_time=a;xt.f_time=b；printf（”请选择n”)；printf（”*n”)；printf(”1：继续更改城市时间n”);printf（0：返回上一级菜单n）;printf(*n)；scanf(d

24、”,&h)；switch（h) case 1: h=1；break；case 0： h=0;break；default：printf(”选择出错n”)；f=t+1;while （t-） g-costnt+1.f_timext+1。f_time=mt+1.f_time;t=f；return（g)；undigraph *createcostf(int o)/飞机花费的存贮和编辑功能undigraph *g;int i,j;int a=0,b=0,f,h=1；if（！（g=（undigraph ）malloc(sizeof（undigraph）)）) /为g分配存储空间。return（null）；f

25、or（i=1；ic_number+1；i+）for(j=1;jc_number+1；j+）g-costij=inf； /初始化使g-costij为无穷。gnumverts=c_number;gcost16=gcost61=960；gcost12=gcost21=840；gcost23=g-cost32=501;gcost34=gcost43=530;g-cost45=g-cost54=400;g-cost56=gcost65=900;g-cost37=g-cost73=690；g-cost78=gcost87=310；g-cost810=g-cost108=670;gcost310=gcost

26、103=340;gcost910=g-cost109=650；g-cost95=g-cost59=1180;if (o） while（h=1）r=r+1；pri()； printf（飞机花费编辑n”)；printf（请输入开始城市的代码n）;scanf（%d”,a)；printf(”请输入结尾城市的代码n);scanf(”d”,b);printf（”请输入你的两地花费n”);scanf(d”,mr.f_cost）；nr。f_cost=a;xr.f_cost=b；printf(”请选择n）；printf（*n）；printf(1:继续更改城市费用n”）；printf（”0:返回上一级菜单n”）；

27、printf（”*n）;scanf(”%d”,h）;switch（h） case 1: h=1;break；case 0： h=0;break；default：printf（”选择出错n）；f=r+1；while （r-） g-costnr+1.f_costxr+1.f_cost=mr+1.f_cost；r=f;return(g);/floyed函数 求任意两点的最短路径：void floyed（undigraph *d,undigraph m) int i,j,k,n；costadj a，c；n=c_number； for（i=1;icostij； pathij=-1; /初始化矩阵p， 置

28、-1. for（k=1；k=n；k+) /k为逐步加入的中间结点 for（i=1;i=n；i+) /i为a中行号for（j=1；j=n；j+)if(aik+akjaij）aij=aik+akj; cij=cik+ckj； pathij=k；/若i经过k到j比i到j小，则令aij=aik+akj。bij=aij；lij=cij; elsebij=aij；lij=cij；/end-for printf（”n最短路径为： n）；/end-floyed/为了求从i到j的最短路径，只需要调用如下的过程：void prn_pass(int i，int j） if（pathij！=-1） prn_pass(

29、i,pathij)；/输出最短路径经过的所有点 pr(pathij，0）；/求最少时间路径。void f_time(int m)int bcity,ecity；/起始成市号码和终点城市号码 int l,h=1； float money；do printf（请输入起始城市和目的城市的代码，中间以空格隔开，范围(1 %d）”,c_number）；scanf(”d”,bcity); scanf（%d,&ecity）;/输入起始城市和终点城市的代码。 if （！(（0bcitybcity5000|lbcityecity10000） printf（”两地间还没有线路通过n”);else money=（f

30、loat）m/10lbcityecity;printf（打折前的费用是%d元n,lbcityecity）；printf(飞机花的费用是d元n,（int)money)； printf(”飞机花的最短时间是d小时n”,bbcityecity）； printf（”nn 1.继续最少花费查找n 2.返回主菜单n 清选择。.。”)； scanf（%d”，l)； /输入1或2选择是否继续. h=l； while（h=1）; printf(”n”）;/求最少花费路径.void f_money（int m) int bcity，ecity；/起始成市号码和终点城市号码 int l;inth=1；float m

31、oney;/undigraph g；*/do printf(请输入起始城市和目的城市的代码，中间以空格隔开，范围（1- d），c_number）； scanf(”%d,&bcity); scanf(d”，&ecity）;/输入起始城市和终点城市的代码。if (!（(0bcity&bcityc_number+1）&（0ecity&ecity5000|lbcityecity10000） printf（两地间还没有线路通过n”）；else money=(float）m/10*bbcityecity;printf（打折前的费用是d元n”，bbcityecity)；printf(飞机花的最少费用是%d元

32、n,(int)money); printf(飞机花的时间是%d小时n，lbcityecity）; printf(”nn 1。继续最少花费查找n 2。返回主菜单n 清选择.。）； scanf(%d,&l）； /输入1或2选择是否继续。 h=l; while(h=1); printf(n)；int year_month()/选择折扣 int i; int discount12； int month,year; srand（(unsigned）time（null）； /随机种子/ pri（);/输出城市列表及相应代码。 printf(请输入年份：”); scanf（%d,year）; for(i=1

33、;i=12；i+) discounti1=rand(）（10-3+1)+3； /产生310之间的随机数*/ printf（%2d月的折扣是： ，i）; printf(%2d折n”，discounti-1）; printf（”请选择月份.。(请在112之间选择) ”)； scanf(d,&month); if（1=month=12) printf（你选择的是%d月，折扣是dn,month，discountmonth-1); else printf(输入出错,请重新输入！）； return discountmonth-1;void add_city(）/对城市的增加static int i=1;i

34、nt j；printf(”请输入你要增加的城市的个数n”）;scanf(”%d,j)；for （i=1;i=j；i+） printf（请输入你要增加的城市名n”）；pr(i,1);c_number=c_number+1;printf(城市增加完毕n);void edit_fline(）/增加编辑飞机的费用createcostf(1)；void edit_fhour()/增加编辑飞机的时间createtimef（1）;void administrator(）/管理员功能int h=1；while （h) printf(*n”);printf（”1:增加城市n)；printf（2：添加或编辑飞机费用n）；printf（”3：添加或编辑飞机时间n）；printf（”0:返回主菜单n）； printf(*n）;printf（请选择:n）；scanf(d，h)；switch（h) case 1 :