程序设计》课程设计姓名：王学号：20100034班级：软件工程00 班指导教师：王会青成绩：2010年 6 月实验一.构造可以使n 个城市连接的最小生成树专业：__软件工程___ 班级：__软件姓名：_王___ 学号：_20100034完成日期：_2010/6/26 ________一、【问题描述】给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。

1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。

2 显示出城市间道路网的邻接矩阵。

3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。

4 输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行Prim 算法→输出最小生成树二、【问题分析】1. 抽象数据类型结构体数组的定义：#ifnd ef ADJACENCYMATRIXED// 防止该头文件被重复引用#define ADJACENCYMATRIXED // 而引起的数据重复定义#define INFINITY 32767 // 最大值∞#define MAX_VERTEX_NUM 20 // 最大顶点个数typedef int VRType; // 权值，即边的值typedef char InfoType; // 附加信息的类型，后面使用时会定义成一个指针typedef char VertexType[MAX_VERTEX_NUM]; // 顶点类型typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{ 有向图，有向网，无向图，无向网}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]; // 顶点向量 AdjMatrixarcs; // 邻接矩阵 int vexnum, arcnum;GraphKind kind;}MGraph;typedef struct{ VertexType adjvex; VRType lowcost;}closedge[MAX_VERTEX_NUM];#endif // 结束 if2 程序模块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); // 以邻接矩阵的形式显示网 G void 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.vexs[i]// 图的当前顶点数和弧数 // 图的种类标志 // 普里姆算法辅助数组的定义输入表示道路的两个城市及道路值G.arcs[i][j].adj返回OKPrim 算法化辅助数组closeEdgefor (i=1; i<G.vexnum; ++i)求下一个城市k = Minimum(closeEdge,G.vexnum)输出找到的道路标记城市，避免重复输出总耗费4.数据类型定义为了用邻接矩阵表示图G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。

并且在图中还定义一个用来存放城市的一维数组及int 型的城市数级道路数。

用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。

这样就建立起了一个城市到城市之间的道路网。

4. 程序主要模块说明：该程序共含5 个模块，本人负责其中2 个模块构造：***************LocateVex(MGraph G, VertexTypev)**************** Status LocateVex(MGraph G, VertexType v);{while (strcmp(G.vexs[i], 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）输入两个城市表示道路，输入道路值；}PRIM 算法MiniSpanTree_PRIM*********void MiniSpanTree_PRIM(MGraph G, VertexType u) {定义辅助数组：closedge closeEdge; 初始化：strcpy(closeEdge[j].adjvex, u);closeEdge[j].lowcost = G.arcs[k][j].adj;for (i=1; i<G.vexnum; ++i){在其余G.vexnum-1 个城市中找到离辅助数组中标记的道路最小值；显示找到的道路；标记新找到的城市；}}********************** Minimum*****************Status Minimum(closedge closeEdge, int n){在辅助数组中找到道路值最小的道路的两点城市：if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)) 返回该城市在G 中的位置}三、【功能实现】#include <iostream.h>#include <stdio.h>#include <string.h>#include <windows.h>#include "TypeDefine.h"#include "AdjacencyMatrix.h"#include "InitializeFunction.h"#include "MiniSpanTree_KRUSKAL.h"#include "MiniSpanTree_PRIM.h"#include "DisplayNet.h" #include "DeleteInfo.h"MGraph 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.vexs[0]);DeleteInfo(G);cout<<endl<<endl;system("pause");return 0;}//intializeFunction.hStatus CreateDG(MGraph &G){return 0;};Status CreateDN(MGraph &G){return 0;};Status CreateUDG(MGraph &G){return 0;};Status CreateUDN(MGraph &G);Status LocateVex(MGraph G, VertexType v){// 判断输入的顶点v 在G 中的位置。

// 根据顶点的类型，可重载此函数。

目前为char int i=0;while (strcmp(G.vexs[i], v)) {i++;}return i;}Status CreateGraph(MGraph &G){// 采用数组(邻接矩阵)表示法，构造图G.G.kind = UDN; // 默认构造无向网/* printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");printf("|1: 有向图2:无向图3:有向网4:无向网\n"); printf("| 请选择:[ ]\b\b");scanf("%d", &G.kind);printf("+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");*/switch (G.kind){case DG: return CreateDG(G); // 构造有向图G case DN: return CreateDN(G);// 构造有向网G case UDG: return CreateUDG(G); // 构造无向图G case UDN: return CreateUDN(G); // 构造无向网G default : return ERROR;}}//CreateGraphStatus CreateUDN （MGraph &G ）{// 采用数组（邻接矩阵）表示法，构造图 G.int i, j, k;VertexType v1, v2;VRType w;printf （" 构造可以使 N 个城市连接的最小生成树 printf （" 请输入城市数、道路数 （至少 6 个城市， 10 条道路 ）："）; cin>>G.vexnum>>G.arcnum; for (i=0; i<G.vexnum; ++i)cin>>G.vexs[i];}for (i=0; i<G.vexnum; ++i) {for (j=0; j<G.vexnum; ++j){G.arcs[i][j].adj = INFINITY;// G.arcs[i][j].info = NULL;}}printf （" 请输入一条道路连接的两个城市名及权值 :\n"）; for (k=0; k<G.arcnum; ++k)printf(" 共%3d 条道路，第 %3d 条道路：", G.arcnum,k+1);printf （" 请输入第 %d 个城市名（共 %d 个):", i+1, G.vexnum); \n"); // 构造顶点向量// 初始化邻接矩阵 // 构造邻接矩阵cin>>v1>>v2>>w; // 输入一条边依附的顶点及权值i = LocateVex(G, v1); // 确定v1、v2 在G 中的位置j = LocateVex(G, v2);G.arcs[i][j].adj = w; // 弧<v1,v2>的权值G.arcs[j][i] = G.arcs[i][j]; // 置<v1,v2>的对称弧<v2,v1>return OK;}//CreateUDN//MiniSpan Tree PRIM.hStatus Minimum(closedge closeEdge, int n){int i, flag, minTemp = INFINITY;for (i=0; i<n; ++i){if ((closeEdge[i].lowcost != 0) && (minTemp > closeEdge[i].lowcost)){minTemp = closeEdge[i].lowcost;flag = i;return flag;void MiniSpanTree_PRIM(MGraph G, VertexType u)// 用普里姆算法从第u 个顶点出发构造网G 的最小生成树T，输出T 的各条边。