广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。由于在表的描述中可以嵌套表，允许表中有表，所以可以通过递归实现广义表。
具体实现如下：
头文件
#pragma once//实现广义表的结构enum Type//枚举类型{ HEAD, VALUE, SUB,};struct GeneralizedNode//广义表的结点{ Type _type;//类型 GeneralizedNode* _next;//值相同层的下一个节点 union//共用体/联合 { int _value;//值节点 GeneralizedNode* _SubLink;//指向字表的指针 }; GeneralizedNode(); GeneralizedNode(Type type, int value); //全缺省构造函数};class Generalized{public: Generalized(); Generalized(const char* str);//构造 Generalized(const Generalized& g);//拷贝构造 Generalized& operator=(const Generalized& g); ~Generalized(); void Print(); size_t Size(); size_t Depth();protected: GeneralizedNode* _CreatList(const char*& str); GeneralizedNode* _Copy(GeneralizedNode* head); bool _isValue(char ch);//判断是否为字母或数字 void _Distory(GeneralizedNode* head); void _Print(GeneralizedNode* head); size_t _Size(GeneralizedNode* head); size_t _Depth(GeneralizedNode* head);protected: GeneralizedNode* _head;}; 各函数的具体实现
#include#include #include using namespace std;#include"Generalized.h"GeneralizedNode::GeneralizedNode():_next(NULL){}GeneralizedNode::GeneralizedNode(Type type, int value): _type(type), _next(NULL){ if (_type == VALUE) { _value = value; } if (_type == SUB) { _SubLink = NULL; }}Generalized::Generalized():_head(NULL){}Generalized::Generalized(const char* str)//构造函数: _head(NULL){ _head = _CreatList(str);}GeneralizedNode* Generalized::_CreatList(const char*& str){//广义表：(a, (b, c)) assert('(' == *str); str++; GeneralizedNode* head = new GeneralizedNode(HEAD, 0);//建立表的头结点 GeneralizedNode* cur = head; while (str) { if (_isValue(*str))//*str为字母或数字 { cur->_next = new GeneralizedNode(VALUE, *str);//建立value结点 cur = cur->_next; str++; } else if (*str == '(')//如果为（，则出现字表，进行递归调用 { GeneralizedNode* subNode = new GeneralizedNode(SUB, 0);//建立子表结点 cur->_next = subNode; cur = cur->_next; subNode->_SubLink = _CreatList(str);//_SubLink指向子表构造子表 } else if (*str == ')')//表示表的结束（包括子表）,返回表的头结点 { str++; return head; } else { str++; } } assert(false); return head;}bool Generalized::_isValue(char ch)//判断是否为字母或数字{ if (ch >= '0' && ch <= '9' || ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') { return true; } return false;}Generalized::Generalized(const Generalized& g)//拷贝构造函数{ _head = _Copy(g._head);}GeneralizedNode* Generalized::_Copy(GeneralizedNode* head){ GeneralizedNode* newhead = new GeneralizedNode(HEAD, 0); GeneralizedNode* cur = head; GeneralizedNode* newcur = newhead; while (cur) { if (cur->_type == VALUE)//cur._type为VALUE或SUB时建立结点，newcur才存在指向下一个结点 { newcur->_next = new GeneralizedNode(VALUE, cur->_value); newcur = newcur->_next; } if (cur->_type == SUB) { newcur->_next= new GeneralizedNode(SUB, 0); newcur = newcur->_next; newcur->_SubLink = _Copy(cur->_SubLink);//递归调用_Copy进行复制 } cur = cur->_next; } return newhead;}Generalized& Generalized::operator=(const Generalized& g)//传统写法{ if (this != &g) { GeneralizedNode* tmp = _Copy(g._head); _Distory(_head); _head = tmp; } return *this;}Generalized::~Generalized(){ _Distory(_head);}void Generalized::_Distory(GeneralizedNode* head){ GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; if (cur->_type == SUB) { _Distory(cur->_SubLink);//释放cur结点的字表 } cur = cur->_next; delete del; }}void Generalized::Print(){ _Print(_head); cout << endl;}void Generalized::_Print(GeneralizedNode* head){ GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << "("; } if (cur->_type == VALUE) { cout << (char)cur->_value;//强转为char类型 if (cur->_next)//如果cur->_next不为空打印“,” cout << ","; } if (cur->_type == SUB) { _Print(cur->_SubLink); if (cur->_next) cout << ","; } cur = cur->_next; } cout << ")";}size_t Generalized::Size(){ return _Size(_head);}size_t Generalized::_Size(GeneralizedNode* head){ GeneralizedNode* cur = head; size_t count = 0; while (cur) { if (cur->_type == VALUE) { ++count; } if (cur->_type == SUB) { count += _Size(cur->_SubLink); } cur = cur->_next; } return count;}size_t Generalized::Depth(){ return _Depth(_head);}size_t Generalized::_Depth(GeneralizedNode* head){ GeneralizedNode* cur = head; size_t depth = 1; while (cur) { if (cur->_type == SUB) { size_t cdepth = _Depth(cur->_SubLink); if (cdepth + 1 > depth)//比较子表深度，保存较大的 { depth = cdepth + 1; } } cur = cur->_next; } return depth;}
测试用例如下：
void Test(){ //Generalized g1("(a)"); //Generalized g2("(a,b)"); Generalized g3("(a,(a,b))"); Generalized g4("(a,(a,(b),c),d)"); Generalized g5 = g4; g5 = g3; //g1.Print(); //g2.Print(); g3.Print(); g4.Print(); g5.Print(); cout << "g3.Size():" << g3.Size() << endl; cout << "g4.Size():" << g4.Size() << endl; cout << "g3.Depth():" << g3.Depth() << endl; cout << "g4.Depth():" << g4.Depth() << endl;}