最近学习了广义表，我们知道广义表也是一种线性表，而顾名思义广义表就是不止一个表，下面来举个栗子：
A=( )
B=（1 , 2，3）
C=(1 ,2 ,3, ( a , b ,c) )
D=(1, 2, 3, (a,( b,c),d),4)
以上A,B,C,D都是广义表，只不过深度不一样，也就是括号的对数不一样，A是个特殊的广义表，即空表。B里面有三个元素，C里面有6个元素，包括一个子表（a，b，c），C也同理，只不过多了一层子表。由此可总结为一句话：表里有表
这样看可能不太直观，下面以广义表C为例来看一下它的结构图：
（图画得有点丑，不要吐槽我）
每当遇到一个前括号，就要创建一个子表，直到遇见收括号。
那么如何创建一个广义表呢，在创建节点结构体的时候，我们要考虑每个节点的类型，有可能是头结
点，也有可能是子表节点，也有可能是普通的值节点，所以在构造节点的时候就要定义一个三元体，由
于是表里有表，我们可以用递归的方法来解决广义表的问题，每个子表都可以递归为一个子问题，就可
以很轻松的解决掉这个问题了。
下面是具体实现的代码：
先构造一个三元结构体：
计算
安全
数据库
网络和加速
企业服务
enum Type
{
HEAD,
VALUE,
SUB,
};
template<class T>
struct GeneralizedNode
{
Type _type;
GeneralizedNode<T>* _next;
union
{
char _value;
GeneralizedNode<T>* _sublink; //子表的头结点
};
public:
GeneralizedNode(Type type = HEAD,char value = '\0')
:_type(type)
,_next(NULL)
{
if (type == VALUE)
{
_value = value;
}
else if (type == SUB)
{
_sublink = NULL;
}
}
};下面来构造一个广义表类
template<class T>
class GeneralizedList
{
public:
GeneralizedList()
:_head(new GeneralizedNode<T>(HEAD))
{}
GeneralizedList(const char* str)
{
_head=_CreateList(str);
}
GeneralizedList(const GeneralizedList& g) //拷贝构造
{
_head = Copy(g._head;)
}
size_t Size()
{
return size(_head);
}
size_t depth()
{
return Depth(_head);
}
void print()
{
Print(_head);
}
protected:
GeneralizedNode<T>* _CreateList(const char*& str)
{
assert(str && *str == '(');
++str;
GeneralizedNode<T>* Head = new GeneralizedNode<T>(HEAD,NULL);
GeneralizedNode<T>* cur = Head;
while (*str)
{
if (_IsValue(*str))
{
cur->_next = new GeneralizedNode<T>(VALUE,*str);
cur = cur->_next;
str++;
}
else if (*str == '(')
{
GeneralizedNode<T>* newNode= new GeneralizedNode<T>(SUB); //将一个子表结点加入到链表中
cur->_next = newNode;
cur = cur->_next;
cur->_sublink = _CreateList(str);
str++;//递归创建一个子表结点
}
else if (*str == ')') //表示一个表已经结束
{
str++;
return Head;
}
else
{
str++; //不需要处理的情况
}
}
assert(false);
return Head;
}
size_t Depth(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* cur = head;
size_t depth = 1;
while (cur)
{
if (cur->_type == SUB)
{
size_t subdepth = Depth(cur->_sublink);
if (subdepth+1 > depth)
{
depth=subdepth;//保存较大的深度
}
}
cur = cur->_next;
}
return depth;
}
size_t size(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* cur = head;
size_t count = 0;
while (cur)
{
if (cur->_type != SUB)
{
count++;
}
else
{
count += size(cur->_sublink);
}
cur = cur->_next;
}
return count;
}
void Print(GeneralizedNode<T>* head)
{
GeneralizedNode<T>* cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << '(';
}
else if (cur->_type == VALUE)
{
cout << cur->_value ;
if (cur->_next != NULL)
{
cout << ',' ;
}
}
else if (cur->_type == SUB)
{
Print(cur->_sublink);
if (cur->_next != NULL)
{
cout << ',';
}
}
cur = cur->_next;
}
cout << ')';
}
bool _IsValue(char ch) //检查是否为合法值
{
if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z'))
{
return true;
}
return false;
}
protected:
GeneralizedNode<T>* _head;
};下面给出测试代码：
#include"Generalized.h"
void Test()
{
char* ch = "(a,b,c,(1,2),c)";
GeneralizedList<char> gl1(ch);
gl1.print();
cout << endl;
cout << "广义表深度为：" << gl1.depth() << endl;
cout << "广义表大小为：" << gl1.Size() << endl;
}
int main()
{
Test();
getchar();
return 0;
}运行结果：
以上就是C++实现广义表的方法啦，里面也许还存在着一些问题，希望大家能够指正出来，共同促进学习。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
