广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名注册、虚拟主机、营销软件、网站建设、闽侯网站维护、网站推广。思想:广义表就类似下图的结构,他的大体(下图第一行)相当于一个带头结点的链表,
代码思想,首先要有一个头结点为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 < 创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网页题目:数据结构--广义表-创新互联
文章来源:http://cdkjz.cn/article/csiojg.html