树型结构 其关系r为层次关系,或称父子关系、上下级关系 图结构 每一个结点可以有多于一个的宜接下级,但是它只能有 唯一的直接上级 根〔root)结点没有父结点 图着限惭:R(,中点相对于前愿和后个数 Q ⊙oooo 物盒啦张促写 北大单张铭写 叔新有,命邮 图结构 数据的存储结构 左图逻辑结构B=(KR),其中 ■映射:逻辑→存储 [A, B. C, D,E, F] ■对于数据逻辑结构(K,r)其中∈R R={r},r={<A,C>,<A, 从K到存储器M的单元的映射:K→M <A, E> <EA>, <B C>, <C, B>, BF>,<F,B>,<C,D>,<D,C, 每一个结点k∈K都对应于唯一的区域c∈M <C, P <F, O, <D, F>,<F,D>, 关系元组(k1,k2)∈r(k1k2∈K映射为 <E, F <FE> 存储单元的地址指向关系 四种存储结构:顺序、链接、索引、散列 可以筒写为 空间时间权衡 r=H(A, C)(A, E),(B, C), (B, F). ■尽量少的空间,尽量快的运算速度 (C, D),(C F (D,F)(E, FI 北真大脆张写 叔新有,量究 顺序存储—数组 链接( inked)的方法 的指向:结点间逻辑后继关系 ■两部分:数据字段、指针字段 ■链索:多个相关结点的依次链接就会形成 把一組结点存储在按地址相邻的顺序存储单元里 存储密度;p=nxE/n(P+E)=E/(P+E) 结点间的逻辑后能关系用存储单元的自然顺序关系来表达 紧凑存储结构 紧凑性可以用存储密度来度量 a…一a 存储密度(≤1)=数本身存储量/整个构占用存健量 单链 First Last 北真大学张铭编写 聊张帖写 权新有,究8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 树型结构 „ 其关系r为层次关系，或称‘父子关系’、‘上下级关系’ „ 每一个结点可以有多于一个的‘直接下级’，但是它只能有 唯一的‘直接上级’。 „ 根（root）结点没有父结点 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 图结构 有 向 图 图：B={K, R}, R={r}, K中结点相对于r前驱和后继个数 都没有限制。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 图结构 无 向 图 左图逻辑结构B=(K, R) ，其中 K＝ ｛A,B,C,D,E,F} R = {r}，r = {<A, C>,<C,A>, <A,E>,<E,A>, <B,C>,<C,B>, <B,F>,<F,B>, <C,D>,<D,C>, <C,F>,<F,C>, <D,F >,<F,D>, <E,F>,<FE>} 可以简写为: r = {(A, C), (A,E), (B,C), (B,F), (C,D), (C,F),(D,F ), (E,F)} 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 数据的存储结构 „ 映射：逻辑 → 存储 „ 对于数据逻辑结构（ K , r ）,其中r∈R „ 从K到存储器M的单元的映射：K→M „ 每一个结点k∈K都对应于唯一的区域c∈M。 „ 关系元组（k1 , k2）∈r（k1, k2∈K映射为 存储单元的地址指向关系 „ 四种存储结构：顺序、链接、索引、散列 „ 空间时间权衡 „ 尽量少的空间，尽量快的运算速度 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 „ 把一组结点存储在按地址相邻的顺序存储单元里 „ 结点间的逻辑后继关系用存储单元的自然顺序关系来表达 „ 紧凑存储结构 „ 紧凑性可以用‘存储密度’来度量： „ 存储密度(≤ 1) =数据本身存储量/整个结构占用存储量 顺序存储——数组 01 2 3 4 5 6 7 S: 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 链接（linked）的方法 „ 指针的指向：结点间逻辑后继关系 „ 两部分: 数据字段、指针字段 „ 链索：多个相关结点的依次链接就会形成 „ 存储密度：ρ= n×E /n(P+E) = E /(P+E) a1 an First Last 单链 表