ky5-广义表-数据结构考研课件-大连海事大学.ppt

第五课 广义表 2、特点： 有次序性 有长度 有深度 可递归 可共享 广义表的存储结构 2013 * * * 制作人：荣誉 广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) 1、定义： ① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。 n是表长 在广义表中约定： 讨论：广义表与线性表的区别和联系？ 广义表中元素既可以是原子类型，也可以是列表； 当每个元素都为原子且类型相同时，就是线性表。 一个直接前驱和一个直接后继 ＝表中元素个数 ＝表中括号的重数 自己可以作为自己的子表 可以为其他广义表所共享 特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。 E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表 1）A =( ) 2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C ) 5）E=(a, E) 例1：求下列广义表的长度。 n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 n=3，3个元素都是子表 n=2，a 为原子，E为子表 D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表 A B D C e a b c d ② A=( a , (b, A) ) 例2：试用图形表示下列广义表. （设 代表原子， 代表子表） e ① D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ) A a b ①的长度为3，深度为3 ②的长度为2，深度为∞ 深度＝括号的重数＝ 结点的层数 介绍两种特殊的基本操作： GetHead( L) ——取表头(可能是原子或列表); GetTail(L ) ——取表尾(一定是列表) 。 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)) 由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示 ，通常用链式结构，每个元素用一个结点表示。 1.原子结点：表示原子，可设2个域或3个域，依习惯而选。 value tag=0 标志域 数值域 注意：列表的“元素”还可以是列表，所以结点可能有两种形式 tp atom tag=０ 标志域 　　值域　表尾指针 法2：标志域、值域、表尾指针 指向下一结点 法1：标志域，数值域 tp hp tag=1 标志域 表头指针 表尾指针 2.表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针。 ① A =( ) ^ 1 e 0 ③ C =( a ,( b , c , d ) ) 1 ^ 1 1 a 0 b 0 d 0 c 0 1 ^ 1 例： ② B=( e ) A=NULL 指向子表 指向下一结点 ^ ^ 1 ⑤ E=(a, E) ④ D=( A , B ,C )＝(( ),(e),(a,(b,c,d))) a 0 ^ 1 1 ^ 1 e 0 1 ^ 1 1 ^ 1 1 a 0 b 0 d 0 c 0 1 ^ 1 ^ 1 本章结束 （参见教材P109图） * *