栈和队列.ppt

《栈和队列.ppt》由会员分享，可在线阅读，更多相关《栈和队列.ppt（72页珍藏版）》请在三一文库上搜索。

1、第三章 栈和队列,插入和删除操作受限的线性表,栈（stack） 后进先出(LIFO:Last In First Out)的线性表 表头端称为栈底（bottom） 表尾端称为栈顶（top） 插入和删除都在栈顶进行 队列（queue） 先进先出(FIFO:First In First Out)的线性表 表头端称为队头（front） 表尾端称为队尾（rear） 插入在队尾进行，而删除则在队头进行,3.1 栈的类型定义和基本操作,栈的基本操作,InitStack( 读取栈顶元素,栈的存储结构,两种方式 顺序表方式（常用） 链表方式 顺序表方式的堆栈类型定义 #define STACK_SIZE 128

2、 ElemType stackSTACK_SIZE; int top; 堆栈容量的设计：根据算法需要，分析算法的空间复杂度 堆栈存储空间的动态扩张和缩小 受限的扩张提早发现死循环 编号系统 0(n-1)，top记载下个空位位置，或者说，元素个数 栈满和栈空,顺序表方式的堆栈操作,#define InitStack() top = 0 #define StackEmpty() (top=0) Status push(elemType e) if (top = STACK_SIZE) return ERROR; stacktop+ = e; return OK; ,顺序表方式的堆栈操作,Statu

3、s pop(elemType ,栈的链式存储结构以及操作,存储结构设计 不带头的单链表 类型定义 struct NODE ElemType data; struct NODE *next; ; struct NODE *stack; 操作算法 InitStack ClearStack: 释放所有节点 其他操作：Push, Pop，GetTop, StackEmpty,3.2 栈的应用举例,栈的应用：简单例子,简单例子：数制转换,void conversion(void) InitStack(); scanf(“%d”, ,栈的应用：迷宫问题,迷宫问题,迷宫问题粗解,栈 栈中元素记录下一步的动作

4、，包括坐标和移动方向 初始状态 push(0,0,EAST); 循环执行下列动作： pop(x,y,dir); push(x,y,dir+1); if (step(x,y,dir) push(x,y,EAST); 函数step(int &x, int &y, int dir) 判断从x,y位置按照方向dir移动一步是否允许 函数返回时修改x,y为新位置的坐标 迷宫的表示方法和step函数的实现,迷宫问题算法：数据结构,方向定义 #define EAST 0 #define SOUTH 1 #define WEST 2 #define NORTH 3 #define BAD_DIRECT 4 迷

5、宫图 char mazeLL; 三种取值： .通路，o障碍，#脚印 堆栈 #define STACK_SIZE (L*L) struct int x，y; int dir; stackSTACK_SIZE; int top;,迷宫问题算法:子程序,#define SetMark(x, y) mazexy = # #define ClearMark(x, y) mazexy = . int step(int ,迷宫问题算法2,基本思路 游历到某点时，将所有可能的下一步位置记录到堆栈中 数据结构 struct XY int x; int y; ; struct XY stackSTACK_SIZE

6、; int top; 堆栈的最大尺寸 3*L*L,迷宫问题算法2的实现,算法实现 stack_init(); push(0, 0); while(!stack_empty() pop(x, y); mazexy = #; if (x,y是出口) return OK; push_all_next(x, y); return ERROR;,迷宫问题算法2的实现:子程序,#define valid(x,y) ( (x = 0 /* East */ ,迷宫问题算法2中的问题,问题： 路径表示 解决方法： 构造与周游顺序倒序的路径链表 struct XY pathLL; 路径链表的逆转算法,算法2的完善

7、:登记路径,#define PUSH(x1, y1) push(x1, y1); pathx1y1.x = x; pathx1y1.y = y; void push_all_next(int x, int y) if (valid(x+1, y) PUSH(x+1, y); /* North */ if (valid(x, y-1) PUSH(x, y-1); /* West */ if (valid(x-1, y) PUSH(x-1, y); /* South */ if (valid(x, y+1) PUSH(x, y+1); /* East */ ,算法2的完善:路径逆转,void re

8、vert_path(void) struct XY head, next, pre; pre.x = pre.y = -1; head.x = head.y = L-1; while (head.x != -1) next = pathhead.xhead.y; pathhead.xhead.y = pre; pre = head; head = next; ,栈的应用：地图染色问题,地图染色问题,回溯法是一种满足一定条件的穷举搜索法：在求解过程中，不断利用可供选择的规则扩展部分解，一旦当前的部分解不成立，就停止扩展，退回到上一个较小的部分解继续试探，直到找到问题所有的解或无解为止。,地图染色

9、问题,邻接矩阵 int adjNN; 颜色 int colorN; 取值1-4 0:未染色,地图染色算法,void main(void) stack_init(); push(0, 1); while (!stack_empty() pop(x, c); if (c = 5) colorx = 0; continue; push(x, c + 1); if (check(x, c, next) colorx = c; if (next != -1) push(next, 1); else goto end; end: for (x = 0; x N; x+) printf(“%d “, col

10、orx); ,地图染色问题:子程序,int check(int x, int c, int ,栈的应用：表达式求值,整型数简单表达式求值,前提假设 表达式语法正确，仅支持加减乘除四则运算和括号 每个操作数都是由单个数字构成 在表达式字符串两侧增加一对括号 算法思想 设置两个堆栈：运算符栈OPTR和操作数栈OPND 将最左侧括号进栈 依次读入表达式字符， 操作数：进OPND栈； 运算符：与算符栈栈顶元素比较优先级后做相应操作,算符优先级,整型数简单表达式求值,stack_init(opnd); stack_init(optr); push(optr, read_next(); c = read_

11、next(); while (!stack_empty(optr) if (c是操作数) push(opnd, c - 0); c = read_next(); else switch(cmp(get_top(optr), c) case : /* 栈顶元素优先级高 */ pop(optr, oper); pop(opnd, b); pop(opnd, a); push(opnd, operate(a, oper, b); break; case =: pop(optr, a); c = read_next(); break; return get_top(opnd);,3.3 栈与递归的实现

12、,栈在函数调用中的作用,过程一,过程二,过程三,过程四,断点一,断点二,断点三,stack,程序的执行环境,指令段 程序：源程序编译后的指令代码 数据段 字符串常数 char *str=“Hello!n”; printf(“a=%d, b=%dn”, a, b); 函数体外定义的全局数据（有初值的数据和没有初值的数据） int a128=2， 3， 4; int b128, *p; 函数体内的静态数据 static int reg; 动态申请的数据区 malloc, free 堆栈段 函数参数 函数的返回地址 函数体内的auto型变量（static型变量不在栈中分配） 程序执行过程中堆栈的动态

13、变化 函数调用前的处理和调用结束处理 函数内访问函数的参数变量和函数内部auto型变量的方法,子程序的嵌套调用,int ab(int a, int b) int c; c = a + b; return c; int abc(int a, int b, int c) int x, y; x = ab(a, b); y = ab(b, c); return x + y; 主程序： abc(1, 2, 3);,使用堆栈实现子程序调用,_DATA SEGMENT $SG51 DB x = %d, 0aH, 00H _DATA ENDS _a$ = 8 _b$ = 12 _c$ = -4 _ab PR

14、OC NEAR ; 2 : push ebp mov ebp, esp push ecx ; 3 : int c; ; 4 : c = a + b; mov eax, _a$ebp add eax, _b$ebp mov _c$ebp, eax ; 5 : return c; mov eax, _c$ebp ; 6 : mov esp, ebp pop ebp ret _ab ENDP,_main PROC NEAR ; 16 : push ebp mov ebp, esp push ecx ; 17 : int x; ; 19 : x = abc(1, 2, 3); push 3 push

15、2 push 1 call _abc add esp, 12 mov _x$ebp, eax ; 21 : printf(“x = %dn“, x); mov eax, _x$ebp push eax push $SG51 call _printf add esp, 8 ; 23 : return; ; 24 : mov esp, ebp pop ebp ret _main ENDP,_a$ = 8 _x$ = -4 _b$ = 12 _y$ = -8 _c$ = 16 _abc PROC NEAR push ebp mov ebp, esp sub esp, 8 ; 9 : int x, y

16、; ; 10 : x = ab(a, b); mov eax, _b$ebp push eax mov ecx, _a$ebp push ecx call _ab add esp, 8 mov _x$ebp, eax . 求y = ab(b, c) ; 12 : return x + y; mov eax, _x$ebp add eax, _y$ebp ; 13 : mov esp, ebp pop ebp ret _abc ENDP,子程序的递归调用,int ab(int a, int b) int c, d; c = a + b; if (c 5) return c; c = ab(a-1

17、, b); d = ab(a, b-1); return c + d; 主程序： ab(2, 3);,递归算法的应用场合,规模较大的问题可以化解为规模较小的问题，且二者处理(或定义)的方式一致 当问题规模降低到一定程度时是可以直接求解的(终止条件),设计递归算法应注意的问题,递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用 递归算法应有出口(终止条件) 考虑递归算法的效率（时间/空间复杂性分析） （分析阶乘问题。斐波那奇数列，hanoi塔问题的效率）,递归算法的特点,优点：递归算法简单明了，直观 设计算法时仅需要从逻辑层次上寻求问题的解，不考虑实现细节 缺点：实现问

18、题 效率低，尤其是许多相同子问题重复计算，例如斐波那奇数列问题 程序运行的空间开销 算法的优化,迷宫问题的递归解法,int maze_path(int x, int y) if (x L-1) return 0; if (y L-1) return 0; if (mazexy !=.) return 0; SetMark(x, y); if (x = L-1 ,12. .n,X Y Z,汉诺(Hanoi)塔问题,将 n 个盘子从 X柱移到 Z 柱，Y 柱可用 每次只能移动一个盘子 在移动过程中，大盘不许压小盘,汉诺塔问题,void hanoi(int n, char x, char y, ch

19、ar z) if (n = 1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); ,递归程序的非递归实现,hanoi递归算法(1),struct TOWER int ndisk; char diskN; int pos; ; void hanoi(int n, struct TOWER *x, struct TOWER *y, struct TOWER *z) if (n = 1) move(x, z); else hanoi(n-1, x, z, y); move(x, z); hano

20、i(n-1, y, x, z); void main(int argc, char *argv) . hanoi(ndisk, ,hanoi仿真递归(2),void hanoi(int n, struct TOWER *x, struct TOWER *y, struct TOWER *z) if (n = 1) move(x, z); else hanoi(n-1, x, z, y); label_1: move(x, z); hanoi(n-1, y, x, z); label_2: void main(int argc, char *argv) . hanoi(ndisk, label_

21、0: 定义三个宏 #define LABEL_0 0 #define LABEL_1 1 #define LABEL_2 2,hanoi仿真递归(3),stack_init(); n = ndisk; x = label_2: /* 此处应增加递归返回处理,最后一次递归返回该goto label_0 其余恢复递归前的程序现场执行,goto到LABEL_1或者LABEL_2 */ label_0:,hanoi仿真递归(4),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(5),stack_init(); n = ndisk; x = labe

22、l_0:,hanoi非递归算法优化(6),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(7),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(7),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(8),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(9),stack_init(); n = ndisk; x = label_0:,hanoi非递归算法优化(10),stack_in

23、it(); n = ndisk; x = label_0:,hanoi非递归算法优化(11),stack_init(); n = ndisk; x = (最终程序),经典问题:背包问题,设有n种物品，每种物品有一个重量Wi及一个价值Vi。但每种物品的数量是无限的. 有一个背包，最大载重量为C，今从n种物品中每样选取Xi件(Xi=0,1,2,)，使其重量的和XiWi小于等于C，而价值的和XiVi为最大。,经典问题:八皇后问题,在国际象棋的规则中，皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8*8个方格），使它们谁也不能被吃掉？ (N皇后问题),3.4 队列,队列的

24、定义,队列是一种特殊的线性表 限定插入和删除操作分别在表的两端进行 具有先进先出(FIFOFirst In First Out)的特点。,队列的操作,主要操作 增加（入队） EnQueue(Q, e); 删除（出队） DeQueue(Q, 判断队列是否为空 QueueLength(Q) 其他操作 初始化队列InitQueue(Q) 获取队列长度 QueueLength(Q) 清除队列中的所有元素 ClearQueue(Q),队列的存储结构和实现,链表方式 顺序表方式,链式队列,链式队列的存储结构,存储结构：选用带头的单项链表,data next,q.front,q.rear,队头,队尾,typ

25、edef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; LinkQueue q;,链式队列的初始化和插入算法,InitQueue(LinkQueue ,链式队列的删除算法,Status DeQueue(LinkQueue ,链式队列的其它算法,求队列长度 遍历队列中现有所有元素 特殊算法：队中插入，队中删除 考虑其他的链表结构实现队列,使用顺序表方式实现队列,循环队列,存储结构： 使用静态的数组

26、或者动态申请的连续存储空间 队列描述： 队头队尾 基本算法 增加和删除元素 队列满和队列空的表示方法 方法一：浪费一个存储空间，以(rear+1)%N=front判断队列满 方法二：设置队列中的数据元素计数,队列的主要用途,典型用法：处理当前数据时，将由当前数据引发的多个待处理数据排队等待随后处理,作业,设计一个算法，判断一个算术表达式中的括号是否配对，并求出括号的最大嵌套层数。提示：考虑下面三种情况： (1+(2+3)*(5+6*(1+2)*8 匹配情况 (1+(2+3)*(5+6*(1+2)*8 左括号太多 (1+(2+3)*(5+6*(1+2)*8 右括号太多 有n个整数存于数组a中，给出求解最大值的递归算法。 写出求解正整数m和n的最大公因子的递归算法。 选作题：写出ack函数的非递归实现算法。（上机实习证明算法的正确性）,上机作业,递归方法实现八皇后问题。,