广义表的定义:
广义表是非线性的结构,是n个元素的有限序列。
举例:A=(a,b,(c,d))
我们先定义它的结构:
(1)它有三种节点,头节点、值节点、子表节点。
(2)两种指向下一节点的指针:指向下一值值节点的指针_next,指向子表节点的指针_sublink.
enum Type//用枚举形式来定义广义表中三种节点类型 { HEAD, //头类型 VALUE,//值类型 SUB,//子表类型 }; struct GeneralizedNode { Type _type;//类型 GeneralizedNode* _next;//指向下一节点的指针 union { int _value;//一个节点下一节点可能是值节点,也可能是子表节点 GeneralizedNode* _sublink; }; GeneralizedNode(Type type) :_next(NULL) , _type(type) {} GeneralizedNode(Type type,int value) :_next(NULL) , _type(type) , _value(value) {} };
下面,我们来看下实现的代码:
class Generalized { public: Generalized() :_head(NULL) {} Generalized(const char* str) { _head = _CreateList(str);//调用函数创建节点 } Generalized(const Generalized& gr) { _head = _Copy(gr._head);//调用函数拷贝节点 } Generalized& operator=(const Generalized& gr) { if (&gr != this) { _Copy(gr._head); _Destroy(_head); } return *this; } ~Generalized() { _Destroy(_head); } void Print() { _Print(_head); } size_t Size() { return _Size(_head); } size_t Depth() { return _Depth(_head); } protected: //拷贝广义表 GeneralizedNode* _Copy(GeneralizedNode* grhead) { GeneralizedNode* grcur = grhead; GeneralizedNode* newHead = new GeneralizedNode(HEAD); GeneralizedNode* newcur = newHead; while (grcur) { if (grcur->_type == VALUE) { GeneralizedNode* tmp = new GeneralizedNode(VALUE); newcur->_next = tmp; newcur = newcur->_next; newcur->_value = grcur->_value; } else if (grcur->_type == SUB) { GeneralizedNode* tmp = new GeneralizedNode(SUB); newcur->_next = tmp; newcur = newcur->_next; newcur->_sublink = _Copy(grcur->_sublink); } grcur = grcur->_next; } newcur = NULL; return newHead; } //释放广义表 void _Destroy(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; cur = cur->_next; if (del->_type == SUB) { _Destroy(del->_sublink); } else { delete del; del = NULL; } } } //打印 void _Print(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { cout << "("; } else if (cur->_type == VALUE) { cout << (char)(cur->_value); if (cur->_next) { cout << ","; } } else if (cur->_type == SUB) { _Print(cur->_sublink); if (cur->_next) { cout << ","; } } cur = cur->_next; } cout << ")"; } //判断是否是值 bool _IsValue(const char* str) { if (*str > 0 && *str<9 || *str>'a' && *str<'z' || *str>'A' && *str < 'Z') { return true; } else { return false; } } //创建节点 GeneralizedNode* _CreateList(const char* str) { assert(*str=='('); ++str; GeneralizedNode* head = new GeneralizedNode(HEAD); GeneralizedNode* cur = head; while (cur) { if (_IsValue(str)) { cur->_next = new GeneralizedNode(VALUE,*str); cur = cur->_next; str++; } else if (*str == '(') { GeneralizedNode* SubNode = new GeneralizedNode(SUB); cur->_next = SubNode; cur = cur->_next; SubNode->_sublink = _CreateList(str); str++; } else if (*str == ')') { str++; return head; } else { str++; } } cout << "广义表出错!" << endl; assert(false); return head; } //大小(值节点数) size_t _Size(GeneralizedNode* head) { GeneralizedNode* cur = head; size_t size = 0; while (cur) { if (cur->_type == VALUE) { size++; } else if (cur->_type == SUB) { size += _Size(cur->_sublink); } cur = cur->_next; } return size; } //深度 size_t _Depth(GeneralizedNode* head) { size_t depth = 1; GeneralizedNode* cur = head; while (cur) { if (cur->_type == SUB) { size_t curdepth = _Depth(cur->_sublink); if (curdepth + 1 > depth) { depth = curdepth + 1; } } cur = cur->_next; } return depth; } private: GeneralizedNode* _head; }; void Test() { Generalized gr1("()"); Generalized gr2("(a,b,(c,d))"); Generalized gr3("(a,b,(c,(d),e))"); Generalized gr4(gr3); gr1.Print(); cout << endl; gr2.Print(); cout << endl; gr3.Print(); cout << endl; gr4.Print(); cout << endl; size_t size = gr4.Size(); cout << "gr4大小:"<另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:【数据结构】广义表的默认成员函数、深度、大小、打印-创新互联
网页路径:http://cdkjz.cn/article/dpjspg.html