traverse( Is->tlink ) ∥向表尾搜索 else cout≤); 回2 对上图所示的广义表进行遍历,得到的遍历结果为A(C(E(x,y),a),DE,e)) (2)利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。 #include <iostream. h> void GenList traverse( GenListNode *Is)i Stack <GenListNode<Type>*>st; while( Is I =NULL)( l; if( ls->utype ==2)4 ∥表结点 if( ls->value. hlink->mark ==0) ∥该子表未访问过 i st Push( Is->tlink ) Is=Is->value hlink; ∥存下一结点地址,访问子表 ut < ls->value hlink-> value listname ∥该子表已访问过,仅输出表名 if Is->tlink I= NULL )i cout <<',' Is= ls->tlink; else i Ise if( ls->utype ==1) ∥原子结点 if(ls-> tlink i=NULL)cout<∵’; if ls->tlink = NULL )i ∥表访问完,子表结束处理 cout >>' if( st IsEmpty( )==0)i ∥栈不空 ∥退栈 if( Is!= NULL )cout <<',i else cout<<”); lse Is ls ->tlink 向表尾搜索traverse ( ls->tlink ); //向表尾搜索 } else cout << ‘)’; } 对上图所示的广义表进行遍历，得到的遍历结果为 A(C(E(x, y), a), D(E, e) )。 (2) 利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。 #include <iostream.h> #include “stack.h” void GenList :: traverse ( GenListNode *ls ) { Stack <GenListNode<Type> *> st; while ( ls != NULL ) { ls->mark = 1; if ( ls->utype == 2 ) { //子表结点 if ( ls->value.hlink->mark == 0 ) //该子表未访问过 { st.Push ( ls->tlink ); ls = ls->value.hlink; } //暂存下一结点地址, 访问子表 else { cout << ls->value.hlink->value.listname; //该子表已访问过, 仅输出表名 if ( ls->tlink != NULL ) { cout << ‘,’; ls = ls->tlink; } } } else { if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点 else if ( ls->utype == 1 ) { //原子结点 cout << ls->value.atom; if ( ls->tlink != NULL ) cout << ‘,’; } if ( ls->tlink == NULL ) { //子表访问完, 子表结束处理 cout >> ‘)’; if ( st.IsEmpty( ) == 0 ) { //栈不空 ls = st.GetTop ( ); st.Pop ( ); //退栈 if ( ls != NULL ) cout << ‘,’; else cout << ‘)’; } } else ls = ls->tlink; //向表尾搜索 } } 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 ∧ ∧ ∧ ∧