第3章限定性线性表-栈和队列

1、第第3章章 限定性线性表限定性线性表栈和队列栈和队列3.1 栈栈3.2 队列队列3.3 总结与提高总结与提高3.1 3.1 栈栈3.1.1 栈的定义栈的定义3.1.2 栈的表示和实现栈的表示和实现3.1.3 栈的应用举例栈的应用举例3.1.4 栈与递归的实现栈与递归的实现栈的定义：栈的定义： 栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 根据栈定义，每次进栈的元素都被放在原栈顶元素

2、之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示： 进栈、出栈图例进栈、出栈图例进栈进栈出栈出栈进栈出栈栈顶栈底ana2a1栈的抽象数据类型定义栈的抽象数据类型定义关系：关系：栈中数据元素之间是栈中数据元素之间是线性关系线性关系数据元素数据元素：可以是任意类型的数据，但必须属于：可以是任意类型的数据，但必须属于同同一个数据对象一个数据对象。 基本操作基本操作：InitStack（S） 2. ClearStack（S）3. IsEmpty（S） 4. IsFull（S） 5. Push（S，x） 1. 6.

3、 Pop（S，x） 7. GetTop（S，x）3.1.2 栈的表示和实现栈的表示和实现栈栈在计算机中主要有在计算机中主要有两种两种基本的存储结基本的存储结构：构：顺序存储结构顺序存储结构和和链式存储结构链式存储结构。顺序存储的栈为顺序存储的栈为顺序栈；顺序栈；链式存储的栈为链式存储的栈为链栈链栈。1.1.顺序栈顺序栈 顺序栈是用顺序存储结构实现的栈，即顺序栈是用顺序存储结构实现的栈，即利用一组利用一组地址连续地址连续的存储单元依次存放的存储单元依次存放自栈自栈底到栈顶底到栈顶的数据元素，同时由于栈的操作的的数据元素，同时由于栈的操作的特殊性，还必须附设一个特殊性，还必须附设一个位置指针位置指

4、针top（栈（栈顶指针）来动态地指示栈顶元素在顺序栈中顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以的位置。通常以top = -1表示空栈。表示空栈。栈的顺序存储结构定义如下栈的顺序存储结构定义如下 ：#define Stack_Size 50typedef struct StackElementType elemStack_Size; /*用来存放栈中元素的一维数组用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标，用来存放栈顶元素的下标，top为为-1表示空栈表示空栈*/SeqStack; 顺序栈中的进栈和出栈图例顺序栈中的进栈和出栈图例AEDCBABAto

5、p top top top顺序栈基本操作的实现顺序栈基本操作的实现1）初始化）初始化void InitStack(SeqStack *S)/*构造一个空栈构造一个空栈S*/ S-top= -1;2）进栈）进栈int Push(SeqStack * S, StackElementType x)if(S-top= Stack_Size-1) return(FALSE); /*栈已满栈已满*/S-top+;S-elemS-top=x;return(TRUE);3）出栈）出栈int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*栈为空栈为空

6、*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针修改栈顶指针 */ return(TRUE); 4） 取栈顶元素取栈顶元素int GetTop（SeqStack S, StackElementType *x） /* 将栈将栈S的栈顶元素弹出，放到的栈顶元素弹出，放到x所指的存储空间中，但所指的存储空间中，但栈顶指针保持不变栈顶指针保持不变 */if(S-top=-1) /*栈为空栈为空*/ return(FALSE);else *x = S-elemS-top; return(TRUE); 两栈共享技术（双端栈）：两栈共享技术（

7、双端栈）：主要利用了栈主要利用了栈“栈底位置不变栈底位置不变，而栈顶位置动态变而栈顶位置动态变化化”的特性。首先为两个栈申请一个共享的一维数的特性。首先为两个栈申请一个共享的一维数组空间组空间SM，将两个栈的栈底分别放在一维数组的，将两个栈的栈底分别放在一维数组的两端，分别是两端，分别是0，M-1。 共享栈的空间示意为：共享栈的空间示意为：top0和和top1分别为两个栈分别为两个栈顶指示器顶指示器 。top0top1Stack：0M-1两栈共享的数据结构定义两栈共享的数据结构定义#define M 100typedef struct StackElementType StackM; int

