数据结构第五章.pptVIP

* 介绍两种特殊的基本操作： GetHead( L) ——取表头(可能是原子或列表); GetTail(L ) ——取表尾(一定是列表) 。 广义表的抽象数据类型定义见教材P107-108 * 1. GetTail【(b, k, p, h)】＝ ; 2. GetHead【( (a,b), (c,d) )】＝ ; 3. GetTail【( (a,b), (c,d) )】＝ ; 4. GetTail【 GetHead【((a,b),(c,d))】】＝ ; 例：求下列广义表操作的结果（严题集5.10②） (k, p, h) （b） (a,b) 5. GetTail【（e）】＝ ; 6. GetHead 【 ( ( ) )】＝ . 7. GetTail【 ( ( ) ) 】＝ . ( ) (a,b) ( ) ( ) ((c,d)) * 5.5 广义表的存储结构 由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示 ，通常用链式结构，每个元素用一个结点表示。 链式存储结构: 1.表头表尾链存储结构 有两类结点：表结点和单元素结点。 表结点 单元素结点 tag标志域，0表示结点为单元素结点，1表示为表结点； hp：表头指针域； tp：表尾指针域； data： 值域。 tag=1 hp tp tag=0 data 标志域 表头指针 表尾指针 指向子表 指向下一结点 * ① A =( ) ^ 1 0 e ③ C =( a ,( b , c , d ) ) 1 ^ 1 1 0 a 0 b 0 d 0 c 1 ^ 1 例： ② B=( e ) A=NULL ^ ^ 1 * ⑤ E=(a, E) ④ D=( A , B ,C )＝(( ),(e),(a,(b,c,d))) 0 a ^ 1 1 ^ 1 0 e 1 ^ 1 1 ^ 1 1 0 a 0 b 0 d 0 c 1 ^ 1 ^ 1 （参见教材P109图） 这种存储结构的特点是： 最上层的表结点数即为广义表的长度； 层次清楚； 表结点数目多，与广义表中括号对的数目不匹配。 5.5 广义表的存储结构 2. 同层结点链存储结构 有两类结点：表结点和单元素结点。 tp为链接同层下一结点的指针域，其它域的含义同 表头表尾链结构。 tag =1 hp tp tag =0 atom tp 表接点 原子接点 * 数据结构课程的内容 * 第5章 数组和广义表（Arrays Lists） ① 元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。 ② 所有数据元素仍属同一数据类型。 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 数组和广义表的特点：一种特殊的线性表 * 5.1 数组的定义 数组： 由一组名字相同、下标不同的变量构成 注意： 本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。 答：对的。因为： ① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。 讨论：“数组的处理比其它复杂的结构要简单”，对吗？ * 二维数**组的特点： 一维数组的特点： 1个下标，ai 是ai+1的直接前驱 2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束： 一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。 N维数组的特点： n个下标，每个元素受到n个关系约束 一个n维数组可以看成是由若干个n－1维数组组成的线性表。 a11 a12 … a1n a21 a22