广义表的长度和深度怎么算

来源：互联网 2023-03-17 00:01:28 版权归原作者所有，如有侵权，请联系我们

广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。

工具/原料

计算机
C语言

广义表的长度和深度的计算

广义表的长度
通过前一节对广义表的介绍，例子中给出了几个广义表的长度。例如：空表的长度为 0，只含有一个原子的广义表长度为 1，等等。
广义表的长度指的是广义表中数据元素的数量。这里需要指明的是，一个广义表中，一个原子算做是一个元素，一个子表也只算做一个元素。
在 LS = (a1,a2,…,an) 中，ai表示原子或者子表， LS 的长度为 n。
广义表的深度
广义表的深度，指的是广义表中括号的重数。
例如：C=(a,(b,c,d))：
该信息未经许可获取自百度经验
求解广义表的深度
求广义表的深度之前，首先要将广义表用某个数据结构表示出来，在前边学习广义表时，介绍了两种表示广义表的方法。这里采用的方法是第一种。
表示结构为：（拿广义表C为例）
广义表第一节中有具体实现的代码，实现函数为：creatGlist(Glist C)。这里不再过多介绍。
求广义表深度的算法用到的是递归的思想，解题思路是：
从广义表 C 的开头位置，一次遍历表中每个数据元素：当遍历对象为原子时，返回原子的深度为 0 ；遍历对象为表 C 的子表时，继续遍历子表中的数据元素。
递归的出口有两个：当遍历对象为原子时，返回 0 ；遍历对象为空表时，返回 1 （空表的深度为 1 ）；
设置一个初始值为 0 的整形变量 max ，用 max 和遍历过程中返回的整形数值进行比较，取大的那一个，知道程序结束，max 1就是广义表的深度。
int GlistDepth(Glist C){
　　//如果表C为空表时，直接返回长度1；
　　if (!C) 　　{
　　　　return 1;
　　}
　　//如果表C为原子时，直接返回0；
　　if (C->tag == 0) 　　{
　　　　return 0;
　　}
　　int max = 0;　　//设置表C的初始长度为0；
　　for (Glist pp=C; pp; pp=pp->ptr.tp) 　　{
　　　　int dep = GlistDepth(pp->ptr.hp);
　　　　if (demax) 　　　　{
　　　　　　max = dep;　　//每次找到表中遍历到深度最大的表，并用max记录
　　　　}
　　}
　　//程序运行至此处，表明广义表不是空表，由于原子返回的是0，而实际长度是1，所以，此处要 1；
　　return max 1;
}

完整代码

#include stdio.h>

#include stdlib.h>

typedef struct GLNode{

　　int tag;　　//标志域

　　union　　{

　　　　char atom;　　//原子结点的值域

　　　　struct　　　　{

　　　　　　struct GLNode *hp, *tp;

　　　　}ptr;　　//子表结点的指针域，hp指向表头；tp指向表尾

　　};

}*Glist, GNode;

Glist creatGlist(Glist C){

　　//广义表C

　　C=(Glist)malloc(sizeof(GNode));

　　C->tag = 1;

　　//表头原子‘a’

　　C->ptr.hp = (Glist)malloc(sizeof(GNode));

　　C->ptr.hp->tag = 0;

　　C->ptr.hp->atom = 'a';

　　//表尾子表（b,c,d）,是一个整体

　　C->ptr.tp = (Glist)malloc(sizeof(GNode));

　　C->ptr.tp->tag = 1;

　　C->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode));

　　C->ptr.tp->ptr.tp = NULL;

　　//开始存放下一个数据元素（b,c,d）,表头为‘b’，表尾为（c,d）

　　C->ptr.tp->ptr.hp->tag = 1;

　　C->ptr.tp->ptr.hp->ptr.hp = (Glist)malloc(sizeof(GNode));

　　C->ptr.tp->ptr.hp->ptr.hp->tag = 0;

　　C->ptr.tp->ptr.hp->ptr.hp->atom = 'b';

　　C->ptr.tp->ptr.hp->ptr.tp = (Glist)malloc(sizeof(GNode));

　　//存放子表(c,d)，表头为c，表尾为d

　　C->ptr.tp->ptr.hp->ptr.tp->tag = 1;

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode));

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag = 0;

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom = 'c';

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp = (Glist)malloc(sizeof(GNode));

　　//存放表尾d

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag = 1;

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp = (Glist)malloc(sizeof(GNode));

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag = 0;

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom = 'd';

　　C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp = NULL;

　　return C;

}

//求广义表的深度，递归调用

int GlistDepth(Glist C){

　　if (!C) 　　{

　　　　return 1;

　　}

　　if (C->tag == 0) 　　{

　　　　return 0;

　　}

　　int max = 0;

　　for (Glist pp=C; pp; pp=pp->ptr.tp) 　　{

　　　　int dep = GlistDepth(pp->ptr.hp);

　　　　if (demax) 　　　　{

　　　　　　max = dep;

　　　　}

　　return max 1;

}

int main(int argc, const char *argv[]){

　　Glist C = creatGlist(C);

　　printf("%d", GlistDepth(C));

　　return 0;

}

运行结果：

注意事项

注意语法编写

以上方法由办公区教程网编辑摘抄自百度经验可供大家参考！

标签： C语言编程

上一篇：static关键字的作用下一篇：C#编程：怎么使用Console.Write()函数

广义表的长度和深度怎么算

工具/原料

广义表的长度和深度的计算

完整代码

注意事项

热门文章

标签列表