数据结构与算法——第5章-数组和广义表-广义表的深度(5.13.2)

发表于 2023-03-11 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 3 分钟

一概述

1.什么是广义表的深度
2.广义表深度的图示
3.广义表深度的计算
4.示例代码

二什么是广义表的深度

1	广义表的深度，可以通过观察该表中所包含括号的层数间接得到。

三广义表深度的图示

3.1 图示

3.2 说明

1
2
3

从图 2 中可以看到，此广义表从左往右数有两层左括号（从右往左数也是如此），因此该广义表的深度为 2。
再比如，广义表 {{1,2},{3,{4,5}}} 中，子表 {1,2} 和 {3,{4,5}} 位于同层，此广义表中包含 3 层括号，因此深度为 3。
以上观察括号的方法需将广义表当做字符串看待，并借助栈存储结构实现，这里不做重点介绍。

四广义表深度的计算

编写程序计算广义表的深度时，以图 1a) 中的广义表为例，可以采用递归的方式：
1.依次遍历广义表 C 的每个节点，若当前节点为原子（tag 值为 0），则返回 0；
若为空表，则返回 1；反之，则继续遍历该子表中的数据元素。

2.设置一个初始值为 0 的整形变量 max，每次递归过程返回时，令 max 与返回值进行比较，并取较大值。
这样，当整个广义表递归结束时，max+1 就是广义表的深度。

其实，每次递归返回的值都是当前所在的子表的深度，原子默认深度为 0，空表默认深度为 1。

五示例代码

C 语言实现代码如下：

#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) {
	//如果表 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 (dep>max) {
			max=dep;//每次找到表中遍历到深度最大的表，并用 max 记录
		}
	}
	//程序运行至此处，表明广义表不是空表，由于原子返回的是 0，而实际长度是 1，所以，此处要+1；
	return max+1;
}
int main(int argc, const char * argv[]) {
	Glist C=creatGlist(C);
	printf("广义表的深度为：%d",GlistDepth(C));
	return 0;
}

程序运行结果：

广义表的深度为：2

六参考

C语言中文网—广义表的深度和长度

0%