第4章数组与串第4节广义表.ppt

《第4章数组与串第4节广义表.ppt》由会员分享，可在线阅读，更多相关《第4章数组与串第4节广义表.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章数组与串第4节广义表 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第4章 数组与串 第4节 广义表（）广义表GL=(a0,a1,an-1)中，a0为广义表GL的表头；(a1,an-1)为广义表GL的表尾(还是广义表），分别记为 head(GL)=a0 tail(GL)=(a1,an-1)（）广义表的长度是指广义表中包含元素（包括原子和子表）的个数。（）广义表的深度是指广义表中所包含括号的层数。第4章 数组与串 第4节 广义表为了区分表与原子的书写区别，通常

2、用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。如：A（）长度为1的表，其中表头是一个空表；B（a，（b，c，d）是长度为2的表；C（A，B，（）长度为3的表，前面二个元素都是广义表，后面一个是空表；D（）为一个空表；长度为0的表；E（a，E）长度为2的表，其中一个为原子，一个是子表 第4章 数组与串 第4节 广义表2广义表的性质广义表的性质从上述广义表的定义和例子可以得到广义表具有下列二个重要性质：一个广义表可以被其它广义表共享，例如，表A、表B是表C的共享子表。广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身

3、的子表。例如表E就是一个递归的表。广义表结构灵活，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。（当二维数组的每行或每列作为子表处理时二维数组即为一个广义表）第4章 数组与串 第4节 广义表3广义表基本运算广义表基本运算广义表主要有取头操作（Head）和取尾操作（Tail）操作。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是子表，而表尾必为子表。例如：Head（B）a Tail（B）（b，c，d）Head（C）A Tail（C）（B，（）Head（A）（）Tail（A）（）Head（E）a Tail（E）（E）此外，在广义表上可以定义与线性表类似

4、的一些操作，如建立、插入、删除、拆开、深度、长度、连接、复制、遍历等。第4章 数组与串 第4节 广义表4.4.2广义表的存储广义表的存储广义表都采用链式的存储结构来存储广义表。结点形式为其中tag是标识域。若结点表示一个原子，则tag=0，且第二个字段为data，它表示原子的名称或数值；若结点表示的是一个广义表，则tag=1，且第二字段为dlink，存放相应子表第一个元素对应结点的地址。Link域是指向同层下一个元素，若没有，即是同层最后一个结点，则置link为空（NULL，或记为）。TagDlink/datalink第4章 数组与串 第4节 广义表第4章 数组与串 第4节 广义表采用C语言其

5、结点形式定义如下：typedef struct lnodeint tag;/结点类型标识 union char data;struct lnode*dlink;val;struct lnode *link;/指向下一个元素 GLNode;第4章 数组与串 第4节 广义表4.4.3 广义表的递归算法广义表的递归算法1 创建一个链式存储结构的广义表创建一个链式存储结构的广义表假定广义表是一个括号表达式组成的字符串，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。每个原子的值被限定为英文字母。算法思想：用字符串变量 s 来表示一个广义表的括号表达

6、式，从头到尾扫描 s 的每一个符号：（1）当遇到是左括号，说明是一个表的开始，则建立一个由 h 指向的表的结点，并用它的dlink域作为子表的表头指针，进行递归调用；第4章 数组与串 第4节 广义表（2）当扫描到一个字母，说明它是一个原子，则建立一个由h指向的原子结点；（3）当遇到是空字符，说明它是空表，则置h为空；（4）在建立一个由h指向的结点后，再遇到逗号，表示存在一个后继结点，则需要建立当前结点（h指向的结点）的后续表（使用link链接），则继续调用递归；（5）在建立一个由h指向的结点后，再遇到是右括号或0时，表示当前所处理的表已经结束，则置结点的link域为空（NULL）。第4章 数组

7、与串 第4节 广义表GLNode *CreatGL(char *s)GLNode *h;char ch=*(s+);/空格、左括号或英文字母 if(ch=)h=NULL;else h=new GLNode;if(ch=()h-tag=1;h-val.dlink=CreatGL(s);else h-tag=0;h-val.data=ch;第4章 数组与串 第4节 广义表 ch=*(s+);/逗号、右括号或0 if(h!=NULL)if(ch=,)h-link=CreatGL(s);else if(ch=)|(ch=0)h-link=NULL;return h;第4章 数组与串 第4节 广义表2广

8、义表的输出广义表的输出 指针 h 表示带表头附加结点的广义表的表头指针，利用广义表的递归特征，对子表进行递归调用，打印输出该广义表。算法思想：(1)当h结点为子表结点时，首先输出表的起始符号左括号”(“；然后利用递归输出h-dlink为表头指针的表；(2)当h结点为原子结点时，则直接输出元素的值;(3)当h-dlink为表头指针的表输出完毕后，输出表的结束符号”)”右括号；(4)h结点输出结束后,若有后继结点，先输出”,”逗号，然后再利用递归继续输出由h-link指针所指向的后继表。第4章 数组与串 第4节 广义表void GLDisp(GLNode*p)/p为一个广义表的头结点指针 if(p

9、!=NULL)/表不为空 if(p-tag=1)/为表结点时 cout val.dlink=NULL)cout val.dlink);/递归输出子表 else cout val.data;/为原子时输出元素值 if(p-tag=1)cout link!=NULL)cout link);/递归输出后续表的内容 第4章 数组与串 第4节 广义表3 求广义表的长度求广义表的长度 所谓广义表的长度是指在广义表中元素个数，由于广义表在同一层次的每个结点是通过link域链接起来的，所以可把它看做是由link域链接起来的单链表。这样，求广义表的长度就变成求单链表的长度了。第4章 数组与串 第4节 广义表 i

10、nt GLLength(GLNode*p)/p为广义表附加头结点的指针 int n=0;p=p-val.dlink;/p指向广义表的第一个元素 while(p!=NULL)n+;p=p-link;return n;第4章 数组与串 第4节 广义表4广义表的复制广义表的复制 复制一个广义表的算法思想：对于一个广义表的头结点*p，若为空，则返回空指针；若为子表，则递归复制子表；否则复制原子结点，然后递归复制后续表。算法结束返回广义表链表指针。第4章 数组与串 第4节 广义表int *GLcopy(GLNode*p)/p为广义表头结点的指针 GLNode*q;if (p=NULL)return NULL;q=new GLNode;q-tag=p-tag;if(p-tag=1)q-val.dlink=GLcopy(p-val.dlink);else q-val.data=p-val.data;q-link=GLcopy(p-link);return q;第4章 数组与串 第4节 广义表作业p.87q.11