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<<cur->_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;//廣義表為空時，深度為1GeneralizedNode*?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;}

轉載于:https://blog.51cto.com/lovemeright/1765692

總結

以上是生活随笔為你收集整理的GeneralList-广义表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。