广义表是我第一次用递归接触链式的数据结构,其结构如下:
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; };
如有什么不足或疑问希望提出。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。