广义表的相关操作
//Generalized.h #pragma once #ifndef __GENERALIZED_H__ #define __GENERALIZED_H__ enum Type { HEAD, VALUE, SUB, }; struct GeneralizedNode { Type _type; GeneralizedNode* _next; union { int _value; GeneralizedNode* _sublink; }; GeneralizedNode() {} GeneralizedNode(Type type, const int value = 0) :_type(type), _next(NULL), _value(value) {} }; class Generalized { public: Generalized(); Generalized(const char* str); Generalized(const Generalized& g); Generalized& operator=(const Generalized& g); ~Generalized(); void Print()const; size_t Size()const; size_t Length()const; size_t Depth()const; protected: GeneralizedNode* _CreateList(const char* &str); GeneralizedNode* _Copy(GeneralizedNode* head); void _Destory(GeneralizedNode* head); void _PrintGeneral(GeneralizedNode* head)const; size_t _SizeGeneralized(GeneralizedNode* head)const; size_t _DepthGeneralized(GeneralizedNode* head)const; protected: GeneralizedNode* _head; }; #endif /*__GENERALIZED_H__*/
Generalized.cpp:
成都创新互联公司专注于沾益网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供沾益营销型网站建设,沾益网站制作、沾益网页设计、沾益网站官网定制、微信小程序定制开发服务,打造沾益网络公司原创品牌,更为您提供沾益网站排名全网营销落地服务。
#define _CRT_SECURE_NO_WARNINGS 1 #include#include "Generalized.h" #include Generalized::Generalized() :_head(NULL) {} Generalized::Generalized(const char* str) : _head(NULL) { _head = _CreateList(str); } GeneralizedNode* Generalized::_CreateList(const char* &str) { assert(str); while (isspace(*str)) { ++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 ((*str >= '0'&&*str <= '9') || (*str >= 'a'&&*str <= 'z') || (*str >= 'A'&&*str <= 'Z')) { cur->_next = new GeneralizedNode(VALUE, *str); cur = cur->_next; ++str; } else if (*str == ')') { ++str; break; } else { ++str; } } return head; } Generalized::Generalized(const Generalized& g) { this->_head = this->_Copy(g._head); } GeneralizedNode* Generalized::_Copy(GeneralizedNode* head) { assert(head); GeneralizedNode* cur = head; GeneralizedNode* retHead = NULL; GeneralizedNode* tmp = NULL; while (cur) { if (cur->_type == HEAD) { retHead = new GeneralizedNode(HEAD); tmp = retHead; } else if (cur->_type == VALUE) { tmp->_next = new GeneralizedNode(VALUE, cur->_value); tmp = tmp->_next; } else if (cur->_type == SUB) { tmp->_next = new GeneralizedNode(SUB); tmp->_next->_sublink = _Copy(cur->_sublink); tmp = tmp->_next; } cur = cur->_next; } return retHead; } Generalized& Generalized::operator=(const Generalized& g) { if (this->_head != g._head) { this->_Destory(this->_head); this->_Copy(g._head); } return *this; } Generalized::~Generalized() { this->_Destory(this->_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 Generalized::Print()const { this->_PrintGeneral(this->_head); } void Generalized::_PrintGeneral(GeneralizedNode* head)const { assert(head); GeneralizedNode* cur = head; while (cur) { if (cur->_type == HEAD) { std::cout << "("; } else if (cur->_type == VALUE) { std::cout << (char)cur->_value; if (cur->_next) { std::cout << ","; } } else if (cur->_type == SUB) { //(a,b,(c,d),(e,(f),h)) _PrintGeneral(cur->_sublink); if (cur->_next) { std::cout << ","; } } cur = cur->_next; } std::cout << ")"; } size_t Generalized::Size()const { return this->_SizeGeneralized(this->_head); } size_t Generalized::_SizeGeneralized(GeneralizedNode* head)const { if (head == NULL) { return 0; } size_t iCount = 0; GeneralizedNode* cur = head; while (cur) { if (cur->_type == VALUE) { ++iCount; } else if (cur->_type == SUB) { iCount += _SizeGeneralized(cur->_sublink); } cur = cur->_next; } return iCount; } size_t Generalized::Length()const { if (this->_head == NULL) { return 0; } GeneralizedNode* cur = this->_head->_next; size_t iCount = 0; while (cur) { ++iCount; cur = cur->_next; } return iCount; } size_t Generalized::Depth()const { return this->_DepthGeneralized(this->_head); } size_t Generalized::_DepthGeneralized(GeneralizedNode* head)const { assert(head); // D = (a,b,(c,d),(e,(f),h)) GeneralizedNode* cur = head; size_t max = 0; size_t d = 0; while (cur) { if (cur->_type == SUB) { d = _DepthGeneralized(cur->_sublink); if (max < d) { max = d; } } cur = cur->_next; } return max + 1; }
网页名称:广义表的相关操作
当前地址:http://myzitong.com/article/pdocjd.html