7.1 广义表的概念 广义表是n（n≥0）个数据元素组成的序列，其中每个数据元素或是单个数据元素（简称原子），或仍然是一个广义表 。

Presentation on theme: "7.1 广义表的概念 广义表是n（n≥0）个数据元素组成的序列，其中每个数据元素或是单个数据元素（简称原子），或仍然是一个广义表 。"— Presentation transcript:

1 7.1 广义表的概念 广义表是n（n≥0）个数据元素组成的序列，其中每个数据元素或是单个数据元素（简称原子），或仍然是一个广义表 。
广义表可以看作是线性表的推广，但如果从原子数据元素的角度看，一个数据元素有多个后继原子数据元素，就属于下一章要讨论的树型结构。所以，广义表本质上是非线性结构。

2 一个广义表通常用一对圆括号括起来，这样当这个广义表中的某个数据元素又是一个广义表时，就可以再用一对括号括起来。广义表中的原子数据元素通常用小写字母表示，而广义表通常用大写字母表示。从结构上看一个广义表对应了一棵树。例如，设有如下广义表： A = () B = (a, b, c) C = (d) D = (B, C) = ((a, b, c), (d)) E = (D, e) = (((a, b, c), (d)), e)。

3 广义表E的图形表示

4 广义表的长度指广义表中数据元素（原子元素或广义表）的个数。如广义表A的长度为0，广义表B的长度为3，广义表C的长度为1，广义表D的长度为2（注意D中只有两个数据元素B和C），广义表E的长度为2。
广义表的原子元素个数指广义表中原子数据元素的个数。如广义表A的原子元素个数为0，广义表B的原子元素个数为3，广义表C的原子元素个数为1，广义表D的原子元素个数为4，广义表E的原子元素个数为5。 广义表的深度指广义表中所有原子数据元素到达根结点的最大值。一个广义表对应了一棵树，广义表的深度即是指广义表所对应的树的深度。如广义表A，B和C的深度均为1，广义表D的深度为2，广义表E的深度为3。

5 一个广义表无论简单或复杂，都可以分做表头和表尾两部分。任何一个非空广义表的表头既可能是原子也可能是广义表，但非空广义表的表尾一定是一个广义表。
例如广义表(a,b)，其表头为原子a，其表尾为广义表(b)；又例如广义表(b)，其表头为原子b，其表尾为空广义表()；又例如广义表(((a,b,c),(d)),e)，其表头为广义表((a,b,c),(d))，其表尾为广义表(e)。 对任何一个广义表的处理都可以由对表头的处理部分和对表尾的处理部分两部分组成。 广义表有许多应用，其中最典型的，是在表处理语言LISP中，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。另外，广义表还可以用来表示m元多项式。所谓m元多项式就是其每一项最多允许有m个变元。

6 广义表抽象数据类型 数据集合： 广义表的数据集合可以表示为a0, a1, a2, ..., an-1，每个
　广义表抽象数据类型 数据集合： 广义表的数据集合可以表示为a0, a1, a2, ..., an-1，每个 数据元素或是原子元素，或是一个广义表。 操作集合： （1）创建广义表CreatGList(S) （2）求长度GListLength(L) （3）求原子元素个数GListAtomNum(L) （4）求深度GListDepth(L)

7 （5）判非空否GListNotEmpty(L)
（6）取表头GetHead(L) （7）取表尾GetTail(L) （8）插入GListInsert(L, e) （9）删除GListDelete(L, e) （10）查找原子元素GListSearch(L, e) （11）撤消DestroyGList(L)

8 7.2 广义表的存储结构 头链和尾链存储结构 一个广义表可以由表头和表尾两部分组成，所以可以用一个头指针和一个尾指针表示一个广义表。这样，头链和尾链结构中一个结点的结构由一个标志域tag决定：当tag值为1时，该结点除标志域外还有一个头指针域和一个尾指针域；当tag值为0时，该结点除标志域外还有一个原子元素域。

9

10 原子和子表存储结构 观察上图中的结点可以发现，头链和尾链存储结构中当结点为原子元素时，需要由头指针所指的结点存储该原子元素。若此时在该结点中直接存储该原子元素，则构成了原子和子表结构。其中标志tag含义同上，即tag值为1时，该结点除标志域外还有一个头指针域和一个尾指针域；当tag值为0时，该结点除标志域外还有一个原子元素域

11

12 7.3 广义表的操作实现 本节分别讨论头链和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。
　 本节分别讨论头链和尾链存储结构下和原子和子表存储结构下一些典型操作的算法实现。 头链和尾链存储结构下，结点的结构体定义 typedef struct GListNode { int tag; union { DataType atom; //原子元素域 struct { struct GListNode *head; //头链 struct GListNode *tail; //尾链 }subList; } val; }GLNode;

13 创建广义表 创建广义表就是按照所给的表示具体广义表的字符串str创建一个广义表h。
对一个广义表的任何操作都可以分解为对表头的操作和对表尾的操作。同样，创建广义表操作可以分解为创建表头广义表和创建表尾广义表。因此，创建广义表函数CreatGList(str)只要递归完成对表头广义表的创建和对表尾广义表的创建即可。 这样，还需要设计一个把表示广义表的字符串str分解成表头字符串hstr和表尾字符串str的函数DecomposeStr(str, hstr)。

14 void DecomposeStr(char str[], char hstr[])
{ int i, j, tag, n = strlen(str); char ch; ch = str[0]; tag = 0; for(i = 0; i <= n-1; i++) { if(str[i] == ',' && tag == 1 ) break; ch = str[i]; if(ch == '(') tag++; if(ch == ')') tag--; } if(i <= n-1 && str[i] == ',') { for(j = 0; j < i-1; j++) hstr[j] = str[j+1]; hstr[j] = '\0'; if(str[i] == ',') i++; str[0] = '('; for(j = 1; i <= n-2; i++, j++) str[j] = str[i]; str[j] = ')'; str[++j] = '\0'; //

15 else { str++; strncpy(hstr,str, n-2); hstr[n-2] = '\0'; str--; strcpy(str, "()"); }

16 GLNode* CreatGList(char str[])
{ GLNode *h; char hstr[200]; int len = strlen(str); if(strcmp(str, "()") == 0) h = NULL; else if(len == 1) { h = (GLNode *)malloc(sizeof(GLNode)); h->tag = 0; h->val.atom = str[0]; }

17 else { h = (GLNode *)malloc(sizeof(GLNode)); h->tag = 1; DecomposeStr(str, hstr); h->val.subList.head = CreatGList(hstr); if(strcmp(str, "()") != 0) h->val.subList.tail = CreatGList(str); h->val.subList.tail = NULL; } return h;

18 求广义表的深度 广义表的深度是广义表中所有原子数据元素到达根结点的最大值。 int GListDepth(GLNode *h)
{ int max, dep; GLNode *pre; if(h == NULL) return 1; if(h->tag == 0) return 0; pre = h; for(max = 0; pre != NULL; pre = pre->val.subList.tail) { dep = GListDepth(pre->val.subList.head); if(dep > max) max = dep; } return max + 1;

19 求广义表长度 在头链和尾链存储结构中，广义表的长度就是表尾指针构成的单链表的长度。 int GListLength(GLNode *h) {
int number = 0; GLNode *p; for(p = h; p != NULL; p = p->val.subList.tail) number++; return number; }

20 求广义表中原子元素个数 int GListAtomNum(GLNode *h) { if(h == NULL) return 0; else
if(h->tag == 0) return 1; else return GListAtomNum(h->val.subList.head) + GListAtomNum(h->val.subList.tail); }

21 原子和子表存储结构下的操作实现 原子和子表存储结构下，结点的结构体定义 typedef struct GListNode {
int tag; struct GListNode *tail; union DataType atom; struct GListNode *head; } val; }GLNode2;

22 创建广义表 创建广义表就是按照所给的表示具体广义表的字符串str创建一个广义表h。
和头链和尾链存储结构广义表的创建算法类同，原子和子表存储结构的创建广义表操作同样可以分解为创建表头广义表和创建表尾广义表。 把表示广义表的字符串str分解成表头字符串hstr和表尾字符串str的函数DecomposeStr(str, hstr)设计和前面的方法完全相同。

23 创建函数如下： GLNode2* CreatGList(char str[]) { GLNode2 *h; char hstr[200]; int len = strlen(str); if(strcmp(str, "()") == 0) h = NULL; else h = (GLNode2 *)malloc(sizeof(GLNode2)); if(len == 1) { h->tag = 0; h->val.atom = str[0]; h->tail == NULL; }

24 else { DecomposeStr(str, hstr); if(strlen(hstr) == 1) { h->tag = 0; h->val.atom = hstr[0]; } { h->tag = 1; h->val.head = CreatGList(hstr); if(strcmp(str, "()") != 0) h->tail = CreatGList(str); h->tail = NULL; return h;

25 作业 1)习题7-1，7-2 ，7-3 ，7-4