数据结构--广义表
广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。
成都创新互联主营弓长岭网站建设的网络公司,主营网站建设方案,成都App制作,弓长岭h5小程序设计搭建,弓长岭网站营销推广欢迎弓长岭等地区企业咨询
思想:广义表就类似下图的结构,他的大体(下图第一行)相当于一个带头结点的链表,
代码思想,首先要有一个头结点为HEAD类型,每一个广义表有且只有一个HEAD,而后每个节点如果有分支则把它定义为SUB类型,SUB便是它分支的一个新头他有一个sublink指针指向他的第一个元素,如果没有则是VALUE类型。
#pragma once #include#include using namespace std; enum Type { HEAD, VALUE, SUB }; struct generalizelistNode { generalizelistNode * _next; Type _type; union { char _value; generalizelistNode *sublink; }; generalizelistNode(Type type=HEAD,char value=0) :_type(type), _value(value), _next(NULL) { } }; class Generalizelist { protected: bool isvalue(char c) { if (c >= 'a'&&c<='z' || c>='A'&&c <= 'Z' || c>='0'&&c <= '9') { return true; } else { return false; } } public: Generalizelist(char *&str) { _head = generallist(str); } ~Generalizelist() { Empty(_head); } void Print() { _Print(_head); } Generalizelist& operator=(Generalizelist g) { swap(_head, g._head); } Generalizelist(Generalizelist &g) { _head = copy(g._head); } int Size() { return _Size(_head); } int Depth() { return _Depth(_head); } protected: generalizelistNode* generallist(char *&str) { assert(*str == '('); generalizelistNode *head = new generalizelistNode(HEAD); generalizelistNode *cur = head; str++; while (*str) { if (isvalue(*str)) { generalizelistNode *Node = new generalizelistNode(VALUE,*str); cur->_next = Node; cur = Node; str++; } else if (*str == '(') { generalizelistNode *sub = new generalizelistNode(SUB); cur->_next = sub; cur = sub; sub->sublink = generallist(str); } else if (*str==')') { ++str; return head; } else { str++; } } } void _Print(generalizelistNode *head) { generalizelistNode *cur = head; while (cur) { if (cur->_type == HEAD) { cout << '('; } else if (cur->_type == VALUE) { cout << cur->_value; if (cur->_next) { cout << ","; } } else { _Print(cur->sublink); } cur = cur->_next; } cout << ")"; } generalizelistNode * copy(generalizelistNode *&_cur) { generalizelistNode *cur = _cur; generalizelistNode *newhead = new generalizelistNode(HEAD); generalizelistNode *tmp = newhead; cur = cur->_next; while (cur) { if (cur->_type == VALUE) { generalizelistNode *node = new generalizelistNode(VALUE, cur->_value); tmp->_next = node; tmp = node; cur = cur->_next; } else { generalizelistNode *node = new generalizelistNode(SUB); tmp->_next = node; tmp = node; tmp->sublink = copy(cur->sublink); cur = cur->_next; } } return newhead; } void Empty(generalizelistNode *&head) { generalizelistNode *tmp = head; head = head->_next; delete tmp; while (head) { if (head->_type == VALUE) { generalizelistNode *tmp = head; head = head->_next; delete tmp; } else if (head->_type == SUB) { generalizelistNode *tmp = head; Empty(tmp->sublink); head = head->_next; } } } int _Size(generalizelistNode *&cur) { int count = 0; generalizelistNode *tmp = cur; while (tmp) { if (tmp->_type == VALUE) { count++; tmp = tmp->_next; } else if (tmp->_type == SUB) { count += _Size(tmp->sublink); tmp = tmp->_next; } else { tmp = tmp->_next; } } return count; } int _Depth(generalizelistNode *&cur) { generalizelistNode *tmp = cur; int depth = 1; while (tmp) { int sub_depth=1; if (tmp->_type == SUB) { sub_depth = _Depth(tmp->sublink); tmp = tmp->_next; if (sub_depth + 1 > depth) { depth += sub_depth; } } else { tmp = tmp->_next; } } return depth; } private: generalizelistNode *_head; }; void Test() { char *str1 = "(a,b,(c,d),e,f)"; Generalizelist T1(str1); T1.Print(); Generalizelist T2(T1); cout <
当前题目:数据结构--广义表
标题网址:http://pwwzsj.com/article/pigsgp.html