零基础学数据结构广义表.pptx

《零基础学数据结构广义表.pptx》由会员分享，可在线阅读，更多相关《零基础学数据结构广义表.pptx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、8.1 广义表 8.1.1 什么是广义表 广义表，也称为列表（lists），是由n个类型相同的数据元素(a1,a2,a3,an)组成的有限序列。其中，广义表中的元素ai可以是单个元素，也可以是一个广义表。通常，广义表记作：GL=(a1,a2,a3,an)。其中，GL是广义表的名字，n是广义表的长度。如果广义表中的ai是单个元素，则称ai是原子。如果广义表中的ai是一个广义表，则称ai是广义表的子表。习惯上用大写字母表示广义表的名字，用小写字母表示原子。第1页/共28页8.1 广义表 在广义表GL中，a1称为广义表GL的表头（head），其余元素组成的表(a2,a3,an)称为广义表GL的表尾（

2、tail）。广义表是一个递归的定义，因为在描述广义表时又用到了广义表的概念。下面是一些广义表的例子。（1）A=()，广义表A是长度为0的空表。（2）B=(a)，B是一个长度为1且元素为原子的广义表（其实就是前面讨论过的一般的线性表）。（3）C=(a,(b,c)，C是长度为2的广义表。其中，第1个元素是原子a，第2个元素是一个子表(b,c)。（4）D=(A,B,C)，D是一个长度为3的广义表，这3个元素都是子表，第1个元素是一个空表A。（5）E=(a,b,E)，E是一个长度为3的递归广义表，相当于 E=(a,b,(a,b,(a,b,(a,b,(a,b)。第2页/共28页8.1 广义表 从上述定义

3、和例子可推出广义表的重要结论如下：（1）广义表的元素既可以是原子，也可以是子表，子表的元素可以是元素，也可以是子表。广义表的结构是一个多层次的结构。（2）一个广义表还可以是另一个广义表的元素。例如，A、B和C是D的子表，在表D中不需要列出A、B和C的元素。（3）广义表可以是递归的表，即广义表可以是本身的一个子表。例如，E就是一个递归的广义表。任何一个非空广义表的表头可以是一个原子，也可以是一个广义表，而表尾一定是一个广义表。例如：head(A)=()，tail（A）=()，head(C)=a,tail(C)=(b,c)，head(D)=A，tail(D)=(B,C)其中，head(A)表示取广

4、义表A的表头元素，tail(A)表示取广义表A的表尾元素。第3页/共28页8.1 广义表8.1.2 广义表的抽象数据类型 1数据对象集合 广义表的数据对象集合为ai|1in，ai可以是原子，也可以是广义表。例如，A=(a,(b,c)是一个广义表，A中包含两个元素a和(b,c)，第2个元素为子表，包含了2个元素b和c。若把(b,c)看成一个整体，则a和(b,c)构成了一个线性表，在子表(b,c)的内部，b和c又构成了线性表。故广义表可看作是线性表的扩展。第4页/共28页8.1 广义表 2基本操作集合 （1）GetHead(L)：求广义表的表头。如果广义表是空表，则返回NULL；否则，返回指向表头

5、结点的指针。（2）GetTail(L)：求广义表的表尾。如果广义表是空表，则返回NULL；否则，返回指向表尾结点的指针。（3）GListLength(L)：返回广义表的长度。如果广义表是空表，则返回0；否则，返回广义表的长度。（4）GListDepth(L)：求广义表的深度。广义表的深度就是广义表中括号嵌套的层数。如果广义表是空表，则返回1；否则返回广义表的深度。（5）CopyGList(&T,L)：复制广义表。由广义表L复制得到广义表T。复制成功返回1；否则，返回0。第5页/共28页8.2 广义表的头尾链表表示与实现 8.2.1 广义表的头尾链表存储结构 因广义表中有两种元素：原子和子表，所

6、以广义表的链表结点也分为两种：原子结点和子表结点，其中，子表结点包含3个域：标志域、指向表头的指针域和指向表尾的指针域。原子结点包含两个域：标志域和值域。表结点和原子结点的存储结构如图8.1所示。其中，tag=1表示是子表，hp和tp分别指向表头结点和表尾结点，tag=0表示原子，atom用于存储原子的值。第6页/共28页8.2 广义表的头尾链表表示与实现我们将广义表的这种存储结构称为头尾链表存储表示。用头尾链法表示的广义表A=()，B=(a)，C=(a,(b,c)，D=(A,B,C)，E=(a,b,E)如图8.2所示。第7页/共28页8.2 广义表的头尾链表表示与实现 广义表的头尾链表存储结

7、构类型描述如下：typedef enumATOM,LISTElemTag;/*ATOM=0 原子，LIST=1子表*/typedef struct ElemTag tag;/*标志位tag用于区分元素是原子还是子表*/union AtomType atom;/*AtomType 是原子结点的值域*/struct struct GLNode*hp,*tp;/*hp指向表头，tp指向表尾*/ptr;*GList,GLNode;第8页/共28页8.2 广义表的头尾链表表示与实现8.2.2 广义表的基本运算（1）求广义表的表头。GLNode*GetHead(GList L)/*求广义表的表头结点操作*

8、/GLNode*p;if(!L)/*如果广义表为空表，则返回NULL*/printf(“该广义表是空表！”);return NULL;p=L-ptr.hp;/*将广义表的表头指针赋值给p*/if(!p)printf(“该广义表的表头是空表”);else if(p-tag=LIST)printf(“该广义表的表头是非空的子表。”);else printf(“该广义表的表头是原子。”);return p;第9页/共28页8.2 广义表的头尾链表表示与实现（2）求广义表的表尾。GLNode*GeTail(GList L)/*求广义表的表尾*/if(!L)/*广义表为空表，则返回NULL*/print

9、f(“该广义表是空表！”);return NULL;return L-ptr.hp;/*广义表不是空表，返回表尾结点的指针*/第10页/共28页8.2 广义表的头尾链表表示与实现（3）求广义表的长度。求广义表的长度只需要沿着表尾指针tp查找下去，统计子表个数，直到tp为NULL为止。如果广义表是空表，则广义表的长度为0。否则，将指针p指向结点的表尾指针，统计广义表的长度。int GListLength(GList L)int length=0;while(L)/*如果广义表非空，则将p指向表尾指针，统计表的长度*/L=L-ptr.tp;length+;return length;第11页/共2

10、8页8.2 广义表的头尾链表表示与实现 （4）求广义表的深度。求广义表的深度可利用递归实现。如果广义表是空表，则返回1。如果是原子，则返回0。如果是一个非空的广义表，递归求每个子表的深度，令p指向表头结点，即L的第一个元素a1（如果a1是子表），求a1的深度，当求出a1的深度后，然后求L的第2个元素a2的深度。依次类推，最后返回广义表GL深度。广义表的深度就是广义表中括号的层数。假设广义表为GL=(a1,a2,a3,an)，ai可能是原子，也可能是子表，求广义表GL的深度可以分解为n个子问题，每个子问题就是求ai的深度。如果ai是原子，则深度为0；如果ai是子表，则继续求ai的深度。广义表GL

11、的深度为所有元素ai的深度的最大值加1。根据定义，空表的深度为1。第12页/共28页8.2 广义表的头尾链表表示与实现求广义表的深度的算法实现如下。int GListDepth(GList L)int max,depth;GLNode*p;if(!L)/*如果广义表为空，则返回1*/return 1;if(L-tag=ATOM)/*如果广义表是原子，则返回0*/return 0;for(max=0,p=L;p;p=p-ptr.tp)/*逐层处理广义表*/depth=GListDepth(p-ptr.hp);if(maxtag=L-tag;if(L-tag=ATOM)/*复制原子*/(*T)-a

12、tom=L-atom;else/*递归复制子表*/CopyList(&(*T)-ptr.hp),L-ptr.hp);CopyList(&(*T)-ptr.tp),L-ptr.tp);第15页/共28页8.2 广义表的头尾链表表示与实现8.2.3 广义表应用举例（采用头尾链表存储结构）【例8_1】设广义表采用头尾链表存储结构，编写算法，建立一个广义表，并求出广义表的长度、深度和原子个数。分析：主要考察大家对广义表的头尾链表存储结构的理解与基本操作。因为广义表表是递归定义的，所以可以使用递归的方法创建广义表、求广义表的长度、深度和原子个数。第16页/共28页8.3 广义表的扩展线性链表表示与实现

13、8.3.1 广义表的扩展线性链表存储 采用扩展线性链表表示的广义表也包含两种结点：表结点和原子结点，这两种结点都包含3个域。其中，表结点由标志域tag、表头指针域hp和表尾指针域tp构成，原子结点由标志域、原子的值域和表尾指针域构成。标志域tag用来区分当前结点是表结点还是原子结点，当tag=0时为原子结点，tag=1时为表结点，hp和tp分别指向广义表的表头和表尾，atom用来存储原子结点的值。扩展性链表的结点结构如图8.5所示。第17页/共28页8.3 广义表的扩展线性链表表示与实现 例如，A=()，B=(a)，C=(a,(b,c)，D=(A,B,C)，广义表D的扩展性链表存储结构如图8.

14、6所示。第18页/共28页8.3 广义表的扩展线性链表表示与实现广义表的扩展性链表存储结构的类型定义描述如下：typedef enumATOM,LISTElemTag;/*ATOM=0，表示原子，LIST=1，表示子表*/typedef structElemTag tag;/*标志位tag用于区分元素是原子还是子表*/union AtomType atom;/*AtomType是原子结点的值域，用户自己定义类型*/struct GLNode*hp;/*hp指向表头*/ptr;struct GLNode*tp;/*tp指向表尾*/*GList,GLNode;第19页/共28页8.3 广义表的扩展

15、线性链表表示与实现 8.3.2 广义表的基本运算（1）求广义表的表头。GLNode*GetHead(GList L)GLNode*p;p=L-ptr.hp;/*将广义表的表头指针赋值给p*/if(!p)/*如果广义表为空表，则返回NULL*/printf(“该广义表是空表！”);return NULL;else if(p-tag=LIST)printf(“该广义表的表头是非空的子表。”);else printf(“该广义表的表头是原子。”);return p;第20页/共28页8.3 广义表的扩展线性链表表示与实现 （2）求广义表的表尾。GLNode*GeTail(GList L)GLNode

16、*p,*tail;p=L-ptr.hp;if(!p)/*如果广义表为空表，则返回NULL*/printf(“该广义表是空表！”);return NULL;tail=(GLNode*)malloc(sizeof(GLNode);/*生成tail结点*/tail-tag=LIST;/*将标志域置为LIST*/tail-ptr.hp=p-tp;/*将tail的表头指针域指向广义表的表尾*/tail-tp=NULL;/*将tail的表尾指针域置为空*/return tail;/*返回指向广义表表尾结点的指针*/第21页/共28页8.3 广义表的扩展线性链表表示与实现（3）求广义表的长度。int GLi

17、stLength(GList L)int length=0;/*初始化化广义表的长度*/GLNode*p=L-ptr.hp;while(p)/*如果广义表非空，则将p指向表尾指针，统计表的长度*/length+;p=p-tp;return length;第22页/共28页8.3 广义表的扩展线性链表表示与实现 （4）求广义表的深度。如果广义表是空表，即L-tag=LIST&L-ptr.hp=NULL，则返回1。如果是原子，即L-tag=ATOM，则返回0。如果是一个非空的广义表，则递归调用GlistDepth函数求广义表的深度。先用头指针域找到下一层的子表，如果该层还有子表，则继续利用头指针域

18、找到下一层，直到该层次结点为原子或者是空表，返回到上一层，并返回所求深度值。然后在该层中利用表尾指针找到该表的表尾，继续利用表头指针进行扫描，重复执行以上操作，直到所有层都返回。第23页/共28页8.3 广义表的扩展线性链表表示与实现求广义表的深度的算法实现如下。int GListDepth(GList L)int max,depth;GLNode*p;if(L-tag=LIST&L-ptr.hp=NULL)/*广义表为空，返回1*/return 1;if(L-tag=ATOM)/*广义表是原子，返回0*/return 0;p=L-ptr.hp;for(max=0;p;p=p-tp)/*逐层处

19、理广义表*/depth=GListDepth(p);if(maxtag=L-tag;if(L-tag=ATOM)/*复制原子*/(*T)-ptr.atom=L-ptr.atom;elseCopyList(&(*T)-ptr.hp),L-ptr.hp);/*递归复制表头*/if(L-tp=NULL)(*T)-tp=L-tp;elseCopyList(&(*T)-tp),L-tp);/*递归复制表尾*/第25页/共28页8.3 广义表的扩展线性链表表示与实现8.3.3 广义表应用举例（扩展线性链表存储结构）【例8_2】编写一个算法，判断两个广义表是否相等（采用扩展线性链表存储结构）。两个广义表相等

20、的含义是指两个广义表具有相同的结构，对应原子结点的数据域值也相等。分析：判定两个广义表是否相等的递归模型如下：第26页/共28页8.4 小结 与数组一样，广义表也是一种扩展的线性表。广义表是由n个相同数据类型的数据元素(a0,a1,a2,an-1)组成的有限序列。由于广义表中的数据元素既可以是原子，也可以是广义表。广义表的链式存储结构有两种：广义表的头尾链表存储表示和广义表的扩展线性链表存储表示。广义表的基本运算包括广义表的创建、求广义表的表头和表尾操作、广义表的深度和长度及复制广义表。广义表的深度指的是括号的嵌套层数。广义表的长度指的是最外层元素的个数。例如，广义表D=(a,b),(),(a,(b,c,d),(a,e)的长度为4，深度为3。第27页/共28页感谢您的观看！第28页/共28页