广义表是一种数据结构,是线性表的推广。也有人称之为列表(lists)。广泛的用于人工智能等领域的表处理结构。
对于广义表,我们需要了解它的结构,通过学习广义表,也加深了对递归的了解。整个广义表都是了利用递归的特性实现的。
(一)首先我们要确定表中每个节点的结构,因为在广义表中有三种不同结构的节点,我们可以使用枚举enum列出我们所用到的结构节点类型。
enum Type { HEAD, SUB, VALUE };
(二)有了type类型,只要定义一个type类型的一个对象就可以轻松定义不同类型的节点。
struct GeneralizedNode { Type _type; union { int _value; GeneralizedNode* _SubLink; }; GeneralizedNode* _next; GeneralizedNode(Type type) { if (type == HEAD) { _type = HEAD; _next = NULL; } else if (type == VALUE) { _type = VALUE; _value = 0; _next = NULL; } else { _type = SUB; _SubLink = NULL; _next = NULL; } } };
我们可以看到一个广义表节点的结构就定义出来了。对于HEAD类型的节点不需要_value和_SubLink这两个数据成员,但是VALUE类型的节点需要_value,而SUB类型需要_SubLink。所以可以使用联合union来把_value和_SubLink放在同一块内存,以节省空间。
(三)有了节点的结构,下面就开始定义广义表的框架。
对于广义表,我们在意的是广义表的结构,也就是说我们实现构造,拷贝构造,赋值重载,打印表,析构等函数即可。
class GeneralizedList { public: GeneralizedList(const char* str); GeneralizedList(); ~GeneralizedList(); GeneralizedList(const GeneralizedList& g); GeneralizedList operator=(GeneralizedList g); size_t Size();//表中数据的个数 size_t Deepth();//表的深度 void Print();//打印表 private: size_t _Size(GeneralizedNode* head); size_t _Deepth(GeneralizedNode* head); bool _IsValue(const char& c); GeneralizedNode* _CreatList(const char*& str); void _Print(GeneralizedNode* head); GeneralizedNode* _Copy(GeneralizedNode* head); void _Release(GeneralizedNode* head); private: GeneralizedNode* _head; };
其实广义表的结构并不难,也就是一个主表上链了一些子表。在这里我们可以把子表看作是一个主表,利用递归的特性,达到分治的效果。这样实现起来会非常的好理解。
要使用递归就不能使用公有成员函数,因为我们需要一个变量来控制递归的开始和结束。显然一个私有成员变量_head是不能实现的,所以我们要定义一些内部私有函数来实现公有函数的功能,
GeneralizedList::GeneralizedList(const char* str) { _head = _CreatList(str); } GeneralizedList::GeneralizedList() :_head(NULL) { } GeneralizedList::~GeneralizedList() { _Release(_head); } GeneralizedList::GeneralizedList(const GeneralizedList& g) { _head = _Copy(g._head); } GeneralizedList GeneralizedList::operator = (GeneralizedList g)//不能加const和& { //if (this != &g) //{ // GeneralizedNode* tmp = _Copy(g._head); // _Release(_head); // _head = tmp; //} //return *this swap(_head, g._head);//现代写法 return *this; } void GeneralizedList::Print() { _Print(_head); } size_t GeneralizedList::Size() { return _Size(_head); } size_t GeneralizedList::Deepth() { return _Deepth(_head); }
可以看到我们通过间接调用私有方法,不仅利用了类的封装的特性,还控制了递归的层数。
(四)下面是私有方法的实现。
void GeneralizedList::_Release(GeneralizedNode* head) { GeneralizedNode* cur = head; while (cur) { GeneralizedNode* del = cur; cur = cur->_next; if (del->_type == SUB) { _Release(del->_SubLink); } delete del; } } bool GeneralizedList::_IsValue(const char& c) { if (c >= '1'&&c <= '9' || c >= 'a'&&c <= 'z' || c >= 'A'&& c <= 'Z') { return true; } return false; } GeneralizedNode* GeneralizedList::_CreatList(const char*& str) { assert(*str == '('); ++str; GeneralizedNode* newhead = new GeneralizedNode(HEAD);//biaozhi GeneralizedNode* cur = newhead; while (*str) { if (_IsValue(*str)) { GeneralizedNode* tmp = new GeneralizedNode(VALUE); tmp->_value = *str; cur->_next = tmp; cur = cur->_next; str++; } else if (*str == '(') { GeneralizedNode * subNode = new GeneralizedNode(SUB); cur->_next = subNode; cur = cur->_next; subNode->_SubLink = _CreatList(str); //如果是'('说明后面是一个子表,我们递归的创建子表, 然后返回子表的头指针,将头指针链到主表上 } else if (*str == ')') { str++; return newhead; } else { ++str; } } assert(false); return _head; } void GeneralizedList::_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打印',',防止在最后一个值后面打印一个',' { cout << ','; } } else { _Print(cur->_SubLink); if (cur->_next)//(1,2,(3,4))cur为空,不打印',' { cout << ','; } } cur = cur->_next; } cout << ')'; } size_t GeneralizedList::_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 GeneralizedList::_Deepth(GeneralizedNode* head) { GeneralizedNode* cur = head; size_t maxDeep = 1; while (cur) { if (cur->_type == SUB) { size_t deep = _Deepth(cur->_SubLink); //最深的一层子表返回1, // 每返回一层deep就会+1; if (deep + 1 > maxDeep) { maxDeep = deep + 1; } } cur = cur->_next; } return maxDeep; } GeneralizedNode* GeneralizedList::_Copy(GeneralizedNode* head) { GeneralizedNode* cur = head->_next; GeneralizedNode* newHead = new GeneralizedNode(HEAD); GeneralizedNode* newCur = newHead; while (cur) { if (cur->_type == VALUE) { newCur->_next = new GeneralizedNode(VALUE); newCur = newCur->_next; newCur->_value = cur->_value; } else if (cur->_type == SUB) { newCur->_next = new GeneralizedNode(SUB); newCur = newCur->_next; newCur->_SubLink = _Copy(cur->_SubLink); //如果是子表节点, //就递归拷贝子表,将子表的头节点返回链接到SUB节点上, //通过SubLink可以找到子表 } cur = cur->_next; } newCur = NULL; return newHead; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。