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-

最近更新

幼儿园说课稿大班数学锦集7篇 23页

幼儿园小班幼儿教学总结八篇(精选8篇) 18页

幼儿园中班圣诞节活动总结(通用4篇) 5页

工程技术辞职报告(精选6篇) 8页

小狗四年级的作文(精选5篇) 4页

小学我喜欢冬天作文400字(通用5篇) 4页

对对联的作文(通用3篇) 5页

实用的财务工作计划集锦七篇(精选7篇) 11页

定格在记忆中的画面作文(通用3篇) 4页

学校趣味运动会活动方案(精选2篇) 6页

妇联年终工作总结(通用5篇) 15页

大学生机械实习报告(通用2篇) 4页

城南旧事读后感(精选4篇) 3页

因个人原因的辞职报告(通用5篇) 7页

后勤工作计划(通用2篇) 4页

半年个人工作总结(精选15篇) 40页

动物音乐会作文(精选8篇) 7页

初中数学教师年度考核个人总结(精选2篇) 5页

出纳实习周记(通用3篇) 16页

写哥哥的作文(通用14篇) 14页

关于七月的句子(精选6篇) 14页

公司员工个人辞职报告(精选7篇) 10页

会计岗位社会实践报告(通用6篇) 16页

仓库年终总结(通用11篇) 17页

中考优秀满分作文(通用4篇) 5页

个人求职信(精选12篇) 14页

万圣节活动总结(通用11篇) 11页

【精选】初中生活作文300字合集八篇(通用8篇.. 6页

【精华】幼儿园大班音乐教案锦集8篇 21页

【热门】初中生活作文汇总四篇(精选4篇) 6页