管道铺设施工的最佳方案选择_精品.doc

《数据结构》实验报告三 一、上机实验的问题： 为何将权值变量改为float或是double型时，运行过程和结果均有误 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 邻接矩阵的数据结构： typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 图的数据结构： typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, // 图的当前顶点数 arcnum; // 图的当前弧数 } MGraph; 　 程序设计的基本思想： 运用用户所输入的结点及权值构建一个矩阵，即n*n的二维数组（n为结点数目）。结点间有弧用1或者权值在数组中表示（有权图用权值，无权图用1），无弧用0表示，由此构造邻接矩阵。再将结点分为两类：一是已经连接部分U，二是未连接部分V-U。另建一个辅助矩阵，用于存储已连接的结点集合。通过循环语句寻找连接部分和未连接部分的最小权值连接U和V-U中的某一结点，重复循环直至V-U为空。 　 三、源程序及注释： #include stdio.h #include string.h #include malloc.h #define MAX_VERTEX_NUM 20 // 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_INFO 20 // 相关信息字符串的最大长度+1 #define INFINITY 10000 // 用10000最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_NAME]; typedef struct ArcCell { // 邻接矩阵的数据结构 VRType adj; // VRType是顶点关系类型。对无权图，用1或0表示是否相邻；对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { // 图的数据结构 VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 } MGraph; typedef struct { // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 VertexType adjvex; VRType lowcost; //存储该边上的权 } minside[MAX_VERTEX_NUM]; int LocateVex(MGraph G,VertexType u) { // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int i; for(i = 0; i G.vexnum; ++i) if( strcmp(u, G.vexs[i]) == 0) return i; return -1; } void CreateAN(MGraph *G) { // 采用数组(邻接矩阵)表示法,构造无向网G。 int i,j,k,IncInfo; int w; char s[MAX_INFO],*info; VertexType va,vb; printf(请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) ); scanf(%d%d%d,(*G).vexnum,(*G).arcnum,IncInfo); printf(请输入%d个顶点的值(%d个字符):\n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;++i) // 构造顶点向量 scanf(%s,(*G).vexs[i]); for(i=0;i(*G).vexnum;++i) // 初始化邻接矩阵 for(j=0;j(*G).vexnum;++j) { (*G).arcs[i][j].adj=INFINIT