12.广义表

数据结构15.4广义表的定义广义表（又称列表）是线性表的推广。线性表定义为n=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，有时这种限制需要拓宽。例如，某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：（俄罗斯，巴西，（中国国家队，河北，四川），古巴，美国，日本）在这个拓宽了的线性表中，中国国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。数据结构2广义表是n个元素a1,a2,a3,…,an的有限序列，n为它的长度。记作LS=（a1,a2,a3,…,an)。每个ai是LS的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表LS的单元素和子表。当广义表LS非空时，称第一个元素a1为LS的表头（Head），称其余元素组成的表（a2，…，ai，…，an）为LS的表尾（Tail）。显然广义表的定义是递归的。一些例子：A＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）=（（），（e),（a，（b，c，d））)E＝（a，E）一个无限列表=(a,(a,(a,…)))F＝（（））数据结构3广义表是一个多层次的线性结构例如：D=(E,F)其中:E=(a,(b,c))F=(d,(e))DEFa()d()bce数据结构4广义表的结构特点:1)广义表中的数据元素有相对次序；2)广义表的长度定义为最外层包含元素个数；3)广义表的深度定义为所含括弧的重数；“原子”的深度为0，“空表”的深度为14)广义表可以共享；5)广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表LS=(1,2,…,n)均可分解为表头Head(LS)=1和表尾Tail(LS)=(2,…,n)。例如:D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()数据结构5(DEFUNHANOI(abcn)(COND((=n1)(MOVE-DISKac))(T(HANOIacb(-n1))(MOVE-DISKac)(HANOIbac(-n1))))member(X,［X|Tail］).member(X,［Head|Tail］):-member(X,Tail).?-member(a,［a,b,[c,d］]).广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。数据结构6ADTGList{数据对象:D={i=1,2,...,n=0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}数据关系:R1={ei-1,ei|ei-1,ei(-D,2=i=n}基本操作:InitGlist(&L);操作结果:创建空的广义表LCreateGList(&L,S);初始条件:S是广义表的书写形式串操作结果:由S创建广义表LDestroyGlist(&L);初始条件:广义表L存在操作结果:销毁广义表LCopyGlist(&T,L);初始条件:广义表L存在操作结果:由广义表L复制得到广义表T数据结构7GListLength(L);初始条件:广义表L存在操作结果:求广义表L的长度,即元素个数GListDepth(L);初始条件:广义表L存在操作结果:求广义表L的深度GlistEmpty(L);初始条件:广义表L存在操作结果:判断广义表L是否为空GetHead(L);初始条件:广义表L存在操作结果:取广义表L的头数据结构8GetTail(L);初始条件:广义表L存在操作结果:取广义表L的尾InsertFirst_GL(&L,e);初始条件:广义表L存在操作结果:插入元素e作为广义表L的第一元素DeleteFirst_GL(&L,&e);初始条件:广义表L存在操作结果:删除广义表L的第一元素,并用e返回其值Traverse_GL(L,Visit());初始条件:广义表L存在操作结果:遍历广义表L,用函数Visit处理每个元素}ADTGList数据结构9广义表有两个重要的基本操作，即取头操作和取尾操作。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：GetHead（B）＝eGetTail（B）＝（）GetHead（C）＝aGetTail（C）＝（（b，c，d））GetHead（D）＝AGetTail（D）＝（B，C）GetHead（E）＝aGetTail（E）＝（E）GetHead（F）＝（）GetTail（F）＝（）A＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）=（（），（e),（a，（b，c，d））)E＝（a，E）一个无限列表=(a,(a,(a,…)))F＝（（））数据结构105.5广义表的存储结构由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。数据结构11⒈头尾表示法若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。由于广义表中的数据元素既可能是列表也可能是单元素，相应地在头尾表示法中结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则表示该结点为元素结点。其形式定义说明如下：数据结构12typedefenum{ATOM,LIST}ElemTag;//ATOM=0：原子；LIST=1：子表typedefstructGLNode{ElemTagtag;//标志域，用于区分原子结点和表结点union{//元素结点和表结点的联合部分AtomTypeatom;//atom是原子结点的值域struct{structGLNode*hp,*tp；}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾};}*GList;//广义表类型tag=1hptptag=0data表结点原子结点头尾表示法结点结构数据结构131^11^11^11^111^1^1^^0a0d0c0b0a0eBCDEFA=NULLA＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）=（（），（e),（a，（b，c，d））)E＝（a，E）一个无限列表=(a,(a,(a,…)))F＝（（））数据结构14从上述存储结构示例中可以看出，采用头尾表示法容易分清列表中原子或子表所在的层次。例如，在广义表D中，单元素a和e在同一层次上，而单元素b、c、d在同一层次上且比a和e低一层，子表B和C在同一层次上。另外，最高层的表结点的个数即为广义表的长度。例如，在广义表D的最高层有三个表结点，其广义表的长度为3。数据结构15广义表从结构上可以分解成广义表=表头+表尾或者广义表=子表1+子表2+···+子表n因此广义表操作常用递归函数，利用分治法求解。分治法的设计思想为:对于一个输入规模为n的函数或问题，用某种方法把输入分割成k(1k≤n)个子集，从而产生m个子问题，分别求解这m个问题，得出m个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。数据结构16广义表的深度=Max{子表的深度}+1例：求广义表的深度可以直接求解的两种简单情况为：空表的深度=1原子的深度=0将广义表分解成n个子表，分别(递归)求得每个子表的深度。（头尾表示法）数据结构17111L…for(max=0,pp=L;pp;pp=pp-ptr.tp){dep=GlistDepth(pp-ptr.hp);if(depmax)max=dep;}例如:求广义表深度GlistDepth(GlistL)pppp-ptr.hppppppp-ptr.hppp-ptr.hp数据结构18intGlistDepth(GlistL){//返回指针L所指的广义表的深度for(max=0,pp=L;pp;pp=pp-ptr.tp){dep=GlistDepth(pp-ptr.hp);if(depmax)max=dep;}returnmax+1;}//GlistDepthif(!L)return1;if(L-tag==ATOM)return0;数据结构19⒉孩子兄弟表示法广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示原子。在有孩子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为无孩子结点。其形式定义说明如下：数据结构20tag=1hptp表结点原子结点孩子兄弟表示法结点结构tag=1datatptypedefenum{ATOM,LIST}Elemtag;//ATOM=0：单元素；LIST=1：子表typedefstructGLENode{ElemTagtag;//标志域，用于区分原子结点和表结点union{//原子结点和表结点的联合部分AtomTypeatom;//原子结点的值域structGLENode*hp;//表结点的表头指针};structGLENode*tp;//指向下一个结点}*GList;//广义表类型数据结构211^1^^1^0e^1^0a1^0b0c0d^1^11^1^0a1^1^1^^ABCDEFA＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）=（（），（e),（a，（b，c，d））)E＝（a，E）一个无限列表=(a,(a,(a,…)))F＝（（））从图的存储结构示例中可以看出，采用孩子兄弟表示法时，表达式中的左括号“（”对应存储表示中的tag=1的结点，且最高层结点的tp域必为NULL。数据结构22广义线性表多维数组广义表逻辑结构存储结构逻辑结构存储结构⑴数组的定义⑵基本操作⑶ADT定义顺序存储压缩存储特殊矩阵·对称矩阵·三角矩阵·对角矩阵稀疏矩阵按行优先按列优先寻址的计算方法⑴基本概念·广义表定义·表头、表尾·长度、深度⑵ADT定义链接存储转置算法数据结构23256色某类型图像文件结构如下，设计算法将图像旋转90度再存入原文件中2字节类型标识4字节文件大小4字节从文件头到实际的位图数据的偏移字节数4字节图象的宽度（象素）4字节图象的高度（象素）4字节是否压缩及压缩格式4字节实际的图像数据占用的字节数4字节指定本图象实际用到的颜色数256*3字节调色板图象数据（该象素颜色在调色板中的索引值。一个字节表示1个象素）。思考题：数据结构24第六章树和二叉树数据结构25树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。