用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;
}
```
请注意,本代码中我使用了递归来处理广义表的各种操作,这种方法比较直观易懂,但是对于非常大的广义表可能会导致栈溢出,所以在实际使用中需要注意。