/**********************
WZ ASUST 2016
表的实现与表头表尾问题
缺函数：找值
**********************/
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;
//实现广义表的结构
// 节点的类型：来代替直接写3类 结构体
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;
};
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);
}
//销毁广义表：依次遍历节点，遇到子表递归，将子表的节点delete完成后，再回到当前层继续遍历。
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;
}
//打印广义表：当节点的类型为SUB时进行递归，最后不要忘了每打印完一层要打印一个后括号。
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);
}
//获取值节点的个数：设置count变量，遇到值节点就加1，遇到SUB节点进行递归并将返回值加给count
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;
}
//广义表的深度：设置变量 分别用来记录当前子表即当前SUB节点指向的子表深度，以及本层所有的SUB节点中深度最大的子表的深度。
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;
}
int main()
{
//Generalized g1("(a)");
//Generalized g2("(a,b)");
Generalized g3("(a,(c,d))");
Generalized g4("(a,(b,(c),d),e)");
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;
return 0;
}/*************************
除了表头即是表尾
有隐含的括号问题
************************/
原文：http://wzsts.blog.51cto.com/10251779/1765581