【数据结构】广义表的默认成员函数、深度、大小、打印
广义表的定义:
广义表是非线性的结构,是n个元素的有限序列。
举例:A=(a,b,(c,d))
我们先定义它的结构:
(1)它有三种节点,头节点、值节点、子表节点。
(2)两种指向下一节点的指针:指向下一值值节点的指针_next,指向子表节点的指针_sublink.
enumType//用枚举形式来定义广义表中三种节点类型{HEAD,//头类型VALUE,//值类型SUB,//子表类型};structGeneralizedNode{Type_type;//类型GeneralizedNode*_next;//指向下一节点的指针union{int_value;//一个节点下一节点可能是值节点,也可能是子表节点GeneralizedNode*_sublink;};GeneralizedNode(Typetype):_next(NULL),_type(type){}GeneralizedNode(Typetype,intvalue):_next(NULL),_type(type),_value(value){}};
下面,我们来看下实现的代码:
classGeneralized{public:Generalized():_head(NULL){}Generalized(constchar*str){_head=_CreateList(str);//调用函数创建节点}Generalized(constGeneralized&gr){_head=_Copy(gr._head);//调用函数拷贝节点}Generalized&operator=(constGeneralized&gr){if(&gr!=this){_Copy(gr._head);_Destroy(_head);}return*this;}~Generalized(){_Destroy(_head);}voidPrint(){_Print(_head);}size_tSize(){return_Size(_head);}size_tDepth(){return_Depth(_head);}protected://拷贝广义表GeneralizedNode*_Copy(GeneralizedNode*grhead){GeneralizedNode*grcur=grhead;GeneralizedNode*newHead=newGeneralizedNode(HEAD);GeneralizedNode*newcur=newHead;while(grcur){if(grcur->_type==VALUE){GeneralizedNode*tmp=newGeneralizedNode(VALUE);newcur->_next=tmp;newcur=newcur->_next;newcur->_value=grcur->_value;}elseif(grcur->_type==SUB){GeneralizedNode*tmp=newGeneralizedNode(SUB);newcur->_next=tmp;newcur=newcur->_next;newcur->_sublink=_Copy(grcur->_sublink);}grcur=grcur->_next;}newcur=NULL;returnnewHead;}//释放广义表void_Destroy(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;cur=cur->_next;if(del->_type==SUB){_Destroy(del->_sublink);}else{deletedel;del=NULL;}}}//打印void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE){cout<<(char)(cur->_value);if(cur->_next){cout<<",";}}elseif(cur->_type==SUB){_Print(cur->_sublink);if(cur->_next){cout<<",";}}cur=cur->_next;}cout<<")";}//判断是否是值bool_IsValue(constchar*str){if(*str>0&&*str<9||*str>'a'&&*str<'z'||*str>'A'&&*str<'Z'){returntrue;}else{returnfalse;}}//创建节点GeneralizedNode*_CreateList(constchar*str){assert(*str=='(');++str;GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;while(cur){if(_IsValue(str)){cur->_next=newGeneralizedNode(VALUE,*str);cur=cur->_next;str++;}elseif(*str=='('){GeneralizedNode*SubNode=newGeneralizedNode(SUB);cur->_next=SubNode;cur=cur->_next;SubNode->_sublink=_CreateList(str);str++;}elseif(*str==')'){str++;returnhead;}else{str++;}}cout<<"广义表出错!"<<endl;assert(false);returnhead;}//大小(值节点数)size_t_Size(GeneralizedNode*head){GeneralizedNode*cur=head;size_tsize=0;while(cur){if(cur->_type==VALUE){size++;}elseif(cur->_type==SUB){size+=_Size(cur->_sublink);}cur=cur->_next;}returnsize;}//深度size_t_Depth(GeneralizedNode*head){size_tdepth=1;GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){size_tcurdepth=_Depth(cur->_sublink);if(curdepth+1>depth){depth=curdepth+1;}}cur=cur->_next;}returndepth;}private:GeneralizedNode*_head;};voidTest(){Generalizedgr1("()");Generalizedgr2("(a,b,(c,d))");Generalizedgr3("(a,b,(c,(d),e))");Generalizedgr4(gr3);gr1.Print();cout<<endl;gr2.Print();cout<<endl;gr3.Print();cout<<endl;gr4.Print();cout<<endl;size_tsize=gr4.Size();cout<<"gr4大小:"<<size<<endl;intdepth=gr4.Depth();cout<<"gr4深度:"<<depth<<endl;}intmain(){Test();system("pause");return0;}
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。