应用数据结构课设最短航空路线求解报告

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

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

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

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

5、2.查看城市3.最低费用查询4.最短时间查询5.添加城市6.飞机花费编辑2. 概要设计1.数据结构本程序运用了关于图这种数据结构，它的抽象数据类型定义如下：typedef struct unDiGraph int numVerts; /结点 costAdj cost; /邻接矩阵unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作结果：构造带权(费用)图。unDiGraph* CreateTimeG()操作结果：构造带权（时间）图。PathMat *Floyed(unDiGraph *D)操作结果：Floyed函数 求任意两点的最短路径。2主程序流程Ma

6、in函数查看城市pri()选择折扣year_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

7、.选择飞机最短时间路线 3.选择飞机最节约费用路线4.管理员程序确 5.退出本程序3 程序的模块为#include <windows.h>#include <stdio.h> # include <stdlib.h># include <time.h> #define INF 65535 /定义一个最大数定为无穷值#define MAX 23typedef int costAdjMAX+1MAX+1;/图邻接矩阵从1开始记数int PathMAX+1MAX+1;/图邻接矩阵从1开始记数typedef struct unDiGraphint num

8、Verts; /结点costAdj cost; /邻接矩阵unDiGraph,*UNG; /图的定义costAdj B,L;void pr(int i)/选择城市void pri()/输出城市unDiGraph *CreateCostG()/构造带权(费用)图 返回首地址G：unDiGraph *CreateTimeG()/构造带权(时间)图 返回首地址G：unDiGraph *CreateFlyG()/飞机的相关信息void Floyed(unDiGraph *D,unDiGraph *M) /Floyed函数 求任意两点的最短路径：void prn_pass(int i,int j) /为

9、了求从i到j的最短路径，只需要调用如下的过程voidf_ time()/求最少时间路径。void f_money()/求最少花费路径void administrator()/管理员功能void main()/main函数2.伪码算法（1）pr() 选择城市begin0=>hIf j=0 then h=iElse if j=1 input addi.aSwitch 条件选择 print 城市名End（2）pri() 输出城市beginPrint 城市代码1=>iWhile i<=c_number Print i调用pr()函数End(3) CreateTimeF()飞机的时间的

10、存贮和编辑功能函数Begin0=>a,0=>b,1=>hG=(unDiGraph *)malloc(sizeof(unDiGraph)If !G then NULL1=>iWhile i<c_number+1 While j <c_number+1 INF=> G->costij 初始化使G->costij为无穷。c_number =>G->numVerts 为各条航线赋权值（时间值）if (o) then while(h=1) t+1=>t调用pri()函数print飞机时间编辑print请输入开始城市的代码input

11、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(

12、unDiGraph *D,unDiGraph *M) 函数 Floyed函数求任意两点的最短路径Beginc_number=>n1=>iwhile(i<=n)1=>jwhile(j<=n) D->costij=>Aij 初始化矩阵A。M->costij=>Cij-1=>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+Akj<Aij)then Aik+Akj =>Aij

13、Cik+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,int j) 输出最短路径所经过的点Begin If ( Pathij!=-1)递归调用prn_pass(i,Pathij)调用pr(Pathij,0)End(6) f_time(int m) 飞机最短时间路径函数Begin1=>hwhile(h=1) print请输入起始城市和目的城市的代码，中间以空格隔开，范

14、围(1- %d)",c_numberinput Bcityinput Ecity 输入起始城市和终点城市的代码。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) then print出错啦! Floyed(CreateTimeF(0),CreateCostF(0) 调用Floyed函数。 pr(Bcity,0) 显示起始城市。 prn_pass(Bcity,Ecity) 调用prn_pass函

15、数，显示最短路径经过的城市。 pr(Ecity,0) 显示终点城市。 if (BBcityEcity>5000|LBcityEcity>10000)then print两地间还没有线路通过else (float)m/10*LBcityEcity=> moneyPrint“打折前的费用是%d元n",LBcityEcityPrint "飞机花的费用是%d元n",(int)money Print "飞机花的最短时间是%d小时n",BBcityEcity Print 1.继续最少花费查找n 2.返回主菜单n 清选择. input l

16、输入1或2选择是否继续。 1=>h End(7) year_month()函数 选择折扣Begin srand(unsigned)time(NULL) 随机种子调用 pri() 输出城市列表及相应代码。 print请输入年份: input year for(i=1;i<=12;i+) rand()%(10-3+1)+3=>discounti-1 产生310之间的随机数 print "%2d月的折扣是: ",i printf "%2d折n",discounti-1 Print 请选择月份.(请在1-12之间选择) Input month

