[树] △ 由广义表构造树（孩子链表CTree）并以广义表的形式输出（严蔚敏《数据结构》6.75|6.76 ）

2024-02-13 12:18
文章标签 输出 链表 数据结构 构造 形式 孩子 广义 严蔚敏 ctree 6.75 6.76

本文主要是介绍[树] △ 由广义表构造树（孩子链表CTree）并以广义表的形式输出（严蔚敏《数据结构》6.75|6.76 ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

【题目】6.75
试写以递归算法，由6.73题定义的广义表表示法的字符序列，构造树的孩子链表。

【题目】6.76
试写以递归算法，以6.73题给定的树的广义表表示法的字符序列形式输出以孩子链表表示的树。

【测试数据】A(B(E,F),C(G),D)
【答案】

/*-------------------------|6.75 用广义表构造树     |-------------------------*/
// @Quesion:有一些格式检测不了"A(" "A()" "A)("
Status CreateCTreeByGList(CTree *pT, int parent) {// 创建新结点newNode --> 放在下标为pT->n// 该结点的爸爸为parentchar c;CNode *p, *q;int newNode;//创建newNode结点newNode = pT->n; //新结点的下标for (c=getchar(); c!='\n'; c=getchar() ) {if (c>='A' && c<='Z') { // 结点信息pT->nodes[newNode].data = c; //给结点赋值pT->nodes[newNode].firstchild = NULL; //给结点赋值pT->n++; //结点数+1//newNode有爸爸，即parentif (parent!=-1) {//创建孩子结点p = (CNode *)malloc(sizeof(CNode));if (!p) exit(OVERFLOW);p->index = newNode;p->next = NULL;//儿子父亲相认if (pT->nodes[parent].firstchild==NULL) {pT->nodes[parent].firstchild = p;} else {for (q=pT->nodes[parent].firstchild; q->next; q=q->next) ;q->next = p;}}} else if (c=='(') { //是newNode的孩子CreateCTreeByGList(pT, newNode); //开始创建newNode的孩子} else if (c==',') { //是newNode的兄弟，即parent的下一个孩子CreateCTreeByGList(pT, parent); //parent的下一个孩子return OK; //newNode结点构造完成（自己创建了、孩子创建了、兄弟创建了）} else if (c==')') { //parent构造完毕return OK; } else {return ERROR; //格式错误}}return OK;
}/*-------------------------|6.76 以广义表的形式输出 |-------------------------*/
Status PrintAsGList(CTree T,int parent) {CNode *p;if (T.n<=0) return ERROR; visit(T.nodes[parent].data);if (T.nodes[parent].firstchild) {printf("(");for (p=T.nodes[parent].firstchild; p; p=p->next) {PrintAsGList(T, p->index);if (p->next) printf(",");}printf(")");}return OK;
}

【完整代码】

