最便宜航空路线求解

学号：课程设计题目最廉价航空线路求解学院管理学院专业信息管理与信息系统班级姓名指导教师2014年07月03日课程设计任务书学生姓名：专业班级：信管指导教师：工作单位：管理学院题目：最廉价航空线路求解初始条件：【问题描述】飞机是远途旅行必不可少的工具，但是高昂的价格也令人颇费思量，因此人们往往宁愿用时间来换金钱而选择较慢的交通工具。不过，当航班线路变得丰富之后，人们也发现很多时候选择直达航班往往并非最省钱的路径，比方飞往美国选择从韩国转机就比直飞要廉价多了〔虽然这样有坠机的危险〕。这样一来，当采用曲线行进能到达省钱也省时间的目的时，坐飞机还是可以接受的。为了能够更好地解决路径的选择问题，我们模拟一下通过适宜的算法来选出最优航空线路。参考上的数据，自选至少10个城市和至少20条航线〔不含中转〕，要求任意两城市间都可达〔这并不意味着两个城市之间就一定有直飞航班，比方大陆到台湾〕，且至少有2条可选飞行路线。预先定义每条航线的最高定价，航线票价每季度都有折扣时机，但并非必须。每条线路每季度的折扣率由随机函数产生，范围是0.20～1.0〔小数点后取两位〕。要求完成的主要任务:〔包括课程设计工作量及其技术要求、说明书撰写等具体要求〕本程序不考虑机场建设费和燃油附加费，只计算机票价格，将其作为路径上的权值处理，消耗矩阵存储结构自行选择。在真实的情形中，同一线路每天可能有许多航班，也可能每周只有一两趟航班，即便同一天的航班早晚价格也可能有所不同。为简便计，假定每条线路每天只有一趟航班，不考虑航空公司的差异。时间安排：序号设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0.5天3编码实现和静态检查3天4上机准备和上机调试2天5总结和整理设计报告1天合计7天指导教师签名：2014年06月25日系主任〔或责任教师〕签名：2014年06月25日最廉价航空线路求解需求分析1.1根本要求〔1〕所有原始数据一律事先用文本文件保存，读入数据时从文件获取。〔2〕航班价格可以用随机函数生成，但建议从网上直接复制真实数据。〔3〕可输出所有城市名称以及每一城市所有可直飞到达的城市列表。〔4〕可输出任一指定直飞线路〔假设没有那么显示无直飞航班〕四个季度的全票和折扣价格。〔5〕输入月份、起始城市和目的城市名称，程序能显示出最经济的中转路线选择方案。1.2输入〔1〕从文件read.txt中读取不同城市之间〔共10个城市〕不同航线〔共24条航线〕的最高价格输入，四个季度有相同的最高价格。〔2〕每条线路每季度的折扣率由随机函数产生，范围是0.20～1.00〔小数点后取两位〕，四个季度有不同的折扣。〔3〕运行程序时需根据要求从键盘输入相应指令，保证程序的正确运行。1.3输出〔1〕输出所有城市名以及每一城市所有可直飞到达的城市列表〔按城市名拼音升序排列〕：始发地可直飞目的地北京长春广州杭州昆明上海首尔武汉香港……首尔北京上海台北香港……〔2〕输出指定线路四个季度的折扣和全价：输入：北京-台北输出：无直飞航班输入：北京-广州输出：季度全票价格折扣折后价格〔不计小数，四舍五入〕112406.5806

211927.0834314754.6679

412308.71070〔3〕输入月份、起始城市和目的城市名称，输出最正确方案：输入：5北京-台北输出：最正确线路：北京-香港，1503，香港-台北，791，合计2294输入：7广州-首尔输出：最正确线路：广州-上海，880，上海-首尔，773，合计1653

输入：10武汉-上海输出：最正确线路：武汉-上海，278，合计278

