452空间开销分析 空间开销分析 结构性开销 存储密度a(≤1)表示数据结构存储的效率 a(存储密度) 数据本身存储量 辅助空间 整个结构占用的存储总量 保存数据结构的逻辑特性 显然a=1-y 方便运算 紧凑结构vs非紧凑结构 y(结构性开销) 辅助结构存储量 叉链表的存储是非紧凑结构 整个结构占用的存储总 张写 空间开销分析 空间开销分析入 根据满二叉树定理:一半的指针是空的 去掉满二叉树叶结点中的指针 ■每个结点存两个指针、一个数据域 (2p)n/2p ■总空间(2p+an 则结构性开销为12(假设p=d) 结构性开销:2pn 如果只在叶结点存数据,dn2 如果p=d,则 在分支结点存储指针,2pn/2=pn 2p(2p+a=2/3 注意:区分叶结点和分支结点又需要额外的算法时间 叔有。轨印当究 张鲁写 前有,聊脂究 回 空间开销分析 453用数组实现完全二叉树 d+可以用两种方法来实现不同的分支结点与叶结点 用 union联合类型定义 顺序方法存储二叉树 使用C+十的子类来分别实现分支结点与叶结点,并采用虚 把所有结点按照一定的次序顺方存储到一片连续的存储单 函数 isLe来区别分支结点与叶结点 早期节省内存资源 使结点在序列中的相互位量反映出二叉树结构的部分信息 利用结点指针的一个空阳位(一个bit)来存蜻点所属的类型 利用指向叶结点的指或者叶结点中的指针域来存储该叶结点的值 ■在存储结构上是线性的,但在逻辑结构上它仍然是 目前,计算机内存资源并不紧张的时候,一般不提倡这种单 纯追求效率,而丧失可读性的做法 二叉树型结构 真大_血单 大息 1010 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 4.5.2 空间开销分析 „ 结构性开销γ „ 辅助空间 „ 保存数据结构的逻辑特性 „ 方便运算 γ = 辅助结构存储量 （结构性开销） 整个结构占用的存储总量 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 空间开销分析 „ 存储密度α (≤1)表示数据结构存储的效率 „ 显然α = 1 - γ „ 紧凑结构 vs 非紧凑结构 „ 二叉链表的存储是非紧凑结构 α = 数据本身存储量 （存储密度） 整个结构占用的存储总量 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 空间开销分析 根据满二叉树定理：一半的指针是空的 „ 每个结点存两个指针、一个数据域 „ 总空间 (2p + d)n „ 结构性开销：2pn „ 如果 p = d, 则 2p/(2p + d) = 2/3 G H E A B C D F I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 空间开销分析 „ 去掉满二叉树叶结点中的指针 (2p) n/2 p (2p) n/2+ dn p + d 则结构性开销为 1/2 （假设p = d） „ 如果只在叶结点存数据, d n/2 在分支结点存储指针，2p n/2 = p n 则结构性开销为 „ pn / (pn + dn / 2) ⇒ 2/3 （假设p = d） „ 注意：区分叶结点和分支结点又需要额外的算法时间 = A B C D E F G H I 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 空间开销分析 „ C+可以用两种方法来实现不同的分支结点与叶结点： „ 用union联合类型定义 „ 使用C++的子类来分别实现分支结点与叶结点，并采用虚 函数isLeaf来区别分支结点与叶结点 „ 早期节省内存资源 „ 利用结点指针的一个空闲位（一个bit）来存储结点所属的类型 „ 利用指向叶结点的指针或者叶结点中的指针域来存储该叶结点的值 „ 目前，计算机内存资源并不紧张的时候，一般不提倡这种单 纯追求效率，而丧失可读性的做法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 4.5.3 用数组实现完全二叉树 „ 顺序方法存储二叉树 „ 把所有结点按照一定的次序顺序存储到一片连续的存储单 元 „ 使结点在序列中的相互位置反映出二叉树结构的部分信息 „ 在存储结构上是线性的，但在逻辑结构上它仍然是 二叉树型结构