5465人阅读
2.数据结构与算法（34）
广义表最基本的操作：取表头head(LS)与取表尾tail(LS)
例：LS=(a,(b,c,d))
head(LS)=a
tail(LS)=((b,c,d))
head(tail(LS))=(b,c,d)
tail(tail(LS))=()
head(head(tail(LS)))=b
tail(head(tail(LS)))=(c,d)
head(tail(head(tail(LS))))=c
tail(tail(head(tail(LS))))=(d)
head(tail(tail(head(tail(LS)))))=d
tail(tail(tail(head(tail(LS)))))=()
转载地址：.cn/s/blog_4d6efb.html
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：236855次
积分：5942
积分：5942
排名：第3696名
原创：354篇
转载：116篇
评论：22条
(10)(4)(7)(15)(28)(11)(16)(13)(10)(13)(40)(18)(35)(8)(36)(110)(73)(15)(4)(3)(2)扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
广义表A=（a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))=?广义表的深度为?长度为?广义表深度长度怎么看呀!比如说我是这么做的帮忙看看有没错就是说B=Tail(A)=(b,(c,d),(e,(f,g))),然后C=Tail(B)=((c,d),(e,(f,g))),D=Head(C)=((c,d)),接下去的E=Tail(D)就不会求了,是等于(c,d)呢还是等于()?谢谢了如果是Head(D)的话应将该就是(c,d)了吧,还有深度广度要怎么算啊我给这些括号和逗号搞晕了
爱醋仝HAyd3
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
d tail(A)=(b,(c,d),(e,(f,g)))=Stail(S)=((c,d),(e,(f,g)))=S1head(S1)=(c,d)=S2tail(S2)=(d)=S3head(S3)=d
为您推荐：
其他类似问题
扫描下载二维码数据结构练习_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构练习
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢广义表的基本操作 - 博客频道 - CSDN.NET
Amo_te_ama_me的专栏
如果毫不费力，你就是在浪费时间。
分类：算法练习
& & & & 这几天学《数据结构》，被其中的广义表难住了，经过今天的小小钻研，总算看懂了。。。
这是广义表的基本概念：
&&& 　广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
1、广义表定义
&&& 　广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
&&& 　①ai--或者是原子或者是一个广义表。
　& 　②广义表通常记作：
&&&&&&&&&& && Ls=( a1，a2，…，ai，…，an)。
　　& ③Ls是广义表的名字，n为它的长度。
　 　 ④若ai是广义表，则称它为Ls的子表。
&&& 　①广义表通常用圆括号括起来，用逗号分隔其中的元素。
&&& 　②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
&&& 　③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。
&&&　 ④广义表是递归定义的
2、广义表表示
（1）广义表常用表示
　　① E=()
&&&& 　E是一个空表，其长度为0。
　　② L=(a，b)
&&&& 　L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
　　③ A=(x，L)=(x，(a，b))
&&&& 　A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
　　④ B=(A，y)=((x，(a，b))，y)
　&&&& B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
　　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
&&&& 　C的长度为2，两个元素都是子表。
　　⑥ D=(a，D)=(a，(a，(a，(…))))
&&&& 　D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。
（2）广义表的深度
　　一个表的&深度&是指表展开后所含括号的层数。
& 【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。
（3）带名字的广义表表示
&&& 　如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))
（4）广义表的图形表示
（a）广义表的图形表示：
&&&　 ①图中的分支结点对应广义表
&&&　 ②非分支结点一般是原子
&&& 　③但空表对应的也是非分支结点。
　　【例】下图给出了几个广义表的图形表示。
&&&&&&&&&&&&&
（b）广义表的图形形状划分：&
　　 ①与树对应的广义表称为纯表，它限制了表中成分的共享和递归
　 　②允许结点共享的表称再入表
& 【例】上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素；
　　 ③允许递归的表称为递归表
& 【例】上图(e)，表D是其自身的子表。
（5）递归表、再人表、纯表、线性表之间的关系满足：
&&　& 广义表不仅是线性表的推广，也是树的推广。
3、广义表运算
&&& 　由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。
&&& 　在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。
&&& 　根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
&&&&& head(L)=a， tail(L)=(b)
&&&&& head(B)=A， tail(B)=(y)
& 由于tail(L)是非空表，可继续分解得到：
&&&&& head(tail(L))=b， tail(tail(L))=()
& 对非空表A和(y)，也可继续分解。
&&& 　广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。
代码操作：&pre name=&code& class=&cpp&&&span style=&color:#cc33&&#include &stdio.h&
#include &stdlib.h&
#include &malloc.h&
typedef char elemT
/************************************************************************/
以下是关于广义表操作的4个简单算法
/************************************************************************/
struct GNode{
/* 标志域：取0表示单元素结点；取1时表示子表结点 */
struct GNode *subL
struct GNode *
/* 指向后继结点的指针域 */
/* 1.求广义表的长度 */
int lenthGList(struct GNode *gl)
if(gl != NULL){
return 1 + lenthGList(gl-&next);
/* 2.求广义表的深度 */
int depthGList(struct GNode *gl)
int max = 0;
/* 遍历每个结点，求出所以子表的最大深度 */
while(gl != NULL){
if(gl-&tag == 1){
/* 递归求出一个子表的深度 */
int dep = depthGList(gl-&subList);
/* 让max始终为同一个所求子表中深度的最大值 */
if(dep & max){
/* 让gl指向下一个结点 */
return max + 1;
/* 返回表的深度 */
/* 3.建立广义表的存储结构 */
int creatGList(struct GNode* *gl)&/span&&span style=&color:#33ff33;&&//二级指针，以修改后继结点和子表的值&/span&&span style=&color:#cc33&&
/* 读入一个字符，此处可能读入'＃'，'（'，'）'，','或者英文字母 */
scanf(&%c&, &ch);
/* 若输入为＃，则置表头指针为空 */
if(ch == '#'){
*gl = NULL;
/* 若输入左括号则建立由*gl所指向的子表结点并递归构造子表 */
else if(ch == '('){
*gl = malloc(sizeof(struct GNode));
(*gl)-&tag = 1;
creatGList(&((*gl)-&subList));
/* 若输入为字符则建立由*gl所指向的单元素结点 */
*gl = malloc(sizeof(struct GNode));
(*gl)-&tag = 0;
(*gl)-&data =
/* 此处读入的字符必为逗号或右括号或分号 */
scanf(&%c&, &ch);
/* 若*gl为空，则什么都不做 */
if(*gl == NULL){
else if( ch== '\n')&/span&&span style=&color:#cc33&&
printf(&输出了回车键\n&);
(*gl)-&next = NULL;
/* 若输入为逗号则递归构造后继表 */
else if(ch == ','){
creatGList(&((*gl)-&next));
/* 若输入为右括号或分号则置*gl的后继指针域为空 */
else if((ch == ')') || (ch == ';')){
(*gl)-&next = NULL;
/* 4.打印广义表 */
int printGList(struct GNode *gl)
/* 对于表结点的处理 */
if(gl-&tag == 1){
/* 存在子表，先输出左括号 */
printf(&(&);
/* 若子表为空，则输出'#'字符 */
if(gl-&subList == NULL){
printf(&#&);
/* 若子表非表，则递归输出子表 */
printGList(gl-&subList);
/* 当一个子表输出结束后，再输出右括号 */
printf(&)&);
/* 对单元素结点，则输出该结点的值 */
printf(&%c&, gl-&data);
/* 输出该结点的后继表 */
if(gl-&next != NULL){
/* 先输出逗号分隔 */
printf(&, &);
/* 再递归输出后继表 */
printGList(gl-&next);
int main()
struct GNode *
printf(&输入一个广义表， 以右括号结束 &);
creatGList(&gl);
printf(&输出广义表：&);
printGList(gl);
printf(&\n&);
printf(&广义表的长度：&);
printf(&%d &, lenthGList(gl-&subList));
printf(&广义表的深度：&);
printf(&%d &, depthGList(gl-&subList));
system(&pause&);
Amo_te_ama_me
排名：千里之外
（29）（16）（18）（0）（2）（16）（2）（1）（0）
马云说，梦想还是要有的，万一实现了呢？所以，如果你不甘平庸，如果你心怀梦想，那就激情起来，即使跑起来被拌倒无数次，也不要规规矩矩走一辈子，岁月不止，奋斗不息，就做这样的自己！}