算法程序设计实验报告

程序设计》课程设计

姓名：王

学号：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 // 结束 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); // 以邻接矩阵的形式显示网 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

返回OK

Prim 算法

化辅助数组closeEdge

for (i=1; i

求下一个城市k = Minimum(closeEdge,

G.vexnum)

输出找到的道路

标记城市，避免重复

输出总耗费

4.数据类型定义

为了用邻接矩阵表示图G ，先是定义二维数组的每一个元素含道路值然后在图的定义中定义

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

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

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

4. 程序主要模块

说明：该程序共含5 个模块，本人负责其中2 个模块构造：***************LocateVex(MGraph G, VertexType

v)**************** 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-1 个城市中找到离辅助数组中标记的道路最小值；显示找到的道路；

标记新找到的城市；

}