零基础学数据结构 第8章 广义表

零基础学数据结构第8章 广义表PPT

第8章 广义表广义表是线性表的推广，也是一种扩展的线性数据结构。广义表 被广泛应用于人工智能等领域的表处理语言 Lisp 中，在 lisp中，广

义表作为一种基本的数据结构，就连程序也表示为一系列的广义表。本章主要给大家介绍广义表的定义、广义表的顺序存储与实现、广 义表的递归算法。 本章重点： 1、广义表的头尾链表表示与算法实现 2、广义表的扩展线性链表表示与算法实现

零基础学数据结构第8章 广义表PPT

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

零基础学数据结构第8章 广义表PPT

8.1 广义表在广义表GL中，a1称为广义表GL的表头(head),其余元素组成的表 (a2,a3,…,an)称为广义表GL的表尾(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…)))。

零基础学数据结构第8章 广义表PPT

8.1 广义表从上述定义和例子可推出广义表的重要结论如下： (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)表示取广义表A的表头元素，tail(A)表示取广义表A的表 尾元素。

零基础学数据结构第8章 广义表PPT

8.1 广义表8.1.2 广义表的抽象数据类型1.数据对象集合 广义表的数据对象集合为{ai|1≤i≤n,ai可以是原子，也可以是 广义表}。例如，A=(a,(b,c))是一个广义表， A中包含两个元素a和

(b,c),第2个元素为子表，包含了2个元素b和c。若把(b,c)看成一个 整体，则a和(b,c)构成了一个线性表，在子表(b,c)的内部，b和c又

构成了线性表。故广义表可看作是线性表的扩展。

零基础学数据结构第8章 广义表PPT

8.1 广义表2.基本操作集合 (1)GetHead(L):求广义表的表头。如果广义表是空表，则返回NULL; 否则，返回指向表头结点的指针。 (2)GetTail(L):求广义表的表尾。如果广义表是空表，则返回NULL; 否则，返回指向表尾结点的指针。 (3)GListLength(L):返回广义表的长度。如果广义表是空表，则返回 0;否则，返回广义表的长度。 (4)GListDepth(L):求广义表的深度。广义表的深度就是广义表中括 号嵌套的层数。如果广义表是空表，则返回1;否则返回广义表的深度。

(5)CopyGList(&T,L):复制广义表。由广义表L复制得到广义表T。复制成功返回1;否则，返回0。

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现8.2.1 广义表的头尾链表存储结构因广义表中有两种元素：原子和子表，所以广义表的链表结点也分 为两种：原子结点和子表结点，其中，子表结点包含3个域：标志域、 指向表头的指针域和指向表尾的指针域。原子结点包含两个域：标志 域和值域。表结点和原子结点的存储结构如图8.1所示。tag=1 hp 表结点 tp tag=0 atom 原子结点

其中，tag=1表示是子表，hp和tp分别指向表头结点和表尾结点， tag=0表示原子，atom用于存储原子的值。

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现我们将广义表的这种存储结构称为头尾链表存储表示。用头尾链法表示的广义 表A=(),B=(a),C=(a,(b,c)),D=(A,B,C),E=(a,b,E)如图8.2所示。A B ^ 1 0 D 1 1 0 a a /\ 1 1 0 b ^ C 1 0 1 1 a ^ ^ 1 1 0 b ^ 1 0 c ^

E

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现广义表的头尾链表存储结构类型描述如下： typedef enum{ATOM,LIST}ElemTag; /*ATOM=0原子，LIST=1子表*/ typedef struct { ElemTag tag; union { AtomType atom; /*AtomType是原子结点的值域*/ struct /*标志位tag用于区分元素是原子还是子表*/

{struct GLNode *hp,*tp; /*hp指向表头，tp指向表尾*/ }ptr; }; }*GList,GLNode;

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现8.2.2 广义表的基本运算(1)求广义表的表头。 GLNode* GetHead(GList L) /*求广义表的表头结点操作*/ { 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; }

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现(2)求广义表的表尾。

GLNode* GeTail(GList L)/*求广义表的表尾*/ { if(!L) { printf(“该广

义表是空表！”); return NULL; } return L->ptr.hp; /*广义表不是空表，返回表尾结点的指针*/ } /*广义表为空表，则返回NULL*/

零基础学数据结构第8章 广义表PPT

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; }

零基础学数据结构第8章 广义表PPT

8.2 广义表的头尾链表表示与实现(4)求广义表的深度。求广义表的深度可利用递归实现。如果广义表

是空表，则返回1。如果是原子，则返回0。如果是一个非空的广义表，递归求每个子表的深度，令p指向表头结点，即L的第一个元素a1(如果 a1是子表),求a1的深度，当求出a1的深度后，然后求L的第2个元素a2

的深度。依次类推，最后返回广义表GL深度。广义表的深度就是广义表中括号的层数。假设广义表为 GL=(a1,a2,a3,…,an),ai可能是原子，也可能是子表，求广义表GL的深

度可以分解为n个子问题，每个子问题就是求ai的深度。如果a …… 此处隐藏：3633字，全部文档内容请下载后查看。喜欢就下载吧 ……