交通咨询系统数据结构c语言(共16页).doc

精选优质文档-倾情为你奉上数 据 结 构 课 程 设 计交通咨询系统设计学 生 姓 名： 学 号： 指 导 教 师： 完 成 日 期： 专心-专注-专业目 录1 设计任务书1.1 题目与要求题目：编写程序实现交通咨询系统设计的模拟。要求：（1）建立交通网络网的存储结构； （2）总体设计要画流程图； （3）提供程序测试方案；（4）界面友好。1.2 知识点本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点。1.3 输入输出分析（1）普通输入对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。 （2）对话式输入在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。（3）程序输出对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()函数输出各个城市的代码城市名字对照表，用户可以更方便的使用。对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观。1.4 实现的功能在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。2 概要设计2.1 结构体类型及函数声明（1）结构体路径图结构体类型 MGraph 花费图结构体类型 HGraph （2）函数声明void pri() /输出城市代号对照表函数。void CreateMGraph(MGraph *G) /创建路径图函数，路径图存放于G中。void CreateHGraph(HGraph *H) /创建花费图函数，花费图存放于H中。void Dijkstra(MGraph *G, int v1,int n) /迪杰斯特拉算法求单源最短路径函数，v1为源点，n为城市个数，这个图存放于G中。void Floyd(MGraph *G, int n) /弗洛伊德求两点间最短路径函数，n表示城市个数，这个图存放于G中。void Floyd1(HGraph *H, int n) /弗洛伊德求两点间最小花费函数，n表示城市个数，这个图存放于H中。2.2 主程序流程（1）主程序调用模块图主程序利用switch()语句实现各个模块的调用，主函数调用如图2-1所示。 主程序根据不同值主调函数0退出1求单源最短路径2求两点间最短路径3求两点间最小花费图2-1 主程序调用模块图3 详细设计3.1 数据类型实现 （1）路径图结构体类型 Vertextype vexsMVNum; /顶点数组，顶点表示城市代号 Adjmatrix arcsMVNum MVNum; /邻接矩阵定义路径图 MGraph;（2）花费图结构体类型typedef struct Vertextype vexsMVNum; /顶点数组，顶点表示城市代号Adjmatrix arcsMVNum MVNum; /邻接矩阵定义花费图 HGraph;3.2 程序代码 #include<stdio.h> #include<stdlib.h> #define MVNum 100 /最大顶点数 #define Maxint 65535 /定义一个最大数，其意义为无穷大enum booleanFALSE,TRUE; typedef char Vertextype; typedef int Adjmatrix; typedef struct Vertextype vexsMVNum; /顶点数组 类型假定为char型 Adjmatrix arcsMVNum MVNum; / 邻接矩阵 假定为int型 MGraph; typedef struct Vertextype vexsMVNum; /顶点数组 类型假定为char型 Adjmatrix arcsMVNum MVNum; / 邻接矩阵 假定为int型 HGraph; int D1MVNum, p1MVNum; int DMVNumMVNum,pMVNumMVNum; void pr(int i)switch(i)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;case 11:printf("株洲 ");break;case 12:printf("贵阳 ");break; case 13:printf("昆明 ");break;case 14:printf("广州 ");break;void pri()int i;printf("城市代号对照表n");printf("*");for(i=1;i<=14;i+)printf("%d.",i); pr(i); pr(i);printf("n"); printf("*");void CreateMGraph(MGraph *G) /采用邻接矩阵表示法构造有向图G，此图为带权距离图 int i,j; for(i=1;i<=14;i+) /输入顶点信息 G->vexsi=(char)i; for(i=1;i<=14;i+) for(j=1;j<=14;j+) G->arcsij=Maxint; / 初始化邻接矩阵 G->arcs12=G->arcs21=137; G->arcs24=G->arcs42=674; G->arcs13=G->arcs31=695; G->arcs34=G->arcs43=349;G->arcs35=G->arcs53=511; G->arcs56=G->arcs65=842;G->arcs37=G->arcs73=534; G->arcs48=G->arcs84=651;G->arcs613=G->arcs136=1100; G->arcs612=G->arcs126=967;G->arcs711=G->arcs117=409; G->arcs810=G->arcs108=825;G->arcs910=G->arcs109=622; G->arcs1011=G->arcs1110=367;G->arcs1112=G->arcs1211=902;G->arcs1213=G->arcs1312=639; G->arcs1114=G->arcs1411=675; void CreateHGraph(HGraph *H) /采用邻接矩阵表示法构造有向图H,此图为带权花费图 int i,j; for(i=1;i<=14;i+) /输入顶点信息 H->vexsi=(char)i; for(i=1;i<=14;i+) for(j=1;j<=14;j+) H->arcsij=Maxint; / 初始化邻接矩阵 H->arcs12=H->arcs21=20; H->arcs24=H->arcs42=93; H->arcs13=H->arcs31=93; H->arcs34=H->arcs43=51;H->arcs35=H->arcs53=72; H->arcs56=H->arcs65=112;H->arcs37=H->arcs73=75; H->arcs48=H->arcs84=91;H->arcs613=H->arcs136=141; H->arcs612=H->arcs126=128;H->arcs711=H->arcs117=62; H->arcs810=H->arcs108=105;H->arcs910=H->arcs109=86; H->arcs1011=H->arcs1110=53;H->arcs1112=H->arcs1211=115;H->arcs1213=H->arcs1312=86; H->arcs1114=H->arcs1411=91; /以下是迪杰斯特拉算法void Dijkstra(MGraph *G, int v1,int n) /用Dijkstra算法求有向网G的v1顶点到其他顶点v的最短路径Pv及其权Dv /设G是有向图的邻接矩阵，若边<i,j>不存在则Gij=Maxint /Sv为真当且仅当v属于S,即已经求得从v1到v的最短路径 int DMVNum, P2MVNum; int v,i,w,min; enum boolean SMVNum; for(v=1;v<=n;v+) / 初始化S和D Sv=FALSE; /置空最短路径终点集 Dv=G->arcsv1v; /置初始的最短路径值 if(Dv< Maxint) P2v=v1; /v1是前趋双亲else P2v=0; /v 无前趋 / End_for Dv1=0;Sv1=TRUE; /S集初始时只有源点 源点到源点的距离为0 /开始循环每次求的V1到某个V顶点的最短路径并加V到S集中 for(i=2;i<=n;i+)/其余n-1个顶点min=Maxint; / 当前所知离v1顶点的最近距离设初值为 for(w=1;w<=n;w+) /对所有顶点检查 if(!Sw && Dw<min) /找离v1最近的顶点w并将其赋给v距离赋给min v=w; /在S集之外的离v1最近的顶点序号 min=Dw; /最近的距离 /W顶点距离V1顶点更近 Sv=TRUE; /将v并入S集 for(w=1;w<=n;w+) /更新当前最短路径及距离 if(!Sw&&(Dv+G->arcsvw<Dw) /修改D2w和p2w w 属于 V-S Dw=Dv+G->arcsvw; /更新D2w P2w=v; /End_if /End_for printf ("路径长度（单位：km） 最短路径n"); for(i=1;i<=n;i+) printf ("%10d", Di); printf ("%13d", i);v=P2i; while(v!=0) printf ("<-%d", v); v=P2v; printf("n"); printf("nn"); /以下是弗洛伊德求最短路径算法void Floyd(MGraph *G, int n) /用Floyd算法求有向网G中各对顶点i和j之间的最短路径int i, j, k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(G->arcsij!=Maxint) pij=j; /j是i的后继 else pij=0; Dij=G->arcsij; for(k=1;k<=n;k+) for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改长度 pij=pik; void Floyd1(HGraph *H, int n) /用Floyd算法求有向网H中各对顶点i和j之间的最小花费int i, j, k; for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(H->arcsij!=Maxint) pij=j; /j是i的后继 else pij=0; Dij=H->arcsij; for(k=1;k<=n;k+) for(i=1;i<=n;i+) for(j=1;j<=n;j+) if(Dik+Dkj<Dij) Dij=Dik+Dkj; /修改长度 pij=pik; void main() MGraph * G; HGraph * H;int v, w, k; int xz=1; G=(MGraph *)malloc(sizeof(MGraph); H=(HGraph *)malloc(sizeof(HGraph);CreateMGraph(G); /建立图的存储结构 CreateHGraph(H); printf("*n");printf("* 姓名： *n");printf("* 学号： *n"); printf("*nnn");while(xz!=0) printf("*求城市之间的最短路径*n"); printf("*n"); printf("0.退出n");printf("1.求一个城市到所有城市的最短路径n"); printf("2.求任意的两个城市之间的最短路径n"); printf("3.求任意的两个城市之间的最小花费n");printf("*n"); scanf("%d",&xz); switch(xz)case 1: pri();printf("请输入城市起点代号："); scanf("%d", &v); Dijkstra(G,v,14); /调用迪杰斯特拉算法 break;case 2: pri(); Floyd(G,14); /调用费洛伊德求最短路径算法 printf("输入城市起点代号和终点代号："); scanf("%d%d",&v,&w ); k=pvw; /k为起点v的后继顶点 if(k=0) printf("顶点%d 到 %d 无路径! n",v,w); else printf("从顶点%d到%d的最短路径是: %d",v,w,v); while(k!=w) printf("->%d",k); /输出后继顶点 k=pkw; /继续找下一个后继顶点 printf("->%d",w); / 输出终点w printf(" 路径长度:%dnnn",Dvw); break; case 3: pri(); Floyd1(H,14); /调用费洛伊德求最小花费算法 printf("输入城市起点代号和终点代号："); scanf("%d%d",&v,&w ); k=pvw; /k为起点v的后继顶点 if(k=0) printf("顶点%d 到 %d 无路径! n",v,w); else printf("从顶点%d到%d的路径是: %d",v,w,v); while(k!=w) printf("->%d",k); /输出后继顶点 k=pkw; /继续找下一个后继顶点 printf("->%d",w); / 输出终点w printf("n最小花费（单位：元）：%dnnn",Dvw); break;4 调试分析4.1 问题分析与回顾问题1：求单源最短路径时，两点间无路径时程序出错。分析 对于边的初始化出错，我在程序开始的地方定义了一个最大数Maxint =65535表示无穷大，初始化邻接矩阵时，添加了一句“G->arcsij=Maxint;”。问题2：求两点间最短路径时，程序运行时不能给出最短路径。分析：Floyd函数里修改长度时少写了一层循环，加上之后就好了。问题3：输出城市代码对照表时出错。分析：pri函数中调用pr函数时，pr函数应写到循环里边，我写到了循环外边。4.2 算法时空分析（1）迪杰斯特拉求单源最短路径的算法：对于n个顶点，每次求的V1到某个V顶点的最短路径时，第一个for循环的时间复杂度是O(n),内层for循环的时间复杂度是O(n),所以总的时间复杂度是O（n2）。（2）弗洛伊德求两点间最短路径的算法：对于n个顶点，循环求最短路径是，第一个for循环时间复杂度是O（n），内层又有两个for循环，其时间复杂度是O（n2），所以总的时间复杂度是O（n3）。（3）弗洛伊德求两点间最小花费的算法：对于n个顶点，此算法和求两点间最短路径算法时间复杂度一样，也是O（n3）。4.3 算法改进在这个交通咨询系统中，创建图时，我是在程序里对图进行了初始化，赋予了一定的权值，这样不利于图的更新和再创建，系统功能还不是很完善。求两点间最短路径和最小花费都用到了弗洛伊德算法，由于我编程的经验不足，对函数参数传递理解的还不够透彻，所以用了两次弗洛伊德算法，这一点上还有待改进。 4.4 经验和体会经过这些天的设计，这个交通咨询系统已经实现。这个设计可以实现用户输入指令，系统进行相应的查询功能。学习数据结构对我后继学习其它课程也有很大的帮助，因为运用数据结构可以编出更“好”的程序。以前学习C语言时，只会编写简单的小程序，对于那些大点的程序，如果不用数据结构，程序就会显得臃肿、杂乱无章。以前只是一味的编程，学了数据结构之后，我明白了程序中的各个部分在计算机中是怎么存储的，明白了怎么编写程序可以降低程序的时空复杂度让程序看起来更有条理。 此次课程设计，给我提供了一个既动手又动脑，独立实践的机会。我回顾了C语言编程的方法和编程的思想，并运用数据结构的知识使程序的时空复杂度都有所降低。这次课程设计让我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路径的问题，而且在编程的过程中，更加锻炼了我的思维模式，让自己的思维更有条理，写出的程序也更简单明了。课程设计中，我将学到的知识融会贯通，同时提高调试程序的能力，养成良好的编程习惯，并增强对程序整体设计的把握，理论与实践相结合。通过此次课程设计，让我明白了数据结构的重要性，同时也提高了我分析问题、解决问题的能力。我会再接再厉，编写出更好的程序。5 测试结果（1） 系统运行首页面如图5-1所示：图5-1 系统首页图（2） 选择“1”，系统会给出城市代号对照表并提示用户输入城市起点代号，运行截图如图5-2所示：图5-2 选择“1”功能运行图（3） 输入城市代号“1”，系统会给出“1”到所有城市的最短路径以及路径长度，运行截图如图5-3所示：图5-3 求单源最短路径输出图（4） 选择功能“2”，并输入城市起点和终点代号“1”和“4”，系统会给出最短路径和最短路径长度，运行截图如图5-4所示：图5-4 求两点间最短路径输出图（5） 选择功能“3”，并输入城市起点和终点代号“3”和“7”，系统会给出最小花费和相应的路径，运行截图如图5-5所示：图5-5 求两点间最小花费输出图参考文献1 严蔚敏，吴伟民数据结构（C语言版）M北京：清华大学出版社，20102 蒋清明，向德生 C语言程序设计M北京：人民邮电出版社，20083 尹德淳，龙脉工作室C函数速查手册M北京：人民邮电出版社，20094 李玲玲C程序设计M北京：清华大学出版社，20115 陈雁数据结构M北京：高等教育出版社，20046 张磊C程序设计教程M北京：中国铁道出版社，20077 严蔚敏，米宁数据结构习题集M北京：清华大学出版社，2009年8 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，2008年9 谭浩强C程序设计M北京：清华大学出版社，200810 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003年数据结构课程设计评分标准学号 姓名得分程序运行情况（占总成绩20%） 能正确运行 基本能正确运行 能运行但结果不完善程序功能的完善程度（占总成绩15%）  完善 基本完善 不完善程序结构的合理性（占总成绩15%）  合理 基本合理 不太合理数据结构的合理性（占总成绩25%） 正确应用并有创新 正确应用 基本正确应用学生的工作态度与独立工作能力（占总成绩10%） 工作态度认真能独立完成任务 工作态度认真但独立性较差 工作态度基本认真但缺乏独立性设计报告的规范性（占总成绩15%）  符合规范 基本符合规范 规范性较差成绩等级总分指导老师签字时间优秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分