数据结构课程设计-最小生成树.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<e?

N
Flag=0
j=e-1
Y

j >=i?

N

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

交换
Flag=1

j++

i++

结束

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

输入n个顶点

i=0

i<n?
函数

N

Y
j=0

Y
j<n?
函数

N

Y
i=j?
函数

N

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

j++

i++

k=0

k<e
函数

Y
N

cin>>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 <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
void main()
{
int i;
adjmatrix GA;
edge *CT;//指向边的指针
edge *C;
edge *GE;
int e,n,ch;
cout<<"请输入顶点数n,边数e:(用空格隔开)"<<endl;
cin>>n>>e;
do{
cout<<"***** WELCOME *****"<<endl;
cout<<"你打算采用那种算法?"<<endl;
cout<<"1. Kruskal 算法"<<endl;
cout<<"2. Prim 算法"<<endl;
cout<<"0. 退出 "<<endl;
cout<<"请输入你的选择(1 or 2 or 0):"<<endl;
cin>>ch;
switch(ch)
{
case 0:break;
case 1:
GE=CreateES(n,e);
GE=SortGE(GE,e);
cout<<"经过排序后:"<<endl;
cout<<"----------"; //从这里开始绘制表格;
for(i=0;i<e;i++)
cout<<"----";
cout<<endl;
cout<<"fromvex : |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].fromvex<<'|';
cout<<endl;
cout<<"endvex : |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].endvex<<'|';
cout<<endl;
cout<<"weight : |";
for(i=0;i<e;i++)
cout<<setw(3)<<GE[i].weight<<'|';
cout<<endl;
cout<<"----------"; //到这里绘制表格结束;
for(i=0;i<e;i++)
cout<<"----";
cout<<endl;
C=Kruskal(GE,n,e);
cout<<"Kruskal算法求得的最小生成树为:"<<endl;
for(i=0;i<n-1;i++)
cout<<"<"<<C[i].fromvex<<","<<C[i].endvex<<","<<C[i].weight<<">"<<" ";
cout<<endl<<"处理结束!"<<endl;
break;
case 2:
CreateAM(GA,n,e);
CT=Prim(GA,n);
cout<<"Prim算法求得的最小生成树为:"<<endl;
for(i=0;i<n-1;i++)
cout<<'<'<<CT[i].fromvex<<','<<CT[i].endvex<<','<<CT[i].weight<<">"<<" ";
cout<<endl<<"处理结束!"<<endl;
break;
default:cout<<"输入有误!"<<endl;
}
} while(ch!=0);
}

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
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<<"输入"<<n<<"个顶点:(之间用空格隔开)"<<endl;
for(i=0;i<n;i++)
cin>>GV[i];//输入顶点的个数
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j) GA[i][j]=0;
else
GA[i][j]=MaxValue;//把权值初始化为最大权值
}
cout<<"输入"<<e<<"条边:(格式:fromvex endvex weight)"<<endl;
for(k=0;k<e;k++) //输入边
{
cout<<"输入第"<<k+1<<"条边:";
cin>>i>>j>>w;
GA[i][j]=GA[j][i]=w;//此图为无向图,对称权值相等
}
}

edge *CreateES(int n,int e) //为克鲁斯卡尔算法构造无向图
{
int i,j,k,w;
vexlist GV;
cout<<"输入"<<n<<"个顶点:(之间用空格隔开)"<<endl;
for(i=0;i<n;i++)
cin>>GV[i];
cout<<"输入"<<e<<"条边:(格式:fromvex endvex weight)"<<endl;
edge*GE=(edge *)malloc(e*sizeof(edge));
for(k=0;k<e;k++)
{
cout<<"输入第"<<k+1<<"条边:";
cin>>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<e;i++)
{
flag=0;
for(j=e-1;j>=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<n;i++) //初始化矩阵
{
for(j=0;j<n;j++)
if(i==j) s[i][j]=1;
else s[i][j]=0;
}
int k=1,d=0,m1,m2;
edge *C=new edge[n-1];
for(i=0;i<n-1;i++)
C[i].fromvex=C[i].endvex=C[i].weight=0; //边初始化
while(k<n)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(GE[d].fromvex==j&&s[i][j]==1) m1=i;
if(GE[d].endvex==j&&s[i][j]==1) m2=i;
}
}
if(m1!=m2)
{
C[k-1]=GE[d];
k++;
for(j=0;j<n;j++)
{
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<n-1;i++)
{
CT[i].fromvex=0;
CT[i].endvex=i+1;
CT[i].weight=GA[0][i+1];
}
for(k=1;k<n;k++)
{
min=MaxValue;
m=k-1;
for(j=k-1;j<n-1;j++)
if(CT[j].weight<min)
{
min=CT[j].weight;
m=j;
}
edge temp=CT[k-1];
CT[k-1]=CT[m];
CT[m]=temp;
j=CT[k-1].endvex;
for(i=k;i<n-1;i++)
{
t=CT[i].endvex;
w=GA[j][t];
if(w<CT[i].weight)
{
CT[i].weight=w;
CT[i].fromvex=j;
}
}
}
return CT;
}