第5章递归与广义表 (I)LI(apple, pear, banana, orange) (2)L2(apple, pear),(banana, orange)) (3)L3(((apple),(pear),(banana), (orange))) (4)L4((((apple))),(pear),(banana), orange (5)L5((((apple), pear), banana), orange 6)L6(apple,(pear, (banana), orange)) 【解答】 (1)Head(Tail (Tail (Ll)) (2)Head(Head(Tail (L2))) (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广义表具有可共享性,因此在遍历一个广义表时必需为每一个结点增加一个标志域 mak,以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志,以后就不 再访问它 (1)试定义该广义表的类结构 (2)采用递归的算法对一个非递归的广义表进行遍历 (3)试使用一个栈,实现一个非递归算法,对一个非递归广义表进行遍历 【解答】 (1)定义广义表的类结构 为了简化广义表的操作,在广义表中只包含字符型原子结点,并用除大写字母外的字 符表示数据,表头结点中存放用大写字母表示的表名。这样,广义表中结点类型三种:表 头结点、原子结点和子表结点。 class genlis ∥ Genlist类的前视声明 class GenListNode i ∥广义表结点类定义 friend class Genlist: private int mark, utype; ∥utpe=0/1/2,mark是访问标记,未访问为0 GenListNode" tlink; ∥指向同一层下一结点的指针 联合 char listname: ∥uype=0,表头结点情形:存放表名 ∥ utype=1,存放原子结点的数据 GenListNode+ hlink: ∥ utype=2,存放指向子表的指针 GenListNode( int tp, char info):mark(0), utype(tp),tink(NULL)∥表头或原子结点构造 函数第 5 章 递归与广义表 61 (1) L1(apple, pear, banana, orange) (2) L2((apple, pear), (banana, orange)) (3) L3(((apple), (pear), (banana), (orange))) (4) L4((((apple))), ((pear)), (banana), orange) (5) L5((((apple), pear), banana), orange) (6) L6(apple, (pear, (banana), orange)) 【解答】 (1) Head (Tail (Tail (L1) ) ) (2) Head (Head (Tail (L2) ) ) (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) //表头或原子结点构造 函数