《数据结构》
课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
（最小生成树问题）
1 课程设计的目的和意义
2 需求分析
3 系统（项目）设计
4 系统实现
5 系统调试
附录 源程序
1 课程设计的目的和意义
据《数据结构》课堂讲授及书本内容，学生做相应的自主练习，消化课堂所讲解的内容；通过调试典型例题或习题积累调试C及C++程序的经验；通过完成课程设计中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。“数据结构”作为计算机专业基础课，该课程的目标就是使学生学会如何从问题出发，分析数据，构造求解问题的数据结构和算法，培养学生有一定进行较复杂程序设计的能力。
本次课程设计的内容是用最小生成树的构造来表示城市间的最小代价即最小距离，最小生成树可以用连接矩阵和连接表表示，而它们的区别就是连接矩阵一般用来表示密集型的网络，连接表一般用来表示稀疏型的网络，连接矩阵是用数组来存储，连接了是用链表来存储的，比较复杂密集型的网络就网连接矩阵较适用了，设计中运用了Prim算法，“构造可以使n个城市连接的最小生成树”问题就是用连接矩阵和Prim算法处理的一个实际应用。通过这个题目的设计实例，了解了最小生成树的实际运用意义，也了解连接矩阵和连接表的相同与不同之处，进一步加深了对最小生成树结构和Prim算法的理解。
通过这次课程设计，一方面使学生加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空分析等课程基本内容的理解，另一方面，使学生在程序设计
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
（如抽象数据类型、结构化分析、模块化设计和结构化设计）、C和C++语言编程环境以及程序的调试和测试方面受到比较系统的严格的训练。
2 需求分析
1. 题目：最小生成树的Prime算法实现（难度**）
要求：
1) 先任意创建一个图；
2) 用Prime算法，求出该图的最小生成树
。
3 系统（项目）设计
(包括总体设计和详细设计)
一. 设计思想及
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
：
n个顶点的连通图应该至少有n-1条边，而生成树正好有n-1条边，所以生成树是对应的连通图的极小连通子图。带权的无向图，经过遍历得到的生成树也是带权的，最小生成树即权值最小的生成树。所以要求图的最小生成树，即只要求权值最小的极小连通子图。这实际上是求图的一个生成树。同时还要考虑造价最低这个条件。一棵树的权定义为它所含各边的权之和。一个连通网络的最小生成树是该图所有生成树中权最小的生成树普里姆算法（Prim）算法：设N=（V,{E}）是连通图，TE是N上最小生成树中边的集合，U为V中具有最小生成树的顶点集合，初始时，TN为空，U={uo}( uo∈V),重复下叙操作：在所有u∈U、v∈V-U的边（u,v）∈E中找一条代价最小的边（u0 ，v0 ）并入集合TE，同时v0 并入集合TE,同时, 直到U=V为止，此时TE必有n-1条边，且T=(V,{TE})为N的最小生成树。
二．模块的设计及介绍
(1). 主程序模块
void main(){
{
接受命令；
处理命令；
Cout<
>s;
switch(s)
{
case 0:
cout<<"邻接矩阵显示如下："<>y;
if(y=='n')
break;
}
}
程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入顶点数和边数上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用creatMGraph（）函数，接着进入菜单，然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价，最后选择输入确定字母y或N确定是否继续。
(2). 邻接矩阵定义模块代码
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
int localvex(MGraph_L G,char v) {
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}
程序解释：用typedef struct定义连接矩阵，通过二维数组来存储连接矩阵，并设定参数的最大值为20。
（3）. 创建链接矩阵模块代码
int creatMGraph_L(MGraph_L &G) {
char v1,v2;
int i,j,w;
cout<<"…………创建无向图（城市分布图）…………"<>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{
cout<<"输入顶点（城市）"<>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{
cout<<"输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括“()”"<>v1>>v2>>w;
i=localvex(G,v1); j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"图G邻接矩阵创建成功！"<
#include
using namespace std;
#define int_max 10000 //最大的顶点数
#define inf 9999 //将无法到达的权值无限大设为9999
#define max 20
//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
int i=0;
while(G.vexs[i]!=v)
{
++i;
}
return i;
}
int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
char v1,v2;
int i,j,w;
printf("请输入顶点元素：\n");
cin>>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{
cout<<"输入顶点"<>G.vexs[i];
}
for(i=0;i!=G.vexnum;++i)
for(j=0;j!=G.vexnum;++j)
{
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
}
for(int k=0;k!=G.arcnum;++k)
{
printf("请输入边两端顶点序号和相应的权值：\n");
cin>>v1>>v2>>w;//输入一条边依附的两点及权值
i=localvex(G,v1);//确定顶点V1和V2在图中的位置
j=localvex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
}
cout<<"图G邻接矩阵创建成功！"<>s;
switch(s)
{
case 0:
cout<<"邻接矩阵显示如下："<>y;
if(y=='n')
break;
}
}
浙公网安备 33021202002483