logo资料库

图的遍历和生成树的求解实现报告设计.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.38M 资料格式：doc 举报 版权申诉
第1页 / 共45页
第2页 / 共45页
第3页 / 共45页
第4页 / 共45页
第5页 / 共45页
第6页 / 共45页
第7页 / 共45页
第8页 / 共45页
资料共45页，剩余部分请下载后查看
    摘要
    序言
    目录
    第一章开发环境和开发工具
    1.1C/ C ++语言简介
    1.2 开发背景
    1.3 开发环境
    第二章 算法思想
    2.1 系统需求分析
    2.2 系统总体设计
    2.2.1 系统设计目标
    2.2.2开发设计思想
    2.2.3 系统功能模块设计
    2.3 算法思想描述
    第三章 算法实现
    3.1 数据结构
    3.2 程序模块
    3.3
    各模块之间的调用关系
    3.2主函数和其他函数的伪码算法
    3.4 源程序代码
    第四章 测试与分析
    4.1 测试数据选择
    4.2 测试结果分析
    总 结
    心得体会
    参考文献
    河南城建学院 课 程 设 计 报 告 书 专 业：计算机科学与技术 课程设计名称：《数据结构课程设计》 题 班 学 姓 目：图的遍历和生成树求解实现 级：0814122 班 号：081412219 名：高靖喜 同 组 人 员:马如飞 指 导 老 师：张延红 张芳芳 杨斌 完 成 时 间：2014 年 2 月 27 日
    摘要 摘要 很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程 序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目 的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先 和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握 课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能 力。 关键字：图、深度优先遍历、广度优先遍历、生成树。 序言 计算机科学与技术本科专业《算法与数据结构课程设计》是在《算法与数据结构》 课程结束之后，要求学生能够设计程序，进一步理解和熟练掌握课本中所学的各种数 据结构，学会如何把学到的知识用于解决实际问题，培养自己的动手能力，独立思考 能力，发现问题并解决问题能力而开设的课程。 从课程性质上讲，《算法与数据结构课程设计》是一门技术实践课。其要求是： 学会分析研究计算机加工的数据结构的特点，以便为应用涉及的数据选择适当的逻辑 结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另 一方面，在前期学习过程中对复杂程序设计理解掌握基础上做进一步的实践训练，并 且能编写出结构清楚，正确易读，符合软件工程规范的程序。 很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程 序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目 的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先 和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握 课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的 动手能力。 由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下 采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。
    目 录 目 录 ................................................................................................................................... 1 第一章 开发环境和开发工具..........................................................................................1 C#语言简介......................................................................................................... 1 1.1 1.2 开发背景................................................................................................................. 1 1.3 开发环境................................................................................................................. 1 第二章 算法思想............................................................................................................... 2 2.1 系统需求分析......................................................................................................... 2 2.2 系统总体设计......................................................................................................... 2 2.2.1 系统设计目标............................................................................................. 2 2.2.2 开发设计思想............................................................................................. 2 2.2.3 系统功能模块设计..................................................................................... 3 2.3 算法思想描述......................................................................................................... 4 第三章 算法实现..............................................................................................................5 3.1 数据结构................................................................................................................. 5 3.2 程序模块................................................................................................................. 6 3.3 各模块之间的调用关系....................................................................................... 10 3.4 源程序代码........................................................................................................... 19 第四章 测试与分析........................................................................................................37 4.1 测试数据选择....................................................................................................... 37 4.2 测试结果分析....................................................................................................... 37 结............................................................................................................................. 41 心得体会............................................................................................................................. 42 参 考 文 献 ..................................................................................................................... 42 总
    第一章 开发环境和开发工具 1.1 C/ C ++语言简介 程序可以让各种组件方便的转变为基于 Web 的应用，并且能够通过 Internet 被 各种系统或是其他开发语言所开发的应用调用。 1.2 开发背景 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深 刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行 信息化管理已成为衡量企业管理科学化和现代化的重要标志，而人事管理的全面自动 化、信息化则是其中重要的组成部分。人事管理的好坏对于企业的决策者和管理者来 说都至关重要，在很大程度上影响着企业的经济效益和社会效益。因此，本文所研究 的人事管理信息系统具有一定的使用价值和现实意义。 1.3 开发环境 本文所采用的开发环境主要是基于很多涉及图上操作的算法都是以图的遍历操 作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网 的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻 辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运 算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知 识用于解决实际问题，培养学生的动手能力。 由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下 采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。 1
    第二章 算法思想 2.1 系统需求分析 图的遍历和生成树求解实现 要求： （1）先任意创建一个图； （2）图的 DFS,BFS 的递归和非递归算法的实现 （3）最小生成树（两个算法）的实现，求连通分量的实现 （4）要求用邻接矩阵、邻接表多种结构存储实现 2.2 系统总体设计 2.2.1 系统设计目标 图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有 线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元 素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及 其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中， 节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生 成树。 2.2.2 开发设计思想 函数的调用 2
    2.2.3 系统功能模块设计 函数名 返回值类型 图 creatMGraph_L(G) creatadj(gra,G) ljjzprint(G) adjprint(gra,G) BFSTraverse(gra) DFStra(gra) DFSTraverse_fen(gra) MiniSpanTree_PRIM(g,G.vexnum) MiniSpanTREE_KRUSCAL(G,gra) int int void void void int int int void 3-1 系统功能模块图 3
    2.3 算法思想描述 1) 图的邻接矩阵存储：根据所建无向图的结点数 n,建立 n*n 的矩阵，其中元素 全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用 1 表示，无边 用 0 表示；有全图的边为权值表示，无边用∞表示。 2) 图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每 一行都转成链表的形式将有边的结点进行存储。 3) 图的广度优先遍历：假设从图中的某个顶点 v 出发，在访问了 v 之后依次访 问 v 的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先 被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已 被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的 重复以上步骤，是一个非递归过程。 4) 图的深度优先遍历：假设从图中某顶点 v 出发，依依次访问 v 的邻接顶点， 然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这 是个递归的过程。 5) 图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索， 而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分 量的顶点集。本程序利用的图的深度优先遍历算法 4
    第三章 算法实现 3.1 数据结构 ADT Queue{ 数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列 Q。 QueueEmpty(Q) 初始条件：Q 为非空队列。 操作结果：若 Q 为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q 为非空队列。 操作结果：插入元素 e 为 Q 的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q 为非空队列。 操作结果：删除 Q 的队头元素，并用 e 返回其值。 }ADT Queue ADT Graph{ 数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R： R={VR} VR={|v,w∈V 且 P（v，w）,表示从 v 到 w 的弧， 谓词 P（v,w）定义了弧的意义或信息} 基本操作 P： CreatGraph(&G,V,VR); 初始条件：V 是图的顶点集，VR 是图中弧的集合。 操作结果：按 V 和 VR 的定义构造图 G。 BFSTraverse(G,visit()); 初始条件：图 G 存在，Visit 是定点的应用函数。 操作结果：对图进行广度优先遍历。一旦 visit（）失 败，则操作失败。 DFSTraverse(G,visit()); 初始条件：图 G 存在，Visit 是定点的应用函数。 操作结果：对图进行广度优先遍历。一旦 visit（）失 败，则操作失败。 DFStra_fen(G) 初始条件：图 G 存在，存在图的深度优先遍历算法。 操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。 }ADT Graph; 5
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

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

    热门标签

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

    最新资料