(最新整理)数据结构课程设计_城市最短路径求解

1、(完整)数据结构课程设计_城市最短路径求解(完整)数据结构课程设计_城市最短路径求解 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)数据结构课程设计_城市最短路径求解）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)数据结构课程设计_城市最短路径求解的全部内容。数据结构课程设计-省会城市最短路径求解一、类关

2、系图说明：graph类继承form类，同时嵌入了cityinf结构体和list类。graph类的几个重要函数、类、结构体 private void init()/初始化函数private void showmap_paint（object sender， painteventargs e) /绘制地图private bool getmindistancefun(int entry) /采用迪杰斯特拉算法获得最短路径private void bfs(int startpoint, int visited, string name） /广度优先遍历函数private void dfs(int st

3、artpoint, int visited, string name)/ 深度优先遍历函数private void prim(）/求解最小生成树 prim算法private class list /广度优先遍历用到的队列类public struct cityinf/存放城市信息:城市名称、城市坐标、状态值二、流程图主界面路径增删应用设置求最短路径仅显示最短路径显示或隐藏距离数据显示全部城市到起点城市的最短路径随机产生路径最小生成树删除两个城市之间的路增加两个城市之间的路深度优先遍历最短距离广度优先遍历寻径过程选择文件查看邻接矩阵(在模拟数据中)模拟数据城市数据真实地图三、主要算法的实现1用迪杰

4、斯特拉算法实现省会城市间最短路径的求解private bool getmindistancefun(int entry） int inputnodenum = citydata。citysum; int mark = new intinputnodenum；/标志位数组 标记数据在哪个集合 int mindis = 0, nextnode = 0;/最短路径,下一个城市结点 int i， j； /第一轮距离数组记录从起始点到其他所有点的边权值 for (i = 0; i inputnodenum； i+） distancei = getcityweight（entry, i）； /所有标志位清

5、零 marki = 0; /如果起始结点可以抵达某个结点 if (i ！= entry & distancei maxweight) routepathi = entry; /则把该结点首先放入路径数组 else routepathi = 1;/表示该路径不通 /初始状态下集合 存放找到最短路径顶点集合的中只包含源点entry 所以把它在mark中标记出来 markentry = 1; /在还没有找到最短路径的结点集合中选取最短距离结点nextnode for （i = 1； i inputnodenum; i+) /设定每轮的初始最小距离为无穷大 mindis = maxweight； fo

6、r (j = 0; j inputnodenum; j+） /保证每次循环mindis是到entry的最小值 if （markj = 0 & distancej mindis)/如果没有进入最短路径且距离小于最小距离 nextnode = j; mindis = distancej;/记录本次循环的最短路径 if (mindis = maxweight)/不存在最短路径 退出 return false; /把nexinode在集合mark中标记成已在最短路径集合中 marknextnode = 1； /每加入一个元素都要修改entry到最短路径集合都要再修改entry到剩余顶点的最短路径长度值

7、 for （j = 0; j inputnodenum； j+）/修改结点v0到其他的结点最短的距离 /找到新的最短路径 if （markj = 0 & getcityweight（nextnode, j) maxweight & distancenextnode + getcityweight（nextnode， j) distancej） /新的最短路径 distancej = distancenextnode + getcityweight（nextnode， j）; /把该点加入路径 routepathj = nextnode； return true; 2.prim算法实现全国公路网

8、最小生成树的求解private void prim（） int i = 0， j = 0， k = 0; /权值数组 保存权值的数组 int weightarrays = new intthis。citydata.citysum； /顶点数组 保存 相应各个顶点的数组 int nodearrays = new intthis。citydata。citysum; /最小权值 初始化时为 this。maxweigh int mincost = this。maxweight; this.mintreeedges = new intthis.citydata.citysum, this.citydat

9、a.citysum; for (i = 0; i this。citydata.citysum; i+) for (j = 0； j this.citydata。citysum； j+） if (i ！= j） this.mintreeedgesi, j = this.maxweight； else this.mintreeedgesi， j = 0; /辅助数组初始化 权值数组赋值 for （i = 1； i this。citydata.citysum; +i) weightarraysi = this.edges0, i； nodearraysi = 0； /某个顶点加入集合u weight

10、arrays0 = 0； nodearrays0 = 0; /判断最小的权值通过的顶点的循环就此开始 for （i = 0; i this。citydata.citysum; +i） k = 1； j = 1； mincost = this.maxweight； /选取权值最小的边和相应的顶点 while （j this.citydata。citysum） if (weightarraysj mincost weightarraysj != 0) mincost = weightarraysj； k = j; j+; /新顶点加入集合u weightarraysk = 0； this。mint

11、reeedgesk, nodearraysk = this。edgesk， nodearraysk； this.mintreeedgesnodearraysk， k = this。edgesk, nodearraysk; /重新计算该顶点到其余顶点的边的权值 for (j = 1; j this。citydata.citysum; j+) if (this.edgesk， j weightarraysj） weightarraysj = this.edgesk, j； nodearraysj = k； this。default()； this。showmintree = true; this.

12、showmap。refresh（); 四、程序测试结果求解两个城市最短路径显示所有城市到“北京的最短路径求解全国省会城市的公路网的最小生成树“增删功能“网络地图”功能五、总结本次课程设计收获很大，使用了多种算法：迪杰斯特拉算法、prim算法.多种数据结：线性表、栈、队列、二维数组。用到了递归程序设计思想。用到了windows程序设计中很重要的gid+绘图方法，采用了巧妙的方法把经纬度转换成坐标，再把省会城市节点绘制到窗体上，使得运行结果更具说服力（1：17 经纬度1度对应17像素点）首次引入网络地图功能，方便用户查看真实地图，更具有实用性。这次的课程设计难度很大，做起来很不轻松，几个算法也是比较巧妙的，代码写了1800左右，功能还是不完善，很多的代码都是为绘图服务的。写windows程序不同于命令提示符下的程序设计,windows程序靠事件驱动，用户在windows系统下做出任何操作都是会产生事件的，比如点击一个按钮，甚至仅仅移动一下鼠标.这就意味着，在图形界面上，如果是gdi绘图的情况下就得考虑用户的各种操作对数据的影响，因为我们不知道用户会选择哪个按钮，然后又会按哪个按钮，所以要考虑大量的情况。这次课设让我对解决程序设计中的困难有更大的信心，程序设