8、top2; /*top0和和top1分别为两个栈顶分别为两个栈顶指示器指示器*/DqStack;（1） 两栈共享的初始化操作算法两栈共享的初始化操作算法void InitStack(DqStack *S)S-top0=-1;S-top1=M;（2） 两栈共享的进栈操作算法两栈共享的进栈操作算法int Push(DqStack *S, StackElementType x, int i) /*把数据元素把数据元素x压入压入i号堆栈号堆栈*/ if(S-top0+1=S-top1) /*栈已满栈已满*/ return(FALSE);switch(i)case 0:S-top0+; S-StackS

9、-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default: return(FALSE) /*参数错误参数错误*/ return(TRUE);（3） 两栈共享的出栈操作算法两栈共享的出栈操作算法int Pop(DqStack *S, StackElementType *x, int i) /* 从从i 号堆栈中弹出栈顶元素并送到号堆栈中弹出栈顶元素并送到x中中 */ switch(i) case 0: if(S-top0=-1) return(FALSE); *x=S-StackS-top0; S-top0-; break;

10、 case 1:if(S-top1=M) return(FALSE); *x=S-StackS-top1;S-top1+;break;default: return(FALSE);return(TRUE);2. 链栈链栈链栈链栈是采用是采用链表链表作为存储结构实现的栈。为作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。便于操作，采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。进行，所以链表的表头指针就作为栈顶指针。 链栈的示意图为：链栈的示意图为：anan-1 a1top top为栈顶

11、指针，始终指向当前栈顶元素前面的头结为栈顶指针，始终指向当前栈顶元素前面的头结点。若点。若top-next=NULL，则代表空栈。，则代表空栈。注意：注意：链栈在使用完毕时，应该释放其空间。链栈在使用完毕时，应该释放其空间。链栈结构的用链栈结构的用C语言定义语言定义typedef struct node StackElementType data; struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;链栈的进栈操作链栈的进栈操作int Push(LinkStack top, StackElementType x)/*

12、 将数据元素将数据元素x压入栈压入栈top中中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申请空间失败申请空间失败 */temp-data=x; temp-next=top-next;top-next=temp; /* 修改当前栈顶指针修改当前栈顶指针 */ return(TRUE);链栈的出栈操作链栈的出栈操作int Pop(LinkStack top, StackElementType *x) /* 将栈将栈top

13、的栈顶元素弹出，放到的栈顶元素弹出，放到x所指的存储空间中所指的存储空间中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*栈为空栈为空*/return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 释放存储空间释放存储空间 */ return(TRUE);如果将可利用的空闲结点空间组织成链栈来管理，则申如果将可利用的空闲结点空间组织成链栈来管理，则申请一个新结点（类似请一个新结点（类似C语言中的语言中的malloc函数）相当于链函数）相当于链栈的什么操作？归还一

14、个无用结点（类似栈的什么操作？归还一个无用结点（类似C语言中的语言中的free函数）相当于链栈的什么操作？试分别写出从链栈函数）相当于链栈的什么操作？试分别写出从链栈中申请一个新结点和归还一个空闲结点的算法。中申请一个新结点和归还一个空闲结点的算法。 【思考题】【思考题】（3）多栈运算）多栈运算将多个链栈的栈顶指针放在一个一维指针数组中来统一管理，将多个链栈的栈顶指针放在一个一维指针数组中来统一管理，从而实现同时管理和使用多个栈。从而实现同时管理和使用多个栈。 0M-1231C1 C2 D1 E1 E2 E3 F1 G1 G2 top#define M 10 /*M个链栈*/typedef s

