数据结构31(栈).pptVIP

* 例：编写一个递归函数，实现从键盘读入一串字符(以回车结束)，并按逆序输出。画出递归工作栈的进出栈示意图。 void inputc() main() { 7 { char s; 8 inputc( ); 3 s=getchar(); 9 } 4 if(s!=‘\n’) inputc(); 5 putchar(s); } 假设输入的一串字符为: 2fty5 * 递推过程： （1）inputc() （2）inputc() （3）inputc() （4）inputc() （5）inputc() （6）inputc() 每递推一次生成一个工作记录进栈,工作记录包括局部变量，上一层的返回地址。 局部(s) 上一层的返回地址 (6) ‘\n’ 5 (5) 5 5 (4) y 5 (3) t 5 (2) f 5 2 9 递归工作栈（进栈） * 回推过程： （1）inputc()：换行 （2）inputc()：输出5 （3）inputc()：输出y （4）inputc()：输出t （5）inputc()：输出f （6）inputc()：输出2 每递推一次生成一个工作记录进栈,工作记录包括局部变量，上一层的返回地址。 局部(s) 上一层的返回地址 (6) ‘\n’ 5 (5) 5 5 (4) y 5 (3) t 5 (2) f 5 2 9 递归工作栈（出栈） * 第三章 栈、队列和数组 栈是“后进先出”的线性表(LIFO)。 队列是“先进先出”的线性表(FIFO)。 * 从数据结构的角度看: 栈与队列和线性表相同 从数据类型的角度看: 栈与队列和线性表不同 线性表：插入 Insert(L, i, x)(1≤i≤n+1) 删除 Delete(L, i)(1≤i≤n) 　　栈：插入 Insert(S, n+1, x) 　　删除 Delete(S, n) 　队列：插入 Insert(Q, n+1, x) 　删除 Delete(Q, 1) * 3.1 栈 3.1.1 栈的定义和运算 栈（STACK）：限定只能在表的一端进行插入和删除的线性表。 栈顶（TOP）：允许插入和删除的一端 栈底（BOTTOM）：不允许插入和删除的一端。 * 进栈 出栈 栈顶 an ┇ ┇ a2 栈底 a1 出栈顺序： an, an-1, ……,a2, a1 * 思考：如果进栈顺序为1，2，3，4。不限制出栈的时间，则下面哪一种出栈顺序不可能。 (1) 1,2,3,4 (2) 2,1,4,3 (3) 3,1,2,4 (4) 4,3,2,1 * 栈的常用基本运算： （1）初始化：InitStack(S) 操作结果：构造一个空栈S。 （2）进栈：Push(S,x) 操作结果：将元素x插入栈S中，使x成为栈S的栈顶元素。 （3）出栈：Pop(S) 操作结果：将栈顶元素赋给x，并从栈中删除当前栈顶元素。 * 栈的常用基本运算： （4）读栈顶：To