构造使n个城市连接的最小生成树______课程设计报告.doc

构造可以使N个城市连接的最小生成树一、课程设计目的及基本要求本课程设计是为了配合计算机软件基础课程的开设，通过设计一完整的程序使学生能达到如下要求，了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用上机调试的基本方法。基本要求：1. 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。2. 显示出城市间道路网的邻接矩阵。3. 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。二、课程设计的主要任务 1. 设计的任务给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。2. 程序执行命令输入城市数、道路数输入城市名输入道路信息执行Kruskal 算法执行 Prim 算法输出最小生成树3、 概要设计 1. 抽象数据类型结构体数组的定义：#ifndef ADJACENCYMATRIXED/防止该头文件被重复引用#define ADJACENCYMATRIXED/而引起的数据重复定义#define INFINITY32767/最大值#define MAX_VERTEX_NUM20/最大顶点个数typedef intVRType;/权值，即边的值typedef charInfoType;/附加信息的类型，后面使用时会定义成一个指针typedef charVertexTypeMAX_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, arcnum;/图的当前顶点数和弧数GraphKindkind;/图的种类标志MGraph;typedef struct/普里姆算法辅助数组的定义VertexTypeadjvex;VRTypelowcost;closedgeMAX_VERTEX_NUM;#endif/结束if 2. 程序模块MGraph G;/网 G，唯一的全局变量int main(int argc, char * argv);/主函数Status LocateVex(MGraph G, VertexType v);/判断城市 v 在网 G 中的位置Status CreateUDN(MGraph &G);/创建网 G 的邻接矩阵void DisplayNet(MGraph G);/以邻接矩阵的形式显示网 Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成树的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成树的 Prim 算法Status Minimum(closedge closeEdge, int n); /Prim 算法中求下一个城市的函数void DeleteInfo(MGraph &G);/释放堆内存上动态申请的空间 3. 流程图创建用邻接矩阵表示的城市道路网输入城市数G.vexnum、道路数G.arcnum输入城市名G.vexsi输入表示道路的两个城市及道路值G.arcsij.adj返回 OK图3-1 创建邻接矩阵的流程图(N-S图)Prim算法化辅助数组closeEdgefor (i=1; iG.vexnum; +i)求下一个城市k = Minimum(closeEdge, G.vexnum)输出找到的道路标记城市，避免重复输出总耗费图3-2 Prim算法流程图（N-S图）4、 详细设计1. 数据类型定义为了用邻接矩阵表示图 G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。2. 程序主要模块说明：该程序共含5个模块，本人负责其中2个模块构造：如图3-1创建邻接矩阵的流程图(N-S图) ，初始化图G*LocateVex(MGraph G, VertexType v)*Status LocateVex(MGraph G, VertexType v);while (strcmp(G.vexsi, v) i+;返回 i；* CreateUDN*输入城市数、道路数；for (i=0; i城市数; +i) 输入城市名；for (i=0; i城市数; +i)for(j=0; j城市数; +j)初始化邻接矩阵：道路值= INFINITY;for (i=0; i城市数; +i)for(j=0; j城市数; +j)输入两个城市表示道路，输入道路值；图3-2 Prim算法* MiniSpanTree_PRIM*void MiniSpanTree_PRIM(MGraph G, VertexType u)定义辅助数组：closedge closeEdge;初始化：strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;for (i=1; i closeEdgei.lowcost)返回该城市在 G 中的位置5、 调试分析和测试结果 1. 调试分析 （1）邻接矩阵初始化本函数的主要功能是对无向网进行邻接矩阵的初始化。构造这种具有n个顶点和e条边的无向网时，关键需要考虑其时间复杂度O（n+e*n）,其中对邻接矩阵G.arcs的初始化花费了O（n）的时间。 （2）Prim 算法Prim 算法的思路是逐步将城市纳入生成树中，这里面的关键步骤是要找到下一个城市。于是通过讨教别人，写了Status Minimum(closedge closeEdge, int n)函数，这样就可以在辅助数组中找到道路值最小的道路的两点城市了。2. 测试结果图5-1 邻接矩阵初始化运行显示界面图5-2 Prim算法运行显示界面六、总结通过课程设计，终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到计算机软件基础课程是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。在以后的学习过程中我将要注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。七、附录/main#include #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(int argc, char * argv);/主函数Status LocateVex(MGraph G, VertexType v);/判断城市 v 在网 G 中的位置Status CreateUDN(MGraph &G);/创建网 G 的邻接矩阵void DisplayNet(MGraph G);/以邻接矩阵的形式显示网 Gvoid MiniSpanTree_KRUSKAL(MGraph G);/最小生成树的 Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);/最小生成树的 Prim 算法Status Minimum(closedge closeEdge, int n);/Prim 算法中求下一个城市的函数void DeleteInfo(MGraph &G);/释放堆内存上动态申请的空间int main(int argc, char * argv)CreateGraph(G);DisplayNet(G);MiniSpanTree_KRUSKAL(G);MiniSpanTree_PRIM(G, G.vexs0);DeleteInfo(G);coutendlG.vexnumG.arcnum;for (i=0; iG.vexsi;for (i=0; iG.vexnum; +i)/初始化邻接矩阵for (j=0; jG.vexnum; +j)G.arcsij.adj = INFINITY;/G. = NULL;printf(请输入一条道路连接的两个城市名及权值:n);for (k=0; kv1v2w;/输入一条边依附的顶点及权值i = LocateVex(G, v1);/确定v1、v2在G中的位置j = LocateVex(G, v2);G.arcsij.adj = w;/弧的权值G.arcsji = G.arcsij;/置的对称弧return OK;/CreateUDN/MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n)int i, flag, minTemp = INFINITY;for (i=0; i closeEdgei.lowcost)minTemp = closeEdgei.lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)/用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边。/记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义见 AdjacencyMatrix.hint i, j, k, totalCost=0;closedge closeEdge;k = LocateVex(G, u);for (j=0; jG.vexnum; +j)/辅助数组初始化if (j != k)strcpy(closeEdgej.adjvex, u);closeEdgej.lowcost = G.arcskj.adj;coutnn+n;cout|用Prim算法求最小生成树的各条边依次为：n-;closeEdgek.lowcost = 0;/初始，U=u;for (i=1; i 0, viV-UcoutcloseEdgek.adjvex,G.vexsk;/输出生成树的边to