数据结构课程设计最小生成树问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
课程设计题目: 最小生成树问题
专业班级: 信息与计算科学1001班
姓 名: 谢炜 学 号:100701114
设计室号: 理学院机房
设计时间: 2011-12-26 批阅时间:
指导教师: 杜洪波 成 绩:
一、摘要:
随着社会经济的发展，人们的生活已经越来越离不开网络，网络成为人们社
会生活的重要组成部分。我们希望拥有一个宽松的上网环境，以便更好的进行信
息的交流，在此我们有必要提升我们的网络传播速度。从某种程度上来说网络传
播速度代
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
着一个国家网络化程度的高低。
为了解决网络传输速度的问题我们希望在各个城市之间多架设一些通信网络线路，以缓解网络不够流畅不够便捷的问题。而在城市之间架设网络线路受到资金因素等的限制，我们希望找到一条捷径这样我们即达到了连接了各个城市网络的目的又节省了建设成本。
通过以上的分析我们得出解决此问题的关键在于找到一个短的路径完成网络的假设。在此我们想将各个城市抽象成为一个个节点，连接各个城市之间的网络作为连接各个节点的边。于是我们就将城市的空间分布抽象成为一个网络图，再将各条边的距离抽象成为各节点之间的权值。在原来的基础上建立一个带有权值的网络图。于是原有的问题就转化为找图的最小生成树问题。
我们利用普利姆算法和卡鲁斯卡尔算法找到我们所需要的最小的生成树。
二、问题分析
在n个城市间建立通信网络，需架设n-1条路线。求解如何以最低的经
济代价建设此通信网，这是一个最小生成树问题。我们可以利用普利姆算法
或者克鲁斯卡尔算法求出网的最小生成树，输入各城市的数目以及各个城市
之间的距离。将城市之间的距离当做网中各点之间的权值。 三、实现本程序需要解决的问题
(1)如何选择存储结构去建立一个带权的网络;
(2)如何在所选存储结构下输出这个带权网络;
(3)如何实现普利姆算法的功能;
(4)如何从每个顶点开始找到所有的最小生成树的顶点;
(5)如何输出最小生成树的边及其权值
此问题的关键就是利用普利姆算法，找到一个最小上的生成树，在一个就是输出我们所需要的信息，在此我们将各个城市看做是网中的各个顶点城市之间的距离看做是个顶点之间的权值。现在我们问题做如下的分析:
这个问题主要在于普利姆算法的实现。我们将各个城市的空间分布抽象成一个带有权值的网络，这个权值就是任意两个城市之间，各个城市就看做是网络的各个顶点。
我们建立的输入的数据格式为:首先提示输入带权的顶点数目，我定义为整形的数据型，然后输入每条边的信息，即边的两个顶点之间的权值，以十进制整数类型数据，这样我们就建立了一个带权的网络。
问题的输出我是将我们所得到的最小生成树的路线输出出来。
题目的要求就是我们在n个城市之间架设网络得到的最为经济的架设方法，我们进行以上的工作就是在找我们所需要的最小生成树，已解决我们的问题。 四、算法思想
普利姆算法求最小生成树的主要思想
假设N=(V，{E})是连通网，TE是N上最小生成树中边的集合。算法从U={u}( u?V),TE={}开始，重复执行下述操作:在所有u?U,v?V-U的边(u,v)00
?E中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V为000
止。此时TE中必有n-1条边，则T=(V，{E})为N的最小生成树。
对于最小生成树问题:最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个但是他们权值之和是相等的。 五、程序设计
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图:
输入需要架设网络的城
市的数目
输入需要架设网络的各 个城市之间的距离
找到一个最小的生成树
输出一个最小的生成树 这个最小的生成树就是 一个架设网络的最优解
六、模块划分
(1)预处理
#include
#define maxvertexnum 20
#define maxedgenum 40
typedef int adjmatrix[maxvertexnum][maxvertexnum];
(2)定义一个储存节点信息的结构体
struct edgenode
{
int frontvex;
int rearvex;
int weight;
};
typedef edgenode adgeset[maxedgenum];
(3)初始化的无向图，将每条边的权值赋值为无穷
void insitadj(adjmatrix &GA)
{
for(int i=1;i
#define maxvertexnum 20
#define maxedgenum 40
typedef int adjmatrix[maxvertexnum][maxvertexnum];
struct edgenode
{
int frontvex;
int rearvex;
int weight;
};
typedef edgenode adgeset[maxedgenum]; //===============================================
void insitadj(adjmatrix &GA);
void setadj(adjmatrix &GA,int n); void fun(adjmatrix GA,adgeset >,int n); void display(adgeset GT,int n);
void insit(adgeset >,int n,adjmatrix GA); //============================================= void insit(adgeset>,int n,adjmatrix GA) {
for(int i=1;i
心得
信息技术培训心得 下载关于七一讲话心得体会关于国企改革心得体会关于使用希沃白板的心得体会国培计划培训心得体会
体会
数据结构是学习计算机的一门重要的基础课，在学习数据结构之前我们学习了C语言在我们看来数据结构就是学习C语言的延续。我们知道像这种计算机类的课程必须配合着上机实际操作才能很好的学习他。但是我们平时在学习数据结构的过程中过少的参与到上机练习，在把精力放在了理论知识的学习上忽视了上机的重要性。在此次课程设计中我们深刻的体会到我们光靠学习理论只是不够的，因而我们很珍惜此次上机学习的机会。认真做好自己的程序。
虽然我在刚刚接触到这些习题的时候会感到无所适从，不知道该从哪里下手。但是还是要细心认真的完成，在调试过程中虽然也会出现或多或少的错误，刚开始在遇到错误的时候非常焦躁，看到程序就会头大，但最终还是找到了状态，一步一步慢慢来，经过无数次的检查程序错误的原因后慢慢懂得了耐心是一个人成功的必然条件～
在本次试验的学习中让我很清楚的认识了利用普利姆和克鲁斯卡尔算法求解最小生成树的算法思想，明白了最小生成树是怎么样形成的。我们将我们的城市的空间分布抽象为一个带有权值的网络为我们利用普利姆算法和克鲁斯卡尔算法提供了基础。
在完成此次试验之后我感触很深。认识到数据结构这门课的重要性，在以后的学习计算机方面的课程时我们要注意理论与实践并行。多多上机实践。只有实践才能出真知，在我们设计程序的时候遇到困难不要急躁，要耐心，细心认真的完成，只有这样才能得到事半功倍的效果。
遇到挫折不要放弃，一步一个脚印，最终会得到自己想要的成果。
浙公网安备 33021202002483