数据结构课程设计最小生成树的构建实验报告

《数据结构课程设计》

题目二：最小生成树的构建

学院：XXXXXXXXXXX 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX 设计时间： XXXXXXXXXXX

目录：

1.需求分析--------------------------------------------- 1

2.课题设计内容--------------------------------------- 1

(1)课程设计基本流程------------------------------------------ (2)详细设计说明------------------------------------------------ (3)界面操作流程图：----------------------------------------- (4)主要程序------------------------------------------------------ (5)运行结果截图-----------------------------------------------

3.得意之处---------------------------------------------

4.设计实践过程中的收获与体会------------------

5.设计目前存在的问题------------------------------

6.主要参考文献--------------------------------------

1 1 2

3 5

6 6 7 7

一、 需求分析

本课程主要是完成一个最小生成树的构建，要求用克鲁斯

卡尔算法或者普利姆算法求网的最小生成树（此程序我用的是普利姆算法），并输出各条边及他们的权值。要求用户在使用时可以准确输入顶点及每个顶点的关系，运算出可以建立的关系网，最后利用普利姆算法准确输出最短路径。

二、 课程设计内容

1、 课程设计基本流程：

关于此课程的设计，是从设计要求入手的。根据对知识的掌握程度，我选择了用普利姆算法进行设计。

根据实验要求，我定义了一个prims类，在类中定义一个私有成员函数和一个公有成员函数。定义相关变量和相关函数，并完善程序。 2、 详细设计说明：

首先在私有成员private中定义节点个数n、图中边的个数g，树的边的个数t，源节点s。定义二维数组graph_edge[99][4]和tree_edge[99][4]，分别为图的边和树的边。因为普利姆算法是把图分为两部分进行运算，所以我定义了T1[50],t1为第一部分， T2[50],t2为第二部分。在公有成员public中定义输入函数input ()、算法函数algorithm()、输出函数output()。

1

在input中进行界面的设计，定义图中边的个数g的初始值为0，利用for循环实现边的权值的输入，嵌套if语句定义图的顶点i,j；边的权值w。用for循环完成图中可以建立关系网的输出。

在algorithm中构造算法，将图的两部分进行运算，利用while循环找出最短路径，其中嵌套for循环和if语句。

在output中打印挑选出的边及其对应的权值。 最后，设计主函数并完善界面。

3、 界面操作流程图：

2

4、 主要程序：

#include class prims {

private:

int n; //节点的个数

int graph_edge[99][4]; //图的边 int g; //图中边的个数

int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点

//把图分成两个部分

int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分

public:

void input(); int findset(int); void algorithm(); void output(); };

void prims::input() {

cout<<\"***********************************\\n\"<cout<<\"****************************************\\n\"; cout<<\"输入顶点的个数 ::\"; cin>>n;

g=0;//图中边的个数初始值为0 cout<<\"输入边的权值 ::\\n\"; for(int i=1;i<=n;i++) {

for(int j=i+1;j<=n;j++) {

cout<<\" < \"< ::\"; int w;

3

cin>>w;

if(w!=0) { g++;

graph_edge[g][1]=i;//定义图的顶点i graph_edge[g][2]=j;//定义图的顶点j graph_edge[g][3]=w;//定义边的权值w } } }

//输出图的边

cout<<\"\\n\\n图中顶点可以建立的关系网::\\n\"; for(i=1;i<=g;i++)

cout<<\" < \"< \"<}

int prims::findset(int x) {

for(int i=1;i<=t1;i++) if(x==T1[i]) return 1;

for(i=1;ivoid prims::algorithm()//构造算法 {

t=0;//初始化边的个数为0 t1=1;

T1[1]=1; //资源节点 t2=n-1; int i;

for(i=1;i<=n-1;i++)

4

T2[i]=i+1;

cout<<\"\\n\\n*****运算开始*****\\n\\n\\n\";

while(g!=0 && t!=n-1) {

// 找出最短路径 int min=99; int p; int u,v,w;

for(i=1;i<=g;i++) {

if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))//如果u和v在不同的部分

{

if(min>graph_edge[i][3]) {

min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } }

//删除图的边

for(int l=p;lgraph_edge[l][1]=graph_edge[l+1][1]; graph_edge[l][2]=graph_edge[l+1][2]; graph_edge[l][3]=graph_edge[l+1][3]; }

//增加树的边 t++;

tree_edge[t][1]=u; tree_edge[t][2]=v; tree_edge[t][3]=w;

5

} }

void prims::output() {

cout<<\"挑选出的边及其对应的权值::\\n\"; for(int i=1;i<=t;i++)

cout<<\"<\"<}

int main() {

prims obj; obj.input(); obj.algorithm(); obj.output(); return 0; }

5、 运行结果截图：

5

三、 得意之处

这次课程设计的课题虽然比较简单，但是每个函数的编写都花了很大的心思。之前有去过之前有去过图书馆查资料、也上网看到了一些，但有很多地方还是不太明白，有些语句通过自己能理解的方式进行了改进，比如for循环语句和if语句的编写等。在编写过程中，比较得意的地方还是用普利姆算法将图分为两个部分的代码的编写，还有可以准确的显示可以建立的关系网，当运行出现bug后，自己又认真修改，解决问题，心情非常喜悦。

另外，我最满意的地方就是在运算完成后，可以准确的输出最短路径及其对应的权值，整个界面设计的简单但不失美观，同时方便用户的使用，增加了友好性。

四、 设计实践过程中的收获与体会

这一星期的课程设计中确实让我增长了不少，也发现自己对于数据结构的知识掌握不够，学得不够好。自己上网看了一些程序，但都不太懂，而且都是用C语言编写的，所以，我去图书馆查了些资料，还是很有帮助的。

对于if语句、for循环语句和while语句我还是查了查C++的书一点一点修改的。其中有一些句子是照着参考资料写的，自己也不太懂。但是经过努力和同学的帮助还是总算没有bug了。

6

五、 设计目前存在的问题

目前这个程序还有很多不足，比如界面太过简单。由于这周前前后后有好多事情挤在一起，程序设计的比较仓促。本来想完成第一部分和第二部分的输出和边的权值的显示，可是由于有bug，问了好多人也不会改，所以放弃了。希望以后能有时间完善这部分的代码吧。

六、 主要参考文献

《数据结构与算法》 电子工业出版社 《C++程序设计基础》 电子工业出版社

7