广义表的C++简单实现
广义表是数据结构中非常关键的一部分,它的学习对于树和二叉树有很大的起承作用。那么,它是怎么实现的呢?广义表的实现应用到了一个很熟悉的算法——递归。来看看它的代码吧!
在宿迁等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站制作、成都网站设计 网站设计制作按需策划,公司网站建设,企业网站建设,品牌网站建设,成都营销网站建设,外贸营销网站建设,宿迁网站建设费用合理。
#pragma once #include#include using namespace std; enum Type { HEAD,//头 VALUE, //值 SUB, //子表 }; struct GeneralizedNode { Type _type; GeneralizedNode* _next; union { char _value; GeneralizedNode* _sublink; }; GeneralizedNode(Type type=HEAD,char value=0) :_type(type) ,_next(NULL) { if(_type==VALUE) { _value=value; } else if(_type==SUB) { _sublink=NULL; } } }; class Generalized { public: Generalized(const char* str) :_head(NULL) { _head=_CreateList(str); } Generalized() :_head(new GeneralizedNode()) {} ~ Generalized() { _Clear(_head); _head=NULL; } size_t Depth() //深度 { return _Depth(_head); } void Print() { _Print(_head); cout< _head,g._head); return *this; } protected: GeneralizedNode* _head; GeneralizedNode* _CreateList(const char* &str) { assert(str && *str=='('); ++str; GeneralizedNode* head=new GeneralizedNode(HEAD); GeneralizedNode* cur=head; while(*str) { if(_Isvalue(*str)) { cur->_next=new GeneralizedNode(VALUE,*str); cur=cur->_next; str++; } else if(*str=='(') { cur->_next=new GeneralizedNode(SUB); cur=cur->_next; cur->_sublink=_CreateList(str); } else if(*str==')') { ++str; return head; } else { ++str; } } assert(false); return head; } bool _Isvalue(char ch) { if( (ch>='0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch<='z')) { return true; } else { return false; } } /*int _Depth(GeneralizedNode* head) { GeneralizedNode* cur=head; int max=0; if(!cur) { return 1; } if(cur->_type==VALUE) { return 0; } for( max=0;cur;cur=cur->_next) { int dep=_Depth(cur->_next); if(dep>max) { max=dep; } } return max+1; }*/ size_t _Depth(GeneralizedNode* head) { size_t dep=1; GeneralizedNode* cur=head; while(cur!=NULL) { if(cur->_type==SUB) { if(_Depth(cur->_sublink)+1> dep) { dep=_Depth(cur->_sublink)+1 ; } } cur=cur->_next; } return dep; } void _Clear(GeneralizedNode* head) { GeneralizedNode* cur = head; while(cur != NULL) { GeneralizedNode* del = cur; cur = cur->_next; if(del->_type == SUB) { _Clear(del->_sublink); } delete del; } } void _Print(GeneralizedNode* head) { GeneralizedNode* cur=head; while(cur) { if(cur->_type==HEAD) { cout<<"("; } else if(cur->_type==VALUE) { cout< _value; if(cur->_next) { cout<<"," ; } } else { _Print(cur->_sublink); if(cur->_next) { cout<<","; } } cur=cur->_next; } cout<<")"; } size_t _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; } GeneralizedNode* _Copy(GeneralizedNode* head) { GeneralizedNode* newHead=new GeneralizedNode(HEAD); assert(head->_type==HEAD); GeneralizedNode* cur=head->_next; GeneralizedNode* newcur=newHead; while(cur) { if(cur->_type==VALUE) { newcur->_next=new GeneralizedNode(VALUE,cur->_value); newcur=newcur->_next ; } else if(cur->_type==SUB) { newcur->_next=new GeneralizedNode(SUB); newcur=newcur->_next; newcur->_sublink=_Copy(cur->_sublink); } cur=cur->_next; } return newHead; } };
代码虽然看起来很长,但是只要你理解了其结构,相信是不难的。
博主也是调试了好久的~~~~~~~~~~~~
网页题目:广义表的C++简单实现
本文路径:http://pwwzsj.com/article/goigdj.html