四回Q D-吨位2团囚 n-{[[2 c口[a[2山 Lc叫[[ 4-6利用广义表的head和tai操作写出函数表达式,把以下各题中的单元素 banana从广义表中分离 出来 ()LI(apple, pear, banana, orange) (2)L2((apple, pear),(banana, orange)) (3)L3(((apple),(pear),(banana),(orange))) (4)L4((((apple))),((pear),(banana), orange (5)LS((((apple), pear ), banana), orange) (6)L6(apple,(pear,(banana), orange)) 【解答】 (1)Head(Tail (Tail(LD))) 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))))) 4-7广义表具有可共享性,因此在遍历一个广义表时必需为每一个结点增加一个标志域mark,以记录 该结点是否访问过。一旦某一个共享的子表结点被作了访问标志,以后就不再访问它 (1)试定义该广义表的类结构 (2)采用递归的算法对一个非递归的广义表进行遍历 (3)试使用一个栈,实现一个非递归算法,对一个非递归广义表进行遍历。 【解答】(1)定义广义表的类结构 为了简化广义表的操作,在广义表中只包含字符型原子结点,并用除大写字母外的字符表示数据, 表头结点中存放用大写字母表示的表名。这样,广义表中结点类型三种:表头结点、原子结点和子表 结点。 class GenList; ∥ Genlist类的前视声 GenListNode i ∥广义表结点类定义 friend class Genlist:4-6 利用广义表的 head 和 tail 操作写出函数表达式，把以下各题中的单元素 banana 从广义表中分离 出来： (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) ) ) ) ) 4-7 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域 mark，以记录 该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。 (1) 试定义该广义表的类结构； (2) 采用递归的算法对一个非递归的广义表进行遍历。 (3) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。 【解答】(1) 定义广义表的类结构 为了简化广义表的操作，在广义表中只包含字符型原子结点，并用除大写字母外的字符表示数据， 表头结点中存放用大写字母表示的表名。这样，广义表中结点类型三种：表头结点、原子结点和子表 结点。 class GenList; //GenList 类的前视声明 class GenListNode { //广义表结点类定义 friend class Genlist; private: D A B C c e a L b c d J1 J2 J3 a D A 0 A 0 D 2 2 2 1 c B 0 B 1 e C 0 C 1 a L 0 L 2 1 b 1 c 1 d ∧ ∧ ∧ ∧ ∧ J1 0 J1 2 2 J2 0 J2 2 1 a 2 J3 0 J3 2 ∧ ∧ ∧