【代码】C++实现广义表及其测试用例-创新互联
广义表是我第一次用递归接触链式的数据结构，其结构如下：
HEAD->VAL->VAL->LINK(->HEAD.....)->VAL->......
在这里，我们的头结点与link节点是不存储数据的，由此我们便可以定义出节点的数据结构：
typedef int DataType;
enum NodeType//枚举类型定义节点类型
{
HEAD,
VALUE,
SUB,
};
struct GeneralizedNode
{
public:
GeneralizedNode()
:_next(NULL)
, _link(NULL)
{}
NodeType _type;
GeneralizedNode* _next;
union//因为link与value是不可能同时存在的，故用共同体节省空间
{
GeneralizedNode* _link;
DataType _value;
};
};因为广义表是链式的嵌套结构，所以我们必须用递归来进行遍历，这里面递归的方式有很多种，可以循环套递归，也可以递归套递归，也可以递归套循环，根据我们不同的需求，可以吧这三种方法都运用在合适的地方，这里，我简单的实现了，返回对象的层数，数据个数，以及一些常用的成员函数，其代码如下：
class Generalized
{
public:
Generalized()
:_head(NULL)
{}
Generalized(const char *str)//构造函数是用字符串来体现广义表如（1,2，（2,3））
{ //这样可以更好的体现出广义表的结构
_head = _CreatList(str);
}
~Generalized()
{
_Destory(_head);
}
void Print()//控制台打印广义表，也是打印出字符串类型
{
_Print(_head);
}
Generalized(const Generalized &g)
{
_head = _Copy(g._head);
}
Generalized&operator = (Generalized g)
{
swap(_head, g._head);
return *this;
}
size_t Depth()
{
return _Depth(_head);
}
size_t Size()
{
size_t size = 0;
_Size(_head, size);
return size;
}
protected:
size_t _Depth(GeneralizedNode* head)
{
size_t depth = 1;
GeneralizedNode* cur = head;
while (cur)
{
if (cur->_type == SUB)
{
size_t newdepth = _Depth(cur->_link) + 1;
depth = depth < newdepth ? newdepth : depth;
}
cur = cur->_next;
}
return depth;
}
void _Size(GeneralizedNode* head, size_t &size)
{
GeneralizedNode* cur = head;
while (cur)
{
if (cur->_type == VALUE)
++size;
else if (cur->_type == SUB)
_Size(cur->_link, size);
cur = cur->_next;
}
}
GeneralizedNode* _Copy(GeneralizedNode *head)
{
GeneralizedNode* cur = head;
GeneralizedNode* newHead = new GeneralizedNode;
GeneralizedNode*tail = newHead;
tail->_type = HEAD;
while (cur)
{
if (cur->_type == SUB)
{
tail->_next = new GeneralizedNode;
tail = tail->_next;
tail->_type = SUB;
tail->_link = _Copy(cur->_link);
}
else if (cur->_type == VALUE)
{
tail->_next = new GeneralizedNode;
tail = tail->_next;
tail->_type = VALUE;
tail->_value = cur->_value;
}
cur = cur->_next;
}
return newHead;
}
void _Print(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
while (cur)
{
if (cur->_type == HEAD)
{
cout << "(";
}
else if (cur->_type == VALUE)
{
cout << cur->_value;
if (cur->_next!=NULL&&
cur->_next->_type == VALUE)
cout << ",";
}
else
_Print(cur->_link);
cur = cur->_next;
}
cout << ")";
}
GeneralizedNode* _CreatList(const char* &str)
{
assert('(' == *str);
GeneralizedNode* head = new GeneralizedNode;
GeneralizedNode* cur = head;
head->_type = HEAD;
while (*++str)
{
if (IsValue(str))
{
cur->_next = new GeneralizedNode;
cur = cur->_next;
cur->_type = VALUE;
cur->_value = *str;
str++;
}
else if (')' == *str)
{
return head;
}
else if ('(')
{
cur->_next = new GeneralizedNode;
cur = cur->_next;
cur->_type = SUB;
cur->_link = _CreatList(str);
}
cur->_next = NULL;
*str++;
}
return head;
}
bool IsValue(const char *str)//判断表内存储数据是否为所需数据类型
{
if (*str <= '9'&&
*str >= '0')
return true;
return false;
}
void _Destory(GeneralizedNode*head)
{
GeneralizedNode*cur = head;
if (cur->_value == SUB)
_Destory(cur->_link);
else if (cur->_next != NULL)
_Destory(cur->_next);
delete cur;
}
protected:
GeneralizedNode* _head;
};如有什么不足或疑问希望提出。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
分享标题：【代码】C++实现广义表及其测试用例-创新互联
当前路径：http://mswzjz.cn/article/ccsjod.html