C++如何实现广义表详解
时间：2021-01-27 10:41:50 | 栏目：C代码 | 点击：次
以下给出几种简单的广义表模型：
由上图我们可以看到，广义表的节点类型无非head、value、sub三种，这里设置枚举类型，利用枚举变量来记录每个节点的类型：
enum Type
{
HEAD, //头节点
VALUE, //值节点
SUB, //子表节点
};
每个节点都有自己的类型以及next指针，除此之外，如果该节点是VALUE类型还要分配空间存储该节点的有效值；但是若该节点是SUB类型，就需定义一个指针指向子表的头。
这里我们可以用联合来解决这个问题。
（联合（或共同体）是一种不同数据类型成员之间共享存储空间的方法，并且联合体对象在同一时间只能存储一个成员值）
构造节点：
struct GeneralizedNode
{
Type _type; // 1.类型
GeneralizedNode* _next; //2.指向同层的下一个节点
union
{
char _value; // 3.有效值
GeneralizedNode* _subLink; // 3.指向子表的指针
};
GeneralizedNode(Type type = HEAD, char value = '0')
:_value(value)
,_type(type)
, _next(NULL)
{
if (_type == SUB)
{
_subLink = NULL;
}
}
};
广义表的定义及基本操作：
class Generalized
{
public:
//无参的构造函数,建立空的广义表
Generalized();
//建造广义表，有参数的构造函数
Generalized(const char* str);
//打印广义表
void Print();
//获取值节点的个数
size_t Amount();
//获取广义表的深度
size_t Depth();
//拷贝构造
Generalized(const Generalized& g);
////赋值运算符的重载
Generalized& operator=(const Generalized& g);
////析构函数
~Generalized();
protected:
void _Print(GeneralizedNode* head);
GeneralizedNode* _CreatList(const char*& str);
size_t _Amount(GeneralizedNode* head);
GeneralizedNode* _Copy(GeneralizedNode* head);
void _Destory(GeneralizedNode* head);
protected:
GeneralizedNode* _head; //记录广义表头指针
};
初始化建立广义表进行循环递归。遍历字符串时遇到字符就建立值节点，遇到'('就进行递归并建立子表；遇到')'就结束当前子表的建立，并返回当前子表的头指针。
GeneralizedNode* _CreatList(const char*& str)
{
assert(*str == '(');
GeneralizedNode* head = new GeneralizedNode(HEAD,'0');
GeneralizedNode* cur = head;
str++;
while (str != '\0')
{
if ((*str >= '0'&&*str <= '9') || (*str >= 'a'&&*str <= 'z') || (*str >= 'A'&&*str <= 'Z'))
{
cur->_next = new GeneralizedNode(VALUE, *str);
cur = cur->_next;
}
else if (*str == '(')
{
cur->_next = new GeneralizedNode(SUB);
cur = cur->_next;
cur->_subLink = _CreatList(str);
}
else if (*str == ')')
{
return head;
}
str++;
}
return head;
}
打印广义表：当节点的类型为SUB时进行递归，最后不要忘了每打印完一层要打印一个后括号。
void _Print(GeneralizedNode* head)
{
if (head == NULL)
{
cout << "Generalized table is NULL" << endl;
return;
}
GeneralizedNode* cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << '(';
}
else if (cur->_type == VALUE)
{
cout << cur->_value;
if (cur->_next)
{
cout << ',';
}
}
else if (cur->_type == SUB)
{
_Print(cur->_subLink);
if (cur->_next)
{
cout << ',';
}
}
cur = cur->_next;
}
cout << ')';
}
获取值节点的个数：设置count变量，遇到值节点就加1，遇到SUB节点进行递归并将返回值加给count
size_t _Amount(GeneralizedNode* head)
{
GeneralizedNode* begin = head;
size_t count = 0;
while (begin)
{
if (begin->_type == VALUE)
{
count++;
}
if (begin->_type == SUB)
{
count += _Amount(begin->_subLink);
}
begin = begin->_next;
}
return count;
}
广义表的深度：设置变量dp和max分别用来记录当前子表即当前SUB节点指向的子表深度，以及本层所有的SUB节点中深度最大的子表的深度。
size_t _Depth(GeneralizedNode* head)
{
if (_head == NULL)
{
return 0;
}
size_t dp=0;
GeneralizedNode* cur = head;
size_t max = 0;
while (cur)
{
if (cur->_type == SUB)
{
dp=_Depth(cur->_subLink);
if (max < dp)
{
max = dp;
}
}
cur = cur->_next;
}
return max+1;
}
销毁广义表：依次遍历节点，遇到子表递归，将子表的节点delete完成后，再回到当前层继续遍历。
void _Destory(GeneralizedNode* head)
{
if (head == NULL)
{
return;
}
while (head)
{
GeneralizedNode* begin = head->_next;
if (head->_type == SUB)
{
_Destory(head->_subLink);
}
delete head;
head = begin;
}
}
实例演示
定义：
广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
其中：
①ai--或者是原子或者是一个广义表。
②广义表通常记作：
Ls=( a1，a2，…，ai，…，an)。
③Ls是广义表的名字，n为它的长度。
④若ai是广义表，则称它为Ls的子表。
注意：
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。
④广义表是递归定义的
画图举例：
代码实现：
[cpp] view plain copy
#include <iostream>
using namespace std;
//表示广义表的结点类型
enum NodeType
{
HEAD_TYPE,//头结点类型
VALUE_TYPE,//值结点类型
SUB_TYPE//子表类型
};
//表示广义表结点的结构体
struct GeneraListNode
{
NodeType _type;//结点类型
GeneraListNode *_next;//存放结点的下一个元素的地址
//一个结点要么是值结点要么是子表，故用联合体来存放节省一定的空间
//若是值结点则存放的是值，是子表结点的话存放的是子表结点头结点的地址
union{
char _value;
GeneraListNode *_subLink;
};
GeneraListNode(NodeType type = HEAD_TYPE, char value = '\0')
:_type(type)
,_next(NULL)
{
if (type == VALUE_TYPE)
{
_value = value;
}else if(type == SUB_TYPE)
{
_subLink = NULL;
}
}
};
class GeneraList
{
private:
GeneraListNode *_link;//用来存放广义表头结点地址
public:
GeneraList(const char *str)
:_link(NULL)
{
_CreateGeneraList(_link, str);//根据指定序列创建广义表
}
~GeneraList()
{}
public:
void Print();//对外提供的打印广义表的接口
int Size();//广义表中值结点的数目的对外获取接口
int Depth();//广义表的最深层次的对外获取接口
private:
void _CreateGeneraList(GeneraListNode *& link, const char *& str);
bool _IsValue(const char ch);//判断指定字符是否为值结点所允许的类型
int _Size(GeneraListNode *head);//计算广义表中值结点的数目的实现
int _Depth(GeneraListNode *head);//计算广义表的最深层次的实现
void _Print(GeneraListNode *link);//打印广义表的接口的底层实现
};
//创建广义表
void GeneraList::_CreateGeneraList(GeneraListNode *& link, const char *& str)
{
//广义表最前端有一个头结点，用来记录实现广义表链表的首地址
//故每次调用该创建广义表的函数首先创建一个头结点
GeneraListNode* head = new GeneraListNode(HEAD_TYPE, NULL);
head->_next = NULL;
link = head;
GeneraListNode* cur = link;//用来记录创建广义表链表时当前创建出的结点位置游标指针
str++;//将广义表序列后移,相当于跳过了'('
while(*str != '\0')
{
if(_IsValue(*str)){//如果当前扫描到的字符是值
//创建一个值结点
GeneraListNode* newNode = new GeneraListNode(VALUE_TYPE, *str);
newNode->_next = NULL;
cur->_next = newNode;//将该值结点加入到链表中
cur = cur->_next;//游标后移
str++;//将广义表序列后移
}else if(*str == '('){//如果扫描到'('创建子表结点
GeneraListNode* subLink = new GeneraListNode(SUB_TYPE, NULL);
subLink->_next = NULL;
cur->_next = subLink;//将子表结点加入到链表中
cur = cur->_next;
_CreateGeneraList(cur->_subLink, str);//递归创建子表
}else if(*str == ')'){
str++;
return;//若扫描到')'表示广义表创建结束
}else{
str++;//空格等其他无效字符跳过
}
}
}
int GeneraList::Size()
{
return _Size(_link);
}
//计算广义表值结点的个数
int GeneraList::_Size(GeneraListNode *head)
{
int size = 0;
GeneraListNode *cur = head;
while(cur != NULL){
if(cur->_type == VALUE_TYPE){
++size;//遇到值结点则将size加一
}else if(cur->_type == SUB_TYPE){
size += _Size(cur->_subLink);//遇到子表进行递归
}
cur = cur->_next;
}
return size;
}
int GeneraList::Depth()
{
return _Depth(_link);
}
int GeneraList::_Depth(GeneraListNode *head)
{
int depth = 1,maxDepth = 1;//depth表示当前表的深度，maxDepth表示目前最大的深度
GeneraListNode *cur = head;
while(cur != NULL){
if(cur->_type == SUB_TYPE){
depth += _Depth(cur->_subLink);
}
if(depth > maxDepth){//更新最大深度
maxDepth = depth;
depth = 1;//将当前深度复位
}
cur = cur->_next;
}
return maxDepth;
}
void GeneraList::Print()
{
_Print(_link);
cout<<endl;
}
//打印广义表
void GeneraList::_Print(GeneraListNode *link)
{
GeneraListNode *cur = link;//遍历广义表的游标
while(cur != NULL){
if(cur->_type == VALUE_TYPE){
cout<<cur->_value;
if(cur->_next != NULL)
{
cout<<',';
}
}else if(cur->_type == HEAD_TYPE){
cout<<"(";
}else if(cur->_type == SUB_TYPE){
_Print(cur->_subLink);//遇到子表递归打印
if(cur->_next != NULL)//如果打印完子表后广义表未结束则打印','
{
cout<<",";
}
}
cur = cur->_next;
}
cout<<")";
}
bool GeneraList::_IsValue(const char ch)
{
if(ch >= 'a' && ch <= 'z' ||
ch >= 'A' && ch <= 'Z' ||
ch >= '0' && ch <= '(')
{
return true;
}
return false;
}
测试代码
[cpp] view plain copy
#include"GeneraList.hpp"
//测试空表
void Test1()
{
GeneraList genList("()");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//测试单层表
void Test2()
{
GeneraList genList("(a,b)");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//测试双层表
void Test3()
{
GeneraList genList("(a,b,(c,d))");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//测试多层表
void Test4()
{
GeneraList genList("(a,b,(c,d),(e,(f),h))");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
//测试多层空表
void Test5()
{
GeneraList genList("(((),()),())");
genList.Print();
cout<<"Size is :"<<genList.Size()<<endl;
cout<<"Depth is :"<<genList.Depth()<<endl<<endl;
}
int main()
{
Test1();
Test2();
Test3();
Test4();
Test5();
return 0;
}
运行结果
总结
以上就是关于C++如何实现广义表详解的全部内容，希望对有需要的人能有所帮助，如果有疑问欢迎大家留言讨论。