数据结构第8章广义表.ppt_第1页
数据结构第8章广义表.ppt_第2页
数据结构第8章广义表.ppt_第3页
数据结构第8章广义表.ppt_第4页
数据结构第8章广义表.ppt_第5页
已阅读5页，还剩1页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、广义表的基本概念 广义表的存储结构,第8章 广义表,一、广义表,定义:广义表（lists)是 n ( 0 )个元素的有限序列， 记作: LS =(a1, a2, an),其中， ai或是原子 或是一个广义表 n 是广义表的长度,通常用小写表示原子，大写表示广义表。,例： E=( ) L=(a, b) A=(x, L)=(x, (a, b) B=(A, y)=(x, L), y)=(x, (a, b), y) C=(A, B)=(x, (a, b), (x, (a, b), y) D=(a, D)=(a, (a, (a,),特点：（1）广义表的元素可以是子表（广义表）。 （2）一个广义表可以为其

2、他多个广义表共享。 （3）广义表可以是递归表。,注：F=( ( ) )与E=( )的区别 n=1 n=0,广义表的逻辑结构,A=(1, 2 ,3, n) 二维数组A是由n个元素组成的广义表， 其中每个元素是由一列元素组成的子表。,线性结构的推广,例：多维数组就是广义表,A=(1, 2 , 3, m) 二维数组A是由m个元素组成的广义表， 其中每个元素是由一行元素组成的子表。,i=(ai1 aij ain),广义表的基本运算,取表头：HeadLS= a1 取第一元素,例：headA=head(x,L)=x head(a, b ), (c, d)=(a, b),LS =(a1, a2, an),取

3、表尾：TailLS=(a2, an) 由第二个元素到最后一个元素组成的子表,例：tail(a, b, c, d)=(b, c, d) tailA=tail(x, L)=tail(x, (a, b)=( (a, b) ) tail(e)=( ) tailheadtail(a, b), (c, d)=?,求表的深度：DepthLS括号嵌套的最大层数,求表的长度：LengthLS,(d),例：depth(a, (b, c), (d, (e), ( ) )=4,广义表的存储结构,由于广义表中元素可以是原子，也可以是子表，只能采用链方式。 单链表示法：以单链表形式链接各结点。 当元素为原子时，存储其元素

4、值。 当元素为子表时，存储指向子表的指针。,1 元素为子表sublist指向子表,0 元素为原子data存储元素值,typedef struct node int tag; struct node *link; union struct node *sublist; datatype data; element; lists;,结点数据类型,LS=( a, (b, c), ( ), (d, e), f),0 a,1,0 b,0 c,1 ,1,1,0 f,0 d,0 e,单链表示法,1,求广义表的深度 基本思想：依次求出每个元素的深度， 则最大值+1为其表的深度。 其中：原子元素的深度=0 利用递归求出子表的深度,d=0,d=0,d=

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论