十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
GeneralList-广义表:
成都创新互联公司专注于成都网站制作、成都网站设计、网页设计、网站制作、网站开发。公司秉持“客户至上,用心服务”的宗旨,从客户的利益和观点出发,让客户在网络营销中找到自己的驻足之地。尊重和关怀每一位客户,用严谨的态度对待客户,用专业的服务创造价值,成为客户值得信赖的朋友,为客户解除后顾之忧。
广义表是非线性的结构,是线性表的一种扩展,是有n个元素组成有限序列。
广义表的定义是递归的,因为在表的描述中又得到了表,允许表中有表。
广义表结构
protected: GeneralizedNode* _head;
节点结构
struct GeneralizedNode { GeneralizedNode(Type type=HEAD,char value=0) :_type(type) ,_next(NULL) { if(_type==VALUE) { _value=value; } else if(_type==SUB) { _sublink=NULL; } } Type _type; GeneralizedNode* _next; union//联合(共用体) { GeneralizedNode* _sublink; char _value; }; };
利用联合来实现不同节点的成员不同
enum Type { HEAD, VALUE, SUB, };
构造函数:构造函数调用_CreateList函数
GeneralizedNode* _CreateList(const char*& str)//加引用避免子表递归返回时str跳到递归之前的位置 { assert(str&&*str=='('); GeneralizedNode* head=new GeneralizedNode(HEAD); GeneralizedNode* cur = head; ++str; 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; }
析构函数:调用_Destroy
void _Destory(GeneralizedNode* head) { GeneralizedNode* cur=head; while(cur) { GeneralizedNode* del=cur;//记录要删除的节点 if(cur->_type==SUB) { _Destory(cur->_sublink);//递归的条件:遇到SUB类型的节点 } cur=cur->_next; delete del; } }
打印函数:调用_Print
void _Print(GeneralizedNode* head) { GeneralizedNode* cur=head; while(cur) { if(cur->_type==HEAD)//遇到头结点,打印前括号 { cout<<"("; } else if(cur->_type==VALUE) { cout<_value; if(cur->_next)//当前value节点后面不为空,打印逗号 { cout<<","; } } else { _Print(cur->_sublink);//递归的条件:遇到SUB类型的节点 if(cur->_next)//子表递归返回时的next不为空 { cout<<","; } } cur=cur->_next; } cout<<")";//表遍历完成之后,打印表的后括号 }
求广义表的size:调用_Size
size_t _Size(GeneralizedNode* head) { GeneralizedNode* cur=head; size_t size=0; while(cur) { if(cur->_type==VALUE)//遇到value,size++ { ++size; } else if(cur->_type==SUB) { size+=_Size(cur->_sublink);//递归的条件:遇到SUB类型的节点 } cur=cur->_next; } return size; }
求广义表的深度:调用_Depth
size_t _Depth(GeneralizedNode* head) { size_t index=1;//广义表为空时,深度为1 GeneralizedNode* cur=head; while(cur) { if(cur->_type==SUB) { size_t subDepth=_Depth(cur->_sublink);//递归的条件:遇到SUB类型的节点 if(subDepth+1>index)//更新深度 { index=subDepth+1; } } cur=cur->_next; } return index; }
拷贝构造函数:调用_Copy
GeneralizedNode* _Copy(GeneralizedNode* head) { assert(head->_type==HEAD);//传入的是头结点才正确 GeneralizedNode* newhead=new GeneralizedNode(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);//递归进入子表 //递归的条件:遇到SUB类型的节点 } cur=cur->_next; } return newhead; }
赋值操作符的重载(采用现代写法)
Generalized& operator=(Generalized g)//现代写法 { swap(_head,g._head); return *this; }