logo资料库

基于最小生成树的小区网线铺设问题的实现.doc

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.08M 资料格式：doc 举报 版权申诉
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
资料共14页，剩余部分请下载后查看
    武汉理工大学《数据结构》课程设计说明书 学 号： 0120810680316 武汉理工大学计算机学院 课 程 设 计 基于最小生成树的小区网线 题 目 铺设问题的实现 院 系 计算机科学与技术 专 业 班 级 姓 名 指导教师 软件工程 0803 刘洋 夏红霞 2010 年 7 月 7 日 1
    武汉理工大学《数据结构》课程设计说明书 课程设计任务书 学生姓名： 刘洋 专业班级： 软件 0803 班 指导教师： 夏红霞 工作单位： 计算机学院 题 目: 基于最小生成树的小区网线铺设问题的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具 体要求） 1、系统应具备的功能： （1）建立小区网络用户间的最小生成树； （2）实现小区网线铺设问题； （3）演示结果。 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、 不足之处、设计体会等； （4）结束语； （5）参考文献。 时间安排： 2010 年 7 月 2 日－7 日 7 月 2 日 查阅资料 7 月 3 日 系统设计，数据结构设计，算法设计 7 月 4 日-5 日 编程并上机调试 7 月 6 日 撰写报告 7 月 7 日 验收程序，提交设计报告书。 指导教师签名： 系主任（或责任教师）签名： 2010 年 7 月 7 日 2010 年 7 月 7 日 2
    武汉理工大学《数据结构》课程设计说明书 小区铺设网线 摘要 在一个小区中铺设网线，设计一个程序，使其成本最低。本程序从这个实 际问题出发，将其抽象为求最小生成树的问题，并通过 C 语言实现，输入结点 的个数及它们之间的距离，即可求解最优的铺设方案。程序求解最小生成树时是 通过 Prim 算法实现。 关键词 最小生成树 Prim 算法 最短路径 无向图 0.引言 《数据结构》是计算机科学与技术、软件工程及相关学科的专业基础课，也 是软件设计的技术基础。《数据结构》课程的教学要求之一是训练学生进行复杂 的程序设计的技能和培养良好程序设计的风格，其重要程度决不亚于理论知识的 传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基 本能力，是培养创新意识和创新能力的极为重要的环节。基本要求如下： (1) 熟练掌握基本的数据结构； (2) 熟练掌握各种算法； (3) 运用高级语言编写质量高、风格好的应用程序。 因此在这个课程设计中我选择的是在一个小区中铺设网线，如何是其成本达 到最小。这个实验的实验要求是使用 Prim 算法，对给定的连通图求出最小生成 树并将之输出。 1.需求分析 在一个小区中铺设网线，如何是其成本达到最小，是一个在现实中非常重要 的问题。这一类的问题在现实中是非常多的，各种线路的架设，道路的修建等， 都使它有重要的现实经济意义。具体到小区铺设网线问题，若要在 N 间楼房之 间铺设网线，只需铺设 N-1 条线路即可，如何以最低的成本建设这个通信网这个 问题的数学描述就是求最小生成树的问题，可以使用 Prim 算法或者 Kruscal 算法， 两者都是求解最小生成树的典型算法。本程序是使用 Prim 算法编成。 在小区内进行网线的铺设，最现实的问题之一就是经济成本的问题。如何设 计网线的铺设路线，使其在经济成本上达到最优化，是需要认真考虑的。在数学 3
    武汉理工大学《数据结构》课程设计说明书 上，这一类的问题就是在一个无向图中求最小生成树的问题。在算法上已经有很 成熟的解决方案。本程序就是使用的 Prim 算法，结合实际问题，通过输入结点 个数，可以理解为楼房的栋数，以及边的权值，可以理解为楼房之间的距离，求 出最小生成树，即最佳的铺设方案。这样就把一个实际的问题，抽象成了一个数 学问题，并使之得到了解决，达到了求出最短路径，经济上最优化的目的。 2.数据结构设计 在本程序中，用 2 个数组分别储存点集和边集，用一个矩阵储存边的权值， 即邻接矩阵，在程序中建立邻接矩阵后通过输入数值使其初始化，其部分代码如 下: int g[max][max]，n，e，weight，k，i，j，v1，v2; printf("input the number of vertex and edge："); scanf("%d %d"，&n，&e); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { /*建立无向图*/ /*初始化矩阵*/ if(i==j) g[i][j]=0; else g[i][j]=inf; } 3.算法设计 3.1 算法的伪代码描述 首先定义数据类型: type adjmatrix=array [1．.n，1..n] of real; //定义一个 n＊n 的矩阵类型 adjmatrix，以便存储邻接矩阵// edge=record beg，en:1。。n; 4
    武汉理工大学《数据结构》课程设计说明书 length:real; end; //定义边的存储结构为 edge，其中 beg 是边的起点， en 是边的终点，length 是 边的权值// treetype=array [1。。n－1] of edge; //定义一个基类型为 edge 的数组类型 treetype，其元素个数为 n－1 个// var net:adjmatrix; //定义一个 adjmatrix 类型的变量 net，图的邻接矩阵就存放在 net 中// tree:treetype; //定义一个 treetype 类型的变量 tree，tree 中可以存放 n－1 条边的信息，包括起 点、终点及权值。在算法结束后，最小生成树的 n－1 条边就存放在 tree 中// 算法如下(设 n 为构造的出发点)： procedure prim(net:adjmatrix;var tree:treetype); //过程首部。参数的含义是:值参数 net 传递图的邻接矩阵，变参 tree 指明最小生 成树的存放地址// begin for v:=1 to n－1 do //此循环将顶点 n 与图中其它 n－1 个顶点形成的 n－1 条边存放在变量 tree 中// [tree[v]。beg:=n; tree[v]。en:=v; tree[v]。length:=net[v]] for k:=1 to n－1 do //此循环执行算法思想中的步骤 2，循环体每执行一次，TE 中将增加一条边，在 算法中，这条增加的边存放在变量 tree 中的第 k 个元素上，可以这样认为，tree 中从第 1 到第 k 号元素中存放了 TE 和 U 的信息。注意:在算法思想中我们特别 提醒了 TE 和 U 的动态性，表现在算法中，这种动态性体现在循环变量 k 的变化 上。// [min:=tree[k]。length; for j:=k to n－1 do 5
    武汉理工大学《数据结构》课程设计说明书 if tree[j]。length
    武汉理工大学《数据结构》课程设计说明书 { int lowcost[max]，closest[max]; int i，j，k，min; for(i=2;i<=n;i++) { lowcost[i]=g[1][i]; closest[i]=1; } lowcost[1]=0; for(i=2;i<=n;i++) { min=inf; k=0; for(j=2;j<=n;j++) /*n 个顶点，n-1 条边*/ /*初始化*/ /*顶点未加入到最小生成树中*/ /*标志顶点 1 加入 U 集合*/ /*形成 n-1 条边的生成树*/ /*寻找满足边的一个顶点在 U，另一个顶点 在 V 的最小边*/ if((lowcost[j]
    武汉理工大学《数据结构》课程设计说明书 printf("\n"); } } 3.2.2 下面的代码实现的邻接矩阵的输出: void prg(int g[][max]，int n) { /*输出无向图的邻接矩阵*/ int i，j; for(i=0;i<=n;i++) printf("%d\t"，i); for(i=1;i<=n;i++) { printf("\n%d\t"，i); for(j=1;j<=n;j++) if(g[i][j]==inf) printf("inf\t"); else printf("%d\t"，g[i][j]); } printf("\n"); } 3.3 有关技术的讨论 算法是指完成一个任务准确而完整的描述。也就是说给定初始状态或输入数 据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数 据。最小生成树是数据结构中图的一种重要应用，它的要求是从一个带权无向完 全图中选择 n－1 条边并使这个图仍然连通，也即得到了一棵生成树，同时还要 考虑使树的权最小。 为了得到最小生成树，人们设计了很多算法，最著名的有 prim 算法和 kruskal 算法。其中 prim 算法的精巧之处在于对求权值最小的边这一问题的分 解，从而大大减小了计算量。让算法的时间复杂度大幅度减小。 Prim 算法是贪心算法这类算法中一种非常典型的算发，所谓贪心法的基本 思路， 即从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更 好的解。当达到某算法中的某一步不能再继续前进时，算法停止。贪心算法总是 作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出 的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    网络技术

    共收录2367份资料，累计7个分类，关注成员有19位，主要包括：综合布线,网管软件,网络监控,网络设备,其它,系统集成,网络基础

    热门标签

    综合布线 网管软件 网络监控 网络设备 其它 系统集成 网络基础

    最新资料