第5章递归 5.1本章知识体系 1. 知识结构图 本章的知识结构如图5.1所示。 图5.1第5章知识结构图 2. 基本知识点 (1) 何时使用递归。 (2) 如何从递归角度提取求解问题的递归模型。 (3) 递归算法的执行过程。 (4) 递归调用的实现原理。 (5) 递归算法的时间复杂度分析方法是先由递归算法推导出执行时间的递推式，然后计算T(n)，再用O表示。 (6) 递归算法的空间复杂度分析方法是先由递归算法推导出占用空间的递推式，然后计算S(n)，再用O表示。 (7) 设计递归算法的一般步骤。 (8) 理解递归数据结构的特征。 (9) 利用递归思想求解复杂的应用问题。 3. 要点归纳 (1) 递归分为直接递归和间接递归，而间接递归算法都可以转换为直接递归算法来实现。 (2) 尾递归是指递归调用语句是最后一条执行语句且把当前运算结果放在参数里传给下层函数。单向递归是指求值过程总是朝着一个方向进行的递归。 (3) 如果求解问题的定义是递归的、存放数据的数据结构是递归的或者问题的求解方法是递归的，一般使用递归算法来求解。 (4) 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。在设计递归算法时首先获取求解问题的递归模型，然后转换为相应的递归算法。 (5) 递归模型由递归出口和递归体两部分构成。递归出口确定递归到何时结束，而递归体确定递归求解时的递推关系。 (6) 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决。 (7) 函数调用是通过一个栈来实现的，用于保存返回地址、函数实参和局部变量值等。 (8) 一般情况下，尾递归和单向递归算法可以通过循环或者迭代方式转换为等价的非递归算法。其他复杂递归算法可以用栈来模拟递归的执行过程，从而将其转换为等价的非递归算法。 (9) 获取递归模型通常分为3个步骤，即分析问题、提取递归体和提取递归出口。在实际中需要根据求解问题来操作。 5.2教材中的练习题及参考答案 1. 有以下递归函数： void fun(int n) {if (n==1) printf("a:%d＼n",n); else {printf("b:%d＼n",n); fun(n-1); printf("c:%d＼n",n); } } 分析调用fun(5)的输出结果。 解： 在调用递归函数fun(5)时先递推到递归出口，然后求值。这里的递归出口语句是printf("a:%d＼n",n)；，递推时执行的语句是printf("b:%d＼n",n)；，求值时执行的语句是printf("c:%d＼n",n)；。调用fun(5)的输出结果如下： b:5 b:4 b:3 b:2 a:1 c:2 c:3 c:4 c:5 2. 以下递归算法用于对数组a［i..j］中的元素进行归并排序： void mergesort(int a［］,int i,int j) {int m; if (i!=j) {m=(i+j)/2; mergesort(a,i,m); mergesort(a,m+1,j); merge(a,i,j,m); } } 求执行mergesort(a，0，n-1)的时间复杂度。其中，merge(a，i，j，m)用于两个有序子序列a［i..m］和a［m+1..j］的合并，是非递归函数，它的时间复杂度为O(合并的元素个数)。 解： 设mergesort(a，0，n-1)的执行时间为T(n)，分析得到以下递归关系。 T(n)= O(1)n=1 2T(n/2)+O(n)n>1 其中，O(n)为merge()所需的时间，设为cn(c为常量)。因此： T(n)=2Tn2+cn=22Tn22+cn2+cn=22Tn22+2cn=23Tn23+3cn  =2kTn2k+kcn=2kO(1)+kcn 由于n2k趋近于1，k=log2n， 所以T(n)=2log2nO(1)+cnlog2n=n+cnlog2n=O(nlog2n)。 3. 已知A［0..n-1］为实数数组，设计一个递归算法求这n个元素的平均值。 解： 设avg(A，i)返回A［0..i］中共i+1个元素的平均值，则递归模型如下。 avg(A，i)=A［0］当i=0时 (avg(A，i-1)×i+A［i］)/(i+1)其他情况 初始调用为avg(A,n-1)。对应的递归算法如下： double avg(double A［］,int i) {if (i==0) return(A［0］); else return((avg(A,i-1)*i+A［i］)/(i+1)); } 求A［n］中n个元素平均值的调用方式为avg(A，n-1)。 4. 设计一个算法求正整数n的位数。 解： 设f(n)为整数n的位数，其递归模型如下。 f(n)=1当n<10时 f(n/10)+1其他情况 对应的递归算法如下： int fun(int n) {if (n<10) return 1; else return fun(n/10)+1; } 5. 上楼可以一步上一阶，也可以一步上两阶，设计一个递归算法，计算共有多少种不同的走法。 解： 设f(n)表示n阶楼梯的不同的走法数，显然f(1)=1，f(2)=2(两阶有一步一步走和两步走两种走法)。f(n-1)表示n-1阶楼梯的不同的走法数，f(n-2)表示n-2阶楼梯的不同的走法数，对于n阶楼梯，第1步上一阶有f(n-1)种走法，第1步上两阶有f(n-2)种走法，则f(n)= f(n-1)+ f(n-2)。对应的递归算法如下： int fun(int n) {if (n==1 ‖ n==2) return n; else return fun(n-1)+fun(n-2); } 6. 设计一个递归算法，利用顺序串的基本运算求串s的逆串。 解： 经分析，求逆串的递归模型如下。 f(s)=s若s= Concat(f(SubStr(s，2，StrLength(s)-1))，SubStr(s，1，1))其他情况 递归思路是： 对于s="s1s2…sn"的串，假设"s2s3…sn"已求出其逆串，即f(SubStr(s，2，StrLength(s)-1))，再将s1(为SubStr(s，1，1))单个字符构成的串连接到最后即得到s的逆串。对应的递归算法如下： #include "sqstring.cpp"//顺序串的基本运算算法 SqString invert(SqString s) {SqString s1,s2; if (StrLength(s)>0) {s1=invert(SubStr(s,2,StrLength(s)-1)); s2=Concat(s1,SubStr(s,1,1)); } else StrCopy(s2,s); return s2; } 7. 设有一个不带表头结点的单链表L，设计一个递归算法count(L)求以L为首结点指针的单链表的结点个数。 解： 对应的递归算法如下。 int count(LinkNode *L) {if (L==NULL) return 0; else return count(L->next)+1; } 8. 设有一个不带表头结点的单链表L，设计两个递归算法，traverse(L)正向输出单链表L中的所有结点值，traverseR(L)反向输出单链表L中的所有结点值。 解： 对应的递归算法如下。 void traverse(LinkNode *L) {if (L==NULL) return; printf("%d ",L->data); traverse(L->next); } void traverseR(LinkNode *L) {if (L==NULL) return; traverseR(L->next); printf("%d ",L->data); } 9. 设有一个不带表头结点的单链表L，设计两个递归算法，del(L，x)删除单链表L中第一个值为x的结点，delall(L，x)删除单链表L中所有值为x的结点。 解： 对应的递归算法如下。 void del(LinkNode *&L,ElemType x) {LinkNode *t; if (L==NULL) return; if (L->data==x) {t=L;L=L->next;free(t); return; } del(L->next,x); } void delall(LinkNode *&L,ElemType x) {LinkNode *t; if (L==NULL) return; if (L->data==x) {t=L;L=L->next; free(t); } delall(L->next,x); } 10. 设有一个不带表头结点的单链表L，设计两个递归算法，maxnode(L)返回单链表L中的最大结点值，minnode(L)返回单链表L中的最小结点值。 解： 对应的递归算法如下。 ElemType maxnode(LinkNode *L) {ElemType max; if (L->next==NULL) return L->data; max=maxnode(L->next); if (max>L->data) return max; else return L->data; } ElemType minnode(LinkNode *L) {ElemType min; if (L->next==NULL) return L->data; min=minnode(L->next); if (min>L->data) return L->data; else return min; } 11. 设计一个模式匹配算法，其中模式串t中含一个或多个通配符'*'，每个'*'可以和任意子串匹配。对于目标串s，求其中匹配模式串t的一个子串的位置（'*'不能出现在t的开头）。 解： 采用BF模式匹配的思路，当s［i］和t［j］比较时，若t［j］为'*'，j++跳过t的当前'*'，取出s中对应'*'的字符及其之后的所有字符构成的字符串，即SubStr(s，i+1，s.length-i)，其中i+1是s中对应'*'字符的字符的逻辑序号。再取出t中'*'字符后面的所有字符构成的字符串，即SubStr(t，j+1，t.length-j)，递归对它们进行匹配，若返回值大于-1，表示匹配成功，返回start。当i或者j超界后结束循环，再判断如果是j超界，返回start，否则返回-1。对应的递归算法如下： #include "sqstring.cpp"//顺序串的基本运算算法 int findpat(SqString s,SqString t) {int i=0,j=0,k,start; while (i-1) 　　//找到了 return start; } else if (s.data［i］==t.data［j］) {i++; j++; } else {i=i-j+1; start=i; j=0; } } if (j>=t.length) return start; else return -1; } 5.3补充练习题及参考答案 5.3.1单项选择题 习题答案 1. 一个正确的递归算法通常包含。 A. 递归出口B. 递归体 C. 递归出口和递归体D. 以上都不包含 2. 递归函数f(1)=1，f(n)=f(n-1)+n(n>1)的递归出口是。 A. f(1)=1 B. f(1)=0 C. f(0)=0 D. f(n)=n 3. 递归函数f(1)=1，f(n)=f(n-1)+n(n>1)的递归体是。 A. f(1)=1 B. f(0)=0 C. f(n)=f(n-1)+n D. f(n)=n 4. 计算f(n)=11×2+12×3+…+1n(n+1)，采用的递归模型为。 A. fn=11×2+12×3+…+1n(n+1) B. fn=11×2+12×3+…+1(n-1)n+f(n-1) C. f1=12，fn=fn-1+1n(n+1) D. fn=fn-1+1n(n+1) 5. 在将递归算法转换成对应的非递归算法时，通常需要使用保存中间结果。 A. 队列 B. 栈 C. 链表 D. 树 6. 函数f(x，y)定义如下： f(x，y)= f(x-1，y)+f(x，y-1)当x>0且y>0时 x+y否则 则f(2，1)的值是。 A. 1 B. 2 C. 3 D. 4 7. 一个递归问题可以用递归算法求解，也可以用非递归算法求解，但单从执行时间来看，通常递归算法比非递归算法。 A. 快 B. 慢 C. 相同 D. 无法比较 8. 以下关于递归的叙述中错误的是。 A. 一般而言，使用递归解决问题比使用循环解决问题需要定义更多的变量 B. 递归算法的执行效率相对较低 C. 递归算法的执行需要用到系统栈 D. 以上都是错误的 9. 在实现递归调用时需要利用系统栈保存参数值。在处理传值参数时，需要为对应形参分配空间，以存放实参的。 A. 空间 B. 副本 C. 代码地址 D. 地址 10. 在实现递归调用时需要利用系统栈保存参数值。在处理引用型参数时，需要保存实参的。 A. 空间 B. 副本 C. 值 D. 地址 5.3.2填空题 习题答案 1. 将f(n)=1+12+13+…+1n转化成递归函数，其递归出口是①，递归体是②。 2. 有以下递归过程： void print(int w) {int i; if (w!=1) {print(w-1); for (i=0;i<=w;i++) printf("%3d",w); printf("＼n"); } } 调用语句print(4)的结果是。 3. 有以下递归过程： void reverse(int m) {printf("%d",n%10); if (n/10 != 0) reverse(n/10); } 调用语句reverse(582)的结果是。 4. 递推式f(1)=0，f(n)=f(n/2)+1的解是。 5. 设a［0..n-1］是一个含n个整数的数组，求该数组中所有元素之和的递归定义是。 6. 有以下递归算法： void fun(int n) {if (n>0) {printf("%d ",n); fun(n-1); fun(n-1); } } 执行fun(3)的输出是。 7. 有以下递归算法： void fun(int n) {if (n>0) {fun(n-1); fun(n-1); printf("%d ",n); } } 执行fun(3)的输出是。 5.3.3判断题 习题答案 1. 判断以下叙述的正确性。 (1) 任何递归算法都有递归出口。 (2) 递归算法的执行效率比功能相同的非递归算法的执行效率高。 (3) 任何能够正确执行的递归算法都能转换成功能等价的非递归算法。 (4) 任何递归算法都是尾递归。 (5) 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 (6) 尾递归算法可以通过循环转换成非递归算法。 2. 判断以下叙述的正确性。 (1) 有以下递归算法： int fun(int n) {if (n==1 ‖ n==0) return n; else return n+fun(n/2); } 其中递归体是n==1或n==0时返回n。 (2) 有以下递归函数： int fun(int n) {if (n==1 ‖ n==0) return n; else return n+fun(n-2); } 执行fun(6)的返回结果是10。 (3) 以下算法中没有循环语句，其时间复杂度为O(1)： int fun(int n) {if (n==1)return 1； else return n*fun(n-1)； } (4) 以下算法中没有循环语句，其空间复杂度为O(1)： int fun(int n) {if (n==1)return 1； else return n*fun(n-1)； } 5.3.4简答题 习题答案 1. 简述递归算法的优缺点。 2. 推导出求x的n次幂的递归模型。 3. 推导出求x的n次幂的递归模型，要求最多使用O(log2n)次递归调用。 4. 采用递归方法，将含有n个字符的C/C++字符串s中最后一个为x的字符改为y，给出其递归模型。 5. 某递归算法的求解时间复杂度的递推式如下： T(n)=1当n=0时 T(n-1)+n+3当n>0时 求该算法的时间复杂度。 6. 设a［0..n-1］是含有n个元素的整数数组，写出求n个整数之积的递归定义。 7. 以下算法是计算两个正整数u和v的最大公因数的递归函数，给出其递归模型。 int gcd(int u,int v) {int r; if ((r=u%v)==0) return(v); else return(gcd(u,r)); } 8. 计算以下算法中的语句频度(不计return语句的返回)。 double rsum(double a［］, int n) {if (n<=0) return a［0］; else return rsum(a,n-1)+a［n-1］; } 9. 分析以下算法的时间复杂度(其中问题规模n=j-i+1)。 void fun(ElemType A［］,int i,int j,ElemType &max,ElemType &min) {int mid; ElemType gmax,gmin,hmax,hmin; if (i==j) {max=min=A［i］; return; } if (i==j-1) {if (A［i］hmax?gmax:hmax); min=(gminnext也是一个不带头结点的单链表(含n-1个结点)，两者除了相差一个结点以外，其他都是相似的。设release(h)的功能是删除并释放单链表h中的所有结点。其递归模型如下： release(h)≡不做任何事情当h为空表时 release(h->next);释放h结点其他情况 对应的递归算法如下： void release(LinkNode *h) {if (h!=NULL) {release(h->next); free(h);//释放h结点 } } 2. 【递归算法设计】 设计一个递归算法，利用串的基本运算SubStr()判断字符x是否在串s中。 解： 设串s="a1a2…an"，Find(s，x)的值表示x是否为串s的元素，若是则返回真，否则返回假。本题的递归模型如下： Find(s，x)=0如果s为空串 1如果a1=x Find("a2…an"，x)其他情况 对应的递归算法如下： #include "SqString.cpp"//包含顺序串的定义和基本运算函数 bool Find(SqString s,char x) {SqString s1; if (s.length==0) return false; else if (s.data［0］==x)//a1=x return true; else {s1=SubStr(s,2,s.length-1);//s1="a2…an" return(Find(s1,x)); } } 3. 【递归算法设计】 一个人赶着鸭子去每个村庄卖，每经过一个村子卖出所赶鸭子的一半又一只,这样他经过了7个村子后还剩两只鸭子。设计一个算法求他出发时共赶了多少只鸭子？ 解： 设fun(i)表示经过i个村子后还剩下的鸭子数，依题意有以下递归模型。 fun(i)=2当i=7时 2×fun(i+1)+1当i<7时 对应的递归算法如下： int fun(int i) {if (i==7) return 2; else return 2*fun(i+1)+1; } 调用fun(0)求得出发时共赶鸭子数为383只。 4. 【递归算法设计】 求解猴子吃桃问题。海滩上有一堆桃子，5只猴子来分。第一只猴子把这堆桃子分为5份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第2只猴子把剩下的桃子又平均分成5份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第3、第4、第5只猴子都是这样做的，问海滩上原来最少有多少个桃子？ 解： 设fun(i)表示第i个猴子分桃子前的桃子总数。显然，第5只猴子分桃子后的桃子总数为m(相当于第6个猴子分桃子前的桃子总数，可以是任何大于或等于0的整数)。f(n+1)应该是(f(n)-1)/5的4倍，即f(n+1)=4［(f(n)-1)/5］，求出f(n)=5f(n+1)/4+1，而f(n)一定为整数，所以m应该取保证所有5f(n+1)/4整除的最小整数。依题意有以下递归模型： fun(6)=m第5只猴子分桃子后的桃子总数为m fun(n)=(fun(n+1)+1)×5当n>1时 对应的递归算法如下： bool isn(int x,int y)//x整除y时返回true {if (x % y==0) return true; else return false; } int fun(int n,int m) {if (n==6) return m; else {if (isn(5*fun(n+1,m),4)) return (5*fun(n+1,m)/4+1); else//当m不合适时返回-1 return -1; } } int pnumber() {int k; int m=0;//m从0开始试探 while(true) {k=fun(1,m); if (k!=-1) break; m++; } return k; } pnumber()的计算结果是3121，所以海滩上原来最少有3121个桃子。 5. 【递归算法设计】 有以下递归计算公式： C(n，0)=1n≥0 C(n，n)=1n≥0 C(n，m)=C(n-1，m)+C(n-1，m-1)n>m，n≥0，m≥0 设计一个递归算法和一个非递归算法求C(n，m)。 解： 对应的递归算法如下。 int fun(int n,int m) {if (n>=0 && m==0 ‖ n>=0 && m==n) return 1; else {if (n>m && n>=0 && m>=0) return(fun(n-1,m)+fun(n-1,m-1)); else {printf("n,m值不正确＼n"); return(-1); } } } 用一个数组a存放C(m，n)的值，对应的非递归算法如下： int fun1(int n,int m) {int a［M］［N］={0},i,j; for (i=0;i<=n;i++) {a［i］［0］=1; a［i］［i］=1; } for (j=1;j<=m;j++) for (i=j+1;i<=n;i++) a［i］［j］=a［i-1］［j］+a［i-1］［j-1］; return a［n］［m］; } 6. 【递归算法设计】 编写一个递归算法，读入一个字符串(以“.”作为结束)，要求打印出它们的倒序字符串。 解： 首先获取用户的按键，如果不是'.'字符，则递归调用该过程，否则显示该字符。对应的算法如下： void reverse() {char ch; scanf("%c",&ch); if (ch!='.') {reverse(); printf("%c",ch); } } 7. 【递归算法设计】 设计一个程序求解全排列问题： 输入n个不同的字符，给出它们所有的n个字符的全排列。 解： 将n个不同的字符存放在字符串str［0..n-1］中，设f(str，k，n)表示输出str［k..n-1］(共n-k个字符)所有字符全排列，而f(str，k+1，n)表示输出str［k+1..n-1］(共n-k-1个字符)所有字符全排列，前者是大问题，后者为小问题。递归模型f(str，k，n)如下： f(str，k，n)≡输出产生的解若k=n-1 对于k~n-1的i，str［i］与str［k］交换位置;其他情况 f(str，k+1，n); 将str［k］与str［i］交换位置(恢复环境); 对应的算法如下： void print(char str［］,int n)//输出一个排列 {for (int i=0;i #define MaxSize 10 int n,r;//全局变量 void print(int a［］)//输出一个组合 {int j; for (j=r-1;j>=0;j--) printf("%d ",a［j］); printf("＼n"); } void comb(int a［］,int m,int k) {int i; for (i=m;i>=k;i--) {a［k-1］=i; if (k>1) comb(a,i-1,k-1); else print(a); } } int main() {int a［MaxSize］; printf("输入n,r(r<=n):"); scanf("%d%d",&n,&r); printf("1..%d中%d个的组合结果如下:＼n",n,r); comb(a,n,r); printf("＼n"); return 1; } 程序的一次执行结果如下： 输入n,r(r<=n):5 3 ↙ 1..5中3个的组合结果如下: 5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 9. 【递归算法设计】 棋子移动问题： 有2n个棋子(n≥4)排成一行，开始位置为白色全部在左边，黑色全部在右边。移动棋子的规则是每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移)，要求最后能够移成黑白相间的一行棋子。 解： n=4的求解过程如下。 12345678910 初始状态： ○○○○●●●●―― 第1步： ○○○――●●●○●// mvtosp(4)： 即位置4开头的两个棋子与"--"交换 第2步： ○○○●○●●――●// mvtosp(8)： 即位置８开头的两个棋子与"--"交换 第3步： ○――●○●●○○●// mvtosp(2)： 即位置２开头的两个棋子与"--"交换 第4步： ○●○●○●――○●// mvtosp(7)： 即位置７开头的两个棋子与"--"交换 第5步： ――○●○●○●○●// mvtosp(1)： 即位置１开头的两个棋子与"--"交换 用数组c［1..2n+2］存放棋子，用init()函数对其所有元素初始化。设mv(n)表示求解2n个棋子移动的问题，则求解棋子移动问题的递归模型如下： mv(n)≡直接求解n=4 将c［n］、c［n+1］棋子对移动到c［2n+1］、c［2n+2］处，即mv(n)； 其他情况 将c［2n-1］、c［2n］棋子对移动到c［n］、c［n+1］处，即mv(2n-1)； mv(n-1)； 对应的程序如下： #include #include const int MAX=100; char c［MAX］［3］; int st=0,sp,n; //全局变量，st记录移动的步骤，sp指向为"-"的棋子 void print()//输出一个移动步骤 {printf("step%-2d:",++st); for (int i=1;i<=2*n+2;i++) printf("%s",c［i］); printf("＼n"); } void mvtosp(int k)//将c［k］和c［k+1］两个棋子与"--"交换 {for (int j=0;j<=1;j++) {strcpy(c［sp+j］,c［k+j］); strcpy(c［k+j］,"―"); } sp=k;//sp指向"--"的棋子 print();//输出一个解 } void mv(int n)//求解2n个棋子移动的问题 {if (n==4)//递归出口 {mvtosp(4);mvtosp(8);mvtosp(2); mvtosp(7);mvtosp(1); } else//求解n>4的情况 {mvtosp(n); mvtosp(2*n-1); mv(n-1); } } void init(int n)//初始化c数组 {int i; st=0; sp=2*n+1;//sp指向第2n+1的棋子，即"--" for (i=1;i<=n;i++) strcpy(c［i］,"○"); for (i=n+1;i<=2*n;i++) strcpy(c［i］,"●"); strcpy(c［2*n+1］,"―"); strcpy(c［2*n+2］,"―"); } int main() {do {printf("输入n值(4-20):"); scanf("%d",&n); } while (n>20 ‖ n<4); init(n); printf("移动过程如下:＼n"); mv(n); printf("＼n"); return 1; } 本程序的一次执行结果如下： 输入n值(4-20):8↙ 移动过程如下: step1 :○○○○○○○――●●●●●●●○● step2 :○○○○○○○●●●●●●●――○● step3 :○○○○○○――●●●●●●○●○● step4 :○○○○○○●●●●●●――○●○● step5 :○○○○○――●●●●●○●○●○● step6 :○○○○○●●●●●――○●○●○● step7 :○○○○――●●●●○●○●○●○● step8 :○○○○●●●●――○●○●○●○● step9 :○○○――●●●○●○●○●○●○● step10:○○○●○●●――●○●○●○●○● step11:○――●○●●○○●○●○●○●○● step12:○●○●○●――○●○●○●○●○● step13:――○●○●○●○●○●○●○●○● 10. 【递归算法设计】 设以字符序列abcd作为顺序栈st的输入，利用push(进栈)和pop(出栈)操作，输出所有可能的出栈序列并编程实现整个算法。 解： 设A=(a0，a1，…，aj)是已出栈的序列，B是已进栈的序列(如果栈不空)，C=(ci，ci+1，…，cn-1)是尚未进栈的序列（初始时i=0表示C中有n个字符），描述进栈、出栈的状态由A、C两个序列表示即可(由A、C序列可以确定B序列)。 图5.2进栈、出栈的状态 产生所有出栈序列的过程是如果所有元素都在A序列中(栈空且C序列中的所有元素处理完)，此时产生一种出栈序列，否则从某个进栈、出栈的状态(如图5.2所示的状态称为初始状态)出发，只有两种操作。 ① 从初始状态出发，将C中的元素ci(i #define MaxSize 100 struct stacknode {int data［MaxSize］; int top; } st; //全局变量，定义整数顺序栈 int n=4;//全局变量，定义输入序列中元素的个数 char str［］="abcd";//全局变量，指定进栈序列 int sum=0;//全局变量，累计出栈序列的个数 void initstack()//初始化顺序栈 { st.top=-1; } void push(int x)//元素x进栈的运算 {st.top++; st.data［st.top］=x; } int pop()//退栈运算 {int temp; temp=st.data［st.top］; st.top--; return temp; } bool empty() //判断栈空否运算 {if (st.top==-1) return true; else return false; } void process(int i,int a［］,int j)//处理C序列中i位置的元素 {int x,k; if (i>=n && empty())//输出一种可能的方案 {printf(""); for (k=0;k