∥ utype=0/1/2,mark是访问标记,未访问为0 GenListNode tlink ∥指向同一层下一结点的指针 union i har listname: ∥ utype=0,表头结点情形:存放表名 char atom; ∥ utype=1,存放原子结点的数据 GenListNode* hlink; ∥utpe=2,存放指向子表的指针 ublic GenListnode( int tp, char info):mark(0), utype(tp),tink(NUL)∥表头或原子结点构造函数 f( utype ==0)value. listname =info; else value. atom GenListNode (GenListNode* hp) ∥表构造函数 mark(0), utype(2), value hlink(hp)& char Info( GenListNode* elem 历返回表元素eem的值 i return( utype ==0)? elem->value listname elem->value. atom; class GenList ∥广义表类定义 private: ∥广义表头指针 void traverse( GenListNode *Is )i 义表遍历 void Remove( GenListNode* Is ) 将以ls为表头结点的广义表结构释放 Genlist( char& value ) ∥构造函数,vale是指定的停止建表标志数据 GenList ( ∥析构函数 ∥遍历广义表 (2)广义表遍历的递归算法 oid GenList traverse (t ∥共有函数 #include <iostream. h> void GenList traverse( GenListNode *Is)i ∥有函数,广义表的遍历算法 if( Is != NULL )4 if( Is->utype ==0)cout < ls->value listname <<'C; ∥表头结点 else if Is->utype ==1) 原子结点 if( Is->tlink NULL)cout < else if Is->utype ==2) /子表结点 if(ls-> value. hlink->mark=0) traverse(ls-> value. hlink);响表头搜索 se cout < Is->value. hlink ->value. lis tname: if(ls> tlink=NULL)cout<‘,’;int mark, utype; // utype ＝0 / 1 / 2, mark 是访问标记, 未访问为 0 GenListNode* tlink; //指向同一层下一结点的指针 union { //联合 char listname; // utype = 0, 表头结点情形：存放表名 char atom; // utype = 1, 存放原子结点的数据 GenListNode* hlink; // utype = 2, 存放指向子表的指针 } value; public: GenListNode ( int tp, char info ) : mark (0), utype (tp), tlink (NULL) //表头或原子结点构造函数 { if ( utype == 0 ) value.listname = info; else value.atom = info; } GenListNode (GenListNode* hp ) //子表构造函数 : mark (0), utype (2), value.hlink (hp) { } char Info ( GenListNode* elem ) //返回表元素 elem 的值 { return ( utype == 0 ) ? elem->value.listname : elem->value.atom; } }; class GenList { //广义表类定义 private: GenListNode *first; //广义表头指针 void traverse ( GenListNode * ls ); //广义表遍历 void Remove ( GenListNode* ls ); //将以 ls 为表头结点的广义表结构释放 public: 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 << ‘,’; }