栈(C语言实现)
西北师范大学地环学院地理信息系
数据结构实验讲义
二 栈 C语言实现
张长城
2011-2-8
[顺序
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
构造栈 ]
1 / 18
一 栈的基本原理分析
作为栈这种数据结构，数据是进行所谓的先进后出操作，但栈在操作中，并不需要在中
间插入删除操作、一般也不需要在进栈数据中查找什么，这种情况下，恰恰是顺序表可以完
成的非常好的场合，所以栈经常是用一个简单的数组即可完成。
1 #include
2 int s[100];
3 int top=0;
4 void push(int e)
5 {
6 s[top]=e;
7 top++;
8 }
9 int pop()
10 {
11 top--;
12 return s[top];
13 }
14 main()
15 {
16 int i;
17 for(i=0;i<10;i++)
18 push(i);
19 for(i=0;i<10;i++)
20 printf("%d\n",pop());
21 }
最简单的栈程序，见s0.c
这个程序就能完成最简单的栈的程序，原理也很简单。
对栈的应用，比如把10进制数1348转换成8进制，则过程是:
商 余
1348/8 168 4 168/8 21 0 21/8 2 5 2/8 0 2 这个结果就是2504，但从计算步骤上看:它的结果次序是反的，是4、0、5、2，如果
把余数的结果先保存进栈，则出栈恰好是正确的结果。
略微修改s0.c就可完成这个工作。这个算法适合任何进制数据转换。
2 / 18
1 main()
2 {
3 int N=1348;
4 while(N)
5 {
6 push(N%8);
7 N=N/8;
8 }
9 while(top>0)
10 printf("%d",pop());
11 printf("\n");
12 }
最简单的栈应用程序，见s0.c
但这个程序有很大的问题:
1 仅仅有一个栈空间，程序如果要用多个栈、则要说明很多s[]、top之类的变量; 2 这个栈也仅仅能进出int类型的数据，如果是多种类型数据组成的表格，则不能处理
;
所以上述程序仅是个原理示范性的程序，在更加广泛的情况下不能用，它太简单了。
要对任意类型的表进行栈操作，那就找C#的泛型或者JavaScript吧，在C这里，我们依然
最一个简单的特定的表格进行栈处理，这个表就是:
struct ElemType
{
char c;
int iData;
long lData;
char sData[20];
};
这是个包含字符、整数、长整数、字符串的表，表本身或许没什么现实意义。根据栈的
原理，我们知道设计栈不需要链表、顺序表已经足够好了。所以设计一个表示栈的表就是: struct sqStack
{
struct ElemType *base,*top;
int Count,Size;
};
这个表中*base指针代表栈空间的首地址;*top代表栈空间的栈顶地址; Count代表进栈数据元素的个数，也就是说进栈数据有多少行; Size代表栈的最大空间，也就是说栈最大能容纳多少行数据。 这个表实际相当于顺序表的目录表，它能使访问栈更加容易。所以编程的整体路线也将
同顺序表、链表中做的那样:不断补充函数。
3 / 18
1 栈的初试化
所谓栈的初始化，就是构造一个指定空间的存储单元，并且给出这片空间的首地址，
这个手段在顺序表、链表的编程中已经很熟悉了。
如果指定栈的空间是Size，那么就意味着为ElemType这样的表申请Size行的存储空间，
写成C语言就是:
struct ElemType *p;
p=(struct ElemType *)malloc(sizeof(struct ElemType)*Size); 当然，要把这个结果存储到栈目录表seqStack中，所以:
struct seqStack *s;
s=(struct seqStack *)malloc(sizeof(struct seqStack));
s->base =p;s->top=p;s->Count =0;s->Size =Size; 注意编程要点:这里的表s 保存的最重要数据就是:当前栈中数据的行数Count、以及
栈的最大容量。当然，在空栈的情况下，栈顶指针和栈的存储空间首地址是一致的。整个函
数就是:
1 struct seqStack * StackInit(int Size)
2 {
3 struct ElemType *p;
4 struct seqStack *s;
5 p=(struct ElemType *)malloc(sizeof(struct ElemType)*Size);
6 s=(struct seqStack *)malloc(sizeof(struct seqStack));
7 s->base =p;s->top=p;s->Count =0;s->Size =Size;
8 return s;
9 }
构造一个有Size存储空间的栈，见s1.c 用这样的方式设置了一个栈、并获得栈空间的地址，从而完成了栈的初始化。
2 进栈操作
如有ElemType类型的数据行e，试图进栈s就是:
首先把e的内容复制到s->top:
s->top ,e;
然后s->count++，这个过程非常简单。完整的函数就是:
1 int Push(struct seqStack *s,struct ElemType *e)
2 {
3 if(s==NULL||e==NULL) return -1;
4 if(s->Count ==s->Size ) return -1;
5 ElemCopy(e,s->top);
6 s->top++;
7 s->Count++;
8 return 0;
9 }
在栈s上让e进栈，见s1.c
这个函数中可以看出:ElemCopy()又是个不可或缺的函数。这个函数请同学们自己补充。
4 / 18
从程序原理上看:这个和s0.c中的栈没什么差别，一样的处理方法，只不过判断了栈空
间是否为空、判断了栈是否已满的操作。
3 出栈操作
从栈s中数据出栈，则是把top指针的数据地址给出来，然后让top--，这个操作就是:
给出:s->top;
s->top--;
这点和s0.c中的程序思路是一致的。
1 struct ElemType * Pop(struct seqStack *s)
2 {
3 if(s==NULL) return NULL;
4 s->top--;
5 s->Count--;
6 return s->top;
7 }
在栈s上出栈，见s1.c
4 得到栈s内的数据行数
返回s->Count即可，就是:
1 int StackLength(struct seqStack *s)
2 {
3 if(s==NULL) return -1;
4 return s->Count;
5 }
返回栈s中数据个数，见s1.c
5 清除栈s的所有数据
这个操作很简单，直接使s->Count=0即可。
6 销毁栈s
1 int DestroyStack(struct seqStack *s)
2 {
3 if(s==NULL) return -1;
4 free(s->base);
5 free(s);
6 return 0;
7 }
销毁栈s，见s1.c 销毁栈的操作非常重要，对我们的简单测试程序而言，基本是一个栈用完整个程序退
出，但在大型程序的应用场合，很多情况是构造多个栈并不断要构造新的栈，所以不再使
用的栈必须销毁，否则程序将会占用大量存储空间而无法继续运行。 到此，有关栈的函数基本完成，相对于顺序表和链表，栈的操作要少的多。完整的栈测
试程序见s1.c，其中main()如下表:
实际就是给出ElemType类型的表行，不断进栈、然后出栈
5 / 18
6 / 18
1 main()
2 {
3 struct ElemType pe,*p;
4 struct seqStack *s;
5 s=StackInit(10);
6 pe.iData =1;pe.c='A';pe.lData=1;strcpy(pe.sData,"AAA"); 7 Push(s,&pe);
8 pe.iData =2;pe.c='B';pe.lData=2;strcpy(pe.sData,"BBB"); 9 Push(s,&pe);
10 pe.iData =3;pe.c='C';pe.lData=3;strcpy(pe.sData,"CCC"); 11 Push(s,&pe);
12 pe.iData =4;pe.c='D';pe.lData=4;strcpy(pe.sData,"DDD"); 13 Push(s,&pe);
14 pe.iData =5;pe.c='E';pe.lData=5;strcpy(pe.sData,"EEE"); 15 Push(s,&pe);
16
17 while(StackLength(s)>0)
18 {
19 p=Pop(s);
20 printf("%d %c %d %s\n",p->iData,p->c,p->lData,p->sData); 21 }
}
栈测试程序，全部程序见s1.c 对这样的简单程序，由于测试完后程序终止，所以没必要一定要销毁这个栈，程序退
出后栈空间将随之全部释放。
7 栈的应用
例1 、个位数四则混合计算
针对个位数的四则运算，如算式:
3*4+5+6*7
首先把一个式子写成这样的树:
这个树的中序遍历就是原算式，其后序遍历是:
3 4 * 5+ 6 7 * +
按后序遍历的结果，我们可以在遇到一个运算符、就可立即把前面的数字进行计算，而不
7 / 18
必考虑运算符的优先级。这就是这个遍历结果的意义。
比如3、4后是*，立刻运算是12，于是3、4、*这个部分变成了:
12 5+6 7 * +
再次右移取5、取+，立刻运算是17，于是这个式子就成为:
17 6 7*+
再次右移取6、取7、取*，立刻运算前取的两个数:6、7，乘积是42，于是式子成: 17 42 +
再次右移取到+，就是:17+42=59
同理，你可以先序遍历这个树，得到:++*3 4 5 * 6 7，这样的式子意味着取到两个数、立刻按前一个运算符进行计算，这个过程请自己推导。
按后序遍历结果形成的式子叫后缀表达式、按先序遍历结果形成的式子叫前缀表达式，而这个式子本身是中缀表达式，后缀表达式也称逆波兰表达式，是计算机进行四则运算的基本手段，也是编译原理课程中的重点。
我们这里仅按这个算式的后缀表达式进行分析，首先，设计一个栈来保存数据，就是读到这个式子中的数据、以及中间的运算结果，都进栈，对式子:
3 4 * 5+ 6 7 * +
的各次进栈运算过程如下:
栈 读算式状态 1 空栈 3 4 * 5+ 6 7 * + 2 3 4 * 5+ 6 7 * + 3 3,4 * 5+ 6 7 * + 4 3、4出栈，计算3*4，结果12进栈，栈中: 遇到*运算符号
12
5 12、5 + 6 7 * + 6 12、5出栈，计算12+5，结果17进栈，栈中: 遇到+运算符号
17
7 17 6 7 * +
8 17、6 7 * +
9 17、6、7 * +
10 6、7出栈，计算6*7，结果42进栈，栈中: 遇到*运算符号
17、42
11 17、42出栈，计算17+42，结果进栈 遇到+运算符号 12 最终结果出栈
表1 后缀表达式3 4 * 5+ 6 7 * +四则运算过程
说白了:就是遇到数字就进栈、遇到运算符就出栈两个数字进行计算，非常简单。
编程实现
上述算法明白后，则先设计一个字符串保留这个后缀表达式:
char F[]={“34*5+67*+”};
根据我们的分析:该问题有四则运算，式子又是字符串、其中运算符是字符，所以首
8 / 18
先编写一个两数计算的函数，其运算符是一个字符，所以这个函数是很容易实现的:
1 int Comput(int a,int b,char o)
2 {
3 int c;
4 switch (o)
5 {
6 case '+': c=a+b;break;
7 case '-': c=a-b;break;
8 case '*': c=a*b;break;
9 case '/': c=a/b;break;
10 default: c=0;
11 }
12 return c;
13 }
一个根据运算符o进行两数计算的函数，见s2.c
说明ch是逐个读F中的字符，说明n是读的F[]中的位置，num是两数计算结果，num1、
num2是要计算的两个数:
char ch;
int n=0,num,num1,num2;
下面肯定就是说明一个栈:
struct seqStack *s;
s=StackInit(100);
我们前面设计的进栈数据类型是ElemType，有着4列各种不同的数据类型，现在这里仅
仅使用其中一列即可，比如是iData，于是进出栈数据就是:
struct ElemType e;
对于一个要进栈的整数m，则要:
e.iData=m;Push(s,&e);
这样的语句来完成。所以这个能进行后缀表达式的程序就是:
9 / 18
1 main()
2 {
3 struct ElemType e,*p;
4 char F[128]={"34*5+67*+"};
5 char ch;
6 int n=0,num,num1,num2;
7 struct seqStack *s;
8 s=StackInit(100);
9 ch=F[n];
10 while(ch!='\0')
11 {
12 if(ch>='0'&&ch<='9')
13 {
14 e.iData=ch-0x30;
15 Push(s,&e);
16 }
17 else
18 {
19 p=Pop(s);num1=p->iData;
20 p=Pop(s);num2=p->iData;
21 num=Comput(num1,num2,ch);
22 e.iData=num;
23 Push(s,&e);
24 }
25 n++;
26 ch=F[n];
27 }
28 printf("%d\n",Pop(s)->iData);
29 }
使用栈、后缀表达式进行四则运算的程序，见s2.c
请注意我们的程序是个能执行运算的程序，而教材中是示意性程序，不能执行。 S2.c和s1.c在函数上没差别，仅仅是main()中是根据不同要求设计的。有关理论介绍见
教材P58以及程序
清单
安全隐患排查清单下载最新工程量清单计量规则下载程序清单下载家私清单下载送货清单下载
3-13。
为什么会用到栈呢,很简单，假如一个问题需要你不断向前走、遇到个什么事物、你
需要回头再处理、那么这个问题就适合用到栈。上述问题就是一个最简单的
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
:不断取
F[]中的字符，遇到运算符就退出两个数据去运算。再比如一个迷宫的探索，见MAZE文件
夹，如果遇到障碍要回退到一个起点重新开始探索，那么保留走过的路径就是进栈、退回
来的过程就是出栈。
自己尝试用前缀表达式完成四则运算，在S2.C的基础上不断修改即可完成。
例2 把一个四则运算算式的中缀表达式转换成后缀表达式
通过例1的分析:四则运算要使用后缀表达式计算，直接使用中缀表达式计算则很难，
10 / 18
于是对于:
a+b*c+(d+e)*f
这样的表达式，该怎么求它的后缀表达式呢,
对于这样的算式，我们可以构造出下面这样的树，从树中进行后序遍历，就是我们要
的结果，但构造二叉树不是我们此时的工作，随后我们在二叉树的章节里会专门介绍到这样
方法的程序。目前仅仅是用字符串分析方法。
直接从上图分析，这个树的后序遍历结果是:
abc*+de+f*+
但此时我们只能是仅仅看着字符串:
a+b*c+(d+e)*f
进行分析。首先我们发现:
1 两个式子中数据项abcdef的次序是一致的，这就是说遇到数据项直接输出即可;
2 取到运算符要先保存、直到取出更低优先级的运算符、则所有保留的运算符逆序输
出取到的运算符再次进栈。假设数据项是由a~z的字符组成，则对于上述分析的1实际很好
满足，而对于运算符，则肯定使用栈，于是有:
栈内数据 算式读取状态 处理方式 输出结果 1 a+b*c+(d+e)*f 取到a直接输出 a 2 + +b*c+(d+e)*f +进栈 3 b*c+(d+e)*f 取到b直接输出 ab 4 +、* *c+(d+e)*f *比+优先级高，进栈 5 +、* c+(d+e)*f 取到c直接输出 abc 6 + +(d+e)*f 取到+，比前一个运算符*abc*+
的优先级低，输出栈内数
据，将这个运算符再次压
进栈。
7 +、( (d+e)*f (是高优先级，进栈
+、( d+e)*f 取到d直接输出 abc*+d
+、(、+ +e)*f 取到+，等)，进栈 abc*+d
+、(、+ e)*f 取到e直接输出 abc*+de
)*f 取到)，出栈+，直到(，但这abc*+de+
里(不能输出
+、* *f 取到*，比+优先级高，进栈 abc*+de+
+、* f 取到f直接输出 abc*+de+f
取完，最后输出栈内数据 abc*+de+f*+
11 / 18
表2 一个中缀表达式转后缀表达式的计算过程
全部过程就是:遇到数据项直接输出，遇到较高运算符进栈、遇到较低优先级运算符
出栈，如上述表格中的第4步，是进栈，而在第6步，取到+、而栈内是*，则栈内数据全部出栈、新取到的+再入栈。
1、 首先要一个运算符高低判断的函数、注意对运算符优先级的定义:
运算符优先级，由低到高 运算符 优先级
低 ( 0
+,- 1
*,/ 2
高 ) 3
仅仅在这四个优先级的判断上、编程处理是很容易的，我们先设定“)“的优先级是
0，+、-运算的优先级是1，*、/运算的优先级是2，)的优先级是3，以此
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
进行优先级判断，然后设置优先级的数组:
char st[]={"(+-*/)"};
int pL[]={0,1,1,2,2,3};
这两个数组中，运算符和优先级是一一对应的。
如有两个符OP1、OP2进行对比，首先确定它们在st[]中的位置，就是:
for(i=0;i<6;i++)
if(st[i]==OP1) break;
这个程序将取得OP1在st[]中的位置下标i，然后取得优先级的值:
a1=pL[i];
同样的方式可以取得OP2的优先级a2，则a1-a2的结果为正，则说明OP1的优先级小于OP2，反之就是OP1的优先级大于OP2。完整的函数如下表:
1 int pLevel(char OP1,char OP2)
2 {
3 char st[]={"(+-*/)"};
4 int pL[]={0,1,1,2,2,3};
5 int a1,a2,i;
6 for(i=0;i<6;i++)
7 if(st[i]==OP1) break;
8 a1=pL[i];
9 for(i=0;i<6;i++)
10 if(st[i]==OP2) break;
11 a2=pL[i];
12 return a1-a2;
13 }
判断运算符OP1、OP2的优先级高低，见s3.c
2、不用出栈即可获得栈顶数据
注意表2的第6步，当取到+运算符时，则首先判断栈顶数据是*，由于取到的+运算符优先级比栈顶的*优先级第，所以要全部栈内数据出栈。
同理注意表2第4步，当取到*运算符号时，栈顶数据是+，所以决定*运算符进栈，所以、这个问题中、取得栈顶数据就成为必须的操作了。
对栈S取得栈顶数据，实际很简单，就是:
Struct ElemType *p;
12 / 18
P=s->top;p--;
由于我们仅仅要该表中的字符数据，所以这个函数整个就是: 1 struct ElemType * GetTop(struct seqStack *s) 2 {
3 struct ElemType *p;
4 if(s==NULL) return NULL;
5 if(s->Count==0) return NULL;
6 p=s->top;
7 p--;
8 return p;
9 }
10 char cGetTop(struct seqStack *s)
11 {
12 if(s==NULL) return ' ';
13 return GetTop(s)->c;
14 }
获得栈顶数据、获得栈顶数据字符项，见s3.c 这样做的好处是我们可以通过GetTop()获得栈顶的全部数据项、也可以通过cGetTop()
获得栈顶数据的字符项。同样的方法，我们修改Push()和Pop()，就是:
1 void cPush(struct seqStack *s,char c)
2 {
3 struct ElemType E;
4 E.c=c;
5 Push(s,&E);
6 }
7 char cPop(struct seqStack *s)
8 {
9 if(s==NULL) return ' ';
10 return Pop(s)->c;
11 }
字符数据进出栈函数，见s3.c
3 算式符号分析
一个表达式是由字符串组成的，字符串中各个字符到底是什么含义,这样的分析在计
算机程序设计中叫词法分析，比如C语言的编译，会立刻告诉你Main()这样的写法是错误
的。当然我们这里的情况要简单的多。
对一个类似:
a+b*c+(d+e)*f
的算式进行分析，可以发现有几种情况:
(1) 由字母(可能是大小写混合的)、数字构成的数据项; (2) ”(“字符，代表一个子式子的运算;
(3) “)”字符，代表着一个子运算式子的结束; (4) “;”，可能会有，代表着一个完整式子的结束; (5) +、-、*、/运算符，代表着各个数据项之间的运算。
13 / 18
所以我们需要一个简单的词法分析函数，在真正的编译系统里，这个词法分析系统会
很复杂，但我们这里可以按上述过程做一个很简单的词法分析函数，用来处理一个语
句中出现的各个字符:
1 int Lexical (char c)
2 {
3 if(c>='a'&&c<='z') return 1;
4 if(c>='A'&&c<='Z') return 1;
5 if(c>='0'&&c<='9') return 1;
6
7 if(c=='(') return 2;
8 if(c==')') return 3;
9 if(c==';') return 4;
10 if(c=='+'||c=='-'||c=='*'||c=='/') return 5;
11 return 0;
}
表达式字符数据含义分析函数，见s3.c
这样的函数、让我们通过1、2、3、4、5这样的结果，就知道当前字符是属于哪种
情况，我们要这样函数的目的是试图把多判断程序通过switch()-case语句完成，而不是使用if-else语句，复杂情况的判断如果是用if-else来判断是很难过的事情，例如教材中P59的程序清单3-14、它并不好读。
4 按词法分析结果处理算式
读一个字符串的算式，仅仅是下面的程序就足够了:
1 char F[128]={"a+b*c+(d+e)*f"};
2 char ch;
3 int n=0;
4 ch=F[n];
5 while(ch!='\0')
6 {
7 if(ch>='a'&&ch<='z')
8 printf("%c",ch);
9 n++;
10 ch=F[n];
11 }
12 printf("\n");
算式处理程序基本框架
注意ch读到的是第n位的字符，这个程序将从头到尾完全读完并显示，有这个框架，
则我们要按词法分析的结果分类处理:
情况1:词法分析Lexical (ch)返回结果是1，说明这是个数据项，或许是字母、或许是数
字，这个情况下就是直接显示即可，于是有:
case 1:printf("%c",ch);break;
情况2:词法分析Lexical (ch)返回结果是2，说明ch中是字符’(‘，此时ch直接进栈即可
:
case 2:cPush(s,ch);break;
14 / 18
情况3:词法分析Lexical (ch)返回结果是3，说明ch中是字符’)‘，此时要求将栈内数据全
部出栈，直到遇到字符’(‘，这样就是:
do {
ch1=cPop(s);
if(ch1!='(') printf("%c",ch1);
} while(ch1!='(' && StackLength(s)>0);
break;
情况4:词法分析Lexical (ch)返回结果是4，说明ch中是字符’;‘，同情况3一样要求全部
数据出栈，所以该情况同3的要求是一致的。这个字符可以没有。
情况5:词法分析Lexical (ch)返回结果是5，说明ch中是+、-、*、/的运算符，此时要判
断:
(1) 假如栈空ch就立刻进栈;
(2) 假如栈不空则取栈顶的字符数据，和ch进行优先级比较，如ch优先级低于栈顶运
算符优先级，则栈内运算符先出栈;
(3) ch进栈;
这样就是有:
case 5:
if(StackLength(s)==0) //栈空就立刻进栈
cPush(s,ch);
else //非空
{
//ch低优先级，栈内运算符出栈
while(StackLength(s)>0 && pLevel(ch,cGetTop(s))<=0)
{
ch1=cPop(s);
if(ch1!='(') printf("%c",ch1);
}
//ch进栈
cPush(s,ch);
按这个过程分析，修改算式处理程序基本框架中的程序，首先计算ch的词法分析结果，
就是:
while(ch!='\0')
{
S=Lexical(ch);
…
然后开始有:
switch(S)
{
case 1:..
case 2:…
case 3:…
case 4:…
case 5:…
}
15 / 18
这样，一个大致的程序框架形成，补充上面的分析结果就是。
所以有以下main()函数:
1 main()
2 {
3 char F[128]={"a+b*c+(d+e)*f"};
4 char ch,ch1;
5 int n=0,S;
6 struct seqStack *s;
7 s=StackInit(100);
8 ch=F[n];
9 while(ch!='\0')
10 {
11 S=Lexical(ch);
12 switch(S)
13 {
14 case 1:printf("%c",ch);break; //处理字母表示的数字、或者是数字
15 case 2:cPush(s,ch);break; //处理"("符号 16 case 3: //处理")"符号 17 case 4: //处理语句结束符号";"，可有可无
18 do
19 {
20 ch1=cPop(s);
21 if(ch1!='(') printf("%c",ch1); 22 }while(ch1!='(' && StackLength(s)>0); 23 break;
24
25 case 5: //处理+、-、*、/这类运算符
26 if(StackLength(s)==0) //栈空就立刻进栈 27 cPush(s,ch);
28 else //栈非空 29 {
30 //ch低优先级，栈内运算符出栈 31 while(StackLength(s)>0 && pLevel(ch,cGetTop(s))<=0)
32 {
33 ch1=cPop(s);
34 if(ch1!='(') printf("%c",ch1); 35 }
36 //当前取到的运算符进栈 37 cPush(s,ch);
38 }
39 break;
40 }
41 n++;
42 ch=F[n];
16 / 18
43 }
44 //可能没有";"做结束符号，则在这里把全部栈内运算符出栈 45 while(StackLength(s)>0)
46 {
47 ch1=cPop(s);
48 if(ch1!='(') printf("%c",ch1);
49 }
50 printf("\n");
51 }
中缀表达式转后缀表达式，见s3.c
自己尝试着把mian()函数转换成一个专用函数。
这个范例或许比较大，但通过这个范例，我们应该学会一点:细致周密地把底层
算法分析做好(如栈系统、表2、pLevel()、Lexcal())，把P13-P16那样的草稿打好，整体
再写程序也不是很难的事情。总之，回答好每个细节问题，整体就才能有把握。
例3 把递归调用转为非递归运算
递归调用的程序简洁、非常漂亮，但其运算效率是十分不好。
比如n!的计算，递归的函数是:
double Fact(int n)
{
if(n==0) return 1;
return n*Fact(n-1);
}
分析这个函数执行过程，如求Fact(5)，则会发现5、4、3、2、1被逐个进栈保存、
而在返回调用的时候逐个出栈，所以可以找到一个规律:
递归调用进入函数:参数进栈、返回则出栈。于是这个函数可以写成:
1 double Fact(int n)
2 {
3 double F=1.;
4 struct seqStack *s;
5 struct ElemType e,*p;
6 s=StackInit(100);
7 while(n>0)
8 {
9 e.iData=n;
10 Push(s,&e);
11 n=n-1;
12 }
13 while(StackLength(s)>0)
14 {
15 p=Pop(s);
16 F=F*p->iData;
17 }
18 DestroyStack(s);
19 return F;
17 / 18
20 }
使用栈消除递归的阶乘计算函数，见s4.c
类似上述计算的函数，一定注意末尾要加上栈销毁函数(第18行)。假如不加栈销毁函数，多次调用它后会占用很多内存空间，这是在大型计算程序中不允许的。
注意这个规律:参数进栈、而出栈则计算。
Ackerman函数是一个典型的递归计算函数，这个函数是:
Ack(m,n)=n+1; (当m=0)
Ack(m,n)=Ack(m-1,1) (当m!=0,n=0)
Ack(m,n)=Ack(m-1,Ack(m,n-1) (当m!=0、n!=0)
尝试着写一个描述m，n逐个进栈的程序。其递归的程序见Ack.c，这个程序由于XP本身对递归调用的限制，它无法计算n,m大于5的情况。
18 / 18
浙公网安备 33021202002483