15、truct node StackElementType data; struct node *next;LinkStackNode, *LinkStack; LinkStack topM; 用用c语言定义语言定义(1)第i号栈的进栈操作int pushi(LinkStack topM, int i, StackElementType x)/*将元素x进入第i号链栈*/LinkStackNode *temp;temp=(LinkStackNode * )malloc(sizeof(LinkStackNode);if(temp=NULL) return(FALSE); /* 申请空间失败 */te

16、mp-data=x;temp-next=topi-next; topi-next=temp; /* 修改当前栈顶指针 */ return(TRUE); (2) 第第i号栈元素的出栈操作号栈元素的出栈操作int Pop(LinkStack topM, int i, StackElementType *x) /* 将栈将栈top的栈顶元素弹出，放到的栈顶元素弹出，放到x所指的存储空间中所指的存储空间中 */ LinkStackNode *temp; temp=topi-next; if(temp=NULL) /*第第i号栈为空栈号栈为空栈*/return(FALSE); topi-next=tem

17、p-next; *x=temp-data; free(temp); /* 释放存储空间释放存储空间 */ return(TRUE); 例如：例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输出顺序输出顺序1、 数制转换数制转换算法原理：N = (N div d)d + N mod d 3.1.3 栈的应用举例栈的应用举例void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N %

18、 8); N = N/8; while (!IsEmpty(S) Pop(S,e); printf ( %d, e ); / conversion2. 括号匹配问题括号匹配问题算法的设计思想：算法的设计思想： 1 1）凡出现左括弧左括弧，则进栈进栈；2 2）凡出现右括弧右括弧，首先检查栈是否空 若栈空栈空，则表明该“右括弧右括弧”多余多余， 否则和栈顶元素和栈顶元素比较， 若相匹配相匹配，则“左括弧出栈左括弧出栈” ” ， 否则表明不匹配不匹配。3 3）表达式表达式检验结束时结束时， 若栈空栈空，则表明表达式中匹配正确匹配正确， 否则表明“左括弧左括弧”有余有余。算法算法: :void Bra

19、cketMatch(char *str)Stack S; int i; char ch;InitStack(&S);For(i=0; stri!=0; i+) switch(stri) case (:case :case : Push(&S,stri); break; case ): case : case :if(IsEmpty(S) printf(n右括号多余右括号多余!); return;elseGetTop (&S,&ch);if(Match(ch,stri) Pop(&S,&ch); else printf(n对应的左右括号不同类对应的

20、左右括号不同类!); return;/*switch*/*for*/if(IsEmpty(S)printf(n括号匹配括号匹配!);elseprintf(n左括号多余左括号多余!);3. 表达式求值表达式求值1) 无括号算术表达式求值无括号算术表达式求值表达式运算及运算符表达式运算及运算符优先级优先级3+4*5 # +- */ * 0 1 2 3 置空栈置空栈OVS、OPTR进进OVS读字符W退退OVS顶、次顶，顶、次顶，OPTR顶顶将将T(i)=OVS新顶新顶进进OPTR栈栈W是操作符是操作符N结束结束NYNYYYW=#OPTRZ栈栈空空YW优先级优先级OPTR栈栈顶优先级顶优先级N无括号算

21、术表达式的无括号算术表达式的处处理过程理过程如右图如右图2) 算术表达式处理规则算术表达式处理规则规定优先级表；规定优先级表；(2) 设置两个栈：设置两个栈：OVS(运算数栈运算数栈)和和OPTR(运算运算符栈符栈)；(3) 自左向右扫描，遇操作符则与自左向右扫描，遇操作符则与OPTR栈顶优栈顶优先级比较：当前操作符先级比较：当前操作符OPTR栈顶则进栈顶则进OPTR栈；当前操作符栈；当前操作符 OPTR栈顶，栈顶，OVS栈顶、次顶栈顶、次顶和和OPTR栈顶，退栈形成运算栈顶，退栈形成运算T（i），）， T（i）进进OVS栈。栈。例：实现例：实现A/BC+D*E#的运算过程时栈区变化情况的运算

22、过程时栈区变化情况3) 带括号算术表达式带括号算术表达式实现算符优先算法时需要使用两个工作栈：一个称实现算符优先算法时需要使用两个工作栈：一个称作作运算符栈运算符栈operator；另一个称作；另一个称作操作数栈操作数栈operand。算法的基本过程如下：算法的基本过程如下：A.初始化操作数栈初始化操作数栈operand和运算符栈和运算符栈operator，并，并将表达式起始符将表达式起始符“#”压入运算符栈；压入运算符栈；B.读入表达式中的每个字符，若是操作数则直接进读入表达式中的每个字符，若是操作数则直接进入操作数栈入操作数栈operand，若是运算符，则与运算符栈，若是运算符，则与运算符

23、栈operator的栈顶运算符进行优先权比较，并做如下的栈顶运算符进行优先权比较，并做如下处理：处理： (1) 若栈顶运算符的优先级低于刚读入的运算符，若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进则让刚读入的运算符进operator栈；栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入则将栈顶运算符退栈，送入，同时将操作数栈，同时将操作数栈operand退栈两次，得到两个操作数退栈两次，得到两个操作数a、b，对，对a、b进进行行运算后，将运算结果作为中间结果推入运算后，将运算结果作为中间结果推入operand栈

24、；栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。（左括号）退栈即可。当当operator栈的栈顶元素和当前读入的字符均为栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符时，说明表达式起始符“#”与表达式结束符与表达式结束符“#”相相遇，整个表达式求值完毕。遇，整个表达式求值完毕。优先关系表（部分运算符）优先关系表（部分运算符） + * i ( ) #+ * i ( ) # 例：利用上述优先关系表描述表达式（例：利用上述优先关系表描

25、述表达式（B*C+D E）的）的计算过程。计算过程。3.1.4 栈与递归的实现栈与递归的实现递归递归 :在定义自身的同时又出现了对自身的调用。在定义自身的同时又出现了对自身的调用。直接递归函数直接递归函数:如果一个函数在其定义体内直接调如果一个函数在其定义体内直接调用自己，则称直接递归函数。用自己，则称直接递归函数。间接递归函数：间接递归函数：如果一个函数经过一系列的中间调如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递用语句，通过其它函数间接调用自己，则称间接递归函数。归函数。1.1.具有递归特性的问题具有递归特性的问题 1）递归定义的数学函数）递归定义的数学函数如

26、二阶Fibonacci数列： Ackerman函数： Fib(n)= 0 若n=0 1 若n=1 Fib(n-1)+Fib(n-2) 其它情况 Ack(m,n)= n+1 当m=0时 Ack(m-1,1) 当m0, n=0时 Ack(m-1,Ack(m,n-1) 当m0, n0时 Ackerman函数可用一个简单的C语言函数描述: int ack(int m,int n) if(m= =0) return n+1; else if (n= =0) return ack(m-1,1); else return ack(m-1, ack(m,n-1); 2 2）实现递归）实现递归n将所有的实在参数

27、、返回地址等信息传递给将所有的实在参数、返回地址等信息传递给被调用函数保存；被调用函数保存；n为被调用函数的局部变量分配存储区；为被调用函数的局部变量分配存储区；n将控制转移到被调用函数的入口。将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：n保存被调函数的计算结果；n释放被调函数的数据区；n依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：void main( ) void

28、 a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区3）递归求解方法）递归求解方法 许多问题的求解过程可以用递归分解的方法许多问题的求解过程可以用递归分解的方法描述，一个典型的例子是著名的汉诺塔问题描述，一个典型的例子是著名的汉诺塔问题（hanoihanoi）问题。）问题。 汉诺（汉诺（Hanoi) 塔问题塔问题 设设：有有X、Y、Z三个塔座，在三个塔座，在X上按直径大小递减次序依上按直径大小递减次序依次插有次插有n个直径各不相同的圆盘，各圆盘按直径从小到大编个直径各不相同的圆盘，各圆盘按直径从小到大编为为1n。 要求：

29、要求：将将X 塔上的塔上的n个圆盘按规则移至个圆盘按规则移至Z上，并仍按同样顺上，并仍按同样顺序叠排序叠排 移动规则：移动规则： 每次只能移动一个圆盘；每次只能移动一个圆盘；移动的圆盘可以移动的圆盘可以插在任一塔座上，但是在任一时刻都不能将大盘压在小盘插在任一塔座上，但是在任一时刻都不能将大盘压在小盘上。上。XYZ1n算法思想：算法思想：当当n=1时，只要将编号为时，只要将编号为1的圆盘从座的圆盘从座X直接移动到塔直接移动到塔座座Z上即可；上即可；当当n1时，需利用塔座时，需利用塔座Y作辅助塔座，若能设法将压在作辅助塔座，若能设法将压在编号为编号为n的圆盘上的的圆盘上的n-1个圆盘从塔座个圆盘

30、从塔座X(依照上述原则依照上述原则)移至移至塔座塔座Y上，则可先将编号为上，则可先将编号为n的圆盘从塔座的圆盘从塔座X 移至塔座移至塔座Z上，上，然后再将塔座然后再将塔座Y上的上的n-1个圆盘个圆盘(依照上述原则依照上述原则)移至塔座移至塔座Z上。上。而如何将而如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同特征属性的问题，只是问题的规模小于和原问题具有相同特征属性的问题，只是问题的规模小于1，因此可以用同样方法求解。因此可以用同样方法求解。 求解求解n阶阶Hanoi塔问题的递归算法塔问题的递归算法 void hanoi(int n,

31、 char x, char y, char z)/* 将塔座将塔座X上从上到下编号为上从上到下编号为1至至n，且按直径由小到大叠放的，且按直径由小到大叠放的n个圆盘，按规则个圆盘，按规则搬到塔座搬到塔座Z上，上，Y用作辅助塔座。用作辅助塔座。*/ if(n=1) move(x,1,z); /*将编号为将编号为1的圆盘从的圆盘从x移动移动z*/ else hanoi(n-1,x,z,y); /* 将将X上编号为上编号为1至至n-1的圆盘移到的圆盘移到y,z作辅助塔作辅助塔 */ move(x,n,z); /* 将编号为将编号为n的圆盘从的圆盘从x移到移到z */ hanoi(n-1, y,x ,

32、z); /* 将将y上编号为上编号为1至至n-1的圆盘移到的圆盘移到z，x作辅助塔作辅助塔 */ if(n=1) move(x,1,z); else hanoi(2,x,z,y); move(x,n,z); hanoi(n-1, y,x ,z); hanoi(3, x, y, z) if(n=1) move(x,1,y); else hanoi(1,x,y,z); move(x,n,y); hanoi(1, z,x ,y); hanoi(2, x, z, y) if(n=1) move(x,1,z); else hanoi(1,x,z,y); move(x,n,z); hanoi(n-1, y

33、,x ,z); hanoi(1, x, y, z) if(n=1) move(y,1,z); else hanoi(1,y,z,x); move(x,n,z); hanoi(n-1, x,y ,z); hanoi(1, y, x, z) if(n=1) move(y,1,z); else hanoi(1,y,x,z); move(x,n,z); hanoi(1, x,y ,z); hanoi(2, y, x, z)函函数数 调调用用过过程程hanoi(3, A, B , C) hanoi(2, A, C, B): hanoi(1, A, B, C) move(A-C) 1号搬到号搬到C mov

34、e(A-B) 2号搬到号搬到B hanoi(1, C, A, B) move(C-B) 1号搬回到号搬回到B move(A-C) 3号搬到号搬到C hanoi(2,B,A,C): hanoi(1, B, C, A) move(B-A) 1号搬到号搬到A move(B-C) 2号搬到号搬到C hanoi(1, A, B, C) move(A-C) 1号搬到号搬到C 下面给出三个盘子搬动时下面给出三个盘子搬动时hanoi(3, A, B , C) 的递归调用过程的递归调用过程递归方法的优点递归方法的优点 ：对问题描述简洁对问题描述简洁 结构清晰结构清晰 程序的正确性容易程序的正确性容易证明证明 设

35、计递归算法的方法设计递归算法的方法 递归算法就是在算法中直接或间接调用算法本身的算法。递归算法就是在算法中直接或间接调用算法本身的算法。 使用递归算法的前提有两个：使用递归算法的前提有两个： 规模最小的子问题具有直接解。规模最小的子问题具有直接解。 原问题可以层层分解为类似的的子问题，且子问题比原问题可以层层分解为类似的的子问题，且子问题比原问题的规模更小。原问题的规模更小。设计递归算法的方法设计递归算法的方法 寻找分解方法寻找分解方法 设计递归出口设计递归出口 2.2.递归过程的实现递归过程的实现 递归退层（递归退层（ii +1层）系统也应完成三件工作：层）系统也应完成三件工作：递归进层（递

36、归进层（ii +1层）系统需要做三件事：层）系统需要做三件事： 保留本层参数与返回地址；保留本层参数与返回地址； 为被调用函数的局部变量分配存储区，给下层参数赋值；为被调用函数的局部变量分配存储区，给下层参数赋值； 将程序转移到被调函数的入口。将程序转移到被调函数的入口。 保存保存被调函数的计算结果；被调函数的计算结果； 释放被调函数的数据区，恢复上层参数；释放被调函数的数据区，恢复上层参数； 依照被调函数保存的返回地址，将控制转移回调用函数。依照被调函数保存的返回地址，将控制转移回调用函数。 3.3.递归算法到非递归算法的转换递归算法到非递归算法的转换 递归算法具有两个特性：递归算法具有两个

37、特性： (1) 递归算法是一种分而治之、把复杂问递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方求解某些复杂问题，递归算法的分析方法是有效的。法是有效的。（2）递归算法的效率较低。）递归算法的效率较低。1）消除递归的原因：）消除递归的原因： 第一：有利于提高算法时空性能第一：有利于提高算法时空性能 第二：无应用递归语句的语言设施环境条第二：无应用递归语句的语言设施环境条件件 第三：递归算法是一次执行完第三：递归算法是一次执行完 消除递归方法有两类消除递归方法有两类 一类是简单递归问题的转换，对于尾递归和单向递

38、归的一类是简单递归问题的转换，对于尾递归和单向递归的算法，可用循环结构的算法替代。算法，可用循环结构的算法替代。 另一类是基于栈的方式，即将递归中隐含的栈机制转化为另一类是基于栈的方式，即将递归中隐含的栈机制转化为由用户直接控制的明显的栈。由用户直接控制的明显的栈。 2) 简单递归的消除简单递归的消除 单向递归单向递归 单向递归是指递归函数中虽然有一处以上的递归调用语句，单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，相互之间参数但各次递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。无关，并且这些递归调

39、用语句处于算法的最后。 例如计算斐波那契数列的递归算法例如计算斐波那契数列的递归算法 计算斐波那契数列的递归算法如下：计算斐波那契数列的递归算法如下： Fib(int n) if（n= =0|n= =1） return n; /* 递归出口递归出口 */ else return Fib(n-1)+Fib(n-2); /* 递归调用递归调用 */ 斐波那齐数列斐波那齐数列 Fib(N)= 0 n=01 n=1Fib(N-1)+Fib(N-2) n2计算斐波那契数列的非递归算法计算斐波那契数列的非递归算法int Fib(int n): int x, y, z;if（n= =0|n= =1）retu

40、rn n; /*计算计算 Fib (0)或或Fib(1) */ else x=0, y=1; /* x= Fib (0) y= Fib (1) */for ( i=2; i= n; i+ ) z=y; /* z= Fib (i-1) */ y=x+y; /* y= Fib (i-1)+ Fib (i-2) 求求Fib (i) */ x=z; /* x= Fib (i-1) */ return y ; 尾递归尾递归 尾递归是指递归调用语句只有一个，而且是处于算法的尾递归是指递归调用语句只有一个，而且是处于算法的最后，尾递归是单向递归的特例。最后，尾递归是单向递归的特例。 求求n!非递归算法非递归

41、算法 ： long Fact (int n) int fac=1; for(int i=1;ifront=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL; return(TRUE);else return(FALSE); /* 溢出！溢出！*/ (2) (2) 入队操作入队操作 int EnterQueue(LinkQueue *Q, QueueElementType x) /* 将数据元素将数据元素x插入到队列插入到队列Q中中 */ LinkQue

42、ueNode * NewNode; NewNode=(LinkQueueNode* )malloc(sizeof(LinkQueueNode); if(NewNode!=NULL) NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return(TRUE); else return(FALSE); /* 溢出！溢出！*/ (3) (3) 出队操作出队操作 int DeleteQueue(LinkQueue * Q, QueueElementType *x) /* 将队列将队列Q的队头元素出队，并存放到

43、的队头元素出队，并存放到x所指的存储空间中所指的存储空间中 */ LinkQueueNode * p; if(Q-front=Q-rear) return(FALSE); p=Q-front-next; Q-front-next=p-next; /* 队头元素队头元素p出队出队 */ if(Q-rear=p) /* 如果队中只有一个元素如果队中只有一个元素p，则，则p出队后成为空出队后成为空队队 */Q-rear=Q-front; *x=p-data; free(p); /* 释放存储空间释放存储空间 */ return(TRUE); 2.2.循环队列循环队列 循环队列循环队列是队列的一种是队

44、列的一种顺序顺序表示和实现方法。表示和实现方法。 1 14 40 02 23 35 5frontfrontrearrear(a)(a)空队列空队列1 14 40 02 23 35 5e e6 6e e7 7e e8 8e e4 4e e3 3e e5 5frontfrontrearrear(b) (b) 队列满队列满时时1 14 40 02 23 35 5e e4 4e e3 3e e5 5frontfrontrearrear(c) (c) 一般情况一般情况#define MAXSIZE 50 /*队列的最大长度队列的最大长度*/typedef structQueueElementType e

45、lementMAXSIZE; /* 队列队列的元素空间的元素空间*/int front; /*头指针指示器头指针指示器*/int rear ; /*尾指针指示器尾指针指示器*/ SeqQueue; 循环队列的类型定义：循环队列的类型定义：循环队列的基本操作循环队列的基本操作 (1)(1)初始化操作初始化操作 void InitQueue（SeqQueue * Q） /* 将将*Q初始化为一个空的循环队列初始化为一个空的循环队列 */Q-front=Q-rear=0; (2)(2)入队操作入队操作 int EnterQueue(SeqQueue *Q, QueueElementType x) /

46、*将元素将元素x入队入队*/ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了队列已经满了*/return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针重新设置队尾指针 */ return(TRUE); /*操作成功操作成功*/ (3)(3)出队操作出队操作 int DeleteQueue(SeqQueue *Q, QueueElementType * x) /*删除队列的队头元素，用删除队列的队头元素，用x返回其值返回其值*/ if（Q-front=Q-rear） /*队列为空队

47、列为空*/return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针重新设置队头指针*/ return(TRUE); /*操作成功操作成功*/ 3.2.3 队列的应用举例队列的应用举例 1打印杨辉三角打印杨辉三角 【算法思想算法思想】由图可看出杨辉三角形的特点：即每由图可看出杨辉三角形的特点：即每一行的第一个元素和最后一个元素均为一行的第一个元素和最后一个元素均为1，其它位置，其它位置上的数字是其上一行中与之相邻的两个整数之和。上的数字是其上一行中与之相邻的两个整数之和。所以第所以第i行上的元素要由第行

48、上的元素要由第i-1行中的元素来生成。我行中的元素来生成。我们可以利用循环队列实现打印杨辉三角形的过程：们可以利用循环队列实现打印杨辉三角形的过程：在循环队列中依次存放第在循环队列中依次存放第i-1行上的元素，然后逐个行上的元素，然后逐个出队并打印，同时生成第出队并打印，同时生成第i行元素并入队。行元素并入队。 void YangHuiTriangle( ) SeqQueue Q; InitQueue (&Q); InitQueue (&Q); EnterQueue (&Q,1); / EnterQueue (&Q,1); /* * 第一行元素入队第一行元素入队

49、* */ / for(n=2;n=N;n+) / for(n=2;n=N;n+) /* * 产生第产生第n n行元素并入队，同时打印第行元素并入队，同时打印第n-1n-1行的元素行的元素* */ / EnterQueue (&Q,1); / EnterQueue (&Q,1); /* * 第第n n行的第一个元素入队行的第一个元素入队* */ / for(i=1;i=n-2;i+) / for(i=1;i=n-2;i+) /* * 利用队中第利用队中第n-1n-1行元素产生第行元素产生第n n行的中间行的中间n-2n-2个元素并入队个元素并入队* */ / DeleteQueu

50、e (&Q,&temp); DeleteQueue (&Q,&temp); Printf( Printf(“%d%d”,temp); /,temp); /* * 打印第打印第n-1n-1行的元素行的元素* */ / GetHead(Q,&x); GetHead(Q,&x); temp=temp+x; / temp=temp+x; /* *利用队中第利用队中第n-1n-1行元素产生第行元素产生第n n行元素行元素* */ / EnterQueue (&Q,temp); EnterQueue (&Q,temp); DeleteQueue (&Q, &x); DeleteQueue (&Q, &x); printf( printf(“%d%d”, x); /, x); /* * 打印第打印第n-1n-1行的最后一个元素行的最后一个元素 * */ / EnterQueue (&Q, 1) / Ente