青岛理工大学琴岛学院教务处
2011 年 7 月 7日
学 生 课题名称 设计地点 aaaa 求解最优交通路径 指导教师 设计时间 7-A-105 （1）用二进制给每个字符进行编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列和作为各个对应的字符的编码，将输入的字符用“0” “1”表示出来，译码的过程是输入“0”“1”代码显示输出相对应的字符。 利用弗洛设计目的 (2) 要求学生根据离散数学或数据结构中最短路径算法进行程序编写。伊德算法结合实际情况，通过以每个点为源顶点求出每对定点之间的最短路径。通过二维数组A存放当前最短路径长度，最后输出对应的最短路径长度。 （3）制作一个查阅词典的雏形，主要利用串的匹配算法KMP算法并结合文件的一些知识。设置目标串和模式串的字符比较，查找出需要查找的单词或者是与需要查找的单词有部分的相同字母的单词。 aaa 2011/6/27-2011/7/8
设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于2000字） 一、 运行环境 Microsoft Visual C++6.0不仅仅是一个编译器。它是一个全面的应用程序开发环境。Visual C++采用的框架是MFC。MFC不仅仅是一个类库。MFC 是一个很大的、扩展了的 C++ 类层次结构，它能使开发 Windows 应用程序变得更加容易。 二、 系统流程图 开始 进入查询界面 输入要查询的两个城市编号m_v0,m_v1 查看各城市对应的编号 输入要查询的两个城市 接收城市编号CreatUDN()创建界面 判断前后两次输入的编号是否在查询范围ShortestPath( )计算出最短路径及距离Output()输出起点和终点 N Y 输出最短路径及距离 输出两站点路径及最短距离 否 是 是否继续查询选择 结束 退出
三、 函数及变量说明 (一) 相关函数 （1）首先创建CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。创建对话框提示用户输入发出城市和终到城市的序号，再调用ShortestPath( )函数求出最短路径，由Output( )函数输出结果。 （2）ShortestPath( )利用了数据结构中图论中的最短路径相关的弗洛伊德算法。Output()函数把计算的结果格式化输出。 （二）对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。 （三）具体实现 1. CreatUDN( )函数生成一首先通过个拥有25个城市，30条公路的交通图 根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。 void CreateUDN(v,a) /*造图函数 向图*/ int v,a;构造无图 { int i,j; G.vexnum=v; G.arcnum=a; for(i=0;i 2. 调用narrate( )函数输出提示信息，提示用户输入发出城市和终到城市的序号：narrate( )函数把能够进行计算的城市列表按简单的格式进行输出 void narrate() /*说明函数*/ { int i,k=0; printf(\欢迎使用最优交通路径程序!***************\\n\ printf(\ 制作人：李盟 高东 孙鹏鹏\\n\ printf(\城市列表如下:\\n\\n\ for(i=0;i<25;i++) { printf(\输出城市列表*/ k=k+1; if(k%4==0) printf(\} 3.用ShortestPath( )函数求出最短路径具体功能实现及相应的迪杰斯特拉算法 为了便于ShortestPath( )函数的计算，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。 void ShortestPath(num) /*最短路径函数 可以查询距离最近的点*/ int num; { int v,w,i,t; int final[25];/*final成员变量表示常量，只能被赋值一次，赋值后值不再改变。*/ int min; for(v=0;v<25;++v) { final[v]=0;D[v]=G.arcs[num][v].adj; for(w=0;w<25;++w) P[v][w]=0; if(D[v]<20000) {P[v][num]=1;P[v][v]=1;} } D[num]=0;final[num]=1; for(i=0;i<25;++i) { min=20000; for(w=0;w<25;++w) if(!final[w]) if(D[w] 4.output 函数输出结果 格式化输出 void output(city1,city2) /*输出函数*/ int city1; int city2; { int a,b,c,d,q=0; a=city2; if(a!=city1) { printf(\从%s到%s的最短路径是\ printf(\最短距离为 %dkm.)\\n\\t\ printf(\ d=city1; for(c=0;c<25;++c) { gate:; /*标号，可以作为goto语句跳转的位置*/ P[a][city1]=0; for(b=0;b<25;b++) { if(G.arcs[d][b].adj<20000&&P[a][b]) { printf(\ P[a][b]=0; d=b; if(q%8==0) printf(\ goto gate; } } } } 5.退出main( )函数，程序结束。 void main() /*主函数*/ { int v0,v1; CreateUDN(25,30); narrate();/*引导界面输出*/ printf(\请选择起点城市（0～24）：\\n\ scanf(\ printf(\请选择终点城市（0～24）：\\n\ scanf(\ ShortestPath(v0); /*计算两个城市之间的最短路径 在此函数中使用迪杰斯特拉算法 output(v0,v1); /*输出结果*/ printf(\请按任意键退出...\\n\ getchar(); }