当前位置:首页 >> 学科竞赛 >>

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


§6
§6.1 广义表的定义

广义表

广义表 (Lists) 又称列表, 是线性表的推广, 广义表是 n (n≥0) 个元素 (子表) 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,第二个元素是子表 L B=(A, y)=((x, (a , b)), y) B 是长度为 2 的列表,第一个元素是子表 A,第二个元素 是原子 y C=(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 广义表的存储结构

由于广义表中的元素可以有不同的结构,单元素或子表,因此难以用顺序存储结构表示, 通常采用链式存储结构。 结点的结构可以这样设计: tag data/hp link

其中,tag 是标志域,若 tag=0,则第二个域中为 data,存储单元素;若 tag=1,则第二 个域中为 hp,存储指向子表的指针。link 为指向同一层下一个结点的指针。

【例 6.2.1】 L =((a,(b)),a,((a,(c)),c),d) 1 0 a 0 a 1 ^ 0 b ^ 1 1 0 a 0 d ^ 0 c ^ 1 ^ 0 c ^ 【例 6.2.2】在一个广义表(不共享)中查找某元素。 输入:第一行:广义表,如:((a,(b)),a,((a,(c)),c),d) 第二行:要查找的元素,如:d 输出:广义表中有该元素,则输出:Yes 否则输出: No [参考程序] program gyb; type pointer=^node; node=record procedure find(p:pointer); link:pointer; begin case tag:0..1 of if p<>nil then 0:(data:char); if p^.tag=0 1:(hp:pointer); then begin end; if p^.data=c var i:integer; Q:string; then begin c:char; t:boolean; t:=true; head:pointer; exit; procedure creat(var p:pointer); end var x:char; else find(p^.link); begin end x:=Q[i]; i:=i+1; else begin case x of find(p^.hp); '(':begin find(p^.link); new(p); p^.tag:=1; end; creat(p^.hp); end; creat(p^.link); end; Begin 'a'..'z':begin readln(Q); new(p); p^.tag:=0; readln(c); p^.data:=x; i:=1; creat(p^.link); t:=false; end; creat(head); ',':creat(p); find(head); ')':p:=nil; if t then write('Yes') end; else write('No'); End.

end;


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市潮阳区 | 广东省汕头市潮南区 | 广东省汕头市 | 广东省汕头市邮编 | 广东省汕头市金平区 | 广东省汕头市澄海区 | 广东省汕头市区号 |