1 / 20
文档名称:

数据结构第15讲 PPT课件.ppt

格式:ppt   页数:20页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构第15讲 PPT课件.ppt

上传人:小马皮皮 2015/10/9 文件大小:0 KB

下载得到文件列表

数据结构第15讲 PPT课件.ppt

相关文档

文档介绍

文档介绍:数据结构——第15讲
主讲:张华杰
Napoleonz@
0371-7657211
第15讲树的计数 图的基本概念和存储表示
章节范围:
上次课的内容
Huffman树—最优二叉树
概念: 路径长度、树的路径长度、结点的带权路径长度、树的带权路径长度、最优树、最优二叉树(Huffman树)、前缀编码、Huffman编码
Huffman树的特点:无度为1的结点
Huffman树的构造算法
Huffman编码与译码
树的高级话题
树与等价问题
集合的表示----双亲表示法表示的树
回溯法与树的遍历
求含n个元素的集合的幂集----依次对集合中元素“取”或“舍”
3-
树的计数
图的定义与术语
图的存储结构
4-
树的计数问题 具有n个结点的不同形态的树有多少棵?
二叉树T和T՛相似
二者均为空树,或
二者均不为空树,且它们的左右子树分别相似
二叉树T和T՛等价
二者相似,且
所有对应结点上的数据元素均相同
二叉树的计数问题 具有n个结点、互不相似的二叉树的数目bn
树的计数(1)
5-
树的计数(2)
二叉树的计数问题的另一种考虑角度
依据:已知二叉树的结点的先序序列和中序序列,能唯一确定一棵二叉树。(为什么?)
假设:二叉树的 n 个结点从1到n 加以编号,且其先序序列为1,2,…, n
不同形态的二叉树的数目先序序列均为1,2,…, n的二叉树所能得到的中序序列的数目 中序遍历的过程:一个结点进栈和出栈的过程 二叉树的形态确定了其结点的进栈和出栈的顺序,也确定了其结点的中序序列。
具有n 个结点的树的数目tn=bn-1 依据:森林与二叉树的相互转换
6-
重点:图在邻接矩阵和邻接表上的遍历算法及其应用
难点:求图的最小生成树、最短路径、拓扑排序等算法及其应用、性能分析
第七章图
第七章图
图的定义和术语
图的存储结构
图的遍历
图的连通性问题
有向无环图及其应用
最短路径
8-
图的定义和术语(1)
图的定义
图是由顶点集合(vertex)及顶点之间的关系集合组成的一种
数据结构。G = (V, {E}) V-顶点集,E-关系的集合
顶点之间的关系是任意的(m : n)
顶点之间的关系是否有方向性:有向图、无向图
无向图:边(v,w) ∊ E (v,w ∊V),v与w互为邻接点,边( v, w )依附于顶点v和w,或者说边( v, w )和顶点v, w相关联。 顶点v 的度是和v相关联的边的数目,记为TD(v) 。
有向图:弧<v,w> ∊ E (v,w ∊V),w为弧头, v为弧尾; 顶点v 邻接到顶点w,顶点w 邻接自顶点v,弧< v, w >和顶点v、w相关联。 顶点v 的入度是以v 为弧头的弧的数目,记为ID(v); v 的出度是以v为弧尾的弧的数目,记为OD(v); v 的度是TD(v) = ID(v) + OD(v)。
9-
图的定义和术语(2)
路径与连通性
路径、简单路径、回路(环)、简单回路
顶点之间的连通性、无向连通图、有向强连通图
G1: V1V3V4V1V2 是从V1 到V2 的路径,不是简单路径; V1V2是简单路径; V1V3V4V1V3V4V1是环,不是简 单环; V1V3V4V1是简单环。 ID(V1)=1, OD(V1)=2, TD(V1)=3 V1和V4是连通的;从V1到V2是连通的, 但从V2到V1是不连通的。 G1不是强连通图
G2: V1V2V3V5V2 是V1和V2间的路径, 但不是简单路径;V1V2是简单路径; V2V3V5V2V3V5V2是环,但不是简单环
V2V3V5V2是简单环。TD(V1)=2 V1和V4是连通的; G2是连通图
V1
V3
V2
V4
V1
V2
V3
V5
V4
G1
G2
10-

最近更新

音乐生学生实习周记 2页

题西林壁古诗词意思 3页

餐桌前的谈话初一500字 2页

高三新生如何制定学习计划 3页

高中数学学习如何适应 4页

高层办公楼工程质量监督制度 4页

高级中学行政领导值周值日制度 2页

孟子第三讲:德行 38页

黑龙江省伊春市宜春东煌外语学校2020年高三历.. 8页

高考冲刺励志口号(精选15篇) 23页

高中历史教师个人工作总结(精选7篇) 16页

饭店寒假社会实践(通用11篇) 22页

面试英语口语自我介绍(通用4篇) 3页

销售团队工作计划(精选15篇) 40页

铁路实习生自我鉴定(通用6篇) 21页

酒店保安工作计划(通用7篇) 10页

黑龙江省哈尔滨市临江中学2022年高一英语上学.. 4页

调查报告作文(精选7篇) 14页

试用期自我述职报告(精选5篇) 8页

西游记读书笔记作文(通用4篇) 4页

英语学期教学工作计划(通用7篇) 16页

股权转让协议书(通用3篇) 9页

置业顾问实习总结(通用15篇) 50页

黑龙江省哈尔滨市宾县第一中学2020-2021学年高.. 9页

黑龙江省哈尔滨市尚志中学2020年高三语文月考.. 11页

第一次月考优秀作文(精选4篇) 5页

黑龙江省哈尔滨市振华中学高一英语月考试卷含.. 4页

社区卫生服务工作计划(通用8篇) 17页

黑龙江省哈尔滨市海城中学高一化学下学期期末.. 4页

黑龙江省哈尔滨市是第二十一中学2021年高三语.. 25页