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

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 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;


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案_学科竞赛_高中教育_教育专区。§1 §1.1 什么是数据结构 概论 数据结构(Data ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案_学科竞赛_高中教育_教育专区。§4 §4.1 串的匹配 串 子串的定位操作称为串的模式匹配,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案_学科竞赛_高中教育_教育专区。§2 §2.1 线性表的定义及其基本运算 线性表 线性表是...
广东省汕头市金山中学高中信息技术竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术竞赛班数据结构专项培训教程04串教案_小学作文_小学教育_教育专区。§4 串§4.1 串的匹配 子串的定位操作称为串的模式匹配, 是...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_学科竞赛_高中教育_教育专区。§3 §3.1 栈 栈和队列 栈(stack)是一种仅限于在...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 08图_学科竞赛_高中教育_教育专区。信息学奥赛,NOIP,信息学 ...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 01数据结构概论_学科竞赛_高中教育_教育专区。金山中学计算机竞赛班教程·数据结构与算法...
...汕头市金山中学信息学竞赛班数据结构专项培训教程—...
【全国百强校】广东省汕头市金山中学信息竞赛班数据结构专项培训教程—— 07树_学科竞赛_高中教育_教育专区。金山中学计算机竞赛班教程·数据结构与算法设计 §7§...
广东省汕头市金山中学高中信息技术 pascal教程06 第六...
广东省汕头市金山中学高中信息技术 pascal教程06 第六课 基本语句(四)教案_其它课程_高中教育_教育专区。第六课 基本语句(四)§6.1 while 语句 其一般形式: ...
更多相关标签: