[树] △ 由广义表GList创建树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.73）

2024-02-13 12:18
文章标签 链表 数据结构 创建 孩子 广义 兄弟 严蔚敏 cstree glist 6.73

本文主要是介绍[树] △ 由广义表GList创建树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.73），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：严蔚敏《数据结构》C语言版本习题册 6.73

【题目】6.73
若用大写字母标识树的结点，则可用带标号的广义表形式表示一棵树，其语法图如下所示：

在这里插入图片描述

例如，6.71题中的树可用下列形式的广义表表示：A(B(E,F),C(G),D)
试写一递归算法，由这种广义表表示的字符序列构造树的孩子-兄弟链表（提示：按照森林和树相互递归的定义写两个互相递归调用的算法，语法图中一对圆括号内的部分可看成为森林的语法图）。

【如何看语法图】https://blog.csdn.net/summer_dew/article/details/82937736
【公式解析】

按照公式有 [树] 的定义：

  1. 不存在空树
  2. 树根：大写字母
    • 没有子树：空
    • 有子树：( 树 ) --> 树里面又返回树的定义
    • 有多个子树：(树1, 树2, 树...) --> 以,分割

【测试数据】

A(B(E,F),C(G),D)
A
A(B)
A(B,C)
A(B,C(D,E))

【答案】

/*-----------------------------------------|6.73 用广义表的形式构造                 |-----------------------------------------*/
// @Version:1.0.1
// @Time:20181005
// @Desc:改进v0.0.1中的循环条件1，加上判断格式
// @Quesion:有一些格式检测不了"A(" "A()" "A)("
Status CreateCSTreeByGList(CSTree *pT) {char c;//创建新结点*pTfor (c=getchar(); c!='\n'; c=getchar()) {if (c>='A' && c<='Z') { //新结点的信息*pT = (CSNode *)malloc(sizeof(CSNode)); if (!*pT) exit(OVERFLOW);(*pT)->data = c; (*pT)->firstchild=(*pT)->nextsibling=NULL;} else if (c=='(') { //新结点的孩子if ( !CreateCSTreeByGList(&(*pT)->firstchild) ) return ERROR; //返回ERROR，表示此层之后发生了错误} else if (c==',') { //新结点的兄弟if ( !CreateCSTreeByGList(&(*pT)->nextsibling) ) return ERROR; //返回ERROR，表示此层之后发生了错误return OK; //新结点已经构造完了-->这里要返回} else if (c==')') { //新结点的父亲已经构建完了return OK;} else {return ERROR; //格式错误}}return TRUE; //正常结束
}

【完整答案】可以直接运行

/*-------------------|树-孩子兄弟表达法 |-------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif#define TElemType char
void visit(TElemType e) {printf("%c", e);
}
typedef struct CSNode{TElemType data;struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;/*-------------------|6.59 输出T的所有边 |-------------------*/
void TreePrintEdge(CSTree T) {CSNode *p;for (p=T->firstchild; p; p=p->nextsibling) {printf("(%c,%c)\n", T->data, p->data); //输出T的孩子TreePrintEdge(p); //输出p的孩子}
}/*-------------------------|6.60 统计叶子结点的个数 |-------------------------*/
int TreeLeafCnt(CSTree T) {// 树的叶子结点-->没有孩子int ret=0;CSNode *p;if (!T) return 0;else if (!T->firstchild) return 1;else {for (p=T->firstchild; p; p=p->nextsibling) ret += TreeLeafCnt(p);return ret;}
}/*-------------------------|6.61 求树的度           |-------------------------*/
int TreeDegree(CSTree T) {// 最大的孩子数int max=-1;int cnt=0;CSNode *child;if (!T) return -1; //空树else if (!T->firstchild) return 0; //只有一个根结点，度为0else {for (cnt=0,child=T->firstchild; child; child=child->nextsibling) cnt++; //求自己的度max = cnt; //当前的最大值for (child=T->firstchild; child; child=child->nextsibling) {cnt = TreeDegree(child);if (cnt>max) max=cnt;}return max;}
}/*-------------------------|6.62 求树的深度         |-------------------------*/
int TreeDepth(CSTree T) {int h1,h2;if (!T) return 0;else {h1 = TreeDepth(T->firstchild)+1; //T孩子的深度+1h2 = TreeDepth(T->nextsibling); //T兄弟的深度return h1>h2 ? h1 : h2;}
}/*---------------------------------|6.66 双亲表示法-->孩子兄弟表达式|---------------------------------*/
#define MAX_TREE_SIZE 50typedef struct PTNode{TElemType data;int parent; //双亲的位置域
}PTNode;
typedef struct{PTNode nodes[MAX_TREE_SIZE];int r,n;
}PTree;
CSTree CreateCSTreeByPTree(PTree T) {CSNode *tmp[MAX_TREE_SIZE]; //创建一个辅助的数组，仿照PTree结点的位置存放CSNode *p, *q;int i,parent;if (T.n<=0) return NULL;for (i=0; i<T.n; i++) { //双亲表按层序存储//创建新结点p = (CSNode *)malloc(sizeof(CSNode)); if(!p) exit(OVERFLOW);//赋值p->data = T.nodes[i].data;p->firstchild=p->nextsibling=NULL;//连接parent=T.nodes[i].parent; //父亲if (parent!=-1) { //不是根结点if (tmp[parent]->firstchild==NULL) tmp[parent]->firstchild=p; //第一个孩子else { //不是第一个孩子for (q=tmp[parent]->firstchild; q->nextsibling; q=q->nextsibling) ; //找到最后一个孩子q->nextsibling = p; //连接}}tmp[i]=p;}return tmp[0];
}/*---------------------------------|6.67 二元组(F,C)创建CSTree      |---------------------------------*/
#define maxSize 50
Status CreateCSTreeByDuplet(CSTree *pT) {char input[5];CSNode *queue[maxSize];int front,rear;CSNode *p, *q;front=rear=0; //对队列初始化for (scanf("%s", input); input[1]!='^'; scanf("%s", input)) {//创建结点p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);p->data=input[1];p->firstchild=p->nextsibling=NULL;//入队列queue[rear]=p;rear=(rear+1)%maxSize;//找爸爸if (input[0]=='^') { //根结点-->不需要找爸爸*pT = p; //传出去} else {for (q=queue[front]; q->data!=input[0]; front=(front+1)%maxSize,q=queue[front]) ; //找爸爸//找哥哥if (!q->firstchild) q->firstchild=p; //它是最大的else { //它不是最大的for(q=q->firstchild; q->nextsibling; q=q->nextsibling) ; //找最近的哥哥q->nextsibling = p; //和哥哥牵手}}}return OK;
}/*-----------------------------------------|6.68 层次序列+每个结点的度-->构造CSTree |-----------------------------------------*/
CSTree CreateCSTreeByLevelDegree(char *levelstr, int *num) {int cnt,i,parent;CSNode *p;CSNode *tmp[maxSize];//先创建结点for (i=0; i < strlen(levelstr); ++i) {p = (CSNode *)malloc(sizeof(CSNode)); if (!p) exit(OVERFLOW);p->data = levelstr[i];p->firstchild=p->nextsibling=NULL;tmp[i]=p;}//连接parent=0; //孩子的爸爸cnt=0; //计数器：表示已经找了几个孩子i=1; //遍历结点，为他们找爸爸while (i<strlen(levelstr)) {if (num[parent]==0 || cnt==num[parent]) { //这个父亲没有孩子 || parent的孩子已经找完了cnt=0; //计数器归0parent++; //位移一位continue;}//这个父亲有孩子（i是parent的孩子）cnt++;if (cnt==1) { //i是parent的第一个孩子tmp[parent]->firstchild = tmp[i];} else { //不是第一个孩子tmp[i-1]->nextsibling = tmp[i]; //它是前面的兄弟}i++;}return tmp[0];
}/*-----------------------------------------|6.71 以树状的形式输出                   |-----------------------------------------*/
void PrintAsTree(CSTree T,int i) {/*思路：1. 观察题目输出的序列ABEFCGD2. 此为树的先根遍历-->对应为二叉树存储的先序遍历3. 前面的空格是该结点所在的层数*/int cnt;if (T) {//输出空格for (cnt=1; cnt<i; cnt++) printf(" ");//输出字符visit(T->data);printf("\n");PrintAsTree(T->firstchild, i+1);PrintAsTree(T->nextsibling, i);}
}/*-----------------------------------------|6.73 用广义表的形式构造                 |-----------------------------------------*/
// @Version:0.0.1
// @Time:20181005
// @Desc:循环条件为1，最好不要设置死循环
Status CreateCSTreeByGList1(CSTree *pT) {char c;while (1) {c = getchar();if (c>='A' && c<='Z') { //根结点*pT = (CSNode *)malloc(sizeof(CSNode)); if (!*pT) exit(OVERFLOW);(*pT)->data = c; (*pT)->firstchild=(*pT)->nextsibling=NULL;} else if (c=='(') { //是我的第一个孩子CreateCSTreeByGList1(&(*pT)->firstchild);} else if (c==',') { //是我的兄弟CreateCSTreeByGList1(&(*pT)->nextsibling);break; //这里要返回} elsebreak;}return OK;
}
// @Version:1.0.1
// @Time:20181005
// @Desc:改进v0.0.1中的循环条件1，加上判断格式
// @Quesion:有一些格式检测不了"A(" "A()" "A)("
Status CreateCSTreeByGList(CSTree *pT) {char c;//创建新结点*pTfor (c=getchar(); c!='\n'; c=getchar()) {if (c>='A' && c<='Z') { //新结点的信息*pT = (CSNode *)malloc(sizeof(CSNode)); if (!*pT) exit(OVERFLOW);(*pT)->data = c; (*pT)->firstchild=(*pT)->nextsibling=NULL;} else if (c=='(') { //新结点的孩子if ( !CreateCSTreeByGList(&(*pT)->firstchild) ) return ERROR; //返回ERROR，表示此层之后发生了错误} else if (c==',') { //新结点的兄弟if ( !CreateCSTreeByGList(&(*pT)->nextsibling) ) return ERROR; //返回ERROR，表示此层之后发生了错误return OK; //新结点已经构造完了-->这里要返回} else if (c==')') { //新结点的父亲已经构建完了return OK;} else {return ERROR; //格式错误}}return TRUE; //正常结束
}/*-----------------------------------------|6.74 以广义表的形式输出                 |-----------------------------------------*/
void PrintAsGList(CSTree T) {CSNode *child;visit(T->data);if (T->firstchild) { //有孩子printf("(");for (child=T->firstchild; child->nextsibling; child=child->nextsibling) {PrintAsGList(child);printf(",");}PrintAsGList(child);printf(")");}
}int main() {
/*6.74测试数据
A(B(E,F),C(G),D)
A
A(B)
A(B,C)
A(B,C(D,E))
*/CSTree CST;int ret;while (1) {ret = CreateCSTreeByGList(&CST); //6.73if (ret) {PrintAsGList(CST); //6.74printf("\n");}elseprintf("格式错误\n");}return 0;
}

这篇关于[树] △ 由广义表GList创建树（孩子兄弟链表CSTree）（严蔚敏《数据结构》6.73）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/705509。

相关文章

MySQL分表自动化创建的实现方案

MySQL分表自动化创建的实现方案

《MySQL分表自动化创建的实现方案》在数据库应用场景中,随着数据量的不断增长,单表存储数据可能会面临性能瓶颈,例如查询、插入、更新等操作的效率会逐渐降低,分表是一种有效的优化策略,它将数据分散存储在... 目录一、项目目的二、实现过程（一）mysql 事件调度器结合存储过程方式1. 开启事件调度器2. 创
阅读更多...
mysql外键创建不成功/失效如何处理

mysql外键创建不成功/失效如何处理

《mysql外键创建不成功/失效如何处理》文章介绍了在MySQL5.5.40版本中,创建带有外键约束的`stu`和`grade`表时遇到的问题,发现`grade`表的`id`字段没有随着`studen... 当前mysql版本：SELECT VERSION();结果为：5.5.40。在复习mysql外键约
阅读更多...
Window Server创建2台服务器的故障转移群集的图文教程

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集，操作与Ser
阅读更多...
Window Server2016 AD域的创建的方法步骤

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器：三、创建AD域，域地址为“test.ly”
阅读更多...
Python在固定文件夹批量创建固定后缀的文件(方法详解)

Python在固定文件夹批量创建固定后缀的文件(方法详解)

《Python在固定文件夹批量创建固定后缀的文件(方法详解)》文章讲述了如何使用Python批量创建后缀为.md的文件夹,生成100个,代码中需要修改的路径、前缀和后缀名,并提供了注意事项和代码示例,... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5.
阅读更多...
使用IntelliJ IDEA创建简单的Java Web项目完整步骤

使用IntelliJ IDEA创建简单的Java Web项目完整步骤

《使用IntelliJIDEA创建简单的JavaWeb项目完整步骤》：本文主要介绍如何使用IntelliJIDEA创建一个简单的JavaWeb项目,实现登录、注册和查看用户列表功能,使用Se... 目录前置准备项目功能实现步骤1. 创建项目2. 配置 Tomcat3. 项目文件结构4. 创建数据库和表5.
阅读更多...
使用SpringBoot创建一个RESTful API的详细步骤

使用SpringBoot创建一个RESTful API的详细步骤

《使用SpringBoot创建一个RESTfulAPI的详细步骤》使用Java的SpringBoot创建RESTfulAPI可以满足多种开发场景,它提供了快速开发、易于配置、可扩展、可维护的优点,尤... 目录一、创建 Spring Boot 项目二、创建控制器类（Controller Class）三、运行
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
手把手教你idea中创建一个javaweb(webapp)项目详细图文教程

手把手教你idea中创建一个javaweb(webapp)项目详细图文教程

《手把手教你idea中创建一个javaweb(webapp)项目详细图文教程》：本文主要介绍如何使用IntelliJIDEA创建一个Maven项目,并配置Tomcat服务器进行运行,过程包括创建... 1.启动idea2.创建项目模板点击项目-新建项目-选择maven，显示如下页面输入项目名称，选择
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2