毕业设计论文-最小生成树问题报告.doc

《数据结构》
课程设计报告

专 业： 软件工程　　　　
题 目： 最小生成树问题

目录
一. 设计目的 2
二. 设计内容 2
三． 概要设计 1
1、功能模块图 1
2、各个模块详细的功能描述 1
四．详细设计 2
1．主函数和其他函数的伪码算法 2
2、主要函数的程序流程图 6
3、函数之间的调用关系图 13
五．测试数据及运行结果 14
1．正常测试数据及运行结果 14
2、非正常测试数据及运行结果 15
六．调试情况，设计技巧及体会 17
七．参考文献 17
八．附录：源代码 17

24

一. 设计目的
课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼：
1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

二. 设计内容
最小生成树问题:

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

三． 概要设计
1、功能模块图
开始
创建一个图
功能选择
1.建立邻接矩阵
2.建立邻接表
3. PRIM算法
4.
kruscal算法
结束

2、各个模块详细的功能描述

※创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。
※功能选择：给用户提示信息，让用户选择相应功能。
※建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。
※建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。
※PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。

四．详细设计
1．主函数和其他函数的伪码算法
※主函数：
void main()
{
MGraph G;
Dgevalue dgevalue;
CreateUDG(G,dgevalue);
char u;
cout<<"图创建成功。";
cout<<"请根据如下菜单选择操作。\n";
cout<<" *****************************************"<<endl;
cout<<" **1、用邻接矩阵存储：********************"<<endl;
cout<<" **2、用邻接表存储：**********************"<<endl;
cout<<" **3、普里姆算法求最经济的连接方案********"<<endl;
cout<<" **4、克鲁斯卡尔算法求最经济的连接方案****"<<endl;
cout<<" *****************************************"<<endl<<endl;
int s;
char y='y';
while(y='y')
{
cout<<"请选择菜单："<<endl;
cin>>s;
switch(s)
{
case 1:
cout<<"用邻接矩阵存储为："<<endl;
Adjacency_Matrix(G);
break;
case 2:
cout<<"用邻接表存储为："<<endl;
Adjacency_List(G,dgevalue);
break;
case 3:
cout<<"普里姆算法最经济的连接方案为:"<<endl;
cout<<"请输入起始城市名称：";
cin>>u;
MiniSpanTree_PRIM(G,u);
break;
case 4:
cout<<"克鲁斯卡尔算法最经济的连接方案为:"<<endl;
MiniSpanTree_KRSL(G,dgevalue);
break;
default:
cout<<"您的输入有误!";
break;
}
cout<<endl<<"是否继续？y/n:";
cin>>y;
if(y=='n')
break;
}
}
※邻接矩阵和临接表的创建：
int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵
{
int i,j,k;
cout<<"请输入城市个数及其之间的可连接线路数目：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个城市名称(分别用一个字符代替)：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化数组
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!)："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;
i = LocateVex(G,dgevalue[k].ch1);
j = LocateVex(G,dgevalue[k].ch2);
G.arcs[i][j].adj = dgevalue[k].value;
G.arcs[j][i].adj = G.arcs[i][j].adj;
}
return OK;
}
※临接矩阵的输出：
void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据
{
int i,j;
for(i=0; i<G.vexnum; i++)
{
for(j=0; j<G.vexnum; j++)
if(G.arcs[i][j].adj==MAX)
cout<<0<<" ";
else
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}

※邻接表的输出：
void Adjacency_List(MGraph G,Dgevalue dgevalue) //用邻接表储存数据
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
cout<<G.vexs[i]<<"->";
for(j=0;j<G.arcnum;j++)
if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i])
cout<<dgevalue[j].ch2<<"->";
else if(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])
cout<<dgevalue[j].ch1<<"->";
cout<<"\b\b "<<endl;
}
}
※最小生成树PRIM算法：
void MiniSpanTree_PRIM(MGraph G,char u)//普里姆算法求最小生成树
{
int i,j,k;
Closedge closedge;
k = LocateVex(G,u);
for(j=0; j<G.vexnum; j++) //辅助数组初始化
{
if(j != k)
{
closedge[j].adjvex = u;
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
closedge[k].lowcost = 0;
for(i=1; i<G.vexnum; i++)
{
k = Minimum(G,closedge);
cout<<" 城市"<<closedge[k].adjvex<<"与城市"<<G.vexs[k]<<"连接。"<<endl;
closedge[k].lowcost = 0;
for(j=0; j<G.vexnum; ++j)
{
if(G.arcs[k][j].adj < closedge[j].lowcost)
{
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost= G.arcs[k][j].adj;
}
}
}
}
int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
int i,j;
double k = 1000;
for(i=0; i<G.vexnum; i++)
{
if(closedge[i].lowcost != 0 && closedge[i].lowcost < k)
{
k = closedge[i].lowcost;
j = i;
}
}
return j;
}
※最小生成树kruscal算法：
void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树
{
int p1,p2,i,j;
int bj[MAX_VERTEX_NUM]; //标记数组
for(i=0; i<G.vexnum; i++) //标记数组初始化
bj[i]=i;
Sortdge(dgevalue,G);//将所有权值按从小到大排序
for(i=0; i<G.arcnum; i++)
{
p1 = bj[LocateVex(G,dgevalue[i].ch1)];
p2 = bj[LocateVex(G,dgevalue[i].ch2)];
if(p1 != p2)
{
cout<<" 城市"<<dgevalue[i].ch1<<"与城市"<<dgevalue[i].ch2<<"连接。"<<endl;
for(j=0; j<G.vexnum; j++)
{
if(bj[j] == p2)
bj[j] = p1;
}
}
}
}
void Sortdge(Dgevalue & dgevalue,MGraph G)//对dgevalue中各元素按权值按从小到大排序
{
int i,j;
double temp;
char ch1,ch2;
for(i=0; i<G.arcnum; i++)
{
for(j=i; j<G.arcnum; j++)
{
if(dgevalue[i].value > dgevalue[j].value)
{
temp = dgevalue[i].value;
dgevalue[i].value = dgevalue[j].value;
dgevalue[j].value = temp;
ch1 = dgevalue[i].ch1;
dgevalue[i].ch1 = dgevalue[j].ch1;
dgevalue[j].ch1 = ch1;
ch2 = dgevalue[i].ch2;
dgevalue[i].ch2 = dgevalue[j].ch2;
dgevalue[j].ch2 = ch2;
}
}
}
}
2、主要函数的程序流程图
※main（）主函数

※CreatUDG()建图函数

※Adjacency_Matrix()邻接矩阵输出函数

※Adjacency_List()邻接表输出函数

※MiniSpanTree_PRIM()普里姆算法：
基本思想： 假设WN=(V,{E})是一个含有n个顶点的连通网，TV是WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而TE是E的一个子集。在算法开始执行时，TE为空集，TV中只有一个顶点，因此，按普利姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有n-1条边为止。在此系统中，N是你所需要输入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设成本。

开始

标志顶点1加入U集合
寻找满足边的一个顶点在U,另一个顶点在V的最小边
形成n-1条边的生成树
顶点k加入U
修改由顶点k到其他顶点边的权值
结束
得到最小生成树

※MiniSpanTree_KRSL()克鲁斯卡尔算法：
基本思想： 假设WN=（V, {E}）是一个含有N个顶点的连通网。则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有n-1条边为止。在此系统中，N是你所需要输入的城市个数。而每条边的权值就是你所输入的每两个城市之间的建设成本。

※LocateVex（）节点位置函数：

※Minimum()权值比较函数：

※Sortdge()权值排序函数：

3、函数之间的调用关系图

五．测试数据及运行结果

1．正常测试数据及运行结果

2、非正常测试数据及运行结果

六．调试情况，设计技巧及体会

通过此次课程设计，我更深刻地理解了最小生成树问题，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求解方式。
数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。这几天的课程设计让 我充分地体会到了上机实践对于计算机编程的重要性。其实在于计算机语言这类课程看重的就是上机的实际操作，不满足于基本理论的学习。上机操作才能让我们更加好的掌握我们所要学习的计算机语言知识。
只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。此外，也让我更加明白编程是要解决现实问题的。只有拥有把现实问题理论化的能力，才是编程真正需要达到的境界。

七．参考文献
《《新编C语言课程设计教程》》 周二强 编著 清华大学出版社
《《数据结构（C语言版）》》 严蔚敏 吴伟民 编著 清华大学出版社
八．附录：源代码
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define MAX 1000
typedef struct Arcell
{
double adj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM]; //节点数组
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前节点数和弧数
}MGraph;
typedef struct Pnode //用于普利姆算法
{
char adjvex; //节点
double lowcost; //权值
}Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct Knode //用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
char ch1; //节点1
char ch2; //节点2
double value;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
int CreateUDG(MGraph & G,Dgevalue & dgevalue);
int LocateVex(MGraph G,char ch);
int Minimum(MGraph G,Closedge closedge);
void MiniSpanTree_PRIM(MGraph G,char u);
void Sortdge(Dgevalue & dgevalue,MGraph G);
void Adjacency_Matrix(MGraph G);
void Adjacency_List(MGraph G,Dgevalue dgevalue);
//-------------------------------------------------------------------------------
int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵
{
int i,j,k;
cout<<"请输入城市个数及其之间的可连接线路数目：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个城市名称(分别用一个字符代替)：";
for(i=0;i<G.vexnum;++i)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;++i)//初始化数组
for(j=0;j<G.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!)："<<endl;
for(k=0;k<G.arcnum;++k)
{
cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;
i = LocateVex(G,dgevalue[k].ch1);
j = LocateVex(G,dgevalue[k].ch2);
G.arcs[i][j].adj = dgevalue[k].value;
G.arcs[j][i].adj = G.arcs[i][j].adj;
}
return OK;
}
int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置
{
int a ;
for(int i=0; i<G.vexnum; i++)
if(G.vexs[i] == ch)
a=i;
return a;
}
void MiniSpanTree_PRIM(MGraph G,char u)//普里姆算法求最小生成树
{
int i,j,k;
Closedge closedge;
k = LocateVex(G,u);
for(j=0; j<G.vexnum; j++) //辅助数组初始化
{
if(j != k)
{
closedge[j].adjvex = u;
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
closedge[k].lowcost = 0;
for(i=1; i<G.vexnum; i++)
{
k = Minimum(G,closedge);
cout<<" 城市"<<closedge[k].adjvex<<"与城市"<<G.vexs[k]<<"连接。"<<endl;
closedge[k].lowcost = 0;
for(j=0; j<G.vexnum; ++j)
{
if(G.arcs[k][j].adj < closedge[j].lowcost)
{
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost= G.arcs[k][j].adj;
}
}
}
}
int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
int i,j;
double k = 1000;
for(i=0; i<G.vexnum; i++)
{
if(closedge[i].lowcost != 0 && closedge[i].lowcost < k)
{
k = closedge[i].lowcost;
j = i;
}
}
return j;
}
void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树
{
int p1,p2,i,j;
int bj[MAX_VERTEX_NUM]; //标记数组
for(i=0; i<G.vexnum; i++) //标记数组初始化
bj[i]=i;
Sortdge(dgevalue,G);//将所有权值按从小到大排序
for(i=0; i<G.arcnum; i++)
{
p1 = bj[LocateVex(G,dgevalue[i].ch1)];
p2 = bj[LocateVex(G,dgevalue[i].ch2)];
if(p1 != p2)
{
cout<<" 城市"<<dgevalue[i].ch1<<"与城市"<<dgevalue[i].ch2<<"连接。"<<endl;
for(j=0; j<G.vexnum; j++)
{
if(bj[j] == p2)
bj[j] = p1;
}
}
}
}
void Sortdge(Dgevalue & dgevalue,MGraph G)//对dgevalue中各元素按权值按从小到大排序
{
int i,j;
double temp;
char ch1,ch2;
for(i=0; i<G.arcnum; i++)
{
for(j=i; j<G.arcnum; j++)
{
if(dgevalue[i].value > dgevalue[j].value)
{
temp = dgevalue[i].value;
dgevalue[i].value = dgevalue[j].value;
dgevalue[j].value = temp;
ch1 = dgevalue[i].ch1;
dgevalue[i].ch1 = dgevalue[j].ch1;
dgevalue[j].ch1 = ch1;
ch2 = dgevalue[i].ch2;
dgevalue[i].ch2 = dgevalue[j].ch2;
dgevalue[j].ch2 = ch2;
}
}
}
}
void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据
{
int i,j;
for(i=0; i<G.vexnum; i++)
{
for(j=0; j<G.vexnum; j++)
if(G.arcs[i][j].adj==MAX)
cout<<0<<" ";
else
cout<<G.arcs[i][j].adj<<" ";
cout<<endl;
}
}
void Adjacency_List(MGraph G,Dgevalue dgevalue) //用邻接表储存数据
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
cout<<G.vexs[i]<<"->";
for(j=0;j<G.arcnum;j++)
if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i])
cout<<dgevalue[j].ch2<<"->";
else if(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])
cout<<dgevalue[j].ch1<<"->";
cout<<"\b\b "<<endl;
}
}
void main()
{
MGraph G;
Dgevalue dgevalue;
CreateUDG(G,dgevalue);
char u;
cout<<"图创建成功。";
cout<<"请根据如下菜单选择操作。\n";
cout<<" *****************************************"<<endl;
cout<<" **1、用邻接矩阵存储：********************"<<endl;
cout<<" **2、用邻接表存储：**********************"<<endl;
cout<<" **3、普里姆算法求最经济的连接方案********"<<endl;
cout<<" **4、克鲁斯卡尔算法求最经济的连接方案****"<<endl;
cout<<" *****************************************"<<endl<<endl;
int s;
char y='y';
while(y='y')
{
cout<<"请选择菜单："<<endl;
cin>>s;
switch(s)
{
case 1:
cout<<"用邻接矩阵存储为："<<endl;
Adjacency_Matrix(G);
break;
case 2:
cout<<"用邻接表存储为："<<endl;
Adjacency_List(G,dgevalue);
break;
case 3:
cout<<"普里姆算法最经济的连接方案为:"<<endl;
cout<<"请输入起始城市名称：";
cin>>u;
MiniSpanTree_PRIM(G,u);
break;
case 4:
cout<<"克鲁斯卡尔算法最经济的连接方案为:"<<endl;
MiniSpanTree_KRSL(G,dgevalue);
break;
default:
cout<<"您的输入有误!";
break;
}
cout<<endl<<"是否继续？y/n:";
cin>>y;
if(y=='n')
break;
}
}