广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案.doc

6 广义表6.1 广义表的定义广义表（lists）又称列表，是线性表的推广，广义表是n (n0) 个元素（子表）a1 , a2 , an 组成的有限序列，一般记作： ls （ a1 , a2 , an ）ls是广义表的名字，n为其表的长度其中ai或者是原子(单个元素)或者是一个广义表，分别称为广义表ls的单元素和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示单元素。广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表的概念。例如：e=( ) e是一个空表，其长度为0。l=(a, b) l是长度为2的列表，它的两个元素都是原子，因此它是一个线性表。a=(x, l)=(x, (a, b) a是长度为2的列表，第一个元素是原子x，第二个元素是子表lb=(a, y)=(x, (a , b), y) b是长度为2的列表，第一个元素是子表a，第二个元素是原子yc=(a, b)=(x, (a, b) , (x, (a, b), y) c的长度为2，两个元素都是子表。d=(a, d)=(a, (a, (a, (.) ) ) ) d的长度为2，第一个元素是原子，第二元素是d自身。展开后，它是一个无限列表。一个表的深度是指表展开所含括号的层数，例如，表a的深度为2，表d的深度为。值得注意的是广义表 ( ) 和 ( ) 不同，前者是空表，长度n=0；后者长度n=1，它有一个元素是空表，可分解得到表头和表尾均是空表( )。广义表的特点： （1）列表可以是递归的，如表d是它本身元素的子表。 （2）列表是多层次的结构，表中的元素可以是子表，子表的元素还可以是子表， （3）列表可以为其它列表所共享，如上例中，表a和表b是表c的子表。6.2 广义表的存储结构由于广义表中的元素可以有不同的结构，单元素或子表，因此难以用顺序存储结构表示，通常采用链式存储结构。结点的结构可以这样设计：tagdata/hplink其中，tag是标志域，若tag0，则第二个域中为data，存储单元素；若tag1，则第二个域中为hp，存储指向子表的指针。link为指向同一层下一个结点的指针。【例6.2.1】 l (a,(b),a,(a,(c),c),d)10a10a10b11000d0cac【例6.2.2】在一个广义表（不共享）中查找某元素。 输入：第一行：广义表，如：(a,(b),a,(a,(c),c),d) 第二行：要查找的元素，如：d 输出：广义表中有该元素，则输出：yes否则输出: no参考程序 program gyb; type pointer=node;procedure find(p:pointer);begin if pnil then if p.tag=0 then begin if p.data=c then begin t:=true; exit; end else find(p.link); end else begin find(p.hp); find(p.link); end;end;begin readln(q); readln(c); i:=1; t:=false; creat(head); find(head); if t then write(yes) else write(no);end. node=record link:pointer; case tag:0.1 of 0:(data:char); 1:(hp:pointer); end; var i:integer; q:string; c:char; t:boolean; head:pointer; procedure creat(var p:pointer); var x:char;begin x:=qi; i:=i+1; case x of (:begin new(p); p.tag:=1; creat(p.hp); creat(p.link); end; a.z