资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称:数据结构课程设计数据结构课程设计 课程设计题目:最短路径算法最短路径算法 院(系):计算机学院 专 业:计算机科学与技术 班 级: 学 号:33 姓 名: 指导教师: 目目 录录 1 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容1 1.2 课程设计要求1 2 2 课程设计原理课程设计原理.2 2.1 课设题目粗略分析2 2.2 原理图介绍3 2.2.1 功能模块图3 2.2.2 流程图分析3 3 数据结构分析数据结构分析.8 3.1 存储结构.8 3.2 算法描述8 4 4 调试与分析调试与分析.9 4.1 调试过程9 4.2 程序执行过程9 参考文献参考文献.11 附附 录(关键部分程序清单)录(关键部分程序清单).12 0 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 设计程序,实现最短路径的求法,系统主要功能如下: 1. 编写算法能够建立带权图,并能够用 Dijkstra 算法求该图的最短路径。 2. 能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图 形方式,可顶点序列方式输出。 1.21.2 课程设计要求课程设计要求 1.带权图的顶点信息用字符串,数据可自定。 2.参考相应的资料,独立完成课程设计任务。 3.较规范课程设计报告和软件代码。 沈阳航空航天大学课程设计报告 1 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求,拟将整体程序分为三大模块。两个子模块相互独立,没 有嵌套调用的情况,在主模块中调用上面两个子模块以下是三个模块的大体分析: 1.建立有向图的存储结构. 2.应用 Dijkstra 算法求出该有向图的最短路径。 3.在主函数中调用上面两个子函数,完成求最短路径的程序设计。 4. 2 2.22.2 原理图介绍原理图介绍 2.2.1 功能模块图功能模块图 求最短路径求最短路径 main 函数函数 Create 函数函数 Dijkstra 函数函数 图 2.1 功能模块图 2.2.2 流程图分析流程图分析 1.主函数 2.2 主函数流程图 2.Create 函数 开始开始 输入数据输入数据 调用调用 Create 函数函数 调用调用 Dijkstra 函数函数 沈阳航空航天大学课程设计报告 3 开始开始 i=1 ivexsi=i i=i+1 Y N i=1 i=n j=1 jarcsij=Maxint N Y N Y j=j+1 k=1 4 karcsij=w k=k+1 结束 Y N 2.3Create 函数流程图 3.Dijkstra 函数 开始开始 int D2MVnum,P2MVnum v=1 v=n Sv=FALSE,D2v=Garcsv1v P2v=v1if(D2vMaxint) P2v=0 v=v+1 Y N 沈阳航空航天大学课程设计报告 5 D2v1=0,Sv1=TRUE i=2 i=n N Y v=w,min=D2w if(!Sw Adjmatrix arcsMVNumMVNum; Mgraph; 3.23.2 算法描述算法描述 1. Dijkstra 算法核心是贪心,实质是按路径长度递增产生诸顶点的最短路径 算法。 迪杰斯特拉算法可用自然语言描述如下: 初始化 S 和 D,置空最短路径终点集,置初始的最短路径值; Sv1=TRUE;Dv1=0; While(S 集中的顶点数n) 开始循环,每次求的 v1 到某个 v 顶点的最短路径,并将 v 加到 S 集中; Sv=TRUE; 更新当前最短路径及距离。 2Dijkstra 算法结束后,通过设置一个数组记录下一个节点的前趋节点,然后 通过倒叙的方式输出该最短路径。 8 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 在调试程序是主要遇到一下几类问题: 1. 程序完成后,调试时没有发现问题,但是当输入开始节点后,运行框却不停 的出现”-a”,后来重新检查程序时发现 for 循环的括号后面多了一个”;”,去掉 该分号之后,程序可以运行。 2. 程序可以运行,但是输出结果不是有序的,解决方法,设立一个前驱数组, 用以记录节点的双亲节点,然后按照倒叙的方式读出该条最短路径的有向序 列。 4.2 程序执行过程程序执行过程 4.1 程序执行过程 沈阳航空航天大学课程设计报告 9 4.2 程序执行过程 10 参考文献参考文献 1 数据结构 (用面向对象方法与 C+描述) ,殷人昆等,清华大学出版社, 2010 年 3 月。 2 算法与数据结构习题精解和实验指导 ,宁正元等,清华大学出版社, 2009 年 6 月。 3 数据结构课程设计 ,苏仕华等,机械工业出版社,2010 年 3 月。 4C 程序设计 ,谭浩强编,清华大学出版社,2006 年 6 月。 沈阳航空航天大学课程设计报告 11 附附 录(关键部分程序清单)录(关键部分程序清单) 程序代码程序代码 #include #include #define MVNum 100 #define Maxint 32767 typedef char VertexType; typedef int Adjmatrix; typedef enum FALSE,TRUEboolean; typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum; MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; void CreateMGraph(MGraph *G,int n,int e) int i,j,k,w; char a,b; for(i=1;ivexsi=i; for(i=1;i=n;i+) for(j=1;jarcsij=Maxint; printf(“输入%d 条边的 i,j 及 w:n“,e); for(k=1;karcsij=w; printf(“有向图的存储结构建立完毕!n“); void Dijkstra(MGraph G,int v1,int n) int D2MVNum,P2MVNum; int v,i,w,min; 12 boolean SMVNum; for(v=1;v=n;v+) Sv=FALSE; D2v=G.arcsv1v; if(D2vMaxint) P2v=v1; else P2v=0; D2v1=0;Sv1=TRUE; for(i=2;i=n;i+) min=Maxint; for(w=1;w=n;w+) if(!Swmin=D2w; Sv=TRUE; for(w=1;w=n;w+) if(!Sw P2w=v; printf(“路径长度 路径n“); for(i=1;i=n;i+) printf(“%5d“,D2i); printf(“%5c“,i-1+a);v=P2i; while(v!=0) printf(“-%c“,v-1+a); v=P2v; printf(“n“); void main() MGraph G; 沈阳航空航天大学课程设计报告 13 int n,e,v; char ch; printf(“输入图中顶点个数和边数 n,e:“); scanf(“%d,%d“, CreateMGraph( while(1) printf(“求最短路径,输入开始点 v:“); fflush(stdin); scanf(“%c“, v=ch-a+1; Dijkstra(G,v,n); 14 课程设计总结:课程设计总结: 本次课程设计涉及到的范围很广,让我能够比较系统的对 C 语言和数据结 构进行一次整理和复习。同时有了很多的体会和经验。 1. 又一次复习了 C 语言,在这次课程设计中我体会到 C 语言超强的逻辑性, 能够熟练使用 VC+的编译环境,也对这两门课程有了新的认识,他们既有联系, 又相互区别,在编写程序过程中要灵活应用。 2. 对数据结构的理解有待加强,这次课程设计应用的算法是 Dijkstra 算 法。在学习的过程中自己就对这方面的知识比较生疏,所以刚拿到这个课设题 目时,自己还是有些不自信,好在自己没有气馁,一步一步的努力终于取得了 成功。 3. 此次设计让我意识到程序设计要求我们必须有不放弃的精神,不能因为 几个错误就轻言放弃,只有坚持不懈方能取得成功。 4. 此次课程设计时间虽短,但我所收获的是永恒的。它让我尝到了学习的 快乐,成功的喜悦,更让我懂得了不少做人的道理。要完成一项任务或把东西 学好就必须有足够的信心,持久的耐心,有面对困难无所畏惧的精神,这对我 日后的学习和生活产生了深远一个影响。 指导教师评语: 指导教师(签字): 年 月 日 课程设计成绩
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号