(3)Head(Head (Tail (Tail(Head(L3))))) (4)Head( Head(Tail(Tail(L4)))) (5)Head (Tail(Head (L5))) (6)Head( Head(Tail(Head(Tail (L6))))) 5-8广义表具有可共享性,因此在遍历一个广义表时必需为每一个结点增加一个标志域 mark,以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志,以后就不 再访问它 (1)试定义该广义表的类结构 (2)采用递归的算法对一个非递归的广义表进行遍历。 (3)试使用一个栈,实现一个非递归算法,对一个非递归广义表进行遍历。 【解答】(1)定义广义表的类结构 为了简化广义表的操作,在广义表中只包含字符型原子结点,并用除大写字母外的字 符表示数据,表头结点中存放用大写字母表示的表名。这样,广义表中结点类型三种:表 头结点、原子结点和子表结点。 ∥ Genlist类的前视声明 class GenListNode i ∥广义表结点类定义 friend class Genlist: private int mark, utype; ∥ape=0/1/2,mark是访问标记,未访问为0 GenListNode* tlink ∥指向同一层下一结点的指针 联合 char misname: ∥ope=0,表头结点情形:存放表名 char atom: ∥ape=1,存放原子结点的数据 GenListNode* hlink ∥ape=2,存放指向子表的指针 public: GenlistNode int p, char info):mark(O),ope(q),tlmk(ML)∥表头或原子结点构造函数 f if urpe ==0)value. misname=info; else value.ato GenLisINode(GenLisiNode* hp) 子表构造函数 mark(O), utype(2), value hlink (hp)0 char Info( GenListNode' elem ∥返回表元素elm的值 f return( urpe==0)? elem->value listname: elem->value. atom; }; class GenList i ∥广义表类定义 private ∥广义表头指针 void traverse( GenListNode'ls ) ∥广义表遍历 void Remove( GenListNode"ls )i ∥将以l为表头结点的广义表结构释放9 (3) Head (Head (Tail (Tail (Head (L3) ) ) ) ) (4) Head (Head (Tail (Tail (L4) ) ) ) (5) Head (Tail (Head(L5) ) ) (6) Head (Head (Tail (Head (Tail (L6) ) ) ) ) 5-8 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域 mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不 再访问它。 (1) 试定义该广义表的类结构； (2) 采用递归的算法对一个非递归的广义表进行遍历。 (3) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。 【解答】(1) 定义广义表的类结构 为了简化广义表的操作，在广义表中只包含字符型原子结点，并用除大写字母外的字 符表示数据，表头结点中存放用大写字母表示的表名。这样，广义表中结点类型三种：表 头结点、原子结点和子表结点。 class GenList; //GenList 类的前视声明 class GenListNode { //广义表结点类定义 friend class Genlist; private: 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: