《常州工学院计算机工程学院》由会员分享，可在线阅读，更多相关《常州工学院计算机工程学院（9页珍藏版）》请在金锄头文库上搜索。
1、常州工学院计算机工程学院C 语言与数据结构实习报告题 目：构造可以使n个城市连接的最小生成树学 号 12030320姓 名 孙帆专业班级 112软卓指导教师 王树峰实践日期 2014年 1月 4号一 综合训练任务主要任务：给定一个地区的 n个城市间的距离网，用 Prim算法或 Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2
2、、表示城市间距离网的邻接矩阵（要求至少 6个城市，10 条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二 普里姆算法编辑普里姆算法是图的最小生成树的一种构造算法。假设 WN=(V,E) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是 最小生成树中边的集合。显然，在算法执行结束时， TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树
3、中含有 n-1条边为止。补充：closedge 的类型：struct VertexData Adjvex;int Lowcost;closedgeMAX_VERTEX_NUM; /求最小生成树的辅助 数组void MiniSpanTree_P( MGraph G, VertexType u )/用普里姆算法从顶点 u 出发构造网 G 的最小生成树k = LocateVex ( G, u );closedgek.Lowcost = 0; / 初始，U=ufor ( j=0; j/io.h 主要定义一些和缓冲区相关的读写函数例如 write open#include /一个是暂停 system(p
4、ause); 一个是刷新 system(cls);#include /无穷大#define MAX_VERTEX_NUM 20 / 最大顶点个数#define MAX_NAME 3 / 顶点字符串的最大长度+1 #define MAX_INFO 20 / 相关信息字符串的最大长度 +1 #define INFINITY INT_MAX / 用整型最大值代替typedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;/ 邻接矩阵的数据结构typedef structVRType adj; / 对带权图，则为权值
5、类型/ 顶点关系类型。对无权图，用 1(是)或 0(否) 表示相邻否；InfoType *info; / 该弧相关信息的指针( 可无) ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM; / 存储顶点向量字符数组AdjMatrix arcs; / 邻接矩阵int vexnum, / 图的当前顶点数arcnum; / 图的当前弧数 MGraph;/ 记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义typedef structVertexTy
6、pe adjvex;/charVRType lowcost;/int 权值。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。minsideMAX_VERTEX_NUM;/ 若 G 中存在顶点 u,则返回该顶点在图中位置 ;否则返回 -1。int LocateVex(MGraph G,VertexType u)int i;for(i = 0; i 0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;/ 算法 7.9 P175 / 用普里姆算法从第 u 个顶点出发构造网 G 的最小生成树 T,输出 T 的
7、各条边void MiniSpanTree_PRIM(MGraph G,VertexType u)int i,j,k;minside closedge;k=LocateVex(G,u);/k=0for(j=0;jG.vexnum;+j) / 辅助数组初始化 if(j!=k)strcpy(closedgej.adjvex,u);/辅存字母从第二个节点开始 u 不变都一样closedgej.lowcost=G.arcskj.adj;/赋权值与 k 有关的各个边的权值closedgek.lowcost=0; / 初始,U=u /closedgek.adjvex=?printf(最小代价生成树的各条边为
8、:n);for(i=1;iG.vexnum;+i) / 选择其余 G.vexnum-1 个顶点 k=minimum(closedge,G); / 求出 T 的下一个结点：第 K 顶点 / printf(%s-%s)t %dn,closedgek.adjvex,G.vexsk,G.arcskclosedgek.lowcost.adj); / 输出生成树的边 printf(%s-%s)n,closedgek.adjvex,G.vexsk); / 输出生成树的边 closedgek.lowcost=0; / 第 K 顶点并入 U 集 for(j=0;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)/ 新顶点并入 U 集后重新选择最小边 strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj;int main()MGraph G;CreateAN(&G);/创建矩阵MiniSpanTree_PRIM(G,G.vexs0);system(pause);return 0;/*
