《算法程序的设计实验报告》由会员分享，可在线阅读，更多相关《算法程序的设计实验报告（21页珍藏版）》请在金锄头文库上搜索。
1、.程序设计课程设计_王学 号：20100034班 级：软件工程00班指导 王会青 成 绩：20XX6月实验一.构造可以使n个城市连接的最小生成树专业：_软件工程_ _软件 _王_ _20100034完成日期：_2010/6/26_一、问题描述给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。1 城市间的道路网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。2 显示出城市间道路网的邻接矩阵。3 最小生成树中包括的边及其权值,并显示得到的最小生成树的总代价
2、。4 输入城市数、道路数输入城市名输入道路信息执行Kruskal 算法执行 Prim 算法输出最小生成树二、问题分析1. 抽象数据类型结构体数组的定义：#ifndef ADJACENCYMATRIXED/防止该头文件被重复引用#define ADJACENCYMATRIXED/而引起的数据重复定义#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大顶点个数typedef intVRType;/权值,即边的值typedef charInfoType;/附加信息的类型,后面使用时会定义成一个指针typedef charVertexTypeMAX_
3、VERTEX_NUM;/顶点类型typedef enum DG=1, DN, UDG, UDN GraphKind;/有向图,有向网,无向图,无向网typedef struct ArcCellVRTypeadj;/VRType 是顶点关系类型。对无权图,用 1 或 0 表示相邻否；对带权图,则为权值类型。InfoType*info;/该弧关系信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixarcs;/邻接矩阵intvexnum
4、, arcnum;/图的当前顶点数和弧数GraphKindkind;/图的种类标志MGraph;typedef struct/普里姆算法辅助数组的定义VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/结束if2 程序模块MGraph G;/网 G,唯一的全局变量int main;/主函数Status LocateVex;/判断城市 v 在网 G 中的位置Status CreateUDN;/创建网 G 的邻接矩阵void DisplayNet;/以邻接矩阵的形式显示网 Gvoid MiniSpanTree_KRUSKAL;/
5、最小生成树的 Kruskal 算法void MiniSpanTree_PRIM;/最小生成树的 Prim 算法Status Minimum; /Prim 算法中求下一个城市的函数void DeleteInfo;/释放堆内存上动态申请的空间3.流程图创建用邻接矩阵表示的城市道路网输入城市数G.vexnum、道路数G.arcnum输入城市名G.vexsi输入表示道路的两个城市及道路值G.arcsij.adj返回 OKPrim算法化辅助数组closeEdgefor i=1; i求下一个城市k = Minimum输出找到的道路标记城市,避免重复输出总耗费4.数据类型定义为了用邻接矩阵表示图 G ,先是
6、定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。用二维数组的两个下标表示道路,这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。4. 程序主要模块说明：该程序共含5个模块,本人负责其中2个模块构造：*LocateVex*Status LocateVex;while strcmp i+;返回 i；* CreateUDN*输入城市数、道路数；for i=0; i 输入城市名；for i=0; iforj=0; j初始化邻接矩阵：道路值= INFINITY;for i=
7、0; iforj=0; j输入两个城市表示道路,输入道路值；PRIM算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM定义辅助数组：closedge closeEdge;初始化：strcpy;closeEdgej.lowcost = G.arcskj.adj;for i=1; i在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小值；显示找到的道路；标记新找到的城市；* Minimum*Status Minimum在辅助数组中找到道路值最小的道路的两点城市：if & closeEdgei.lowcost返回该城市在 G 中的位置三、功能实现#i
8、nclude #include #include #include #include TypeDefine.h#include AdjacencyMatrix.h#include InitializeFunction.h#include MiniSpanTree_KRUSKAL.h#include MiniSpanTree_PRIM.h#include DisplayNet.h#include DeleteInfo.hMGraph G;/全局变量Gint main;/主函数Status LocateVex;/判断城市 v 在网 G 中的位置Status CreateUDN;/创建网 G 的邻接
9、矩阵void DisplayNet;/以邻接矩阵的形式显示网 Gvoid MiniSpanTree_KRUSKAL;/最小生成树的 Kruskal 算法void MiniSpanTree_PRIM;/最小生成树的 Prim 算法Status Minimum;/Prim 算法中求下一个城市的函数void DeleteInfo;/释放堆内存上动态申请的空间int mainCreateGraph;DisplayNet;MiniSpanTree_KRUSKAL;MiniSpanTree_PRIM;DeleteInfo;coutendlendl;system;return 0;/intializeFun
10、ction.hStatus CreateDGreturn 0;Status CreateDNreturn 0;Status CreateUDGreturn 0;Status CreateUDN;Status LocateVex/判断输入的顶点v在G中的位置。/根据顶点的类型,可重载此函数。目前为charint i=0;while strcmp i+;return i;Status CreateGraph/采用数组邻接矩阵表示法,构造图G.G.kind = UDN;/默认构造无向网/*printf;printf;printf;scanf;printf;*/switch case DG: return CreateDG;/构造有向图Gcase DN: return CreateDN;/构造有向网Gcase UDG: return CreateUDG;/构造无向图Gcase UDN: return CreateUDN;/构造无向网Gdefault : return ERROR;/CreateGraphStatus CreateUDN/采用数组邻接矩阵表示法,构造图G.int i, j