……1.4测试数据文本文件read.txt内容：读文本文件read.txt。假设文件名输入正确且文件无错误，那么显示主菜单。假设文件名输入错误或文件有错误，那么显示“翻开输入文件出错”。根据主菜单提示选择需要执行的功能。假设输入功能序号在0—4之间，那么执行相应的功能。假设输入功能序号不在0—4之间，那么显示“出错啦!!!请在0-4之间选择!!”和主菜单，需重新选择。选择1，输出城市列表及相应代码。选择2，输出所有城市名以及每一城市所有可直飞到达的城市列表〔按城市名拼音升序排列〕。选择3，先显示城市列表及相应代码，方便后面的输入操作，根据提示“请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--10)”输入两个城市代码，假设两城市间有直飞航班那么显示指定线路四个季度的折扣和全价。假设两城市间无直飞航班那么显示“无直飞航班”。选择4，显示“请输入月份(请在1-12之间选择)：”假设月份输入正确，那么先显示城市列表及相应代码，方便后面的输入操作，根据提示“请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--10)”输入两个城市代码，假设代码输入正确，那么显示最正确方案。假设月份输入错误，那么显示“输入出错”。假设城市代码输入错误，那么显示“出错啦!!!”。选择0，那么直接退出程序。在每一个功能执行完后，都会提示继续执行还是返回主菜单。12191.5无向带权费用图12191584武汉箭头流程1584武汉箭头流程厦门北京厦门北京261126111575157374315751573743大连郑州大连郑州广州广州10061006长沙长沙113011301903612上海1903612上海1461天津深圳1461天津深圳2346概要设计23462.1抽象数据类型定义本程序运用了关于图这种数据结构，它的抽象数据类型定义如下：typedefstructunDiGraph{ intnumVerts;//结点 costAdjcost;//邻接矩阵}unDiGraph,*UNG;根本操作：unDiGraph*CreateCostG()操作结果：构造带权(费用)图。PathMat*Floyed(unDiGraph*D)操作结果：Floyed函数求任意两点的最短路径。2.2主程序流程及各程序模块之间的层次〔调用〕关系Main函数输出方式1f_money1()pri()查看城市输出方式3f_money3()输出方式2f_money2()退出退出程序pr(i,0)Floyed()Floyed()pr(Bcity,0)pr(Bcity,0)prn_pass(Bcity,Ecity)prn_pass(Bcity,Ecity)pr(Ecity,0)pr(Ecity,0)详细设计3.1数据类型〔1〕主界面包括1.查看城市2.输出所有城市名及所有可直飞到达的城市列表〔按城市名拼音升序排列〕3.输入起始城市和目的城市名称，输出指定线路四个季度的折扣和全价输入月份、起始城市和目的城市名称，输出最正确方案0.退出程序〔2〕程序的模块为#include<stdio.h>#include<stdlib.h>#include<time.h>//需引用的头文件#defineINF65535//定义一个最大数为无穷值,表示两城市之间无直飞航班#defineMAX23typedefintcostAdj[MAX+1][MAX+1];//图邻接矩阵从1开始记数intPath[MAX+1][MAX+1];//图邻接矩阵从1开始记数typedefstructunDiGraph{ intnumVerts;//结点 costAdjcost;//邻接矩阵}unDiGraph,*UNG;//图的定义costAdjB,L;voidpr(inti)//选择城市voidpri()//输出城市unDiGraph*CreateCostG()//构造带权(费用)图返回首地址G：voidFloyed(unDiGraph*D,unDiGraph*M)//Floyed函数求任意两点的最短路径：voidprn_pass(inti,intj)//为了求从i到j的最短路径，只需要调用如下的过程voidf_money1()//输出所有城市名及所有可直飞到达的城市列表〔按城市名拼音升序排列〕voidf_money2()//输入起始城市和目的城市名称，输出指定线路四个季度的折扣和全价voidf_money4()//输入月份、起始城市和目的城市名称，输出最正确方案intLineNumStat(FILE*fp)//统计文本文件的行数voidmain()//main函数3.2伪码算法〔1〕pr()选择城市begin0=>hIfj=0thenh=iElseifj=1inputadd[i].aSwitch条件选择print城市名End〔2〕pri()输出城市beginPrint城市代码1=>iWhilei<=c_number{Printi调用pr()函数}End〔3〕unDiGraph*CreateCostF(into)飞机花费的存贮功能Begin0=>a,0=>b,1=>hWuhan[10],Beijing[10],Xiamen[10],Guangzhou[10],Dalian[10], Shanghai[10],Changsha[10],Shenzhen[10],Zhengzhou[10],Tianjin[10]G=(unDiGraph*)malloc(sizeof(unDiGraph)If!GthenNULL1=>iWhilei<c_number+1{Whilej<c_number+1INF=>G->cost[i][j]初始化使G->cost[i][j]为无穷。}c_number=>G->numVertswhile(!feof(fp))fscanffp,"%f%f%f%f%f%f%f%f%f%f",&Wuhan[i],&Beijing[i],&Xiamen[i],&Guangzhou[i],&Dalian[i],&Shanghai[i],&Changsha[i],&Shenzhen[i],&Zhengzhou[i],&Tianjin[i] for(0=>j;j<c_number+1;j++) {Wuhan[j-1]=>G->cost[j][1]Beijing[j-1]=>G->cost[j][2] Xiamen[j-1]=>G->cost[j][3]Guangzhou[j-1]=>G->cost[j][4] Dalian[j-1]=>G->cost[j][5] Shanghai[j-1]=>G->cost[j][6]Changsha[j-1]=>G->cost[j][7] Shenzhen[j-1]=>G->cost[j][8] Zhengzhou[j-1]=>G->cost[j][9] Tianjin[j-1]=>G->cost[j][10] }return(G);}End〔4〕Floyed(unDiGraph*D,unDiGraph*M)函数Floyed函数求任意两点的最短路径Beginc_number=>n1=>iwhile(i<=n){1=>jwhile(j<=n){D->cost[i][j]=>A[i][j]初始化矩阵A。 M->cost[i][j]=>C[i][j] -1=>Path[i][j] 初始化矩阵p,置-1. } } for(0=>k;k<=n;k++)为逐步参加的中间结点 { for(0=>i;i<=n;i++)i为A中行号 { for(0=>j;j<=n;j++) if(A[i][k]+A[k][j]<A[i][j])then{A[i][k]+A[k][j]=>A[i][j]K=>Path[i][j]假设i经过k到j比i到j小，那么令A[i][j]=A[i][k]+A[k][j] A[i][j]=>B[i][j]} else{ A[i][j]=>B[i][j] } } }print最短路径为:End〔5〕prn_pass(inti,intj)输出最短路径所经过的点BeginIf(Path[i][j]!=-1){递归调用prn_pass(i,Path[i][j])调用pr(Path[i][j],0)}Endf_money1()输出方式1函数Beginl1=>hdo{Print始发地可直飞目的地Print北京广州武汉Print长沙大连天津Print大连长沙厦门郑州Print广州北京上海郑州Print上海广州深圳天津Print深圳上海天津Print天津长沙上海深圳Print武汉北京厦门Print厦门大连武汉Print郑州长沙广州Print1.继续输出所有城市名以及每一城市所有可直飞到达的城市列表2.返回主菜单清选择... inputl输入1或2选择是否继续。1=>h}End〔7〕f_money2()输出方式2函数Begin1=>hBcity,Ecity//起始成市号码和终点城市号码lmoney[4]i,js,wdiscount[4]while(h==1){print请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--%d,c_numberinputBcityinputEcity输入起始城市和终点城市的代码。 if(!((0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity))thenprint出错啦!!!exit(1)Floyed(CreateTimeF(0),CreateCostF(0))调用Floyed函数。 pr(Bcity,0)显示起始城市。prn_pass(Bcity,Ecity)调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0)显示终点城市。if(B[Bcity][Ecity]>5000||L[Bcity][Ecity]>10000) thenprint无直飞航班 else {Print"季度全票价格折扣折后价格〔不计小数，四舍五入〕\n" srand((unsigned)time(NULL))随机种子for(0=>j;j<4;j++) {for(0=>i;i<100;i++) { if(!(i%10))rand()%80+20=>ww/100=>s break; }s=>discount[j] } for(0=>i;i<4;i++) {(floatdiscount[i]*B[Bcity][Ecity]=>money[i]Print"%d%d%.2lf%.lf\n",i+1,B[Bcity][Ecity],discount[i],money[i]); Print“打折前的费用是%d元\n",L[Bcity][Ecity] }Print1.继续输入起始城市和目的城市名称，输出指定线路四个季度的折扣和全价\n2.返回主菜单\n清选择... inputl输入1或2选择是否继续。1=>h }Endf_money3()输出方式3函数Begin1=>hBcity,Ecity起始成市号码和终点城市号码Lmoneyi,js,wdiscount[4]Mmonth quarterdo{Print"请输入月份(请在1-12之间选择)：" Inputmonth if(month>=12||month<=1) {Print"输入出错！\n" exit(1); } pri()输出城市列表及相应代码。 print请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--%d,c_numberinputBcityinputEcity输入起始城市和终点城市的代码。 if(!((0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity)) {Print\n出错啦!!!\n"输入出错 exit(1)关闭所有文件，终止正在执行的程序 } Floyed(CreateCostF(0))调用Floyed函数。 if(B[Bcity][Ecity]>5000) { print无航班\n" } else{ srand((unsigned)time(NULL随机种子for(0=>j;j<4;j++) {for(0=>i;i<100;i++) { if(!(i%10))rand()%80+20=>ww/100=>s break; }s=>discount[j] }if(1<=month<=3) { discount[0]=>m 1=>quarterPrint"你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m } elseif(4<=month<=6) { discount[1]=>m2=>quarterPrint"你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m } elseif(7<=month<=9) { discount[2]=>m3=>quarterPrint"你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m } elseif(10<=month<=12) { discount[3]=>m4=>quarterPrint"你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m }(float)m*B[Bcity][Ecity]=>moneyPrint"最正确线路："pr(Bcity,0)显示起始城市。prn_pass(Bcity,Ecity)调用prn_pass函数，显示最短路径经过的城市。 pr(Ecity,0)显示终点城市。Print"合计："Print"%.lf\n",money }Print1.继续输入月份、起始城市和目的城市名称，输出最正确方案\n2.返回主菜单\n清选择... inputl输入1或2选择是否继续。1=>h }End调试分析4.1问题与解决方法〔1〕声明变量语句的位置我在运行的过程中一直出现这个错误〔见下列图〕，系统报错说未定义变量，但我确实定义过了，后来通过在网上百度资料才知道要把声明变量的语句得放到函数的最前面，而printf要放在所有变量声明语句后面。修改程序之后，那些错误果然没有了。文本文件的读取程序在读取文本文件时总说翻开文件出错，原因是read.txt中含有非法字符，删去即可。而且在程序末尾要记得调用函数fclose()，关闭文件。把从文本文件读取的数据保存到数组中编写这一局部的时候总是出现错误，主要是对指向数组的指针认识不清，通过这次编程对它有了更深的了解。〔4〕scanf("%s",&add[i].a)和 printf("%s",add[i-10].a)在编写程序阶段，我最开始编写这两个函数的时候是scanf("%c",&add[i].a)printf("%c",add[i-10].a)，当时没有看清add[i].a最初的定义，它其实是一个字符数组，所以在运行的时候老出错，后面慢慢研究和调试才知道在输入和输出的格式占位符应该用%s.〔5〕随机函数的编写我以前几乎没接触过随机函数，所以对其不是很了解。刚开始的时候都不会写，后来在网上找实例，才知道其用法。而且根据题目的要求产生折扣的范围是0.20～1.0〔小数点后取两位〕，所以要产生有小数范围的不同随机数，就要用时间作为产生随机数的种子，并且通过取余运算和除以整数100来确定随机数的范围。另外还需引用以下头文件：#include<stdlib.h>#include<time.h>4.2算法的时空分析〔1〕时间复杂度：Floyed函数T(n)=O(n2+n3)〔2〕空间复杂度：本程序的空间复杂度均为S(n)=(n2);即存放n2个节点数据辅助空间。4.3经验和体会c语言的学习实践很重要。自学习C语言以来，我们就没怎么练习上机实践能力，所以对于代码的敏感度不够，一个错误出现了，不是很容易发现。在这次课程设计中，我就犯了很多高手认为很根底的错误，比方说：printf函数的用法，变量声明的位置，还有就是指针数组的用法。犯错误是不可防止的，但是我们要认真地去发现错误和修改错误。我在运行后，知道自己的程序有错误，我首先一步一步慢慢看，慢慢分析，在整个程序中找不出来就将该局部别离出去进行测试，这样，就很容易找到问题所在了。编写c语言程序必须要细心，特别注意标点符号的书写。同一个error可能要改个几遍才能改好，由于平时编程经历少的缘故，总感觉有些吃力，要解决这一问题就要自己找题目练习，而不是仅仅依赖于老师每次实验和考试。另外通过程序的编写还发现自己在c语言编程方面存在缺乏，要继续加强练习。要善于利用身边的资源。资源既包括网络资源也包括人力资源。遇到一个问题先要通过网络查找解决方法，如果还是不能解决就要学会请教别人，毕竟身边有很多技术牛人和学长学姐，他们都给我很耐心地解答，让我很感动的同时也受益匪浅。〔4〕通过这次课设对弗洛伊德算法有了更深刻的了解。本次课程设计的问题归根到底是求最短路问题，用弗洛伊德算法求任意两点最短路径的过程比用迪杰斯特算法算n次的形式上更加简单，时间复杂度为O(n2+n3)，是一个简便的算法。用户使用说明5.1使用程序的操作步骤运行程序后输入存储输入数据的文件名，用户会看到程序的主菜单，根据标号的提示输入序号让程序执行相应的操作。选择序号1，程序输出所有的城市及其代码。可以选择继续查询或返回主菜单，输入序号执行相应功能。选择序号2，程序输出所有城市名及所有可直飞到达的城市列表〔按城市名拼音升序排列〕。可以选择继续查询或返回主菜单，输入序号执行相应功能。选择序号3，程序输出所有的城市及其代码，根据提示输入两城市标号，程序输出指定线路四个季度的折扣和全价。可以选择继续查询或返回主菜单，输入序号执行相应功能。选择序号4，按要求输入月份，程序输出所有的城市及其代码，根据提示输入两城市标号，程序输出你选择的月份、位于的季度、折扣以及最正确方案。可以选择继续查询或返回主菜单，输入序号执行相应功能。选择序号0，退出程序。测试结果6.1测试结果展示文本文件read.txt内容：〔1〕读文本文件read.txt。假设文件名输入正确且文件无错误，那么显示主菜单。假设文件名输入错误或文件有错误，那么显示“翻开输入文件出错”。〔2〕根据主菜单提示选择需要执行的功能。假设输入功能序号在0—4之间，那么执行相应的功能。假设输入功能序号不在0—4之间，那么显示“出错啦!!!请在0-4之间选择!!”和主菜单，需重新选择。〔3〕选择1，输出城市列表及相应代码。〔4〕选择2，输出所有城市名以及每一城市所有可直飞到达的城市列表〔按城市名拼音升序排列〕。〔5〕选择3，先显示城市列表及相应代码，方便后面的输入操作，根据提示“请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--10)”输入两个城市代码，假设两城市间有直飞航班那么显示指定线路四个季度的折扣和全价。假设两城市间无直飞航班那么显示“无直飞航班”。〔6〕选择4，显示“请输入月份(请在1-12之间选择)：”假设月份输入正确，那么先显示城市列表及相应代码，方便后面的输入操作，根据提示“请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--10)”输入两个城市代码，假设代码输入正确，那么显示最正确方案。假设月份输入错误，那么显示“输入出错”。假设城市代码输入错误，那么显示“出错啦!!!”。〔7〕选择0，那么直接退出程序。〔8〕在每一个功能执行完后，都会提示继续执行还是返回主菜单。附录#include<stdio.h>#include<stdlib.h>#include<time.h>//需引用的头文件#defineINF65535//定义一个最大数为无穷值,表示两城市之间无直飞航班#defineMAX23staticintc_number=10;//定义城市个数staticintk=0;staticintv=0,z=0,r=0,t=0;typedefintcostAdj[MAX+1][MAX+1];//图邻接矩阵从1开始记数intPath[MAX+1][MAX+1];//图邻接矩阵从1开始记数typedefstructunDiGraph{ intnumVerts;//结点 costAdjcost;//邻接矩阵}unDiGraph,*UNG;//图的定义typedefstructc_edit{chara[10];}c_edit;c_editadd[10];costAdjB;//城市列表定义intpr(inti,intj){ inth=0;if(j==0){ h=i;}elseif(j==1){ scanf("%s",&add[i].a);} switch(h)//运用switch语句。 { case(0):printf(""); break; case(1):printf("武汉");break;case(2):printf("北京"); break;case(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",add[i-10].a); } return1;}//输出城市列表及相应代码voidpri(){ inti;printf("城市及其代码\n\n\n");printf("**********************************************************\n");for(i=1;i<=c_number;i++) { printf("%d",i); printf("."); pr(i,0); } printf("\n"); printf("**********************************************************\n\n\n\n\n\n");}//构造带权(票价)图返回首地址GunDiGraph*CreateCostF(into,FILE*fp)//飞机花费的存贮功能{ unDiGraph*G; inti,j,time=1; inth=1; intWuhan[10],Beijing[10],Xiamen[10],Guangzhou[10],Dalian[10], Shanghai[10],Changsha[10],Shenzhen[10],Zhengzhou[10],Tianjin[10]; if(!(G=(unDiGraph*)malloc(sizeof(unDiGraph))))//为G分配存储空间。 { return(NULL); } for(i=1;i<c_number+1;i++) { for(j=1;j<c_number+1;j++) { G->cost[i][j]=INF;//初始化使G->cost[i][j]为无穷。 } } G->numVerts=c_number; i=0; while(time!=11) { fscanf(fp,"%d",Wuhan+i); fscanf(fp,"%d",Beijing+i); fscanf(fp,"%d",Xiamen+i); fscanf(fp,"%d",Guangzhou+i); fscanf(fp,"%d",Dalian+i); fscanf(fp,"%d",Shanghai+i); fscanf(fp,"%d",Changsha+i); fscanf(fp,"%d",Shenzhen+i); fscanf(fp,"%d",Zhengzhou+i); fscanf(fp,"%d",Tianjin+i); time++; i++; } for(j=1;j<c_number+1;j++) {G->cost[j][1]=Wuhan[j-1];G->cost[j][2]=Beijing[j-1]; G->cost[j][3]=Xiamen[j-1]; G->cost[j][4]=Guangzhou[j-1]; G->cost[j][5]=Dalian[j-1]; G->cost[j][6]=Shanghai[j-1];G->cost[j][7]=Changsha[j-1]; G->cost[j][8]=Shenzhen[j-1]; G->cost[j][9]=Zhengzhou[j-1]; G->cost[j][10]=Tianjin[j-1]; } return(G); }//Floyed函数求任意两点的最小票价voidFloyed(unDiGraph*D){ inti,j,k,n; costAdjA; n=c_number;for(i=1;i<=n;i++) { for(j=1;j<=n;j++) {A[i][j]=D->cost[i][j];//初始化矩阵A。 Path[i][j]=-1; //初始化矩阵Path,置-1.保存最短路径，求A[i][j]时，Path[i][j]存放从顶点vi到顶点vj的中间节点编号不大于k的最短路径上前一个节点的编号 }} for(k=1;k<=n;k++)//k为逐步参加的中间结点 { for(i=1;i<=n;i++)//i为A中行号 { for(j=1;j<=n;j++) if(A[i][k]+A[k][j]<A[i][j]) {A[i][j]=A[i][k]+A[k][j]; Path[i][j]=k;//假设i经过k到j比i到j小，那么令A[i][j]=A[i][k]+A[k][j]。 B[i][j]=A[i][j]; } else{ B[i][j]=A[i][j]; } } }//end-for}///end-Floyed//为了求从i到j的最短路径，只需要调用如下的过程voidprn_pass(inti,intj){ if(Path[i][j]!=-1) { prn_pass(i,Path[i][j]);//输出最短路径经过的所有点 pr(Path[i][j],0); }}//输出所有城市名以及每一城市所有可直飞到达的城市列表〔按城市名拼音升序排列〕voidf_money1(){ intl; int h=1;do{ printf("始发地可直飞目的地\n"); printf("北京广州武汉\n"); printf("长沙大连天津\n"); printf("大连长沙厦门郑州\n"); printf("广州北京上海郑州\n"); printf("上海广州深圳天津\n"); printf("深圳上海天津\n"); printf("天津长沙上海深圳\n"); printf("武汉北京厦门\n"); printf("厦门大连武汉\n"); printf("郑州长沙广州\n"); printf("\n\n1.继续输出所有城市名以及每一城市所有可直飞到达的城市列表\n2.返回主菜单\n清选择..."); scanf("%d",&l);//输入1或2选择是否继续。 h=l; }while(h==1);printf("\n");}//输入起始城市和目的城市名称，输出指定线路四个季度的折扣和全价voidf_money2(FILE*fp){ intBcity,Ecity;//起始成市号码和终点城市号码intl; int h=1; floatmoney[4]; inti,j;floats,w;floatdiscount[4];do{ pri();//输出城市列表及相应代码。 printf("请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--%d)",c_number); scanf("%d",&Bcity); scanf("%d",&Ecity);//输入起始城市和终点城市的代码。 if(!((0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity)) { printf("\n出错啦!!!\n");//输入出错 exit(1); } Floyed(CreateCostF(0,fp));//调用Floyed函数。 if(B[Bcity][Ecity]>5000){ printf("无直飞航班\n"); } else{ printf("季度全票价格折扣折后价格〔不计小数，四舍五入〕\n"); srand((unsigned)time(NULL));//随机种子for(j=0;j<4;j++) {for(i=0;i<100;i++) { if(!(i%10))w=rand()%80+20;s=w/100; break; }discount[j]=s; } for(i=0;i<4;i++) {money[i]=(float)discount[i]*B[Bcity][Ecity]; printf("%d%d%.2lf%.lf\n",i+1,B[Bcity][Ecity],discount[i],money[i]); } } printf("\n\n1.继续输入起始城市和目的城市名称，输出指定线路四个季度的折扣和全价\n2.返回主菜单\n清选择..."); scanf("%d",&l);//输入1或2选择是否继续 h=l; }while(h==1);printf("\n");}//输入月份、起始城市和目的城市名称，输出最正确方案voidf_money3(FILE*fp){ intBcity,Ecity;//起始成市号码和终点城市号码intl; int h=1; floatmoney; inti,j;floats,w;floatdiscount[4]; floatm; intmonth; intquarter;do{printf("请输入月份(请在1-12之间选择)："); scanf("%d",&month); if(month>=12||month<=1) {printf("输入出错！\n"); exit(1); } pri();//输出城市列表及相应代码。 printf("请输入起始城市和目的城市的代码，中间以空格隔开，范围(1--%d)",c_number); scanf("%d",&Bcity); scanf("%d",&Ecity);//输入起始城市和终点城市的代码。 if(!((0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity)) { printf("\n出错啦!!!\n");//输入出错 exit(1);//关闭所有文件，终止正在执行的程序 } Floyed(CreateCostF(0,fp));//调用Floyed函数。 if(B[Bcity][Ecity]>5000) { printf("无航班\n"); } else{ srand((unsigned)time(NULL));//随机种子for(j=0;j<4;j++) {for(i=0;i<100;i++) { if(!(i%10))w=rand()%80+20;s=w/100; break; }discount[j]=s; } if(1<=month<=3) { m=discount[0]; quarter=1; printf("你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m); } elseif(4<=month<=6) { m=discount[1]; quarter=2; printf("你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m); } elseif(7<=month<=9) { m=discount[2]; quarter=3; printf("你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m); } elseif(10<=month<=12) { m=discount[3]; quarter=4; printf("你选择的是%d月，位于第%d季度,折扣是%.2lf\n",month,quarter,m); }money=(float)m*B[Bcity][Ecity]; printf("最正确线路："); pr(Bcity,0);//显示起始城市 prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市 pr(Ecity,0);//显示终点城市 printf("合计："); printf("%.lf\n",money); } printf("\n\n1.继续输入月份、起始城市和目的城市名称，输出最正确方案\n2.返回主菜单\n清选择..."); scanf("%d",&l);//输入1或2选择是否继续。 h=l; }while(h==1);