#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);
}
#define MAX_TREE_SIZE 100
#define maxSize 50typedef struct CNode{int index; //这个孩子的结点号（注意：在严书中变量名为child）struct CNode *next; //下一个孩子结点
}CNode, *ChildPtr; //孩子结点结构（在严书中名为CTNode）
typedef struct{TElemType data;CNode* firstchild;
}PNode; //双亲结点结构（在严书中，结构名为CTBox）
typedef struct{PNode nodes[MAX_TREE_SIZE];int n,r; //结点数 和 根结点的位置
}CTree; //树结构// 先根遍历
void SubPreOrder(CTree T, int index) {CNode *child;visit(T.nodes[index].data);for (child=T.nodes[index].firstchild; child; child=child->next)SubPreOrder(T, child->index);
}
void PreOrder(CTree T) {SubPreOrder(T, T.r);
}/*-------------------------|6.63 求树的深度         |-------------------------*/
int SubTreeDepth(CTree T, int index) { //序号为index的子树深度int max=-1; //孩子的最大深度int sd; //孩子的深度CNode *p;if (!T.nodes[index].firstchild) return 1; //没有孩子，深度为1for (p=T.nodes[index].firstchild; p; p=p->next) { //遍历该结点的所有孩子sd = SubTreeDepth(T, p->index); //求孩子的深度if (max<sd) max=sd;}return max+1; //孩子的最大深度+1
}
int TreeDepth(CTree T) { return SubTreeDepth(T, T.r);
}/*-------------------------|6.72 将树打印成树状     |-------------------------*/
void PrintAsTree(CTree T, int index, int i) {/*思路1. 观察题目输出的序列ABEFCGD2. 此为树的先根遍历–>对应为二叉树存储的先序遍历3. 前面的空格是该结点所在的层数*/CNode *p;int cnt;//输出空格for (cnt=1; cnt<i; cnt++) printf(" ");//输出元素visit(T.nodes[index].data);printf("\n");//遍历它的孩子for(p=T.nodes[index].firstchild; p; p=p->next)PrintAsTree(T, p->index, i+1);
}// 树的层序次序+每个结点的度 --> 创建CTree
Status CreateCTreeByLevelDegree(CTree *pT,char *levelstr, int *degree) {CNode *c,*sibling;int parent;int i,cnt;//创建结点for (i=0; i<strlen(levelstr); ++i) {//赋值pT->nodes[i].data = levelstr[i];pT->nodes[i].firstchild = NULL;}pT->n=strlen(levelstr); //个数pT->r=0; //根结点//为孩子找爸爸parent=0; //当前的爸爸i=1; //遍历孩子cnt=0; //已经为parent找到了cnt个孩子while (i<strlen(levelstr)) {if (degree[parent]==0 || cnt==degree[parent]) { //parent没有孩子 || parent的孩子已经全部找到cnt=0;parent++;continue;}cnt++; //为parent找到了一个孩子//创建孩子结点c = (CNode *)malloc(sizeof(CNode)); if (!c) exit(OVERFLOW);c->index = i; //孩子的编号c->next = NULL;if (cnt==1) { //第一个孩子pT->nodes[parent].firstchild = c;} else { //不是第一个孩子for(sibling=pT->nodes[parent].firstchild; sibling->next; sibling=sibling->next) ;sibling->next = c;}i++;}return TRUE;
}/*-------------------------|6.75 用广义表构造树     |-------------------------*/
// @Quesion:有一些格式检测不了"A(" "A()" "A)("
Status CreateCTreeByGList(CTree *pT, int parent) {// 创建新结点newNode --> 放在下标为pT->n// 该结点的爸爸为parentchar c;CNode *p, *q;int newNode;//创建newNode结点newNode = pT->n; //新结点的下标for (c=getchar(); c!='\n'; c=getchar() ) {if (c>='A' && c<='Z') { // 结点信息pT->nodes[newNode].data = c; //给结点赋值pT->nodes[newNode].firstchild = NULL; //给结点赋值pT->n++; //结点数+1//newNode有爸爸，即parentif (parent!=-1) {//创建孩子结点p = (CNode *)malloc(sizeof(CNode));if (!p) exit(OVERFLOW);p->index = newNode;p->next = NULL;//儿子父亲相认if (pT->nodes[parent].firstchild==NULL) {pT->nodes[parent].firstchild = p;} else {for (q=pT->nodes[parent].firstchild; q->next; q=q->next) ;q->next = p;}}} else if (c=='(') { //是newNode的孩子CreateCTreeByGList(pT, newNode); //开始创建newNode的孩子} else if (c==',') { //是newNode的兄弟，即parent的下一个孩子CreateCTreeByGList(pT, parent); //parent的下一个孩子return OK; //newNode结点构造完成（自己创建了、孩子创建了、兄弟创建了）} else if (c==')') { //parent构造完毕return OK; } else {return ERROR; //格式错误}}return OK;
}/*-------------------------|6.76 以广义表的形式输出 |-------------------------*/
Status PrintAsGList(CTree T,int parent) {CNode *p;if (T.n<=0) return ERROR; visit(T.nodes[parent].data);if (T.nodes[parent].firstchild) {printf("(");for (p=T.nodes[parent].firstchild; p; p=p->next) {PrintAsGList(T, p->index);if (p->next) printf(",");}printf(")");}return OK;
}int main() {
/*6.75测试数据
A(B(E,F),C(G),D)
A
A(B)
A(B,C)
A(B,C(D,E))
*/CTree T;T.n=0;T.r=0;CreateCTreeByGList(&T, -1); //6.75PrintAsGList(T, T.r); //6.76return 0;
}

这篇关于[树] △ 由广义表构造树（孩子链表CTree）并以广义表的形式输出（严蔚敏《数据结构》6.75|6.76 ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

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

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代，文本到语音（Text-to-Speech, TTS）技术已成为人机交互的关键桥梁，无论是为视障人士提供辅助阅读，还是为智能助手注入声音的灵魂，TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术，再到现今的深度学习解决方案，TTS 技术经历了一段长足的进步。这篇文章将带您穿越时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2