您好,欢迎来到独旅网。
搜索
您的当前位置:首页最小生成树实验报告材料

最小生成树实验报告材料

来源:独旅网
实用标准

数据结构课程设计报告

题目: 最小生成树问题

院(系): 计算机工程学院 学生姓名: 班级: 学号: 起迄日期:

指导教师:

2011—2012年度 第 2 学期

一、需求分析

文案大全

实用标准

1.问题描述:

在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。

2.基本功能

在n个城市之间建设网络,只需要架设n-1条线路,建立最小生成树即可实

现最经济的架设方法。

程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。

3.输入输出

以文本形式输出最小生成树,同时输出它们的权值。通过人机对话方式即

用户通过自行选择命令来输入数据和生成相应的数据结果。

二、 概要设计

1.设计思路:

因为是最小生成树问题,所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求,需采用多种存储结构,所 以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计: 图状结构: ADT Graph{

数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R={VR}

VR={|v,w∈V且P(v,w),表示从v到w的弧,

谓词P(v,w)定义了弧的意义或信息}

基本操作:

CreateGraph( &G, V, VR )

初始条件:V是图的顶点集,VR是图中弧的集合。 操作结果:按V和VR的定义构造图G。 DestroyGraph( &G ) 初始条件:图G存在。 操作结果:销毁图G。 LocateVex( G, u )

初始条件:图G存在,u和G中顶点有相同特征。

操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返 回其它信息。 GetVex( G, v )

初始条件:图G存在,v是G中某个顶点。

文案大全

实用标准

操作结果:返回v的值。 PutVex( &G, v, value )

初始条件:图G存在,v是G中某个顶点。 操作结果:对v赋值value。 FirstAdjVex( G, v )

初始条件:图G存在,v是G中某个顶点。

操作结果:返回v的第一个邻接顶点。若顶点在G中没有邻接顶点, NextAdjVex( G, v, w )

InsertVex( &G, v )

DeleteVex( &G, v )

InsertArc( &G, v, w )

DeleteArc( &G, v, w )

DFSTraverse( G, Visit() )

BFSTraverse( G, Visit() )

}ADT Graph

文案大全

则返回“空”。 初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点。 操作结果:返回v的(相对于w的)下一个邻接顶点。若w是v的 最后一个邻接点,则返回“空”。 初始条件:图G存在,v和图中顶点有相同特征。 操作结果:在图G中增添新顶点v。 初始条件:图G存在,v是G中某个顶点。 操作结果:删除G中顶点v及其相关的弧。 初始条件:图G存在,v和w是G中两个顶点。

操作结果:在G中增添弧,若G是无向的,则还增添对称弧 。

初始条件:图G存在,v和w是G中两个顶点。

操作结果:在G中删除弧,若G是无向的,则还删除对称弧 。

初始条件:图G存在,Visit是顶点的应用函数。

操作结果:对图进行深度优先遍历。在遍历过程中对每个顶点调用 函数Visit一次且仅一次。一旦visit()失败,则操作失败。 初始条件:图G存在,Visit是顶点的应用函数。

操作结果:对图进行广度优先遍历。在遍历过程中对每个顶点调用 函数Visit一次且仅一次。一旦visit()失败,则操作失败。 实用标准

存储结构: 邻接矩阵:

#define INFINITY INT_MAX//最大值无穷 #define MAX_VERTEX_NUM 20//最大顶点个数 typedef enum{UDN} GraphKind; typedef struct ArcCell{

VRType adj;//VRType是顶点关系类型 //对带权图为权值类型

InfoTyep *info;//该弧相关信息的指针

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{

VertexType vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵

int vexnum,arcnum;//图的当前顶点数和弧数 GraphKind kind;

}MGraph;

三、 详细设计

1.数据类型的定义 <1>图类型

#define M 20 #define MAX 20 #define null 0

#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 VertexType[MAX_NAME];// 邻接矩阵的数据结构 typedef struct {

VRType adj; // 顶点关系类型。对无权图,用1(是)或0(否)表示 相邻否;

// 对带权图,则为权值类型

InfoType *info; // 该弧相关信息的指针(可无)

文案大全

实用标准

}ArcCell, adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct {

VertexType vexs[MAX_VERTEX_NUM];// 顶点向量 adjMatrix arcs;// 邻接矩阵 int vexnum,// 图的当前顶点数 arcnum;// 图的当前弧数 } mGraph;

// 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct {

VertexType adjvex; VRType lowcost;

}minside[MAX_VERTEX_NUM]; 2.主要模块的算法描述 <1>主函数