17、if(1<=month<=12) then print "你选择的是%d月，折扣是%dn",month,discountmonth-1 else print 输入出错，请重新输入！ return discountmonth-1End4. 调试分析1.问题与解决办法（1）scanf("%s",&addi.a) 和printf("%s ",addi-10.a)在编写程序阶段，我最开始编写这两个函数的时候是scanf("%c",&addi.a) printf("%c ",a

18、ddi-10.a) ，当时没有看清addi.a最初的定义，它其实是一个字符数组，所以在运行的时候老出错，后面慢慢研究和调试才知道在输入和输出的格式占位符应该用%s.(2)printf 中中文与变量一起输出的例子例如printf("请输入起始城市和目的城市的代码，中间以空格隔开，范围(1-"%d")", c_number);我在调试的时候，系统一直报错，当时我看了半天都没看出错误在哪，后来通过网上查阅资料，请教学长和不断地调试验证，终于知道%d之间的引号应该去掉，因为printf的第一个参数是一个字符串 。（3）声明变量语句的位置我在运行的过程中

19、一直出现这个错误（见下图），系统报错说未定义变量，但我确实定义过了，后来请教高年级的学长才知道要把声明变量的语句得放到函数的最前面，而printf要放在 所有变量声明语句后面。修改程序之后，那些错误果然没有了。（4）随机函数的编写因为我们使用随机函数的次数很少，所以对其不时很了解。刚开始的时候都不会写，后来在网上找实例，才知道其用法# include <stdlib.h># include <time.h> /*需引用的头文件*/srand(unsigned)time(NULL); /*随机种子*/n=rand()%(x-y+1)+y; /*产生yx之间的随机

20、数*/然后我就借用此函数构造了随机打折的函数，但是在构造的过程中，我又忽略了一个问题，那就是随机函数只能产生整数随机数，我最开始的目的是构造0.31之间的随机数，所以定义的变量时float型，后来运行不通过，仔细思考之后才知道该随机函数只能产生310之间的数，修改变量定义之后就可以运行成功了。2.时间复杂度1.构造带权图CreateFlyG CreateCostG和CreateTimeG：T(MAX)=O(MAX)2)2. Floyed函数 Floyed : T(n)=O(n2+n3)3.显示路径函数 prn_pass : T(n)=O(n)3.空间复杂度 本程序的空间复杂度均为S(n)=(n

21、2); 即存放n2个节点数据辅助空间。4.经验和体会自学习C语言以来，我们就没怎么练习上机实践能力，所以对于代码的敏感度不够，一个错误出现了，不是很容易发现。在这次课程设计中，我就犯了很多高手认为很基础的错误，比如说：printf函数的用法，变量声明的位置，还有就是指针数组的用法。犯错误是不可避免的，但是我们要认真地去发现错误和修改错误。我在运行后，知道自己的程序有错误，我首先一步一步慢慢看，慢慢分析，在整个程序中找不出来就将该部分分离出去进行测试，这样，就很容易找到问题所在了。当然请教别人也是一个学习的方法，如果自己很长时间也找不出错误，何不请教高年级的学长呢。在这次的课程设计中，我也请教过

22、大三的学长还有老师，虽然他们只是给了提示，但真的是我懂了不少。5. 用户使用说明运行程序，用户会看到该程序的主界面。由用户输入数字，选择相应的操作。1.查看城市 输出所有的城市及其代码。2.选择最短时间路线输出所有的城市及其代码请输入年份输出每月对应的折扣 请选择月份.(请在1-12之间选择)请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- %d) 输出最短路径和飞机最短时间及花费3. 选择最低花费路线输出所有的城市及其代码请输入年份输出每月对应的折扣 请选择月份.(请在1-12之间选择)请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- %d) 输出最短路径和飞机最低花费及

23、时间4. 管理员程序 输出管理员程序子菜单 请选择 （1）增加城市 请输入要增加的个数 请输入你要增加的城市名 城市增加完毕 （2）添加或编辑飞机费用 输出所有的城市及其代码 飞机花费编辑 请输入开始和结尾城市代码 请输入两地花费 （3）添加或编辑飞机时间 输出所有的城市及其代码 飞机时间编辑 请输入开始和结尾城市代码 请输入两地时间 （4）返回主菜单5.退出程序6. 测试结果1.开始界面2.查看城市（这是原始存储的城市）3.最短时间查询。以输入年份2009为例，选择1月，对应的折扣是4折，起始城市是1，目的城市是2最短路径是 成都 西安 打折前的费用是840元，打折后336元，最短时间是2个

24、小时4.选择2，返回主菜单，选择3.选择最节约费用路线，以输入2010年为例，对应的折扣如下图，选择2月份，折扣是6折，起始城市是1，目的城市是2，最短路径是 成都 西安 打折前的费用是840元，打折后的最少费用是336元，花费的时间是2小时。5.返回主菜单，4.添加城市。界面如下。6.添加或编辑飞机费用7.添加城市后，进行最少费用查询7. 附录#include <windows.h>#include <stdio.h> # include <stdlib.h># include <time.h> /*需引用的头文件*/#define INF 6

