Genlist( char& value ) ∥构造函数,abe是指定的停止建表标志数据 -GenList (; ∥析构函数 ∥遍历广义表 (2)广义表遍历的递归算法 void GenList: traverse (i ∥共有函数 void GenList: traverse( GenListNode*ls){∥私有函数,广义表的遍历算法 if( Is I= NULL)( if( Is->utype ==0)cout <</s->value listname <<' ∥表头结点 else if( ls->urpe==1)t ∥原子结点 if( ls->link I= NULL )cout <<', else if( ls->urpe ==2) ∥子表结点 ir(bs-> value hlink->mark==0) traverse(ls-> value hlink);m表头搜索 if( Is->tlink NULL)cout <<', traverse( ls->tlink ) ∥向表尾搜索 0 oA foell- 國@{國國l 对上图所示的广义表进行遍历,得到的遍历结果为A(C(E(x,y),a),D(E,e)) (3)利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址 #include <iostream. h> include“ stack h” void GenList: traverse( GenListNode "ls)i Stack <GenListNode<Type>">sH;10 Genlist ( char& value ); //构造函数, value 是指定的停止建表标志数据 ~GenList ( ); //析构函数 void traverse ( ); //遍历广义表 } (2) 广义表遍历的递归算法 void GenList :: traverse ( ) { //共有函数 traverse ( first ); } #include <iostream.h> void GenList :: traverse ( GenListNode * ls ) { //私有函数, 广义表的遍历算法 if ( ls != NULL ) { ls->mark = 1; if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点 else if ( ls->utype == 1 ) { //原子结点 cout << ls->value.atom; if ( ls->tlink != NULL ) cout << ‘,’; } else if ( ls->utype == 2 ) { //子表结点 if ( ls->value.hlink->mark == 0 ) traverse( ls->value.hlink ); //向表头搜索 else cout << ls->value.hlink->value.listname; if ( ls->tlink != NULL ) cout << ‘,’; } traverse ( ls->tlink ); //向表尾搜索 } else cout << ‘)’; } 对上图所示的广义表进行遍历，得到的遍历结果为 A(C(E(x, y), a), D(E, e) )。 (3) 利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。 #include <iostream.h> #include “stack.h” void GenList :: traverse ( GenListNode *ls ) { Stack <GenListNode<Type> *> st; 0 0 C 0 1 a 0 2 0 1 x 0 1 y 0 1 e 0 0 E 0 2 0 0 D 0 2 0 0 A 0 2 ∧ ∧ ∧ ∧