没有合适的资源?快使用搜索试试~ 我知道了~
图的存储与遍历(数据结构)
5星 · 超过95%的资源 需积分: 9 45 下载量 29 浏览量
2008-12-10
18:44:14
上传
评论
收藏 124KB DOC 举报
温馨提示
试读
16页
目 录 第一章 课程设计目的 2 第二章 课程设计内容和要求 2 第三章 课程设计分析 3 第四章 算法描述 4 第五章 源代码 8 第六章 运行结果分析 13 第七章 结束语 15 第八章 参考文献 15 第一章 课程设计目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程,为了让大家更好地理解与运用所学知识,提高动手能力,我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识,还要求实习者具备一定的C语言基础和编程能力。 具体说来,这次课程设计主要有两大方面目的。 一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说,所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。 二是通过实习巩固并提高实习者的C语言知识,并初步了解Visual C++的知识,提高其编程能力与专业水平。 第二章 课程设计内容和要求 2.1课程设计内容 该课题要求以邻接表的方式存储图,输出邻接表,并要求实现图的深度、广度两种遍历。
资源推荐
资源详情
资源评论
《数据结构》课程设计
题 目 图的存储与遍历
学生姓名
指导教师
学 院
专业班级
完成时间
目 录
第一章 课程设计目的 2
第二章 课程设计内容和要求 2
第三章 课程设计分析 3
第四章 算法描述 4
第五章 源代码 8
第六章 运行结果分析 13
第七章 结束语 15
第八章 参考文献 15
1
第一章 课程设计目的
本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性
非常强的课程,为了让大家更好地理解与运用所学知识,提高动手能力,我们
进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中
的各方面知识,还要求实习者具备一定的 C 语言基础和编程能力。
具体说来,这次课程设计主要有两大方面目的。
一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍
历》这一课题来说,所要求掌握的数据结构知识主要有:图的邻接表存贮结构
队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、
图的深度优先搜索周游算法实现。
二是通过实习巩固并提高实习者的 C 语言知识,并初步了解 Visual C++的
知识,提高其编程能力与专业水平。
第二章 课程设计内容和要求
2.1 课程设计内容
该课题要求以邻接表的方式存储图,输出邻接表,并要求实现图的深度、
广度两种遍历。
2.1.1 图的邻接表的建立与输出
对任意给定的图(顶点数和边数自定),并且对有向图与无向图都应进行
讨论,根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式
输出邻接表。
2.1.2 图的遍历的实现
图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利
用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)来实
现。首先建立一空队列,从初始点出发进行访问,当被访问时入队,访问完出
队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非
2
递归算法来实现。
2.2 运行环境
该程序的运行环境为 Windows xp 系统,Microsoft Visual C++6.0 版本。
第三章 课程设计分析
3.1 图的存储
本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构,在邻
接表中,对图中每个顶点建立一个单链表,第 i 个单链表中的结点表示依附于
顶点 Vi 的边(对有向图是以顶点 Vi 为尾的弧)。每个结点由 3 个域组成,其中
邻接点域(adjvex)指示与顶点 Vi 邻接的点在图中的位置,链域(nextarc)指
示下一条边或弧的结点;数据域(info)存储和边或弧相关的信息,如权值等。
所以一开始必须先定义邻接表的边结点类型以及邻接表类型,并对邻接表
进行初始化,然后根据所输入的相关信息,包括图的顶点数、边数、是否为有
向,以及各条边的起点与终点序号,建立图的邻接表。此时要分两种情况:有
向图与无向图。对于无向图,一条边的两的个顶点,互为邻接点,所以在存储
时,应向起点的单链表表头插入一边结点,即终点。同时将终点的单链表表头
插入一边结点,即起点。对于有向图,只能向起点的单链表的表头插入一个边
结点,即终点。但不能反过来。至于邻接表的输出,由于不了解 C++中的绘图
操作,故采用 for 语句输出各结点,并配合一些符号完成邻接表的输出。
3.2 图的遍历
3.2.1 图的深度优先遍历
假设初始状态是图中所有顶点未曾被访问,深度优先遍历可以从图的初始
点出发,访问初始点,然后依次从 v 未被访问的邻接点出发深度优先遍历图,
直至图中所有和 v 有路径相通的顶点都被访问到;若此时仍有顶点未被访问到,
则从另一个未被访问的顶点出发,重复上述过程,直至所有点都被访问到为止
这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优
先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被
访问。
具体过程应为:先访问初始点 Vi,并标志其已被访问。此时定义一指向边
结点的指针 p,并建立一个 while()循环,以指针所指对象不为空为控制条件,
当 Vi 的邻接点未被访问时,递归调用深度优先遍历函数访问之。然后将 p 指针
指向下一个边结点。这样就可以完成图的深度优先遍历了。
3.2.2 图的广度优先遍历
广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点 v 出
发,在访问了 v 之后访问它们的邻接点,并使“先被访问的顶点的邻接点”先于
“后被访问的顶点的邻接点的邻接点”被访问,直到图中所有已被访问的顶点的
邻接点都被访问到。若此时图中尙有顶点未被访问,则另选图中一个未曾被访
3
剩余15页未读,继续阅读
资源评论
- workmimi2013-01-07还不错,不过是c语言的,有些不一样
- Jayce-Ye2014-07-07还不错,不过是c语言的,有些不一样
ausatge3
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 海尔H42E10 6i981BTA DH1PY600000 MBOOT usb.bin 程序.zip
- 网盘的功能实现之数据库搭建笔记
- 软件工程与软件测试阶段作业三.doc
- 软件工程中的人工智能辅助设计研究.pptx
- 海尔智能电视刷机数据 H42E07 机编DH1QR000H07 务必确认机编一致 强制刷机 整机USB升级主程序
- 4444444444444444444
- 基于PHP实现响应式创业园区管委会网站.zip
- 安卓手机用作电脑网络摄像头的工具文件
- 海尔智能电视刷机数据 H32E10 机编DH1QX000805 务必确认机编一致 强制刷机 整机USB升级主程序
- ComfyUI AI老照片修复上色工作流
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功