数据结构课程设计报告_最短路径c++

《数据结构课程设计报告_最短路径c++》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、青岛理工大学琴岛学院教务处2011年7月7日学生aaaa指导教师aaa课题名称求解最优交通路径设计时间2011/6/27-2011/7/8设计地点7-A-105设计目的（1）用二进制给每个字符进行编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列和作为各个对应的字符的编码，将输入的字符用“0”“1”表示出来，译码的过程是输入“0”“1”代码显示输出相对应的字符。(2)要求学生根据离散数学或数据结构中最短路径算法进行

2、程序编写。利用弗洛伊德算法结合实际情况，通过以每个点为源顶点求出每对定点之间的最短路径。通过二维数组A存放当前最短路径长度，最后输出对应的最短路径长度。（3）制作一个查阅词典的雏形，主要利用串的匹配算法KMP算法并结合文件的一些知识。设置目标串和模式串的字符比较，查找出需要查找的单词或者是与需要查找的单词有部分的相同字母的单词。设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于2000字）一、运行环境MicrosoftVisualC++6.0不仅仅是一个编译器。它是一个全面的应用程序开发环境。Visu

3、alC++采用的框架是MFC。MFC不仅仅是一个类库。MFC是一个很大的、扩展了的C++类层次结构，它能使开发Windows应用程序变得更加容易。进入查询界面是否继续查询选择查看各城市对应的编号判断前后两次输入的编号是否在查询范围之内输入要查询的两个城市输出两站点路径及最短距离退出否是YN二、系统流程图开始输入要查询的两个城市编号m_v0,m_v1接收城市编号CreatUDN()创建界面ShortestPath()计算出最短路径及距离Output()输出起点和终点输出最短路径及距离结束一、函数及变量说明(一)相关函数

4、（1）首先创建CreatUDN()函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。创建对话框提示用户输入发出城市和终到城市的序号，再调用ShortestPath()函数求出最短路径，由Output()函数输出结果。（2）ShortestPath()利用了数据结构中图论中的最短路径相关的弗洛伊德算

5、法。Output()函数把计算的结果格式化输出。（二）对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。（三）具体实现1.CreatUDN()函数生成一首先通过个拥有25个城市，30条公路的交通图根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。voidCreateUDN(v,a)/*造图函数向图*/intv,a;构造无图{inti,j;G.ve

6、xnum=v;G.arcnum=a;for(i=0;i

7、离是互相的，所以要对图中对称的边同时赋值。*/G.arcs[0][2].adj=G.arcs[2][0].adj=1892;G.arcs[1][2].adj=G.arcs[2][1].adj=216;···G.arcs[18][19].adj=G.arcs[19][18].adj=367;G.arcs[19][20].adj=G.arcs[20][19].adj=622;···G.arcs[10][11].adj=G.arcs[11][10].adj=511;G.arcs[11][12].adj=G.arcs[12]

8、[11].adj=349;}1.调用narrate()函数输出提示信息，提示用户输入发出城市和终到城市的序号：narrate()函数把能够进行计算的城市列表按简单的格式进行输出voidnarrate()/*说明函数*/{inti,k=0;printf("*****************欢迎使用最优交通路径程序!**************