清华大学：《数据结构及其应用》课程教学资源（试卷习题）试题6

5-1已知A为整数数组,试写出实现下列运算的递归算法 (1)求数组A中的最大整数 (2)求n个整数的和 (3)求n个整数的平均值 【解答】 class RecureArray i ∥数组类声明 int· Elements; ∥数组指针 ∥数组尺寸 ∥当前已有数组元素个数 public Recurve Array( int MaxSize =10) Array Sie( MaxSize ) Elements( new int[MaxSie]) cRecurveArray (i delete Elements: j 输入数组的内容 int n ); 求最大值 int Sum(intn片; 求数组元素之和 noat Average( int n ) ∥求数组元素的平均值 void RecurveArray: Inputarray(){/输入数组的内容 cout Elements[j; int RecurveArray : Markey( intn)t ∥递归求最大值 f(n== l)return Elements[OI if( Elementsn-1>temp)return Elements[n-1; int Recurve Array : Sum( int n)i ∥递弟归求数组之和 if(n==1) else return Elements[n-1]+ Sum(r1); float RecurveArray {∥递归求数组的平均值

1 5-1 已知 A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组 A 中的最大整数。 (2) 求 n 个整数的和。 (3) 求 n 个整数的平均值。 【解答】 #include class RecurveArray { //数组类声明 private: int *Elements; //数组指针 int ArraySize; //数组尺寸 int CurrentSize; //当前已有数组元素个数 public : RecurveArray ( int MaxSize =10 ) : ArraySize ( MaxSize ), Elements ( new int[MaxSize] ){ } ~RecurveArray ( ) { delete [ ] Elements; } void InputArray(); //输入数组的内容 int MaxKey ( int n ); //求最大值 int Sum ( int n ); //求数组元素之和 float Average ( int n ); //求数组元素的平均值 }; void RecurveArray :: InputArray ( ){ //输入数组的内容 cout > Elements[i]; } int RecurveArray :: MaxKey ( int n ) { //递归求最大值 if ( n == 1 ) return Elements[0]; int temp = MaxKey ( n - 1 ); if ( Elements[n-1] > temp ) return Elements[n-1]; else return temp; } int RecurveArray :: Sum ( int n ) { //递归求数组之和 if ( n == 1) return Elements[0]; else return Elements[n-1] + Sum (n-1); } float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0];

else return((float)Elements[n-1]+(n-D)*Average(n-1))/n; int main( int arg, char"argv[)t cout 0.n=0 v=akm(m, 1)); ∥m>0.n>0 return akm(m-1, v); 计算akm(2,1)的递归调用树如图所示:

2 else return ( (float) Elements[n-1] + ( n - 1) * Average ( n - 1 ) ) / n; } int main ( int argc, char* argv [ ] ) { int size = -1; cout > size; RecurveArray ra ( size ); ra.InputArray(); cout 0, n == 0 else return akm ( m-1, akm ( m, n-1 ) ); // m > 0, n > 0 } (2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从 结构中独立出来： unsigned akm ( unsigned m, unsigned n ) { unsigned v; if ( m == 0 ) return n+1; // m == 0 if ( n == 0 ) return akm ( m-1, 1 ); // m > 0, n ==0 v = akm ( m, n-1 ) ); // m > 0, n > 0 return akm ( m-1, v ); } 计算 akm(2, 1)的递归调用树如图所示：

akm(1, 3) akm=5 akm(1 akm =3 =akm(1,2) akmn(0,4)=5 y=2 akm(1,0) 用到一个栈记忆每次递归调用时的实参值,每个结点两个域{m,m}。对以上实例,栈 的变化如下: V vn 1n vn 1 1 vN 改akm(m-1,1) 改akm(m-1,1) 改akn(m-1)改abmn(m-1,y) 0 改akm(m-1,1)v=n+1=2改aAm(m-1,)改akm(m-1,)改aAm(m-1,)栈空,返回y=5 v=n+1=3v=n+1=4y=n+1=5 相应算法如下 #include #define maxie 3500 unsigned akm( unsigned m, unsigned n)i stack st( maxSize ) node w; unsigned v; while( stGetTop(). vm>0) 川计算akn(m-1,antm,m1)) while( st GetTop().I7>0) 川计算akm(m,m1),直到akm(m,0) w=st. GerTop(: st Pop(): 川计算akm(m-1,1) 1; St Push(w);

3 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm, vn}。对以上实例，栈 的变化如下： 相应算法如下 #include #include “stack.h” #define maxSize 3500; unsigned akm ( unsigned m, unsigned n ) { struct node { unsigned vm, vn; } stack st ( maxSize ); node w; unsigned v; w.vm = m; w.vn = n; st.Push (w); do { while ( st.GetTop( ).vm > 0 ) { //计算 akm(m-1, akm(m, n-1) ) while ( st.GetTop( ).vn > 0 ) //计算 akm(m, n-1), 直到 akm(m, 0) { w.vn--; st.Push( w ); } w = st.GetTop( ); st.Pop( ); //计算 akm(m-1, 1) w.vm--; w.vn = 1; st.Push( w ); akm(2, 1) v =akm(2, 0) akm(1, 1) v =akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(1, 3) v = akm(1, 2) v = akm(1, 1) v = akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(0, 3) = 4 akm(0, 4) = 5 v = 2 v = 2 v = 3 v = 4 v = 3 akm = 5 akm = 5 akm = 3 2 1 2 1 2 1 2 1 2 1 1 3 2 0 1 1 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) 改 akm(m-1,1) v = n+1= 2 改 akm(m-1,v) 改 akm(m-1,v) v = n+1 = 3 vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn 1 3 1 3 1 3 1 3 0 4 1 2 1 2 1 2 0 3 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) v = n+1 = 2 改 akm(m-1,v) 改 akm(m-1,v) 改 akm(m-1,v) 栈空, 返回 v = 5 v = n+1 = 3 v = n+1 = 4 v = n+1 = 5

∥直到akm(0,akm(1,*)) w= st.GerTopo; st Pop();v=ww++;计算v=akm(1,*)+1 if( st IsEmpty(==0) ∥如果栈不空,改栈顶为(m-1,y) iw=st GetTopO: st Pop(): wvm wn=v: stPush( w):) I while(st. IsEmpro==0); 5-3【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为 v[1]lw(2]…,w[m。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之 和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真):否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此 背包问题的递归定义如下:) 此时背包问题一定有解 False 总重量不能为负数 KNAP(s, n)= s>0且n0且n≥1所选物品中不包括wn时 KNAP(s-wnl, n-1) 所选物品中包括n时 【解答】根据递归定义,可以写出递归的算法, enu boolean Knap( int s, int n)i if(s0&&n<1)return False; if( Knap(s-wIn] l)==True {cou≤<Wn]<‘,’; return True; return Knap(s, 1); 若设w={0,1,2,4,8,16,32},s=51,n=6。则递归执行过程如下 eturn True,完成 Kma(51-32,5) return True,打印3 nap(19-16,4 return True,打印16 nap(3-8, 3) return False Knap(3,3) return T return F Knap(3-4, 4) return False Knap(3, 2) return Tr s=-1<0 return False Knape3-2, 1)return True,打印2 Knap(1-1,0) I return True,打印1 return True 5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋 盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者

4 } //直到 akm( 0, akm( 1, * ) ) w = st.GetTop(); st.Pop( ); v = w.vn++; //计算 v = akm( 1, * )+1 if ( st.IsEmpty( ) == 0 ) //如果栈不空, 改栈顶为( m-1, v ) { w = st.GetTop(); st.Pop( ); w.vm--; w.vn = v; st.Push( w ); } } while ( st.IsEmpty( ) == 0 ); return v; } 5-3 【背包问题】设有一个背包可以放入的物品的重量为 s，现有 n 件物品，重量分别为 w[1], w[2], …, w[n]。问能否从这 n 件物品中选择若干件放入此背包中，使得放入的重量之 和正好为 s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。（提示：此 背包问题的递归定义如下：）          − − −      = = ( [ ], 1) [ ] ( , 1) 0 1 [ ] False 0 1 False 0 True 0 ( , ) 所选物品中包括 时 或 且 所选物品中不包括 时 且 物品件数不能为负数 总重量不能为负数 此时背包问题一定有解 KNAP s w n n w n KNAP s n s n w n s n s s KNAP s n 【解答】根据递归定义，可以写出递归的算法。 enum boolean { False, True } boolean Knap( int s, int n ) { if ( s == 0 ) return True; if ( s 0 && n < 1 ) return False; if ( Knap ( s – W[n], n-1 ) == True ) { cout << W[n] << ‘ , ’; return True; } return Knap( s, n-1 ); } 若设 w = { 0, 1, 2, 4, 8, 16, 32 }，s = 51, n = 6。则递归执行过程如下 递 归 Knap(51, 6) return True, 完成 Knap(51-32, 5) return True, 打印 32 Knap(19-16, 4) return True, 打印 16 Knap(3-8, 3) return False Knap(3, 3) return True, 无动作 s = -5 < 0 return False Knap(3-4, 4) return False Knap(3, 2) return True, 无动作 s = -1 < 0 return False Knap(3-2, 1) return True, 打印 2 Knap(1-1, 0) return True, 打印 1 s = 0 return True 5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1 行，第 2 行，…。第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋 盘的合法布局都必须满足 3 个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者

同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提 示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向 反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子 恢复安放该棋子前的状态,试探本行的第+1列。) 【解答】此为典型的回溯法问题 次对角线 1#次对角线 2#次对角线 3#次对角线 4#次对角线 5#次对角线 6#次对角线 0#主对角线 #主对角线 2#主对角线 主对角线 4#主对角线 5#主对角线 6#主对角线 在解决8皇后时,采用回溯法。在安放第i行皇后时,需要在列的方向从1到n试 探(j=1,…,n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它 皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后 不动,递归安放第计1行皇后 解题时设置4个数组 coln]:coll标识第i列是否安放了皇后 md2n-1]:muk]标识第k条主对角线是否安放了皇后 sd2n-1]:sak]标识第k条次对角线是否安放了皇后 q]:q[记录第i行皇后在第几列 利用行号和列号j计算主对角线编号k的方法是k=n+i-1;计算次对角线编号k的 方法是k=计j。n皇后问题解法如下 void Queen( int i)i for intj=1; j i(co=0&&md叶r1=0&&sd==0){∥第i行第j列没有攻击 col=m+r1=s汁=l;q= ∥在第i行第j列安放皇后 出一个布局 forG=0;j<=n;+)cout≤<q<∵,; cout << endl else Queen(i+1); ∥在第计1行安放皇后 co]=md叶+广1=sd=0;q[=0; ∥撤消第i行第j列的皇后

5 同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提 示：用回溯法。在第 n 行第 j 列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、 反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子， 恢复安放该棋子前的状态，试探本行的第 j+1 列。) 【解答】此为典型的回溯法问题。 在解决 8 皇后时，采用回溯法。在安放第 i 行皇后时，需要在列的方向从 1 到 n 试 探( j = 1, …, n )：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它 皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后 不动，递归安放第 i+1 行皇后。 解题时设置 4 个数组： col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] ：md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] ：sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] ：q[i] 记录第 i 行皇后在第几列 利用行号 i 和列号 j 计算主对角线编号 k 的方法是 k = n+i-j-1；计算次对角线编号 k 的 方法是 k = i+j。n 皇后问题解法如下： void Queen( int i ) { for ( int j = 1; j <= n; j++ ) { if ( col[j] == 0 && md[n+i-j-1] == 0 && sd[i+j] == 0 ) { //第 i 行第 j 列没有攻击 col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; //在第 i 行第 j 列安放皇后 if ( i == n ) { //输出一个布局 for ( j = 0; j <= n; j++ ) cout << q[j] << ‘,’; cout << endl; } else Queen ( i+1 ); //在第 i+1 行安放皇后 } col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; //撤消第 i 行第 j 列的皇后 } } 0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线 6# 次对角线 5# 次对角线 4# 次对角线 3# 次对角线 2# 次对角线 0# 次对角线 1# 次对角线 0 1 2 3 0 1 2 3    

5-5已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归 算法 (1)求链表中的最大整数。 (2)求链表的结点个数。 (3)求所有整数的平均值 【解答】 ∥定义在头文件" RecurveList h"中 class ListNode i ∥链表结点类 ∥结点数据 Listooder°lnk; ∥结点指针 Listnode( const int item):dao(lem,ink(NUL){}构造函数 ∥链表类 private ListNode first, current; int Max( listNode v; int Num( LisinNode v) noat Ag( ListNode f, int& n )i Lit(: firsT(NULl,cren(NULL){}∥构造函数 -List( ∥析构函数 Listnode* Ney node( const int iten);∥创建链表结点,其值为iem void New List const int revalue ) ∥建立链表,以输入 revalue结束 void PrintList ( 输出链表所有结点数据 int GetMax (return Max(first );1 求链表所有数据的最大值 int genU(){ return num(frst;}/求链表中数据个数 foat GetAg(return Ag(first )) ∥求链表所有数据的平均值 }; ListNode' List New Node( const int item )i ∥创建新链表结点 ListNode "newnode= new ListNode(item); return new node void List New List( const int revalue)( ∥建立链表,以输入 revalue结束 first= NULL; int value; ListNode g:

6 5-5 已知 f 为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归 算法： (1) 求链表中的最大整数。 (2) 求链表的结点个数。 (3) 求所有整数的平均值。 【解答】 #include //定义在头文件"RecurveList.h"中 class List; class ListNode { //链表结点类 friend class List; private: int data; //结点数据 ListNode *link; //结点指针 ListNode ( const int item ) : data(item), link(NULL) { } //构造函数 }; class List { //链表类 private: ListNode *first, current; int Max ( ListNode *f ); int Num ( ListNode *f ); float Avg ( ListNode *f, int& n ); public: List ( ) : first(NULL), current (NULL){ } //构造函数 ~List ( ){ } //析构函数 ListNode* NewNode ( const int item ); //创建链表结点, 其值为 item void NewList ( const int retvalue ); //建立链表, 以输入 retvalue 结束 void PrintList ( ); //输出链表所有结点数据 int GetMax ( ) { return Max ( first ); } //求链表所有数据的最大值 int GetNum ( ) { return Num ( first ); } //求链表中数据个数 float GetAvg ( ) { return Avg ( first ); } //求链表所有数据的平均值 }; ListNode* List :: NewNode ( const int item ) { //创建新链表结点 ListNode *newnode = new ListNode (item); return newnode; } void List :: NewList ( const int retvalue ) { //建立链表, 以输入 retvalue 结束 first = NULL; int value; ListNode *q;

提示 cin > value 输入 while( value I= revalue)i 输入有效 q= New Node( value ) ∥建立包含whe的新结点 if (first== NULL )first=current ∥空表时,新结点成为链表第一个结点 else i current->link= g: current=9:) 非空表时,新结点链入链尾 cin > values ∥再输入 current->link= NULL ∥链尾封闭 void List: PrintList (t 输出链表 cout datalink; j coutlink==NULL)return/->data; ∥递归结束条件 int temp= Max(f-> link ) ∥在当前结点的后继链表中求最大值 if(->data >temp )returnf->data; ∥如果当前结点的值还要大,返回当前检点值 lse return temp; ∥否则返回后继链表中的最大值 t List: Num( ListNode i ∥递归算法:求链表中结点个数 if(f==NULL)return 0; 空表,返回0 return 1+ Num(-> ink ) ∥否则,返回后继链表结点个数加1 float List: Ag( ListNode int& n)i ∥递归算法:求链表中所有元素的平均值 ∥链表中只有一个结点,递归结束条件 in=l: return( float )(->data ):1 else( float Sum Ag(f->link, n)*n; n++: return(->data Sum)/n;) #include"RecurveList h ∥定义在主文件中 int main( int argc, chararg[i List test; int finished; cout<<“输入建表结束标志数据:”; 7

7 cout > value; //输入 while ( value != retvalue ) { //输入有效 q = NewNode ( value ); //建立包含 value 的新结点 if ( first == NULL ) first = current = q; //空表时, 新结点成为链表第一个结点 else { current->link = q; current = q; } //非空表时, 新结点链入链尾 cin >> value; //再输入 } current->link = NULL; //链尾封闭 } void List :: PrintList ( ) { //输出链表 cout data link; } cout link == NULL ) return f ->data; //递归结束条件 int temp = Max ( f ->link ); //在当前结点的后继链表中求最大值 if ( f ->data > temp ) return f ->data; //如果当前结点的值还要大, 返回当前检点值 else return temp; //否则返回后继链表中的最大值 } int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数 if ( f == NULL ) return 0; //空表, 返回 0 return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加 1 } float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值 if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件 { n = 1; return ( float ) (f ->data ); } else { float Sum = Avg ( f ->link, n ) * n; n++; return ( f ->data + Sum ) / n; } } #include "RecurveList.h" //定义在主文件中 int main ( int argc, char* argv[ ] ) { List test; int finished; cout << “输入建表结束标志数据 ：”;

输入建表结束标志数据 lest NewList(finished ) ∥建立链表 ∥打印链表 cout <<"nThe Max is: "<<test GetMax ( out << nThe Ave is: "< test Gethe (<<n'; printf("Hello World! n"); return 0 5-6画出下列广义表的图形表示和它们的存储表示: (I)D(A(c), B(e), C(a, L(b, c, d)) (2)J1(J2(J1,a,J3(1),J3(J1) 【解答】()D(A(c),B(e,C(a,L(b,c,d)(2)Jl(J2(Jl,a,J3(J),J3(J1) B嘛画-型 D-c型 n2-仁囚 C四[囚 3-2 5-7利用广义表的head和lail操作写出函数表达式,把以下各题中的单元素 banana从广义 表中分离出来 (I)LI(apple, pear, banana, orange) (2)L2(apple, pear),(banana, orange)) (3)L3(((apple), (pear),(banana),(orange))) (4)LA((((apple))),((pear )),(banana), orange) (5)L5((((apple), pear), banana), orange (6)L6(apple, (pear, (banana), orange)) 【解答】 (1) Head(Tail (Tail (LD))) (2)Head(Head(Tail(L2)))

8 cin >> finished; //输入建表结束标志数据 test.NewList ( finished ); //建立链表 test.PrintList ( ); //打印链表 cout << "\nThe Max is : " << test.GetMax ( ); cout << "\nThe Num is : " << test.GetNum ( ); cout << "\nThe Ave is : " << test.GetAve () << '\n'; printf ( "Hello World!\n" ); return 0; } 5-6 画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 【解答】(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 5-7 利用广义表的 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) ) ) 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 ∧ ∧ ∧

(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:

Genlist( char& value ) ∥构造函数,abe是指定的停止建表标志数据 -GenList (; ∥析构函数 ∥遍历广义表 (2)广义表遍历的递归算法 void GenList: traverse (i ∥共有函数 void GenList: traverse( GenListNode*ls){∥私有函数,广义表的遍历算法 if( Is I= NULL)( if( Is->utype ==0)cout value listname urpe==1)t ∥原子结点 if( ls->link I= NULL )cout urpe ==2) ∥子表结点 ir(bs-> value hlink->mark==0) traverse(ls-> value hlink);m表头搜索 if( Is->tlink NULL)cout tlink ) ∥向表尾搜索 0 oA foell- 國@{國國l 对上图所示的广义表进行遍历,得到的遍历结果为A(C(E(x,y),a),D(E,e)) (3)利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址 #include include“ stack h” void GenList: traverse( GenListNode "ls)i Stack ">sH;

10 Genlist ( char& value ); //构造函数, value 是指定的停止建表标志数据 ~GenList ( ); //析构函数 void traverse ( ); //遍历广义表 } (2) 广义表遍历的递归算法 void GenList :: traverse ( ) { //共有函数 traverse ( first ); } #include void GenList :: traverse ( GenListNode * ls ) { //私有函数, 广义表的遍历算法 if ( ls != NULL ) { ls->mark = 1; if ( ls->utype == 0 ) cout value.listname utype == 1 ) { //原子结点 cout value.atom; if ( ls->tlink != NULL ) cout utype == 2 ) { //子表结点 if ( ls->value.hlink->mark == 0 ) traverse( ls->value.hlink ); //向表头搜索 else cout value.hlink->value.listname; if ( ls->tlink != NULL ) cout tlink ); //向表尾搜索 } else cout #include “stack.h” void GenList :: traverse ( GenListNode *ls ) { Stack *> st; 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 ∧ ∧ ∧ ∧