数 据 结 构 课 程 设 计
交通咨询系统设计
学 生 姓 名： 学 号： 指 导 教 师： 完 成 日 期：
目 录
1 设计任务书.................................................................................................................. 1
1.1 题目与要求....................................................................................................... 1 1.2 知识点............................................................................................................... 1 1.3 输入输出分析................................................................................................... 1 1.4 实现的功能....................................................................................................... 1 2 概要设计...................................................................................................................... 2
2.1 结构体类型及函数声明................................................................................... 2 2。2 主程序流程.................................................................................................... 2 3 详细设计...................................................................................................................... 3
3。1 数据类型实现................................................................................................ 3 3。2 程序代码........................................................................................................ 3 4 调试分析.................................................................................................................... 11
4。1 问题分析与回顾.......................................................................................... 11 4。2 算法时空分析.............................................................................................. 11 4。3 算法改进...................................................................................................... 11 4.4 经验和体会..................................................................................................... 12 5 测试结果.................................................................................................................... 12 参考文献.......................................................................................................................... 14
1 设计任务书
1。1 题目与要求
题目：编写程序实现交通咨询系统设计的模拟。 要求：（1）建立交通网络网的存储结构; （2)总体设计要画流程图； （3）提供程序测试方案;
（4）界面友好。
1.2 知识点
本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点.
1.3 输入输出分析
（1)普通输入
对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。
（2）对话式输入
在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。
（3）程序输出
对于用户查询结果的展示,考虑美观以及方便用户的因素，我写了一个pri(）函数输出各个城市的代码城市名字对照表,用户可以更方便的使用.对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观.
1.4 实现的功能
在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。
1
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 主程序调用模块图
2
3 详细设计
3。1 数据类型实现
（1）路径图结构体类型 ｛
Vertextype vexs[MVNum]； //顶点数组，顶点表示城市代号 Adjmatrix arcs［MVNum］ ［MVNum]； //邻接矩阵定义路径图
｝MGraph;
(2）花费图结构体类型 typedef struct ｛
Vertextype vexs[MVNum］; //顶点数组,顶点表示城市代号 Adjmatrix arcs[MVNum］ ［MVNum］； //邻接矩阵定义花费图
｝HGraph;
3。2 程序代码
＃include ＃define MVNum 100 //最大顶点数 ＃define Maxint 65535 //定义一个最大数，其意义为无穷大 enum boolean{FALSE,TRUE}; typedef char Vertextype； typedef int Adjmatrix; typedef struct ｛ Vertextype vexs［MVNum］; //顶点数组 类型假定为char型 Adjmatrix arcs[MVNum］ [MVNum]； // 邻接矩阵 假定为int型 }MGraph； typedef struct { Vertextype vexs［MVNum］; //顶点数组 类型假定为char型 Adjmatrix arcs［MVNum] [MVNum]; // 邻接矩阵 假定为int型 ｝HGraph； int D1[MVNum], p1［MVNum］; int D[MVNum］[MVNum］，p[MVNum]［MVNum］； 3 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 8:printf(”上海 ”）；break; case 9：printf(”福州 ”)；break; case 11：printf（”株洲 ”）；break； case 12:printf（\"贵阳 ”);break; case 14:printf（”广州 \"）；break； case 7:printf(\"武汉 \"）；break； case 10：printf(”南昌 \");break; case 13：printf（\"昆明 \"）;break; } } void pri() { int i; printf（\"城市代号对照表\\n\"）; printf(”*＊＊**＊**＊＊*＊*＊＊＊＊**＊＊**＊*＊＊*＊＊***＊＊＊＊*＊＊*＊＊*＊for(i=1；i<=14；i++） { ｝ printf（”\\n”）; printf(\"%d.\"，i）; ＊***＊＊*****＊*＊*＊＊＊*＊＊**＊＊＊**＊**＊＊*＊\"）; pr（i)； pr(i）； printf(\"*＊＊*****＊＊*＊＊*＊＊*＊＊＊*＊＊**＊****＊＊*＊**＊*＊*＊＊*＊*******＊＊*＊＊＊****＊＊**＊＊*＊＊**＊*＊＊＊*＊*”）; } void CreateMGraph(MGraph *G) ｛ //采用邻接矩阵表示法构造有向图G，此图为带权距离图 int i，j; 4 for(i=1；i〈=14；i++） //输入顶点信息 ｛ ｝ G—>arcs[1］[2］=G—〉arcs[2][1］=137; for(j=1；j<=14；j++) { ｝ G->arcs［i］［j]=Maxint; // 初始化邻接矩阵 G-〉vexs［i]=(char）i； for(i=1；i〈=14；i++) G—〉arcs［2]［4]=G->arcs[4］［2］=674； G—>arcs［1][3］=G-〉arcs［3］［1］=695； G—〉arcs[3]［4］=G—>arcs［4][3］=349； } void CreateHGraph（HGraph *H） ｛ //采用邻接矩阵表示法构造有向图H，此图为带权花费图 int i,j； for(i=1；i<=14；i++） //输入顶点信息 { H—〉vexs[i］=（char)i； for(i=1;i〈=14；i++） for(j=1;j<=14;j++) ｛ ｝ 5 G->arcs［3］[5]=G—〉arcs[5］［3]=511； G—>arcs[3］［7]=G-〉arcs[7］[3]=534； G—>arcs[6]［13]=G—>arcs[13][6]=1100; G-〉arcs[7］[11]=G->arcs［11]［7]=409; G—〉arcs[9]［10］=G->arcs[10]［9］=622; G—>arcs［11][12］=G—〉arcs[12］［11]=902; G-〉arcs［12］［13］=G->arcs[13][12］=639; G->arcs［5][6］=G—>arcs［6]［5]=842； G—〉arcs[4］[8]=G—〉arcs[8]［4]=651； G-〉arcs［6][12]=G—>arcs［12]［6]=967； G-〉arcs［8][10]=G—>arcs［10］［8]=825; G—〉arcs[10][11］=G-〉arcs[11］［10］=367； G->arcs［11］[14]=G—>arcs［14］[11］=675； H-〉arcs［i］[j］=Maxint； // 初始化邻接矩阵 ｝ H—〉arcs[1］[2］=H->arcs［2］［1］=20； H-〉arcs［2］［4]=H-〉arcs［4][2]=93； H->arcs[1］［3]=H->arcs［3］［1]=93; H—>arcs［3][4]=H—〉arcs[4]［3］=51； H—>arcs［3］［5］=H—〉arcs［5]［3］=72； H—>arcs[3］［7]=H—〉arcs［7][3]=75; H—>arcs[6]［13]=H—〉arcs［13]［6]=141； H-〉arcs[7][11］=H-〉arcs[11]［7]=62; H—>arcs［9]［10]=H-〉arcs［10]［9]=86; H-〉arcs[11]［12］=H->arcs[12］［11］=115; H—〉arcs［12][13］=H-〉arcs［13］[12］=86； H—〉arcs［5］[6]=H—〉arcs[6]［5］=112； H->arcs[4］［8］=H-〉arcs[8]［4］=91; H—〉arcs[6］[12]=H—>arcs[12］[6］=128； H—〉arcs［8］［10］=H->arcs[10］［8］=105； H—〉arcs［10］[11]=H—〉arcs[11］［10］=53； H->arcs［11］[14］=H-〉arcs［14］[11］=91； ｝ //以下是迪杰斯特拉算法 void Dijkstra(MGraph ＊G， int v1,int n) { //用Dijkstra算法求有向网G的v1顶点到其他顶点v的最短路径P［v］及其权D[v] //设G是有向图的邻接矩阵，若边〈i，j〉不存在则G[i］[j］=Maxint //S[v]为真当且仅当v属于S，即已经求得从v1到v的最短路径 int D［MVNum]， P2[MVNum]； int v，i,w，min； enum boolean S[MVNum］； for（v=1；v〈=n;v++) { // 初始化S和D S［v］=FALSE; //置空最短路径终点集 D［v]=G->arcs［v1]［v］； //置初始的最短路径值 if(D[v]〈 Maxint) P2［v］=v1； //v1是前趋双亲 P2[v]=0; //v 无前趋 else } // End_for D［v1]=0;S[v1]=TRUE； //S集初始时只有源点 源点到源点的距离为0 //开始循环每次求的V1到某个V顶点的最短路径并加V到S集中 6 for（i=2；i<=n；i++)//其余n-1个顶点 { min=Maxint； // 当前所知离v1顶点的最近距离设初值为∞ for(w=1；w〈=n;w++） //对所有顶点检查 if(！S[w］ ＆& D[w] v=w; //在S集之外的离v1最近的顶点序号 min=D[w］； //最近的距离 } //W顶点距离V1顶点更近 S[v］=TRUE； //将v并入S集 for（w=1；w<=n；w++) //更新当前最短路径及距离 if(!S［w］＆＆(D［v]+G-〉arcs［v］［w] } //End_if ｝ //End_for printf (”路径长度（单位：km) 最短路径\\n\"）; for（i=1；i〈=n;i++） { printf （\"％10d”, D[i］）; printf （”%13d”, i）;v=P2[i］; while（v！=0) { printf （\"〈-%d\"， v)； v=P2［v］； } printf(\"\\n\"); } printf（\"\\n\\n\")； } //以下是弗洛伊德求最短路径算法 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—〉arcs［i］[j］!=Maxint） 7 p［i]［j］=j； //j是i的后继 else p[i］[j］=0； D［i］[j］=G-〉arcs［i］［j］； ｝ for（k=1;k〈=n；k++) { { for（i=1;i〈=n；i++) for(j=1;j<=n；j++） { if（D[i]［k］+D[k][j] } ｝ } } } 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—〉arcs[i]［j］！=Maxint) p［i］[j］=j; //j是i的后继 else p［i]［j]=0; D［i][j］=H—〉arcs［i］[j]； } for(k=1;k<=n；k++) ｛ ｛ for(i=1；i<=n；i++) for(j=1;j〈=n；j++） { if(D[i］[k］+D[k］[j］〈D［i］[j]) ｛ D[i][j]=D［i]［k］+D[k］[j］； 8 //修改长度 //修改长度 ｝ } ｝ p［i］[j］=p[i]［k］; } } 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）； //建立图的存储结构 printf（\"＊*＊**＊*****＊＊＊*＊**＊*＊**＊*＊＊*＊＊＊**＊\\n\")； printf(\"＊ 姓名： *\\n”)； printf(”＊ 学号： *\\n\")； while（xz!=0） { printf(\"**＊*＊＊求城市之间的最短路径*＊**＊＊*＊\\n”）； printf（\"＊**＊*＊**＊*＊＊**＊＊*＊＊＊***＊＊***＊*****\\n\"）； printf(\"1。求一个城市到所有城市的最短路径\\n\"); CreateHGraph(H）； printf（”＊＊＊*＊***＊******＊*＊*＊*＊******＊＊*＊＊*\\n\\n\\n”）; printf（\"0.退出\\n\")； printf（”2。求任意的两个城市之间的最短路径\\n”)； printf（\"3.求任意的两个城市之间的最小花费\\n\"); printf（”**＊***＊＊＊**＊*＊**＊＊＊＊*＊＊＊*＊***＊*＊**\\n\"); switch（xz） ｛ case 1: { pri(）； printf（”请输入城市起点代号：\"）； scanf（”％d”， &v)； Dijkstra(G，v,14）; //调用迪杰斯特拉算法 9 scanf（\"％d”,&xz)； } break; case 2: ｛ pri()； Floyd（G，14）; //调用费洛伊德求最短路径算法 printf（”输入城市起点代号和终点代号：”）； scanf(”％d％d\＆v,&w )； k=p[v］［w]； //k为起点v的后继顶点 if(k==0) printf(”顶点%d 到 ％d 无路径！ \\n”，v，w); else { printf（”从顶点%d到%d的最短路径是： ％d\，w，v); ｝ ｛ printf（\"->%d”，k)； //输出后继顶点 k=p［k］[w］； //继续找下一个后继顶点 ｝ printf(”->%d\； // 输出终点w printf（\" 路径长度：％d\\n\\n\\n”，D［v］[w］）； while(k!=w） ｝ break； ｛ pri(); Floyd1(H，14)； //调用费洛伊德求最小花费算法 printf(\"输入城市起点代号和终点代号:”); case 3： scanf(\"%d％d”，&v，＆w ）; k=p［v］［w]; //k为起点v的后继顶点 if（k==0) printf(\"顶点％d 到 ％d 无路径! \\n\"，v,w）; else ｛ printf(”从顶点%d到％d的路径是: %d”，v,w,v)； ｝ { printf(”—>％d\； //输出后继顶点 k=p[k］[w]; //继续找下一个后继顶点 } 10 while(k！=w) } } } printf(”-〉%d”,w); // 输出终点w printf(\"\\n最小花费（单位：元）：％d\\n\\n\\n\］）； } break; 4 调试分析 4.1 问题分析与回顾 问题1：求单源最短路径时，两点间无路径时程序出错. 分析 对于边的初始化出错，我在程序开始的地方定义了一个最大数Maxint =65535表示无穷大，初始化邻接矩阵时，添加了一句“G-〉arcs［i][j]=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 算法改进 在这个交通咨询系统中，创建图时，我是在程序里对图进行了初始化，赋予了一定的权值，这样不利于图的更新和再创建，系统功能还不是很完善。 求两点间最短路径和最小花费都用到了弗洛伊德算法，由于我编程的经验不足,对函数参数传递理解的还不够透彻，所以用了两次弗洛伊德算法，这一点上还有待改进。 11 4。4 经验和体会 经过这些天的设计，这个交通咨询系统已经实现.这个设计可以实现用户输入指令，系统进行相应的查询功能。 学习数据结构对我后继学习其它课程也有很大的帮助，因为运用数据结构可以编出更“好”的程序.以前学习C语言时,只会编写简单的小程序，对于那些大点的程序，如果不用数据结构，程序就会显得臃肿、杂乱无章.以前只是一味的编程,学了数据结构之后,我明白了程序中的各个部分在计算机中是怎么存储的，明白了怎么编写程序可以降低程序的时空复杂度让程序看起来更有条理. 此次课程设计，给我提供了一个既动手又动脑，实践的机会。我回顾了C语言编程的方法和编程的思想，并运用数据结构的知识使程序的时空复杂度都有所降低。这次课程设计让我更深刻地理解了迪杰斯特拉算法和弗洛伊德算法求最短路径的问题，而且在编程的过程中，更加锻炼了我的思维模式，让自己的思维更有条理，写出的程序也更简单明了。课程设计中,我将学到的知识融会贯通，同时提高调试程序的能力,养成良好的编程习惯，并增强对程序整体设计的把握，理论与实践相结合。通过此次课程设计,让我明白了数据结构的重要性，同时也提高了我分析问题、解决问题的能力。我会再接再厉，编写出更好的程序。 5 测试结果 （1） 系统运行首页面如图5-1所示： 图5-1 系统首页图 （2） 选择“1”，系统会给出城市代号对照表并提示用户输入城市起点代号，运 行截图如图5-2所示： 图5-2 选择“1”功能运行图 12 （3） 输入城市代号“1”，系统会给出“1”到所有城市的最短路径以及路径长度， 运行截图如图5—3所示： 图5—3 求单源最短路径输出图 （4） 选择功能“2\"，并输入城市起点和终点代号“1\"和“4”，系统会给出最短 路径和最短路径长度，运行截图如图5—4所示: 图5-4 求两点间最短路径输出图 （5） 选择功能“3”，并输入城市起点和终点代号“3\"和“7\"，系统会给出最小 花费和相应的路径，运行截图如图5-5所示： 图5-5 求两点间最小花费输出图 13 参考文献 [1] 严蔚敏，吴伟民．数据结构（C语言版）［M］．北京：清华大学出版社，2010． ［2］ 蒋清明,向德生． C语言程序设计［M］．北京:人民邮电出版社，2008． [3］ 尹德淳，龙脉工作室．C函数速查手册［M］．北京：人民邮电出版社，2009． [4] 李玲玲．C程序设计［M]．北京:清华大学出版社，2011． [5] 陈雁．数据结构［M]．北京：高等教育出版社,2004． [6] 张磊．C程序设计教程[M]．北京：中国铁道出版社，2007． [7］ 严蔚敏，米宁．《数据结构习题集》[M]．北京：清华大学出版社，2009年． [8] 黄同成，黄俊民，董建寅．数据结构[M]．北京:中国电力出版社,2008年． [9] 谭浩强．C程序设计［M]．北京:清华大学出版社，2008． [10］ 刘振鹏，张晓莉,郝杰．数据结构[M］．北京：中国铁道出版社，2003年． 14 《数据结构课程设计》评分标准 学号 程序运行情况 （占总成绩20%） 能正确运行 基本能正确运行 能运行但结果不完善 程序功能的完善程度 （占总成绩15％） 完善 基本完善 不完善 程序结构的合理性 (占总成绩15%） 合理 基本合理 不太合理 数据结构的合理性 (占总成绩25％） 正确应用并有创新 正确应用 基本正确应用 学生的工作态度与 工作能力 （占总成绩10％） 工作态度认真能完成任务 工作态度认真但性较差 工作态度基本认真但缺乏性 设计报告的规范性 （占总成绩15％） 符合规范 基本符合规范 规范性较差 成绩等级 指导老师签字 总分 时间 姓名 得分 优秀：90分~100分 良好：80分~分 中等：70~79分 及格：60~69分 不及格0分～59分
因篇幅问题不能全部显示，请点此查看更多更全内容