西北工业大学数据结构试验(图的结构建立和最短路径算法).docVIP

《数据结构》实验报告 ◎实验目:实验目的：实验内容：一、需求分析 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提息”之后，由用户在键盘上输入相应数据3．程序执行的命令包括： （1）；（）；。 4、测试数据：二概要设计Create() 操作结果：通过获得图的结点数和弧数，构造图 Location() 初始条件：图已经存在 操作结果：寻找结点在图中的位置 ShortestPath() 初始条件：图已经存在 操作结果：计算两个结点之间的最短路径 2、本程序包括三个模块： （1）主程序模块 （2）构建图模块 （3）寻找结点模块 （4）寻找最短路径模块 3、模块调用关系图 主程序模块 构建图模块 寻找结点模块 寻找最短路径模块 三详细设计 #includestdio.h #includestring.h #define MAX_VERTEX_NUM 50 #define FALSE 0 #define TRUE 1 #define INFINITY 100000 typedef struct { char vexs[MAX_VERTEX_NUM][100]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, arcnum; }MGraph; 2、每个模块的分析： （1）主程序模块： int main() { MGraph G; char v0[100]; int i,j; int k; int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int D[MAX_VERTEX_NUM]; GreatUDN(G); printf(起始点为:\n); scanf(%s, v0); k = Location(G, v0); ShortestPath(G, k, P, D); for(i=0; iG.vexnum; ++i) { printf(%s-%s,G.vexs[k], G.vexs[i]); if( D[i] == INFINITY) { printf(无路径\n); } else { printf(路径为:); printf(); for(j=0; jG.vexnum; j++) { if(P[i][j] == TRUE) { printf(%s-, G.vexs[j]); } } printf(\b\b); printf(); printf(路径长度为%d,D[i]); printf(\n); } } return 0; } （2）构建图模块： int Create(MGraph G) { int i, j, k; int w; char v1[100], v2[100]; printf(请分别输入顶点和路径的的个数：\n); scanf(%d%d, G.vexnum, G.arcnum); for(i=0; iG.vexnum; ++i) { for(j=0; jG.vexnum; ++j) { G.arcs[i][j] = INFINITY; } } printf(请输入%d个顶点:\n,G.vexnum); for(k=0; kG.vexnum; k++) { scanf(%s, G.vexs[k]); } for(k=0; kG.arcnum; ++k) { printf(请输入第%d条弧上的两个顶点以及弧的权值:\n,k+1); scanf(%s%s%d, v1, v2, w); i = Location(G,v1); j = Location(G,v2); G.arcs[i][j] = w; } return 0; } （3）寻找结点模块： int Location(MGraph G, char ch[]) { int i; for(i=0; iG.vexnum; i++) { if( !strcmp(G.vexs[i], ch)) { break; } } return i; } （4）寻找最短路径模块： void ShortestPath(MGraph G, int v0, int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int D[]) { int v, w; int i, k; int min; int final[MAX_VERTEX_NUM]; for(v=0; vG.vexnu