东北大学信息科学与工程学院。
数据结构课程设计报告。
题目校园光纤网络铺设。
课题组组长乔连鹏
课题组成员何青强刘义晖黄渭亨徐梦赵阳阳。
专业名称计算机科学与技术。
班级计1003
指导教师孟凡荣。
2012 年 7月。
课程设计任务书。
课题任务分工。
1 课题背景。
1.1 课题**。
本课题有指导老师提供。
1.2 课题任务。
【问题描述】
东北大学铺设校园光纤网络。假设有n个学院和办公楼，只需要铺设n-1条光缆通道。采用最小生成树的算法，给出一个最佳铺设方案。
【设计要求】
设计基于最小生成树的校园光缆铺设程序。
（1）采用图结构、数组、并集树等数据结构。
（2）采用克鲁斯卡尔算法设计最小代价生成树。
（3）可以采用堆排序算法选择权值最小的边。
1.3 课题原理。
1.克鲁斯卡尔算法原理。
考虑问题的出发点：
为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法：先构造一个只含 n 个顶点的子图 sg，然后从权值最小的边开始，若它的添加不使sg 中产生回路，则在 sg 上加上这条边，如此重复，直至加上 n-1 条边为止。如图1.
3.1所示。
图 1.3.1 克鲁斯卡尔算法示意图。
算法描述：构造非连通图 st=( v, )
k = i = 0; /k 计选中的边数。
while (ki;
检查边集 e 中第 i 条权值最小的边(u,v);
若(u,v)加入st后不使st中产生回路，则输出边(u,v); 且 k++;
时间复杂度：
克鲁斯卡尔算法适用于稀疏图，其时间复杂度为o(eloge)。
2.堆排序原理。
堆是满足下列性质的数列：
堆排序算法描述如下：
void heapsort ( heaptype &h )
} /heapsort
堆排序分为两个步骤：建堆和筛选。
（1）筛选。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结使整个二叉树也成为一个堆。如图1.3.2所示。
图 1.3.2 堆筛选示意图。
（2）建堆。
建堆是一个从下往上进行“筛选”的过程。如图1.3.3所示。
图 1.3.3建堆示意图。
堆排序的时间复杂度：
对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；.对 n 个关键字，建成深度为h(= log2n +1)的堆，所需进行的关键字比较的次数至多 4n次；调整“堆顶”共需要 n-1 次，总共进行的关键字比较的次数不超过 2 ( log2(n-1) +log2(n-2) +log22) <2n( log2n )；因此，堆排序的时间复杂度为o(nlogn)。
3.并集树原理。
并集树是一种解决等价问题的高效算法。
1.4 课题调研。
光纤传输是一种高效的数据传输方案。随着信息时代的到来，人们对数据高效传输的需求日益迫切。
我们以东北大学的光纤网络铺设为背景，展开了我们的研究。下图是一张东北大学的地图（图1.4.
1），这张地图虽有些过时，但其稍加处理后与东北大学的实际布局大致相符。而且由于其简洁性，这张地图很容易转换为抽象的逻辑数据，输入计算机。
图 1.4.1 东北大学地图。
我们依据这张地图绘制了东北大学模拟布局图（图1.4.2）。
图 1.4.2 东北大学模拟布局图。
2.需求分析。
2.1 可行性分析（可选）
1.核心算法的可行性。
程序的主要算法包括克鲁斯卡尔算法、堆排序算法、并集树算法。这些算法思维模式和程序实现已经相当成熟。它们的可行性是无容置疑的。
课程设计的可行性主要取决于我们对这些算法的理解程度和熟练运用的程度。经过一个学期数据结构的学习，我相信这些应该不是主要的问题。
2.图形界面的可行性。
对于我们来说，当前做图形界面，主要有四种方法：
（1）dos环境下的图形界面。
（2）用windows api做图形界面。
（3）基于mfc的图形界面。
（4）基于。net的图形界面。
对第一种方法，虽然我有过成功的经验，但这需要大量的时间和精力，各种细节都需要自己处理。而且，除非有特别的需要，这种方法已经不适合于当前图形界面程序的开发。第二种方法同样不是当前图形界面开发的主流。
而且由于我对其了解不多，所以我同样没有选择这种方法。第三种方法是当前大软件的图形界面开发的首选。其运行的效率要胜于第四种方法。
但鉴于经验的缺乏和其本身的复杂性，我排除了在短期内掌握它的可能性。由于我对。net开发有一定的经验，所以我选择了第四种方法。
而且第四种方法有很好的扩展性。无论是开发b/s型应用程序还是数据库应用程序，其都提供了容易的解决方案。但不可否认，它的运行效率不如第三种方法。
这一点即使在我们开发的这样一个简单的应用程序中也体现出来了。
2.2 业务（用户）需求。
经过实际调研，对程序提出了以下几点需求：
（1）程序要能正确的输出结果。
（2）程序应具有良好的人机接口。程序应能所见即所得的输入数据。这就如同在vs中可视化的开发图形界面一样。
程序应能精确的输入数据。每一个点的坐标，每条弧的权值都应能由用户精确控制。这就如同在vs中用**编辑用户界面一样。
（3）程序应能友好的展现结果。
（4）程序应具有演示功能和调试功能。
（5）程序应具有磁盘操作的能力。程序应该可也从磁盘上读取数据，把用户输入的数据存盘，把程序的结果存盘。
（6）程序应具有操作注册表的能力。程序应该能够注册它所使用的文件扩展名，注册它的程序图标，方便用户双击文件直接打开程序。
（7）程序应能显示制作者的信息。
（8）程序应该具有帮助系统。
（9）程序应能很好的控制各个按钮的焦点与可用性。确保即使用户在误操作的情况下，程序仍能很好的运行。
2.3 功能需求。
根据业务需求，程序应具有以下功能：
（1）正确生成光纤网络的最佳铺设方案。
（2）可视化输入数据的能力。
（3）精确输入数据的能力。
（4）友好的显示程序结果的能力。
（5）文件操作的能力。
（6）注册表操作的能力。
（7）焦点控制的能力。
（8）具有帮助系统。
（9）显示制作者信息的能力。
3 方案设计。
3.1 总体（功能）设计。
1.光纤网络铺设系统功能。
系统主要由以下几个功能模块组成：主算法模块、输入模块、输出模块、文件操作模块、焦点控制模块、画图模块、基础类模块、注册表操作模块、帮助模块。各模块之间的关系如图3.
1.1所示。
图 3.1.1 光纤网络铺设系统功能图。
各模块概述如下：
主算法模块：完成程序的所有核心算法，包括克鲁斯卡尔算法、堆排序算法、并集树算法及其他附属操作。此模块主要由kgraph类完成。
输入模块：完成程序的可视化输入和**输入操作。此模块主要由editform和editform_code类完成。
输出模块：主要完成向用户显示最佳光纤网络铺设方案的操作。此模块主要由userform和programmerform类完成。
文件操作模块：完成图数据和最小生成树数据的文件读取和保存操作。此模块主要通过childform类、各个子窗体的保存函数、各个基础类的成员函数协同完成。
焦点控制模块：完成主窗体工具栏按钮的焦点控制，以确保用户不产生不正当的操作。此模块主要由各个子窗体的closeevent事件、主窗体的事件处理函数完成。
课程设计报告格式 课程设计
洛阳理工学院。课程设计说明书。课程名称。设计课题。专业。班级。学号。姓名。完成日期2014年12月26日。问题描述 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的内容要求。基本要求 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的基本要求。测试数据 小四宋体，行间距单倍行距，每...
课程设计总结,课程设计报告
课程设计总结，课程设计报告。3.尝试应用项目管理软件进行项目进程的规划管理 绘制甘特图，不作硬性要求 二 选题说明。人事管理是企业信息管理的重要部分，面对大量的人事工资信息，财务部门采用人力处理将浪费大量的时间 人力和物力，且数据的准确性低。因此，开发一个界面友好，易于操作的人事工资管理软件进行自动...
课程设计 课程设计报告格式
学校名。课程设计报告。课程名称 c语言程序设计 系别 专业班级 学号。姓名。课程题目 企业人事管理系统 完成日期 指导老师 年月日。附件。课程设计的内容。企业人事管理系统 本项目的目标是开发一个功能实用，操作简便，简单明了的人事管理系统。能够录入人事的基本资料，在操作上能够完成诸如添加 修改 删除 ...