25、5535 /定义一个最大数定为无穷值#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 unDiGraphint numVerts; /结点costAdj cost; /邻接矩阵unDiGraph,*

26、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;

27、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) : pr

28、intf("徐州 ");break;default: printf("%s ",addi-10.a);return 1;/输出城市列表及相应代码void pri()int i; printf(" 城市及其代码 nnn"); printf("*n"); for (i=1;i<=c_number;i+)printf("%d",i);printf(".");pr(i,0);printf("n");printf("*nnnnnn");/构

29、造带权(时间)图 返回首地址G：unDiGraph *CreateTimeF(int o)/飞机的时间的存贮和编辑功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;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->costij=INF;/初始化使G->costij为无穷。G->numVerts=c_number;G->cost16=G->

30、;cost61=3;G->cost12=G->cost21=2;G->cost23=G->cost32=1;G->cost34=G->cost43=2;G->cost45=G->cost54=4;G->cost56=G->cost65=3;G->cost37=G->cost73=6;G->cost78=G->cost87=1;G->cost810=G->cost108=2;G->cost310=G->cost103=3;G->cost910=G->cost109=6;G-&g

31、t;cost95=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;prin

32、tf("请选择n");printf("*n");printf("1：继续更改城市时间n");printf("0:返回上一级菜单n");printf("*n");scanf("%d",&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

33、;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);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF; /初始化使G->costij为无穷。G->numVerts=c_number;G->cost16=G->

34、cost61=960;G->cost12=G->cost21=840;G->cost23=G->cost32=501;G->cost34=G->cost43=530;G->cost45=G->cost54=400;G->cost56=G->cost65=900;G->cost37=G->cost73=690;G->cost78=G->cost87=310;G->cost810=G->cost108=670;G->cost310=G->cost103=340;G->cost910=G

35、->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

36、_cost=a;xr.f_cost=b;printf("请选择n");printf("*n");printf("1：继续更改城市费用n");printf("0:返回上一级菜单n");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_cos

37、txr+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;i<=n;i+) for(j=1;j<=n;j+)Aij=D->costij;/初始化矩阵A。 Cij=M->costij; Pathij=-1; /初始化矩阵p, 置-1. for(k=1;k<=n;k+) /k为逐步加入的中间结点 for(i=1;i<=n;i+) /i为A

38、中行号for(j=1;j<=n;j+)if(Aik+Akj<Aij)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(i,Pathij);/输出最短路径经过的所有点 pr(Pathij,

39、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 (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecit

40、y&&Ecity<c_number+1)&&Bcity!=Ecity) printf("n出错啦! n"); Floyed(CreateTimeF(0),CreateCostF(0);/调用Floyed函数。pr(Bcity,0);/ 显示起始城市。 prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>10000) printf("两地间还没有线路通过n")

41、;else money=(float)m/10*LBcityEcity;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&qu

42、ot;);/求最少花费路径。void f_money(int m) int Bcity,Ecity;/起始成市号码和终点城市号码 int l;inth=1;float money;/*unDiGraph *G;*/do printf("请输入起始城市和目的城市的代码，中间以空格隔开，范围(1- %d)",c_number); scanf("%d",&Bcity); scanf("%d",&Ecity);/输入起始城市和终点城市的代码。if (!(0<Bcity&&Bcity<c_number

43、+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) printf("n出错啦! n"); /输入出错Floyed(CreateCostF(0),CreateTimeF(0);/调用Floyed函数。pr(Bcity,0);/显示起始城市。prn_pass(Bcity,Ecity);/调用prn_pass函数，显示最短路径经过的城市。pr(Ecity,0);/显示终点城市。if (BBcityEcity>5000|LBcityEcity>10000) print

44、f("两地间还没有线路通过n");else money=(float)m/10*BBcityEcity;printf("打折前的费用是%d元n",BBcityEcity);printf("飞机花的最少费用是%d元n",(int)money); printf("飞机花的时间是%d小时n",LBcityEcity); printf("nn 1.继续最少花费查找n 2.返回主菜单n 清选择."); scanf("%d",&l); /输入1或2选择是否继续。 h=l; whi

45、le(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;i<=12;i+) discounti-1=rand()%(10-3+1)+3; /*产生310之间的随机数*/ printf("%2d月的折扣是:

46、",i); printf("%2d折n",discounti-1); printf("请选择月份.(请在1-12之间选择) "); scanf("%d",&month); if(1<=month<=12) printf("你选择的是%d月，折扣是%dn",month,discountmonth-1); else printf("输入出错，请重新输入！"); return discountmonth-1;void add_city()/对城市的增加static int

47、 i=1;int 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