int main(void) //主函数 { int i;

scanf(\"%d\ {

case 1:{ 用prim算法求最小生成树

}break; }break;

default:printf(\"\\输入错误!请重新输入!\\n\"); }

case 2:{ 用kruskal算法求最小生成树

switch(i) /*选择菜单*/

}

<2>使用prim算法生成最小生成树 {

定义图的数据结构; 图的构建;

{/*prim算法求最小生成树*/

文案大全

实用标准

对I,j,k定义;

记录从顶点集U到V-U的代价最小的边的辅助数组定义; 把顶点信息的赋给k; 辅助数组初始化;

令最小代价初始化为0,closedge[k].lowcost=0; // 初始,U={u}; 满足当循环变量i小于图的当前节点数时循环; {

按照选取最小代价法则(即求closedge.lowcost的最小正值)选取当 前节点的下一结点(第k顶点); 输出生成树的边; 将第k顶点并入U集合;

满足循环变量j小于图的当前点数时循环;

{

新顶点并入U集后重新选择最小边; } }

} }

<3>使用克鲁斯卡尔算法生成最小生成树 {

图的构建并初始化 {

定义图的数据结构;

申请节点空间(如果失败则返回信息); 创建图;

/*kruskal算法求最小生成树*/

{

对i,j,n,m, parent[M],edge edges[M]定义或初始化; 满足当循环变量i小于图的当前节点数时循环; {

满足循环变量j=i+1小于图的当前点数时循环; {

if(第i个顶点于第j个顶点相连)

{ 把i赋给edges[k].begin; 把j赋给edges[k].end;

文案大全

实用标准

把i,j之间的权值赋给edges[k].weight; K++;}/*对结构体edge进行初始化*/ } }

对图G边的权值进行排序sort(edges, G); 当循环变量i小于当前弧度数时

{将0赋给parent[i],初始化数组;}

当循环变量i小于当前弧度数时(此时第i条弧为最小的) {

找第i条弧的起点和终点;并分别赋给你n,m; 当n,m不相等时

{把m赋给parent[n];

输出此时第i条弧的起点、终点、权值; } }

}

流程图:

Prim算法

主函数 克鲁斯卡尔算法 四、 调试分析

本次课程设计基本达到了设计需求。但是还有很多不足。比如不能随意切换两种算法,也不能由用户选择使用邻接矩阵还是邻接表,以后更加深入的学习计算机知识或许可以在这两个方面进行改进。

五、测试结果

prim算法正确结果:

文案大全

实用标准

prim算法错误结果:

克鲁斯卡尔算法正确结果:

克鲁斯卡尔算法错误结果:

文案大全

实用标准

六、体会与自我评价

“数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心课程,而且已成为其他理工专业的热门选修课。本学期通过学习这门课程,我学会了分析研究计算机加工的数据结构的特性,以及算法的事件分析和空间分析。这些帮助我在设计程序的过程中,更好为数据选择适当的逻辑结构、存储结构及其相应的算法。

通常情况下,交通、道路问题的数学模型是一种称为“图”的数据结构。在本课题中,每个顶点代表一个城市,每一条边代表一条通信录井,同时给每条路径赋予权值,代表着这条路径的建设代价。通过最小生成树的实现,可以实现以最节省经费的方式来建立这个通信网。对于n个顶点的联通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。但是根据要求,我们需要以最少的经费来完成整个通信网的建设,于是便有了最小生成树问题。

为了完成本次课程设计,因为课本上只有prim算法的代码,所以克鲁斯卡尔算法还需要自己使用百度进行查找。在查找到算法之后,要将其变为程序源代码,将它们的功能实现出来。这就需要用到计算机高级语言编程了。我们所学的是C语言版的数据结构,C语言的课程是在大一下半学期就完成的,所以总体来说难度并不是很大。再加上题目要求也不多,属于很简单的题目,所以基本上没有碰到大的难题。

通过本次设计,我对C语言有了更深一层的认识,同时也更好的掌握了“图”部分的算法及其实现方法。这让我对数据结构这门课程都有了更深层次的体会。进行课程设计的确会对本课程的学习有很大的帮助。

文案大全

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- dcrkj.com 版权所有 赣ICP备2024042791号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务