第5章递归与广义表 第5章递归与广义表 5-1已知An]为整数数组,试写出实现下列运算的递归算法 (1)求数组A中的最大整数。 (2)求n个整数的和。 (3)求n个整数的平均值。 【解答】 #include Elements[: int recurvearray:; MarKey(intn){∥递归求最大值 if(n==1)return Elements[O: if( Elements n-1> temp )return Elements[n-1; else return temp; int RecurveArray Sum( int n )i ∥递归求数组之和 if(n== D)return Elements[0; else return Elements[n-1]+ Sum(n-1);
第 5 章 递归与广义表 53 第 5 章 递归与广义表 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); }
第5章递归与广义表 float RecurveArray∷ Average(intn){∥递归求数组的平均值 else return((float)Elements[n-1]+(n-1)* Average(n-1))/n int main( int arge, char argv [)i InputArrayo 0,n=0 else return akm( m-l, akm( m, n-1)); ∥m>0.n>0 (2)为了将递归算法改成非递归算法,首先改写原来的递归算法,将递归语句从 结构中独立出来 unsigned akm( unsigned m, unsigned n )i f(m==0) return n+l: if (n==o)return akm( m-1, 1); ∥m>0,n==0 v= akm(m, n-1)); ∥m>0,n>0 return akm( m-l, v)
第 5 章 递归与广义表 54 float RecurveArray :: Average ( int n ) { //递归求数组的平均值 if ( n == 1) return (float) Elements[0]; 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 );
第5章递归与广义表 计算akm(2,1)的递归调用树如图所示: =akm(2,0) a(3)am=5 akm(1 akm =3 =akm(1,2)|akm(0,4)=5 y=2 v=am(1,0)|am0,2)=3 用到一个栈记忆每次递归调用时的实参值,每个结点两个域{vm,Ⅶm。对以上实例,栈 的变化如下: V vn 1n vn 1 1 vn 改akm(m-1,1) 改akm(m-1,1)y=n+1=2改akmm-1,y)改akm(m-1,) 翻誧蚩 改akm(m-1,1)y=n+1=2改akmn(m-1,1)改akmm-1,y)改akm(m-1,)栈空,返回v=5 =n+1=3v=n+1=4v=n+1=5 相应算法如下 #include include“ stack h #define max Size 3500; ed tackst( maxSize ) node wvm=m; wvn=n; st Push(w); while( st GetTop().vm >0)t 川计算akm(m-1,akm(m,n-1))
第 5 章 递归与广义表 55 } 计算 akm(2, 1)的递归调用树如图所示： 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{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) ) 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
第5章递归与广义表 川计算akm(m,n-1),直到akm(m,O) wvn--; st Push(w片;} 川计算akm(m-1,1) wvm;w vn=1; st Push(w); ∥直到akm(O,akm(1,*)) +;川计算v=akm( 如果栈不空,改栈项为(m-1,v) iw=st GetTop(: st Pop(: wvm wvn=v: st Push(w):) 5-3【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为 w[1],w2]…,wn。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之 和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真):否 则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此 背包问题的递归定义如下:) Tes=0此时背包问题一定有解 False 总重量不能为负数 KNAP(s, n)= s>0且n0且n≥1所选物品中不包括wn时 KNAP(s-wnl, n-1) 所选物品中包括{r时 【解答】根据递归定义,可以写出递归的算法。 enu boolean Knap( int s, int n )i if(s0&&n<l)return False; if( Knap(s-winl, n-1)==True {cout≤<w[n< eturn True; 1 n Knap( s, n-1); 若设w={0,1,2,4,8,16,32},s=51,n=6。则递归执行过程如下 return True,完成 return True,打印16 p(3-8, 3) return False Knap(3, 3) return T return F Knap(3-4, 4) return False Knap(3, 2 return Tr return False Knap(3-2,1) return True,打印2 Knap(1-1,0) I return True,打印1 return True
第 5 章 递归与广义表 56 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( 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章递归与广义表 5-4【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋 盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者 同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提 示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向 反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子 恢复安放该棋子前的状态,试探本行的第j+1列。) 【解答】此为典型的回溯法问题 0#次对角线 1#次对角线 2#次对角线 3#次对角线 4#次对角线 5#次对角线 人厦 6#次对角线 0#主对角线 1#主对角线 2#主对角线 主对角线 4#主对角线 5#主对角线 6#主对角线 在解决8皇后时,采用回溯法。在安放第i行皇后时,需要在列的方向从1到n试 探(j=1,…,n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它 皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后 不动,递归安放第i+1行皇后 解题时设置4个数组 col[n]:col[标识第i列是否安放了皇后 md口2n-1]:mdk]标识第k条主对角线是否安放了皇后 sd[2n-1]:sdk]标识第k条次对角线是否安放了皇后 qn]:q[记录第i行皇后在第几列 利用行号i和列号j计算主对角线编号k的方法是k=n+i-j-1:计算次对角线编号k的 方法是k=计+j。n皇后问题解法如下: void Queen( int i)( for intj=0; j<n; j++)i i(col=0&&md[nijl=0&&sd=0){∥第i行第j列没有攻击 col0]=md[n+ij-1=sd[i+J=1; q0=j; ∥在第i行第j列安放皇后 出一个布局 for(j=0;j<n;j++)cout <<q0]<<', i
第 5 章 递归与广义表 57 5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第 1 行，第 2 行，…。第 8 行上布放棋子。在每一行中有 8 个可选择位置，但在任一时刻，棋 盘的合法布局都必须满足 3 个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者 同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提 示：用回溯法。在第 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 = 0; 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; } 0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线 6# 次对角线 5# 次对角线 4# 次对角线 3# 次对角线 2# 次对角线 0# 次对角线 1# 次对角线 0 1 2 3 0 1 2 3
第5章递归与广义表 else( Queen(i+1) ∥在第计1行安放皇后 colD=md[n+ij-1]=sd[i+J]=0: 90=0; ∥撤消第i行第j列的皇后 5-5已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归 算法 (1)求链表中的最大整数。 (2)求链表的结点个数。 (3)求所有整数的平均值 【解答】 #include ∥定义在头文件" Recurvelist h"中 class ListNode i ∥链表结点类 ∥结点数据 ∥结点指针 Listnode( const int item):data(item,link(NUL){}∥构造函数 ∥链表类 int Max( ListNode *f); int Num( ListNode *f); float Avg( ListNode *f, int& n) public: List(): first(NULL), current(NULL) ∥构造函数 ∥析构函数 ListNode newnode( const int item);∥创建链表结点,其值为iem void NewList( const int revalue ) ∥建立链表,以输入 revalue结束 void PrintList ( ∥输出链表所有结点数据 int GetMax(){ return max(frst);}∥求链表所有数据的最大值 int Getnum(){ return Num( first片;}∥求链表中数据个数 noat GetAvg(){ return Avg(fist);}/求链表所有数据的平均值 }; ListNode* List: NewNode( const int item)( ∥创建新链表结点 ListNode *newnode= new ListNode(item):
第 5 章 递归与广义表 58 else { Queen ( i+1 ); //在第 i+1 行安放皇后 col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; //撤消第 i 行第 j 列的皇后 } } } 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);
第5章递归与广义表 ∥建立链表,以输入 结束 irst= NULL: int ListNode *q outlink=q; current=q;}∥空表时,新结点链入链尾 cin > value ∥再输入 current-> link NULL ∥链尾封闭 void List PrintList (t 输出链表 p=first while( p I=nUll)( cout datalink; 3 coutlink== NULL)return f->data; ∥递归结束条件 ∥在当前结点的后继链表中求最大值 if(f->data >temp )return f->data ∥如果当前结点的值还要大,返回当前检点值 lse return temp ∥否则返回后继链表中的最大值 2)求链表的结点个数 int List Num( ListNode *f)i ∥递归算法:求链表中结点个数 if (f== NULL )return 0; 空表,返回0 return 1+ Num(f->link ) ∥否则,返回后继链表结点个数加1 (3)求所有整数的平均值 float List Avg( ListNode *f, int& n)( ∥递归算法:求链表中所有元素的平均值 if (f->link = NULL ∥链表中只有一个结点,递归结束条件
第 5 章 递归与广义表 59 return newnode; } void List :: NewList ( const int retvalue ) { //建立链表, 以输入 retvalue 结束 first = NULL; int value; ListNode *q; 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; //否则返回后继链表中的最大值 } (2) 求链表的结点个数 int List :: Num ( ListNode *f ) { //递归算法 : 求链表中结点个数 if ( f == NULL ) return 0; //空表, 返回 0 return 1+ Num ( f ->link ); //否则, 返回后继链表结点个数加 1 } (3) 求所有整数的平均值 float List :: Avg ( ListNode *f , int& n ) { //递归算法 : 求链表中所有元素的平均值 if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件
第5章递归与广义表 in=l; return( float )(f->data );3 else float Sum=Avg(f->link, n)*n; n++: return(f->data+ Sum)/n;) nclude"Recurvelist h" ∥定义在主文件中 int main( int argc, charang[)i List test; int finished; cout<<“输入建表结束标志数据: 输入建表结束标志数 test NewList( finished ) ∥建立链表 test PrintList ( ∥印链表 cout <<The Max is: <<test GetMax ( cout<<"nThe Num is: "<<test. GetNum ( out <<"nThe Ave is: "< test GetAve 0<<"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) 【解答】(1)D(A(c),B(e),C(a,L(b,c,d)(2)Jl(J2(J1,a,J3(J),J3(J) D-西 回[团 C面囚 -四[2 5-7利用广义表的head和tai操作写出函数表达式,把以下各题中的单元素 banana从广义 表中分离出来:
第 5 章 递归与广义表 60 { 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 > 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 从广义 表中分离出来： 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 ∧ ∧ ∧
第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) //表头或原子结点构造 函数
第5章递归与广义表 i if( utype ==0)value. listname info; else val info; J GenListNode( GenListNode* hp ∥表构造函数 mark(0), utype(2), value hlink(hp) har Info( GenListNode* elem ∥返回表元素elem的值 f return( utype==0) elem->value listname elem->value. atom; 3 class ∥广义表类定义 private GenListNode "first: 义表头指针 stRode *Is ) void Remove( GenListNode* Is ) ∥将以ls为表头结点的广义表结构释放 Genlist( char& value ) ∥构造函数, value是指定的停止建表标志数据 ∥析构函数 void traverse o ∥遍历广义表 (2)广义表遍历的递归算法 void GenList: traverse (t ∥共有函数 traverse( first) void GenList: traverse( GenListNode*ls){∥私有函数,广义表的遍历算法 if( Is I= NULL )( if( Is->utype==0)cout value listname uty! ){ ∥原子结点 cout value. atom: if Is->tlink I= NULL )cout utype ==2)i ∥子表结点 if( ls->value. hlink->mark =0)traverse( Is->value hl 向表头搜索 else cout value. hlink->value listname: if( ls->tlink NULL )cout tlink )i ∥向表尾搜索 lse cout <<)
第 5 章 递归与广义表 62 { 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 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 << ‘)’; ∧
