栈和队列课件

1、第三章 栈和队列栈 栈的存储结构及应用 队列队列的存储结构及应用栈的基本概念定 义数据元素之间是一对一的关系 顺序存储或链式存储 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则存储结构运算规则逻辑结构只能在表的一端进行插入和删除的线性表基本操作建栈、判断栈满或栈空、入栈、出栈、取栈顶元素值栈的示意图栈是仅在表尾进行插入、删除操作的线性表表尾(即 an 端)称为栈顶 (top) 表头(即 a1 端)称为栈底(bottom)插入元素到栈顶的操作，称为入栈从栈顶删除元素的操作，称为出栈栈 S= (a1 , a2 , a3 , .,an-1 , an )栈顶元素栈底元

2、素插入和删除都只在表的一端（栈顶）进行栈的基本操作 INISTACK(S)：初始化操作。设置一个空栈S。EMPTY(S)：判栈空函数。若S为空栈，函数值为1，否则为0SIZE(S)：求栈深函数。函数值为栈中当前的元素个数。TOP(S)：读栈顶元函数。若栈S不空，函数值为栈顶元素，否则为空元素NULL。PUSH(S,x)：进栈操作。将元素x插入栈S中，使x成为栈S的栈顶元素。POP(S):出栈函数。若栈S不空，函数值为栈顶元素，且从栈中删除当前栈顶元素，否则函数值为空元素NULL。CLEAR(S):栈置空操作。不论栈S是否为空栈，将S置为空栈35178421011001余数结果：10011十进制

3、数转换成二进制数把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）,十进制数35转换成二进制数 将带头结点的单链表（a1,a2,an）逆置 栈的顺序存储结构(顺序栈)顺序栈:利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素C语言中预设较大的数组空间栈底设为0栈顶随插入和删除元素而变化用一个整型变量top来指示栈顶的位置 a1 a2 an顺序栈S ai0n栈底栈顶top压入(PUSH): Stop+=an+1弹出( POP) : e=S-top顺序栈存储结构的描述#define MAXSIZE 100 typedef int elemtype;typedef

