用C++语言数据结构写一个代码实现一个可运行代码,功能包括:用户从键盘输入描述广义表的字符串,系统实现创建广义表,求广义表的长度、深度,复制广义表,遍历广义表,取广义表的表头、表尾的操作。

时间: 2024-03-16 10:44:34 浏览: 19
好的,以下是我为您写的C++代码: ```c++ #include<iostream> #include<cstring> #include<stack> using namespace std; //广义表的节点类型 struct GLNode{ char data;//数据域 GLNode *sublist;//子表指针域 GLNode *next;//兄弟节点指针域 }; //广义表类 class GList{ private: GLNode *head;//头结点 GLNode *Create(string s, int &index);//创建广义表 void Destroy(GLNode *p);//销毁广义表 int Length(GLNode *p);//求广义表长度 int Depth(GLNode *p);//求广义表深度 GLNode *Copy(GLNode *p);//复制广义表 void Traverse(GLNode *p);//遍历广义表 GLNode *GetHead(GLNode *p);//取广义表的表头 GLNode *GetTail(GLNode *p);//取广义表的表尾 public: GList(){head = NULL;} ~GList(){Destroy(head);} void Create();//创建广义表 int Length();//求广义表长度 int Depth();//求广义表深度 GList Copy();//复制广义表 void Traverse();//遍历广义表 GLNode *GetHead();//取广义表的表头 GLNode *GetTail();//取广义表的表尾 }; GLNode *GList::Create(string s, int &index){ GLNode *p = NULL; char ch = s[index]; if(ch == '('){//子表 p = new GLNode; p->sublist = NULL; p->next = NULL; index++; ch = s[index]; GLNode *q = p; while(ch != ')'){ q->next = Create(s, index); q = q->next; ch = s[index]; } index++; } else if(ch == ')'){//空表 index++; } else{//原子 p = new GLNode; p->data = ch; p->sublist = NULL; p->next = NULL; index++; } return p; } void GList::Create(){ string s; cout << "请输入广义表的字符串表示:" << endl; cin >> s; int index = 0; head = Create(s, index); } void GList::Destroy(GLNode *p){ if(p){ Destroy(p->sublist);//递归销毁子表 Destroy(p->next);//递归销毁兄弟节点 delete p; } } int GList::Length(GLNode *p){ int len = 0; while(p){ if(p->sublist){//遍历子表 len += Length(p->sublist); } len++; p = p->next;//遍历兄弟节点 } return len; } int GList::Length(){ return Length(head);//从头结点开始遍历 } int GList::Depth(GLNode *p){ int max_depth = 0; while(p){ if(p->sublist){//遍历子表 int depth = Depth(p->sublist) + 1; if(depth > max_depth){ max_depth = depth; } } p = p->next;//遍历兄弟节点 } return max_depth; } int GList::Depth(){ return Depth(head);//从头结点开始遍历 } GLNode *GList::Copy(GLNode *p){ GLNode *q = NULL; if(p){ q = new GLNode; q->data = p->data; q->sublist = Copy(p->sublist);//递归复制子表 q->next = Copy(p->next);//递归复制兄弟节点 } return q; } GList GList::Copy(){ GList gl; gl.head = Copy(head);//从头结点开始复制 return gl; } void GList::Traverse(GLNode *p){ while(p){ if(p->sublist){//遍历子表 cout << "("; Traverse(p->sublist); cout << ")"; } else{ cout << p->data; } p = p->next;//遍历兄弟节点 } } void GList::Traverse(){ Traverse(head);//从头结点开始遍历 cout << endl; } GLNode *GList::GetHead(GLNode *p){ if(p && !p->sublist){//如果p非空且不是子表,则取p为表头 return p; } else{ return NULL; } } GLNode *GList::GetHead(){ return GetHead(head);//从头结点开始取表头 } GLNode *GList::GetTail(GLNode *p){ if(!p || !p->next){//如果p为空或者p没有兄弟节点,则取p为表尾 return p; } else{ stack<GLNode*> s;//用栈保存兄弟节点 while(p->next){ s.push(p->next); p = p->next; } GLNode *tail = GetTail(p->sublist);//递归取子表的表尾 while(!s.empty()){ GLNode *q = s.top(); s.pop(); tail->next = GetTail(q->sublist);//递归取兄弟节点的表尾 tail = tail->next; } return tail; } } GLNode *GList::GetTail(){ return GetTail(head);//从头结点开始取表尾 } int main(){ GList gl; gl.Create(); cout << "广义表的长度为:" << gl.Length() << endl; cout << "广义表的深度为:" << gl.Depth() << endl; cout << "广义表的遍历结果为:"; gl.Traverse(); GLNode *head = gl.GetHead(); if(head){ cout << "广义表的表头为:" << head->data << endl; } else{ cout << "广义表为空,无法取表头!" << endl; } GLNode *tail = gl.GetTail(); if(tail){ cout << "广义表的表尾为:" << tail->data << endl; } else{ cout << "广义表为空,无法取表尾!" << endl; } GList gl_copy = gl.Copy(); cout << "复制后的广义表的遍历结果为:"; gl_copy.Traverse(); return 0; } ``` 请注意,本代码中我使用了递归来处理广义表的各种操作,这种方法比较直观易懂,但是对于非常大的广义表可能会导致栈溢出,所以在实际使用中需要注意。

相关推荐

最新推荐

recommend-type

c++ 连接两个字符串实现代码 实现类似strcat功能

c++ 连接两个字符串实现代码 实现类似strcat功能,需要的朋友可以参考下
recommend-type

C++语言数据结构 串的基本操作实例代码

主要介绍了C语言数据结构 串的基本操作实例代码的相关资料,需要的朋友可以参考下
recommend-type

C++实现判断字符串是否回文实例解析

主要介绍了C++实现判断字符串是否回文,其中采用了数据结构中栈以及过滤字符等技术,,需要的朋友可以参考下
recommend-type

模拟通讯录-数据结构(顺序表实现基本功能).doc

模拟通讯录,设计相关数据结构,用菜单选择方式实现:通讯录的建立、通讯联系人的插入、删除、修改、查找等功能。
recommend-type

详解C++ string常用截取字符串方法

string常用截取字符串方法有很多,但是配合使用以下两种,基本都能满足要求: find(string strSub, npos); find_last_of(string strSub, npos); 其中strSub是需要寻找的子字符串,npos为查找起始位置。找到返回子...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

解释minorization-maximization (MM) algorithm,并给出matlab代码编写的例子

Minorization-maximization (MM) algorithm是一种常用的优化算法,用于求解非凸问题或含有约束的优化问题。该算法的基本思想是通过构造一个凸下界函数来逼近原问题,然后通过求解凸下界函数的最优解来逼近原问题的最优解。具体步骤如下: 1. 初始化参数 $\theta_0$,设 $k=0$; 2. 构造一个凸下界函数 $Q(\theta|\theta_k)$,使其满足 $Q(\theta_k|\theta_k)=f(\theta_k)$; 3. 求解 $Q(\theta|\theta_k)$ 的最优值 $\theta_{k+1}=\arg\min_\theta Q(
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。