logo资料库

构造可以使n个城市连接的最小生成树(源码).doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.34M 资料格式：doc 举报 版权申诉
第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
资料共23页，剩余部分请下载后查看
    课程设计（论文） 课程名称： 数据结构课程设计 题 目： 构造可以使 n 个城市连 接的最小生成树 院 （系）： 信息与控制工程学院 专业班级： 计算机 0802 姓 名： 宋亚鹏 学 号： 080620218 指导教师： 李智杰 2010 年 9 月 10 日
    西安建筑科技大学课程设计（论文）任务书 专业班级：计算机802 学生姓名： 宋亚鹏 指导教师（签名）： 一、课程设计（论文）题目 问题描述：给定一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立 最小生成树，并计算得到的最小生成树的代价。 二、本次课程设计（论文）应达到的目的 数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手 段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实 施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训 练，将起到显著的促进作用。 本题目要达到目的：熟练掌握数组的各种应用。 三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技 术参数、设计要求等） 基本要求： 1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的 定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要 求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生 成树的代价。 2、表示城市间距离网的邻接矩阵（要求至少 6 个城市，10 条边） 3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 四、应收集的资料及主要参考文献： 由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经 上机练习了“数组及其有关”的基本操作。 参考文献： 1．本年级用的教材：数据结构与算法分析（C++版）（第二版）影印版 2005，7； 2．C++程序设计技能百练，中国铁道出版社，2004，1 蒋立翔编著； 3. 数据结构与 C++，西安交通大学出版社，1999，11 周叶著； 4．C/C++与数据结构，清华大学出版社，2002，3，1 王立柱； 5．数据结构使用 C++语言描述，东南大学出版社，2001，1，1 陈慧南； 五、审核批准意见 教研室主任（签字）
    设计总说明 当今时代在高速发展，城市之间需要建设大量道路来保证人 流或者货物运输的畅通，高速公路、普通公路等在城市之间、乡 镇之间逐渐增多，如何节约成本就是成了一个重要问题。最直接 地，连接同样几个城市道路总长越短则成本越低。如果城市过多， 对人脑来说分析怎样连接最短是个非常繁杂而且容易出错的问 题，因此求助于计算机是个很好的方法。 此程序的设计目的是利用计算机构造可以使 N 个城市连接的 最小生成树。我们在 visaul C++ 6.0 环境下，在读入 N 个城市之间 的距离之后，用 Prim 算法计算出最小生成树，并用图形显示出结 果，图形显示方面用 ezwin 来实现。利用这个程序，用户只需要输 入城市间距离网的邻接矩阵，就可以得到城市之间的最小生成树， 并可以从图形中直观地看见连接情况。 关键字：最小生成树，PRIM 算法，图形显示，ezwin，城市道路
    目录 一． 设计目的------------------------------------1 二． 问题描述------------------------------------1 三． 需求分析------------------------------------2 四． 概要设计------------------------------------2 五． 详细设计------------------------------------3 六． 调试分析------------------------------------6 七． 使用说明------------------------------------8 八． 设计总结------------------------------------11 九． 参考文献------------------------------------12
    西安建筑科技大学课程设计（论文） 《数据结构》课程设计——构造可以使n个 城市连接的最小生成树 一、设计目的 1．培养学生运用算法与数据结构的基本知识解决实际编程中 的数据结构设计和算法设计问题。 2．培养学生独立设计程序与解决问题的能力，培养学生团队 协作集成程序模块及调试能力。 3．培养学生初步的软件设计及软件测试的能力。 4．提高学生的对程序语言 C++的应用能力以及对集成开发环 境 Visual C++ 6.0 的使用能力。 二、问题描述 1．给定一个地区的N个城市间的距离网,用PRIM算法或 KRUSKAL算法建立最小生成树,并计算得到的最小生成树的代价。 2．城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构 定义采用课本中给出的定义，若两个城市之间不存在道路，则将 相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到 的最小生成树中包括了哪些城市间的道路，并显示得到的最小生 成树的代价。 3．表示城市间距离网的邻接矩阵。 4．最小生成树中包括的边及其权值，并显示得到的最小生成 树的代价。 第 1页 共 19 页
    西安建筑科技大学课程设计（论文） 三、需求分析 1．可以计算N个城市之间的最小生成树，即连接N个城市的最 短路径，核心是Prim算法。 2．N个城市间距离网的邻接矩阵，即所需数据，可以由键盘 输入和文件读入，也可由已存在的邻接矩阵直接赋值。 3．可由图形显示出生成的最小生成树的连接情况，使生成的 结果更直观。 四、概要设计 程序的主要功能是生成 N 个城市间距离网的最小生成树，其 核心是 Prim 算法，然后需要以图形直观显示出生成结果，在程序 中以一定的方法实现了此功能。 开始 由键盘输入数据或由文 件读入数据或由已存在 的邻接矩阵直接导入 以 矩 阵 形 式 显 示读入的数据 生 成 最 小 生 成 树 后 以矩阵形式显示 文字描述生成 的最小生成树 最小生成树生成 前后的图形对比 以更直的图形显 示最小生成树 第 2页 共 19 页 退出 图 1 主函数流程图
    西安建筑科技大学课程设计（论文） 五、详细设计 1．Node类：用圆形来表示城市，由圆形中的整数来区分各个 城市。 2．TextRay类：用直线来表示城市之间的道路，直线上的数 字可以表示城市间的距离。 3．Prim类：包含N个城市间距离网的邻接矩阵和程序核心 Prim算法，以及矩阵形式显示、语言描述、图形显示邻接 矩阵的方法。 4．主程序：控制整个流程。 5．Prim算法生成最小生成树流程图： (graph_size代表城市个 数) 第 3页 共 19 页
    西安建筑科技大学课程设计（论文） 开始 以 0 号节点为源城市，将 0 号 节 点 存 入 数 组 component[graph_size]中 将数组 component 中的城市作为一 个整体进行处理，记为 C 在其他城市中找出跟整体 C 最近 的城市，将它存入 component 中 并将此城市到 C 的权值存入数组 distance[graph_size]中 所有城市都已存入 component 中 将 component 中 的 城 市 节 点 和 distance 中的权值存入到另一个 邻接矩阵中 结束 图 2 PRIM 算法流程图 第 4页 共 19 页
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料