数据结构教学课件（陈倩）第三章 集合、稀疏矩阵和广义表.pptVIP

广义表中的数据元素可以是单元素也可以是子表，其类型不同，用顺序存储结构比较困难，因此通常用链式存储结构来表示。 3.5.2 广义表的存储结构 可以顺序 存储吗？ 广义表的结点结构 （a）子表结点 （b）单元素结点 3.5.2 广义表的存储结构 tag = 1 sublist next tag = 0 data next 利用标志域区分两种不同结点。 单元素结点：包括值域和next指针域； 子表结点：包括sublist和next指针域。 数据结构与算法 Data Structures and Algorithms struct GLNode{ bool tag; union{ ElemType data; GLNode* sublist; }; GLNode* next; } 公用体（联合） 联合中的多种数据类型在内存中共用同一位置，在同一时刻联合只能代表其中的一种数据类型。 结点类型定义如下： false(0)：表示单元素结点； True(1)：表示子表结点。 数据结构与算法 Data Structures and Algorithms 0 e Λ 0 a 1 Λ 0 c 0 b 0 d Λ A=NULL B C A=( ) B=(e) C=(a,(b,c,d)) 数据结构与算法 Data Structures and Algorithms 1 Λ 1 1 Λ 0 e Λ 0 a 1 Λ 0 c 0 b 0 d Λ 1 Λ 0 a 0 b Λ 0 a 1 1 Λ 0 c Λ 1 0 b Λ 0 a D E E=((a,(a,b),((a,b),c))) D=(A,B,C)=(( ),(e), (a,(b,c,d))) 数据结构与算法 Data Structures and Algorithms 1 Λ 0 a 1 Λ 0 c 0 b 0 d Λ A B C A=( ) B=(e) C=(a,(b,c,d)) 1 Λ Λ 0 e Λ 1 Λ 带表头附加结点的广义表的链接存储结构 数据结构与算法 Data Structures and Algorithms 3.5.3 广义表的运算 广义表可看作为是由next域链接起来的单链表。 1. 求广义表的长度 单链表的结构也是一种递归结构。 数据结构与算法 Data Structures and Algorithms int Lenth(GLNode* GL) { if(GL!=NULL) return 1+Lenth(GL-next); else return 0; } 求广义表长度的递归算法如下： 数据结构与算法 Data Structures and Algorithms 2. 求广义表的深度 广义表深度的递归定义： 所有子表中表的最大深度加1，若一个表为空或仅由单元素所组成，则深度为1。 1 Λ 0 a 0 b Λ 0 a 1 1 Λ 0 c Λ 1 0 b Λ 0 a 数据结构与算法 Data Structures and Algorithms 设dep表示任一子表的深度，max表示所有子表中表的最大深度，Depth表示广义表的深度，则有： Depth=max+1 因一个表不包含任何子表时，其深度为1，所以max的初值应为0。 数据结构与算法 Data Structures and Algorithms 下面是求一个广义表深度的算法： int Depth(GLNode* GL) { int max=0; //给max赋初值0 while(GL!=NULL) { if(GL-tag= =true) { int dep=Depth(GL-sublist); if(depmax) max=dep; } GL=GL-next; } return max+1; } 数据结构与算法 Data Structures and Algorithms G=( ( ) , a , ( ( b , c ) , d ) ) 设一个广义表为： 数据结构与算法 Data Structures and Algorithms int