C++数据结构广义表
GeneralList-广义表
站在用户的角度思考问题，与客户深入沟通，找到阳原网站设计与阳原网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都做网站、网站建设、企业官网、英文网站、手机端网站、网站推广、域名与空间、网页空间、企业邮箱。业务覆盖阳原地区。
广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。
广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。
<1> A = ()
<2> B = (a,b)
<3> C = (a,b,(c,d))
<4> D = (a,b,(c,d),(e,(f),h))
<5> E = (((),()))
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
using namespace std;
enum Type
{
HEAD,
VALUE,
SUB
};
struct GeneralizedNode
{
Type _type;//类型
GeneralizedNode* _next;//指向同层下一个结点
union
{
//int _value;
char _value;
GeneralizedNode* _subLink;//指向子表的指针
};
GeneralizedNode(Type type = VALUE, const int value = 0)
:_type(type)
,_next(NULL)
,_value(value)
{}
};
class Generalized
{
public:
Generalized()
:_head(NULL)
{}
Generalized(const char* str)
:_head(NULL)
{
_head = _CreateList(str);
}
void Print() const
{
_Print(_head);
cout< } size_t Size() const { return _Size(_head); } size_t Depth() const { return _Depth(_head); } //===========新加的 Generalized(const Generalized& g); Generalized& operator=(Generalized g); // 现代写法 ~Generalized(); protected: GeneralizedNode* _CreateList(const char*& str); void _Print(GeneralizedNode* head) const; bool _IsValue(char ch); size_t _Size(GeneralizedNode* head) const; size_t _Depth(GeneralizedNode* head) const; GeneralizedNode* _Copy(const GeneralizedNode* head); void _Destory(GeneralizedNode* head); protected: GeneralizedNode* _head; }; bool Generalized:: _IsValue(char ch) { if ((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) { return true; } else { return false; } } GeneralizedNode* Generalized::_CreateList(const char*& str)//注意& { assert(str); assert(*str == '('); // D = (a,b,(c,d),(e,(f),h)) GeneralizedNode* head = new GeneralizedNode(HEAD); GeneralizedNode* cur = head; ++str; while (*str != '\0') { if (*str == '(')// 有子层 { cur->_next = new GeneralizedNode(SUB); cur = cur->_next; cur->_subLink = _CreateList(str);//下一层 } else if(_IsValue(*str)) { cur->_next = new GeneralizedNode(VALUE, *str); cur = cur->_next; ++str; } else if (*str == ')') { ++str;// **********更新上一层的str break; } else // 其他情况 *str为 逗号 空格 制表符 等 { ++str; } } return head; } void Generalized::_Print(GeneralizedNode* head)const { assert(head && head->_type == HEAD); GeneralizedNode* cur = head->_next; cout<<"("; while(cur) { if (cur->_type == VALUE) { cout< cur = cur->_next; if (cur != NULL) { cout<<","; } } else if (cur->_type == SUB) { _Print(cur->_subLink); cur = cur->_next; if (cur != NULL) { cout<<","; } } } cout<<")"; } size_t Generalized::_Size(GeneralizedNode* head) const { assert(head && head->_type == HEAD); GeneralizedNode* cur = head->_next; size_t count = 0; while(cur) { if (cur->_type == VALUE) { count++; } else if(cur->_type == SUB) { count += _Size(cur->_subLink); } cur = cur->_next; } return count; } // 有问题 //size_t Generalized::_Depth(GeneralizedNode* head) const //{ //assert(head && head->_type == HEAD); //GeneralizedNode* cur = head->_next; //size_t depth = 1; //while(cur) //{ //if (cur->_type == SUB) //{ //depth += _Depth(cur->_subLink); //} // //cur = cur->_next; //} // //return depth; //} size_t Generalized::_Depth(GeneralizedNode* head) const { assert(head && head->_type == HEAD); GeneralizedNode* cur = head->_next; size_t depth = 1; while (cur) { if (cur->_type == SUB) { size_t SubDepth = _Depth(cur->_subLink); if (depth < 1 + SubDepth) // 找最大的 depth 注意 不要用 depth = depth + SubDepth { depth = 1 + SubDepth; } } cur = cur->_next; } return depth; } Generalized:: Generalized(const Generalized& g) { _head = _Copy(g._head); } GeneralizedNode* Generalized::_Copy(const GeneralizedNode* head) { assert(head && head->_type == HEAD); const GeneralizedNode* cur = head->_next; GeneralizedNode* retHead = new GeneralizedNode(HEAD); GeneralizedNode* newNode = retHead; while (cur) { if (cur->_type == VALUE) { newNode->_next = new GeneralizedNode(VALUE, cur->_value); newNode = newNode->_next; } else if (cur->_type == SUB) { newNode->_next = new GeneralizedNode(SUB); newNode = newNode->_next; newNode->_subLink = _Copy(cur->_subLink); } cur = cur->_next; } return retHead; } Generalized& Generalized::operator=(Generalized g) // 现代写法 { swap(_head, g._head); return *this; } Generalized::~Generalized() { _Destroy(_head); } void Generalized::_Destory(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; cur = cur->_next; if (del->_type == SUB) { _Destory(del->_subLink); } delete del; del = NULL; } } void test_G_chuangjian() { char* str = "(a,b,(c,d))"; Generalized g(str); g.Print(); cout< cout< cout<<"============"< char* str2 = "(a,b,(c,d),(e,(f),h))"; Generalized g2(str2); g2.Print(); cout< cout< cout<<"============"< Generalized g3(g2); g3.Print(); cout< cout< cout<<"============"< Generalized g4; g4 = g2; g4.Print(); cout< cout< } int main() { test_G_chuangjian(); return 0; }
本文名称：C++数据结构广义表
网页链接：http://scyanting.com/article/pisooe.html