4、struct stack elemtype elemMAXSIZE; int top； /栈顶指针sqstacktp； /顺序栈类型定义sqstacktp *s； /s为顺序栈类型变量的指针s=(sqstacktp *)malloc(sizeof(sqstacktp);123450栈空栈顶指针top,可初始化为0，指向实际栈顶后的空位置.top123450进栈Atop出栈BCDEF设数组大小为MAXSIZEs-top=0,栈空，此时出栈则下溢s-top= MAXSIZE,栈满，此时入栈上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop设MAXS

5、IZE=6顺序栈的几种情况栈空栈满top顺序栈上实现的操作初始化（栈置空）操作void ini_sqstack(sqstacktp *s)；判栈空函数int empty_sqstack(sqstacktp *s)；进栈操作void push_sqstack(sqstacktp *s，elemtype x)；出栈函数elemtype pop_sqstack(sqstacktp *s) ；求栈深函数int size_sqstack(sqstacktp *s)；读栈顶元函数elemtype top_sqstack(sqstacktp *s)；栈的链式存储结构定义栈的链式存储结构，简称链栈组织形式与单

6、链表类似，链表的尾部是栈底，链表的头部是栈顶 FtopdatanextEDANULL栈顶栈底栈的链式存储结构链栈的类型定义：typedef struct stacknode elemtype data； struct stacknode *next； stacknode;typedef struct stacknode *top; /栈顶指针linkstack;linkstack *ls;ls=(linkstack *)malloc(sizeof(linkstack);ls-top=?初始化操作void init_linkstack(linkstack *ls)； 进栈操作void push_

7、linkstack(linkstack *ls,elemtype x)；出栈操作elemtype pop_linkstack(linkstack *ls)；链栈上实现的操作对算术表达式求值： 1 + 2 * 4 - 9 / 3遵循先乘除后加减、先左后右及先括号内，后括号外的四则运算法则，其计算顺序应为：1 + 2 * 4 - 9 / 3 栈的应用实例表达式求值采用“运算符优先数法” 对每种运算符赋于一个优先数，如：运算符： * / + - #优先数： 2 2 1 1 0其中 # 是表达式结束符对表达式求值时，一般设立两个栈运算符栈（OPTR)操作数栈(OPND)分别存放表达式中的运算符和操作数

8、 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 1+2*4-9/3# PUSH(OPND,1) 2 # 1 +2*4-9/3# PUSH(OPTR,+) 3 # + 1 2*4-9/3# PUSH(OPND,2) 4 # + 1 2 *4-9/3# PUSH(OPTR,*) 5 # + * 1 2 4-9/3# PUSH(OPND,4) 6 # + * 1 2 4 -9/3# operate(2,*,4) 7 # + 1 8 -9/3# operate(1,+,8) 8 # 9 -9/3# PUSH(OPTR,-) 9 # - 9 9/3# PUSH(OPND,9) 10 # -

9、9 9 /3# PUSH(OPTR,/) 11 # - / 9 9 3# PUSH(OPND,3) 12 # - / 9 9 3 # operate(9,/,3) 13 # - 9 3 # operate(9,-,3) 14 # 6 # RETURN(TOP(OPND) 利用算法对算术表达式求值的操作过程栈在回溯法中的应用在某些问题的求解过程中常常采用试探方法，当某一路径受阻时，需要逆序退回，重新选择新路径，这样必须用栈记录曾经到达的每一状态，栈顶状态即是回退的第一站。 地图四染色问题“四染色”定理可以用不多于四色对地图着色，使相邻的地区不重色算法思想 ：“回溯”法从第一号地区开始逐一染色，每

10、一个地区逐次用色数1、2、3、4进行试探若当前所取的色数与周围已染色的地区不重色，则用栈记下该地区的色数，否则依次用下一色数进行试探若出现用1.4色均与相邻地区发生重色，则需退栈回溯，修改当前栈顶的色数。地图四染色问题算法实现“四染色”定理数据结构graphnnn*n的关系矩阵grphij=0表示地区i与地区j不相邻graphij=1表示地区i与地区j相邻。colorn颜色表：顺序存储colori表示i号地区的染色数。(1)(2)(4)(5)(6)(7)(3)r 7 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1

11、 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 1223414334231# 紫色 2# 黄色 3# 红色 4# 绿色地图四染色算法栈与函数调用由于程序设计都采用模块化程序设计方法，模块（函数、过程）是完成功能相对独立的一个程序段，在主函数（主程序）中调用模块来解决复杂的实际问题由于函数调用后，需返回调用处，所以，在调用时，需用栈记录断点的地址以及有关信息，以便返回。 栈的应用-函数调用int func_B(int x,int y) int z; z=x+y; return z; int func_A(

12、) int x=10,y=20,k; k=func_B(x,y); return k;void main() printf(“%d”,func_A(); 函数调用栈与函数堆栈是存储器的一个区域编译器一般使用堆栈实现函数调用函数占用的区域被称作函数的栈帧 函数调用时，为被调用的函数分配栈帧，存放函数的参数、局部变量等信息函数嵌套调用时，堆栈中会同时存在多个函数的栈帧，每个函数占用一个连续的区域函数独占自己的栈帧空间当前正在运行的函数的栈帧总是在栈顶两个特殊的寄存器ESP，EBP栈与函数栈帧中的信息局部变量栈帧状态值保存前一栈帧的顶部和底部函数返回地址保存函数调用前的指令位置栈与函数r主程序srr

13、rs子过程1rst子过程2rst子过程3栈与函数调用的图示递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的二叉树是结点的有限集合，这个集合或者是空的，或者由一个根结点或两棵互不相交的称为左子树的和右子树的二叉树组成 若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。 直接递归fun_a() fun_a() 间接递归fun_a() fun_b() fun_b() fun_a() 递归的定义递归条件解决问题时，可以把一个问题转化为一个新的问题，这个新问题的解决方法，与原问题的解法相同，只是所处理的对象有所不同。这些被处理的对象之间有规律的递增或递减要有一个

14、明确的结束递归的条件，否则递归将会无止境地进行下去，直到耗尽系统资源.必须要有终止递归的条件适用递归技术的问题以下三种情况常常用到递归方法定义是递归的数据结构是递归的问题的解法是递归的求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);例如，阶乘函数定义是递归的 例如，单链表结构f f 数据结构是递归的一个结点，它的指针域为NULL，是一个单链表一个结点，它的指针域指向单链表，仍是一个单链表打印单链表最后一个结点的值void Print ( ListNode *f

15、 ) if ( f -link = NULL ) printf(“%dn”, f -data); else Print ( f -link );f f f f a0a1a2a3a4f 递归找链尾数据结构是递归的1 3 3 21 31 22 12 31 3源中间目的 1 2 3源中间目的64个 a b cmove(n,a,b,c)move(n-1,a,c,b)a cmove(n-1,b,a,c)64个64个问题的解法是递归的hanoi(3,1,2,3)n=3 a=1 b=2 c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,

16、2)n=2 a=1 b=3 c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1 a=1 b=2 c=3 move(a,c); 1-3 1-2 1-3hanoi(1,3,1,2)n=1 a=3 b=1 c=2move(a,c); 3-2hanoi(2,2,1,3)n=2 a=2 b=1 c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1 a=2 b=3 c=1move(a,c); 2-1 2-3hanoi(1,1,2,3)n=1 a=

17、1 b=2 c=3move(a,c); 1-3void hanoi(int n,int a,int b,int c) if( n = 1) move(a,c); else hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); 1-3 1-2 3-2 2-1 2-3 1-3 1-3递归模型 递归是把一个不能或不好直接求解的“大问题”转化为一个或几个“小问题”再把这些“小问题”进一步分解成更小的“小问题”来解决直到递归出口为止递归模型反映一个递归问题的递归结构递归模型由递归出口和递归体两部分组成前者确定递归到何时为止后者确定递归的方式 递归模型 递归出口的一般格式为f(s0)=m0这里的s0与m0均为常量，有的递归问题可能有几个递归出口。递归体的一般格式为f(s)=g(f(s1), f(s2), f(sn),c1, c2,，cm)s是一个递归“大问题”s1, s2, sn是递归“小问题”c1, c2,，cm是若干个可以直接（用非递归方法）解决的问题g是一个非递归函数，反映了递归问题的结构。 递归模型 例如，阶乘函数递归出口递归体主程序 main : fact(4)参数 4 计算 4*fact(3) 参数 3 计算 3*fact(2) 参数 2 计算 2*fact(1)