数据结构课程设计报告

中南大学《数据结构》课程设计题目第9题Dijkstra算法求最短路径学生姓名XXXX指导教师XXXX学院信息科学与工程学院专业班级XXXXXXX完成时间XXXXXXX

第一章问题分析与任务定义—-3课程设计题目———3原始数据的输入格式—3实现功能3测试用例3问题分析3第二章数据结构的选择和概要设计—4数据结构的选择—-4概要设计4第三章详细设计与编码———6框架的建立

点结构体的定义,—7创立+H-而权值有向图,邻接矩阵的显--8示,递归函数的应9用10Dijkstra算法实现最短路径第四章上机调10试11记算算第五章录法法测调试过程的时间的设计试中课、错调误和11空间试经结问题的性能---11验和11处分体理析会果——12第六章第七章学参习考心得文体会--12献12第一章问题分析与任务定义1、课程设计题目：题目：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径要求：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法。具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来。原始数据的输入格式建图：数字显示：数字+逗号+数字+回车字母+回车实现功能建立有向图显示存储的有向图显示从顶点到其他各个顶点的最短路径和是否存在路径测试用例正确数据：输入顶点；边值信息输出结果：最短路径是否存在，存在的情况最短路径是多少，其次是不存在。问题分析实现本程序要解决以下几个问题：如何存储一个有向图。如何在界面中输出该有向图。如何定义起始源点。如何选择出最短路径。找到的最短路径如何输出。第二章数据结构的选择和概要设计数据结构的选择：在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图；另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的,采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素,时间复杂度为O(n2)，这对于顶点很多而边较少的图(稀疏图)是非常不合算的。以邻接矩阵存储有向图。概要设计对于最短路径问题：最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：从某源点到其余各顶点之间的最短路径。每一段顶点之间的最短路径在这里我们解决第一类问题。Dijkstra算法用于求最短路径：Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。算法建立一个顶点集合S,初始时该集合只有源点V0,然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。2..3Dijkstra算法思想设cost[i,j]=0，S为已经求得最短路径的顶点集合，distance[i]数组的每个元素表示当前状态下源点V0到Vi的最短路径。算法如下：1）初始化：S={V0},distance[i]=cost[0,i]o2）选择一个终点Vj，满足distance[j]=MIN{distance[i]|ViEV-S}。3）把Vj加入到S中。4）修改distance数组元素，修改逻辑为对于所有不在S中的顶点Vi.if（distance[j]+cost[i,j]<distance[i]）{distance[i]=distance[j]]+cost[i,j]}5）重复操作2）、3）、4）,直到全部顶点加入到、中。实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。程序流程图：(1)输入顶点个数n,边的条数，初始化邻接矩阵。初始化所每条边的权值与D[h]中①找出v0到图中其他各点的最小值经过改最小值的点到除它外其他各点的最小值直到s中的所有值全部被处理过，输出各最短路径的长度D[w]算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。第三章详细设计和编码框架的建立typedefcharVertexType;dj=INFINITY;G->arcs[i][j].info二NULL;}for(k=0;k<G->arcnum;k++){dj=n;nfo=NULL;dj<INFINITY)printf("\t%5d",G->arcs[j][k].adj);elseprintf("\t3000");dj<INFINITY)printf("\t%5d",G->arcs[j][k].adj);elseprintf("\t3000");node[0]=v0初始化记录经过的顶点数都为0。path[i].num=0;初始化顶点集合s为空，即还未开始。s[i]=0;源点的选择：将v0顶点加入到顶点集合s中。s[v0]=1利用for循环选择一个终点Vj,使其满足V0到Vj距离最短，同时将Vj加入集合S中。c）根据j顶点调整当前的最短路径，若满足dist[i]>dist[j]+cost[j][i],则修改dist[i]的值。同时V0到Vi的最短路径中经过的顶点数加1,即path[i].num++;并将经过的顶点存入数组pnode即path[i].pnode[path[i].num]=jd）此时一趟求最短路径完毕，将终点V1添加到路径中。e）循环执行d）,e）,f）操作，直到全部顶点加入到、中。第四章上机调试记录调试过程中错误和问题的处理1）当输入格式不符合程序要求时，会出现循环2）当两顶点间没有路径时，权值为无穷大，但在本程序中只能用一个具体的数字2000代替抽象的无穷大。3）在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作调整和改动。算法的时间和空间性能分析时间复杂度对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O（n），调整最短路径的循环共执行n-1次，是二层循环，所以，时间复杂度是O（n2）。空间复杂度采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O（n2）。算法设计、调试的经验和体会Dijkstra算法在上课的时候曾作为重点讲过，所以在做查找最短路径的算法时很流畅，但是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时，使用的是结构体数组,所以当处理V0到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。第五章测试结果测试结果：TOC\o"1-5"\h\zID:\CYuYam\bin\wwtemp.exeo~~请输入顶点个麴和弧数如括号里的方式0拘:勺&-请输入囹的第1个顶点:aH请输入图的第2个顶点:£请输入图的第3个顶点*请输入图的第4个顶点:x请输入边的起点和终点和权值如（Vi,v2,n）：ajEj3请输入边的起点和终点和权值如（vl,戒,n）:ajSj2请输入边的起点和终点和权值如（:V1,戒,11）：也为S请输入边的起点和终点和极值如能,n）：SjKj9邻接矩阵显示；aZSX30003253000300030003000半:请输入边的起点和终点和权1宜如(vljv23n):a3Zj3■请输入边的起点和终点和权11如（V1,能,n）:头司2请输入边的起点和终点和权值如（vl,拓,n）：头电S请输入边的起点和终点和极值如（vl.v^n）:*胰邻接疤阵显示:azska3000325z3000300030003000s3000300030009k3000300030003000请输AfcH-始的唳点；a从逐.a没有不存在路径！从催!e的最短路径-X度为：3蜡径正：冬E从逐!日的最蛆路径-W应为：2路径正：%s从萄x的最短路径-半：氏度为：5路径正：T1■D:\CYuYan\bin\v/wtemp.execzi叵1注意问题:1、输入顶点个数：最大不超过25，请输入罗马数字，若输入其他符号，无意义；2、以“字母字母数字”的格式输入图的信息，输入第一个字母为原点，第二个字母为终点，输入“数字”为权值，最后输入一个“字母”为顶点输入。输入完成；3、在输入完成后，屏幕显示邻接矩阵与最短路径。第六章学习心得体会通过对本次课程设计的学习与交流，使我学习到一部分很重要的关于编程方面思想，同时也获得了部分学习其他学科的方法。学习重在于体会，体会这种学科给我带来的思考，给我带来由浅入深的演算心得。做一次课程设计，不仅仅是为了完成某项任务，而在于是否能从这次任务中总结出一些处理同类任务的方法和技巧。每次全力的付出，都会有或多或少的收获。通过对本次课程设计涉及的问题的分析和处理，了解到学习数据结构对编程的技巧和思想方法。以前也了解过数据结构相关的书籍，但没有深入的学习，本次上机课程设计从选题上也把学习的方法应用其中，在编程时算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么来算法来实现，最后通过查找部分资料，修改调试，总结心得，就是一种进步。第七章参考文献:严蔚敏吴伟明编著的《数据结构》（C语言版）:杨晓波主编王弘王聪华胡永副主编的《数据结构实验指导》（C语言版）附件：#include<>#include<>#defineMAX_VERTEX_NUM25dj=INFINITY;G->arcs[i][j].info二NULL;for(k=0;k<G->arcnum;k++){dj=n;nfo=NULL;dj<INFINITY)printf("\t%5d",G->arcs[j][k].adj);elseprintf("\t3000");dj;dj)<D[n]){D[n]=min+G->arcs[i][n].adj;path[n]=i;}//if}//forfor(m=0;m<G->vexnum;m++){if(final[m]==1&&m!二w){printf("\t从%c到%c的最短路径长度为：%d\t路径是：",G->vexs[w],G->vexs[m],D[m]);//输出最大值时则表示两点之间没有最短路径Short(G,path,m,w);printf("%c",G->vexs[m]);pr