云南大学软件学院数据结构试验图及其应用.doc

云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩123指导教师 （签名）学期：2010秋季学期 任课教师: 朱艳萍 实验题目: 图及其应用 小 组 长: 联系电话: 电子邮件: 完成提交时间：2010 年 1 月 1 日一、【实验构思（Conceive）】(10%)本次实验应用了图的构建，图的存储，图的遍历以及找最短路径。图的存储用的是邻接矩阵的方式存储的，把图中的各个节点的距离存储在一个数组中，然后进行图的深度遍历，来找到两个点之间的距离，把他们放在一个数组里面，再通过弗洛伊算法求出最短路径。二、【实验设计(Design)】(20%) 抽象数据类型：邻接矩阵表示法：#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20Typedef struct ArcCellVRType adj;InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;Typedef structVertexType vexMAX_VERTEX_NUM;AdjMatrix arcs;Int vexnum,arcnum;GraphKind kind;Mgraph;typedef struct VertexType int number;/* 建筑编号 */ char sight10;/* 建筑名称 */ VertexType;/* 定义顶点的类型 */typedef structVertexType vexNUM;/* 图中的顶点，即为建筑 */ int arcsNUMNUM;/* 图中的边，即为建筑间的距离 */int vexnum,arcnum;/* 顶点数，边数 */ MGraph; /* 定义图的类型 */主程序模块：MGraph G= 0,力行楼,1,格物楼,2,校医院,3,楸苑,4,楠苑,5,知味堂,6,中山邦,7,西门,8,体育场,9,百家大道, 0 ,500,1000,300,400,350,3000,5000,4500,3500, 500, 0 ,1500,200,200,300,200,4500,4000,3000, 1000,1500, 0 ,200,1400,1350,4000,MAX,MAX, 300,200,1300, 0 ,100,200,2000,4600,4250,3150, 400,200,1400,100, 0 ,100,1500,4600,4100,3100, 350,300,1350,200,100, 0 ,2000,4650,4150,3150, 3000,200,4000,2000,2000,1500 ,0 , MAX,MAX,MAX, 5000,4500,4000,4600,4600,4650,MAX,0,1100,100, 4500,4000,MAX,4250,4100,4150,MAX,1100,0,1100, 3500,3000,MAX,3150,3100,3150, MAX,100,1100,0, 10, 16;构造一个图，它是一个带有权值的图，它的权值表示两点之间的距离。int v0,v1;for(i=0;i10;i+)for(j=0;j10;j+)aij=G.arcsij;/将costij复制到aijfor(k=0;k10;k+)/对最高下标为k的结点的路径 for(i=0;i10;i+)/对于所有可能的结点对for(j=0;j(aik+akj)aij=aik+akj;pathijk=k;/将k结点加入到结点对（i，j）的最短路径中这个是求两节点之间的最短路径，用到了弗洛伊算法。dock=Menu();switch(ck)case 1:printf(tttt建筑%d和%d的最短距离为：%d,v0,v1,av0v1); /* 计算两个建筑之间的最短路径*/ printf(nntttt请按任意键继续.n);getchar();getchar();break;case 2:printf(%d ,v0);puts(G.vexv0.sight);for(k=0;k10;k+)if(pathv0v1k)/打印出已存入的路径printf(%d ,pathv0v1k);puts(G.vexk.sight);printf(%d ,v1);puts(G.vexv1.sight);printf(nntttt请按任意键继续.n);getchar();getchar();break; while(ck!=3);这个是对菜单那个模块程序的实现。各程序模块伪代码的说明：char Menu() /* 主菜单*/ char c;int flag;doflag=1;system(cls);printf(n*n);printf(n*1、查询建筑间的最短距离*n);printf(n*2、选择最佳路线*n);printf(n*3、退出*n);printf(n*n);printf(n请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e) flag=0;while(flag);return c;这个是主菜单程序，是用户根据自己的需要选择。三、【实现描述（Implement）】(30%)抽象数据类型具体实现函数的说明：typedef struct VertexType int number;/* 建筑编号*/ char sight10;/* 建筑名称*/ VertexType;/* 定义顶点的类型*/typedef structVertexType vexNUM;/* 图中的顶点，即为建筑*/ int arcsNUMNUM;/* 图中的边，即为建筑间的距离*/int vexnum,arcnum;/* 顶点数，边数*/ MGraph; /* 定义图的类型*/ MGraph G; /* 把图定义为全局变量*/MGraph G= 0,力行楼,1,格物楼,2,校医院,3,楸苑,4,楠苑,5,知味堂,6,中山邦,7,西门,8,体育场,9,百家大道, 0 ,500,1000,300,400,350,3000,5000,4500,3500, 500, 0 ,1500,200,200,300,200,4500,4000,3000, 1000,1500, 0 ,200,1400,1350,4000,MAX,MAX, 300,200,1300, 0 ,100,200,2000,4600,4250,3150, 400,200,1400,100, 0 ,100,1500,4600,4100,3100, 350,300,1350,200,100, 0 ,2000,4650,4150,3150, 3000,200,4000,2000,2000,1500 ,0 , MAX,MAX,MAX, 5000,4500,4000,4600,4600,4650,MAX,0,1100,100, 4500,4000,MAX,4250,4100,4150,MAX,1100,0,1100, 3500,3000,MAX,3150,3100,3150, MAX,100,1100,0, 10, 16;是这个函数的实现算法实现的伪代码：for(k=0;k10;k+)/对最高下标为k的结点的路径 for(i=0;i10;i+)/对于所有可能的结点对for(j=0;j(aik+akj)aij=aik+akj;pathijk=k;/将k结点加入到结点对（i，j）的最短路径中流程图：时间复杂度：O（2n+n*n*n）四、【测试结果（Testing）】(10%)四、【实验总结】(10%)通过本次实验，对图图的存储，图的遍历都有一定的了解，而且对于邻接矩阵存储和链式存储做了一次简单的比较，求两点间的最短路径，有两种算法，在本次实验中用到的是弗洛伊算法，Dijkstra算法在课后想要尝试一下。在本次实验中，出现了一些的错误，比如打印输出路径的时候，而且会出现一些常见的小错误。五、【项目运作描述（Operate）】(10%)能够对学校范围内的某些建筑进行遍历搜索找到最小路径。六、【代码】(10%)#include#include#define MAX 5000 #define NUM 10typedef struct VertexType int number;/* 建筑编号 */ char sight10;/* 建筑名称 */ VertexType;/* 定义顶点的类型 */typedef structVertexType vexNUM;/* 图中的顶点，即为建筑 */ int arcsNUMNUM;/* 图中的边，即为建筑间的距离 */int vexnum,arcnum;/* 顶点数，边数 */ MGraph; /* 定义图的类型 */ MGraph G; /* 把图定义为全局变量 */char Menu() /* 主菜单 */ char c;int flag;doflag=1;system(cls);printf(n*n);printf(n*1、查询建筑间的最短距离*n);printf(n*2、选择最佳路线*n);printf(n*3、退出*n);printf(n*n);printf(n请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e) flag=0;while(flag);return c;int main() MGraph G= 0,力行楼,1,格物楼,2,校医院,3,楸苑,4,楠苑,5,知味堂,6,中山邦,7,西门,8,体育场,9,百家大道, 0 ,500,1000,300,400,350,3000,5000,4500,3500, 500, 0 ,1500,200,200,300,200,4500,4000,3000, 1000,1500, 0 ,200,1400,1350,4000,MAX,MAX, 300,200,1300, 0 ,100,200,2000,4600,4250,3150, 400,200,1400,100, 0 ,100,1500,4600,4100,3100, 350,300,1350,200,100, 0 ,2000,4650,4150,3150, 3000,200,4000,2000,2000,1500 ,0 , MAX,MAX,MAX, 5000,4500,4000,4600,4600,4650,MAX,0,1100,100, 4500,4000,MAX,4250,4100,4150,MAX,1100,0,1100, 3500,3000,MAX,3150,3100,3150, MAX,100,1100,0, 10, 16;/图的邻接矩阵,5000表示无穷大int a1010; /结点之间的最短路径矩阵int path101010=0; /存放结点对之间的路径，初值均为0int i,j,k;char ck;int v0,v1;for(i=0;i10;i+)for(j=0;j10;j+)aij=G.arcsij;/将costij复制到aijfor(k=0;k10;k+)/对最高下标为k的结点的路径 for(i=0;i10;i+)/对于所有可能的结点对for(j=0;j(aik+akj)aij=aik+akj;pathijk=k;/将k结点加入到结点对（i，j）的最短路径中 system(color fc);printf(建筑序号：n);printf( 0为力行楼,1为格物楼,2校医院,3楸苑,4楠苑,n 5为知味堂,6中山帮,7西门,8体育场,9百家大道);printf(nnttt请选择起点建筑（0-9）：);scanf(%d,&v0);printf(ttt请选择终点建筑（0-9）：);scanf(%d,&v1);dock=Menu();switch(ck)case 1:printf(tttt建筑%d和%d的最短距离为：%d,v0,v1,av0v1); /* 计算两个建筑之间的最短路径 */ printf(nntttt