数据结构课程设计-最小生成树.doc

完整word版)数据结构课程设计_最小生成树
《最小生成树的两种算法》
数据结构课程设计报告

题 目： 最小生成树的两种算法
姓 名： 张芹芹
学 号： 2008082238
专 业： 计算机科学与技术
班 级： 2008级（1）班
指导老师： 高攀

二零一零年三月二十五日
目 录
1.课程设计要求及实现目标
………………………………………………………………3
2.程序运行环境
………………………………………………………………3
3.程序的主要功能及模块设计与分析
………………………………………………………………3
4.运行结果
………………………………………………………………8
5.系统使用说明
………………………………………………………………9
6.程序特色
………………………………………………………………9
7.收获及体会
………………………………………………………………10
8.参考书籍
………………………………………………………………10
9.源程序
………………………………………………………………11

一．课程设计要求及实现目标
能够完成最小生成树的两种算法
二、程序运行环境
1.硬件环境
微处理器（cpu）:233MHZ Pentium或更高（或与之相当的处理器）
内存:建议大于1 GB（RAM最小64MB，最大4GB）
磁盘：5GB以上
2.软件环境
操作系统：Microsoft Windows 2003/xp
使用软件: VC6系列
三、程序的主要功能及模块设计与分析
（一）模块主要功能介绍：
此程序主要用于图问题中求最小生成树的运算，包含生成最小生成数的两种方法：PRIM算法和KRUSKAL算法。PRIM算法包括图的矩阵存储，以及生成算法。KRUSKAL算法包括：无向图的生成、按权值排序、以及生成算法。
矩阵存储：用于实现对图的存储
PRIM生成算法：用于按照权值对图求最小生成树
无向图的生成：用于构造吐的存储，能够利用KRUSKAL算法进行求解最小生成树
按权值排序：用于对图中各边按照权值进行排序
KRUSKAL算法：用于对图进行求解，生成最小生成树

（二）、程序模块设计：

主函数

K
R
U
S
K
A
L
算
法

K

al

退出系统
P
R
I
M
算
法

算法实现

图的
矩阵存储

按
权
值
排
序

无
向
图
的
存
储

算法实现

（三）、程序模块流程图：
（1） 主函数 void main()

开始

输入定点数n
边数e
n

0 1 2

PR
IM
K
RU
S
K
A
L

退出系统

CreateES()
CreateAM)

Prim()
SortGE()

Kruskal()

结束

（2）构造图的存储结构 CreateES()
输入顶点的名称
cin>>n
输出提示信息
开始

输出提示信息

输入边信息
f 、e、w

Return GE

结束

（3）排序 SortGE( )
开始

定义变量i，j

i=0

i

j >=i?

N

Y
[j-1].w>[j].w?

交换
Flag=1

j++

i++

结束

（4）图的矩阵存储 CreateAM( )
开始

输入n个顶点

i=0

i N

Y
GA[i][j]=
maxvalue
GA[i][j]=0

j++

i++

k=0

k>f,e,w GA[i][j]=GA[j][i]

k++

结束

（四）运行结果
1.主函数

2.选用Kruskal算法

3.选择方法2

4.选择0退出

（五）、系统使用说明
1.选择Kruskal算法
在主界面上输入1，进入该算法。程序将自动对您的操作进行引导。并自动对临接矩阵进行存储，排序，并最终生成我们所需的最小生成树
2.选择Prim算法
在主界面上输入2，进入该算法。程序将自动对您的操作进行引导。并自动对您输入的图进行存储，并采用该方法最终生成我们所需的最小生成树
3.退出系统
在系统主界面中输入0便实现操作了。
（六）.程序特色
1.有操作的选择界面：可以将所有的功能列出，功能一目了然，方便用户选择自己所需的操作。
2.按最小生成树生成的两种方式，可以选择自己想要的方法；
（七）收获及体会
通过这次课程设计，数据结构这门课程，让我发现程序设计的乐趣，在学习数据结构的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个跟深入的了解。
这次课程设计根据老师给的题目，经过自己的编写，参考相关的书籍，最终实现了算法。首先做函数的主体，一步步的再做其它子函数…这学期所学的数据结构的理论知识得到巩固，但同时也发现自己很多的不足之出，在以后的上机中应更加注意。发现上机实训的重要作用，特别是对结构有了深刻的理解。
通过实际操作，学会利用数据结构编程的方法，锻炼了自己的逻辑思维能力。深刻体会到“实践出真知”，“团结就是力量”，“”书本是最好的老师，“不耻下问”……的寓意。
在此希望以后能有更多这样的实践机会，培养自己独立思考问题的能力，提高实际操作水平
(八).参考资料
[1] 谭浩强主编,《C++程序设计基础》[M],北京：清华大学
出版社，2004
[2] 李春葆主编，《数据结构教程》[M],北京：清华大学
出版社，2007
[3] 刘振鹏 张小莉 郑艳娟主编，《数据结构》 [M],北京：
中国铁道出版社，2007
（九）.源程序

- 16 -
#include "建立.cpp"
#include
#include
#include
void main()
{
int i;
adjmatrix GA;
edge *CT;//指向边的指针
edge *C;
edge *GE;
int e,n,ch;
cout<<"请输入顶点数n,边数e:(用空格隔开)"<>n>>e;
do{
cout<<"***** WELCOME *****"<>ch;
switch(ch)
{
case 0:break;
case 1:
GE=CreateES(n,e);
GE=SortGE(GE,e);
cout<<"经过排序后:"<ndvex : |";
for(i=0;i
cout<"<<" ";
cout<n);
cout<<"Prim算法求得的最小生成树为:"<"<<" ";
cout<
include
#include
const int MaxVertexNum=30;
const int MaxValue=50; //最大权值
typedef int VertexType; //顶点信息类型为整型
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵
struct edge //边结构
{
int fromvex; //起点
int endvex; //终点
int weight;//权值
};
struct edgenode//边结点
{
int adjvex;
edgenode *next;//指向边结点的指针
};
void CreateAM(adjmatrix &GA,int n,int e) //里姆算法构造无向图
{
vexlist GV;
int i,j,k,w;
cout<<"输入"<>GV[i];//输入顶点的个数
for(i=0;ix weight)"<>i>>j>>w;
GA[i][j]=GA[j][i]=w;//此图为无向图,对称权值相等
}
}

edge *CreateES(int n,int e) //为克鲁斯卡尔算法构造无向图
{
int i,j,k,w;
vexlist GV;
cout<<"输入"<个顶点:(之间用空格隔开)"<>GV[i];
cout<<"输入"<>i>>j>>w;
GE[k].fromvex=i;
GE[k].endvex=j;
GE[k].weight=w;
}
return GE;
}

edge *SortGE(edge *GE,int e)//按权值的大小排序
{
int i,j,flag;
edge temp;
for(i=0;i=i;j--)
if(GE[j-1].weight>GE[j].weight)
{
temp=GE[j-1];
GE[j-1]=GE[j];
GE[j]=temp;
flag=1;
}
if(flag==0) return GE;
}
}
edge *Kruskal(edge *GE,int n,int e)//用克鲁斯尔算法求最小生成树
{
int i,j;
adjmatrix s; //矩阵
for(i=0;i for(i=0;i s[m1][j]=s[m1][j]||s[m2][j];
s[m2][j]=0;
}
}
d++;
}
return C;
}
edge *Prim(adjmatrix GA,int n)//用普里姆算法求最小生成树
{
int i,j,k,min,t,m,w;
edge *CT=new edge[n-1];

for(i=0;i CT[i].endvex=i+1;
CT[i].weight=GA[0][i+1];
}
for(k=1;k