广义表(C++实现)
2024-08-29 08:32:34
广义表是非线性结构，其定义是递归的。
以下给出几种简单的广义表模型：
由上图我们可以看到，广义表的节点类型无非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;
}
}
广义表的拷贝构造及赋值运算符重载与构造函数的递归方式类似，这里就不再阐述冗余信息。
最新文章
- 同一网站中HTML相对路径引用
- XE3随笔11：Merge、Clone、ForcePath
- php开发memcached
- python中使用多继承
- C#基础精华02（静态类，值类型，引用类型，枚举，结构，ref与out）
- 【暑假】[实用数据结构]KMP
- BWT(Burrows-Wheeler Transformation)的讲解及java实现
- &lt;五&gt;读《《大话设计模式》》之工厂模式
- ExtJs3学习资料分享
- python 二进制转换
- PowerApps 经验总结
- 【编程技巧】 iOS 5的StoryBoard(故事板)的一些用法
- vue组件，可以通过npm引用的组件
- numpy通用函数
- system.net.httpclient 4.0 vs2015
- Socket网络编程基本介绍
- Hibernate注解与JPA
- HDU1098---数学
- bzoj2301
- Docker容器挂载主机目录访问出现Permission denied的解决办法