第4章 栈和队列（修改）

null第四章 栈和队列 第四章 栈和队列 插入和删除操作受限的线性表插入和删除操作受限的线性表栈（stack） 后进先出(LIFO:Last In First Out)的线性表 表头端称为栈底（bottom） 表尾端称为栈顶（top） 插入和删除都在栈顶进行 队列（queue） 先进先出(FIFO:First In First Out)的线性表 表头端称为队头（front） 表尾端称为队尾（rear） 插入在队尾进行，而删除则在队头进行 4.1 栈的类型定义和基本操作4.1 栈的类型定义和基本操作 栈的基本操作 栈的基本操作InitStack(&s) 初始化堆栈 StackEmpty(S) 判断堆栈是否空 Push(S, &e) 将元素e压入堆栈 Pop(s, &e) 弹出栈顶元素 GetTop(s, &e); 读取栈顶元素栈的存储结构栈的存储结构两种方式 顺序表方式（常用） 链表方式 顺序表方式的堆栈类型定义 #define STACK_SIZE 128 ElemType stack[STACK_SIZE]; int top; 堆栈容量的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ：根据算法需要， 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法的空间复杂度 堆栈存储空间的动态扩张和缩小 受限的扩张提早发现死循环 编号系统 0~(n-1)，top记载下个空位位置，或者说，元素个数 栈满和栈空顺序表方式的堆栈操作顺序表方式的堆栈操作#define InitStack() top = 0 #define StackEmpty() (top==0) Status push(elemType e) { if (top == STACK_SIZE) return ERROR; stack[top++] = e; return OK; } 顺序表方式的堆栈操作顺序表方式的堆栈操作Status pop(elemType &e) { if (top == 0) return ERROR; e = stack[--top]; return OK; } Status GetTop(elemType &e) { if (top == 0) return ERROR; e = stack[top-1]; return OK; } 栈的链式存储结构以及操作栈的链式存储结构以及操作存储结构设计 不带头的单链表 类型定义 struct NODE { ElemType data; struct NODE *next; }; struct NODE *stack; 操作算法 InitStack ClearStack: 释放所有节点 其他操作：Push, Pop，GetTop, StackEmpty4.2 栈的应用举例4.2 栈的应用举例栈的应用：简单例子栈的应用：简单例子简单例子：数制转换简单例子：数制转换 void conversion(void) { InitStack(); scanf(“%d”, &n); while(N) { push(N % 8); N /= 8; } while (!StackEmpty()) { Pop(&e); printf(“%d”, e); } } 栈的应用：迷宫问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 栈的应用：迷宫问题迷宫问题迷宫问题 迷宫问题粗解迷宫问题粗解栈 栈中元素 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 下一步的动作，包括坐标和移动方向 初始状态 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 迷宫图 char maze[L][L]; 三种取值： .通路，o障碍，#脚印 堆栈 #define STACK_SIZE (L*L) struct { int x，y; int dir; } stack[STACK_SIZE]; int top;迷宫问题算法:子程序迷宫问题算法:子程序#define SetMark(x, y) maze[x][y] = '#' #define ClearMark(x, y) maze[x][y] = '.' int step(int &x, int &y, int dir) { switch(dir) { case EAST: y++; break; case WEST: y--; break; case SOUTH: x++; break; case NORTH: x--; break; } if (x < 0 || x > L-1) return 0; if (y < 0 || y > L-1) return 0; return maze[x][y] == '.'; }迷宫问题算法2迷宫问题算法2基本思路 游历到某点时，将所有可能的下一步位置记录到堆栈中 数据结构 struct XY { int x; int y; }; struct XY stack[STACK_SIZE]; int top; 堆栈的最大尺寸 3*L*L迷宫问题算法2的实现迷宫问题算法2的实现算法实现 stack_init(); push(0, 0); while(!stack_empty()) { pop(x, y); maze[x][y] = '#'; if (x,y是出口) return OK; push_all_next(x, y); } return ERROR; 迷宫问题算法2的实现:子程序迷宫问题算法2的实现:子程序#define valid(x,y) \ ( (x >= 0 && x < L) && \ (y >= 0 && y < L) && \ maze[x][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中的问题迷宫问题算法2中的问题问题： 路径表示 解决方法： 构造与周游顺序倒序的路径链表 struct XY path[L][L]; 路径链表的逆转算法算法2的完善:登记路径算法2的完善:登记路径#define PUSH(x1, y1) { \ push(x1, y1); \ path[x1][y1].x = x; \ path[x1][y1].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的完善:路径逆转算法2的完善:路径逆转void revert_path(void) { struct XY head, next, pre; pre.x = pre.y = -1; head.x = head.y = L-1; while (head.x != -1) { next = path[head.x][head.y]; path[head.x][head.y] = pre; pre = head; head = next; } } 栈的应用：地图染色问题 栈的应用：地图染色问题地图染色问题地图染色问题回溯法是一种满足一定条件的穷举搜索法：在求解过程中，不断利用可供选择的规则扩展部分解，一旦当前的部分解不成立，就停止扩展，退回到上一个较小的部分解继续试探，直到找到问题所有的解或无解为止。地图染色问题地图染色问题邻接矩阵 int adj[N][N]; 颜色 int color[N]; 取值1-4 0:未染色地图染色算法地图染色算法void main(void) { stack_init(); push(0, 1); while (!stack_empty()) { pop(x, c); if (c == 5) { color[x] = 0; continue; } push(x, c + 1); if (check(x, c, next)) { color[x] = c; if (next != -1) push(next, 1); else goto end; } } end: for (x = 0; x < N; x++) printf("%d ", color[x]); }地图染色问题:子程序地图染色问题:子程序int check(int x, int c, int &next) { int i; /* 检测颜色冲突 */ next = -1; for (i = 0; i < N; i++) { if (adj[x][i] && color[i] == c) return 0; } /* 选择下一个待涂色区域 */ for (i = 0; i < N; i++) if (color[i] == 0 && x != i) next = i; return 1; } 栈的应用：表达式求值 栈的应用：表达式求值整型数简单表达式求值整型数简单表达式求值前提假设 表达式语法正确，仅支持加减乘除四则运算和括号 每个操作数都是由单个数字构成 在表达式字符串两侧增加一对括号 算法思想 设置两个堆栈：运算符栈OPTR和操作数栈OPND 将最左侧括号进栈 依次读入表达式字符， 操作数：进OPND栈； 运算符：与算符栈栈顶元素比较优先级后做相应操作算符优先级算符优先级 整型数简单表达式求值整型数简单表达式求值stack_init(opnd); stack_init(optr); push(optr, read_next()); c = read_next(); while (!stack_empty(optr)) { if (c是操作数) { push(opnd, c - '0'); c = read_next(); } else { switch(cmp(get_top(optr), c)) { case '<': /* 栈顶元素优先级低 */ push(optr, c); c = read_next(); break; 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);4.3 栈与递归的实现4.3 栈与递归的实现栈在函数调用中的作用栈在函数调用中的作用过程一过程二过程三过程四断点一断点二断点三stack 程序的执行环境程序的执行环境指令段 程序：源程序编译后的指令代码 数据段 字符串常数 char *str=“Hello!\n”; printf(“a=%d, b=%d\n”, a, b); 函数体外定义的全局数据（有初值的数据和没有初值的数据） int a[128]={2， 3， 4}; int b[128], *p; 函数体内的静态数据 static int reg; 动态申请的数据区 malloc, free 堆栈段 函数参数 函数的返回地址 函数体内的auto型变量（static型变量不在栈中分配） 程序执行过程中堆栈的动态变化 函数调用前的处理和调用结束处理 函数内访问函数的参数变量和函数内部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 PROC 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 2 push 1 call _abc add esp, 12 mov _x$[ebp], eax ; 21 : printf("x = %d\n", 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; ; 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, b); d = ab(a, b-1); return c + d; } 主程序： ab(2, 3);递归算法的应用场合递归算法的应用场合规模较大的问题可以化解为规模较小的问题，且二者处理(或定义)的方式一致 当问题规模降低到一定程度时是可以直接求解的(终止条件)设计递归算法应注意的问题设计递归算法应注意的问题递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用 递归算法应有出口(终止条件) 考虑递归算法的效率（时间/空间复杂性分析） （分析阶乘问题。斐波那奇数列，hanoi塔问题的效率）递归算法的特点递归算法的特点优点：递归算法简单明了，直观 设计算法时仅需要从逻辑层次上寻求问题的解，不考虑实现细节 缺点：实现问题 效率低，尤其是许多相同子问题重复计算，例如斐波那奇数列问题 程序运行的空间开销 算法的优化 迷宫问题的递归解法迷宫问题的递归解法int maze_path(int x, int y) { if (x < 0 || x > L-1) return 0; if (y < 0 || y > L-1) return 0; if (maze[x][y] !='.') return 0; SetMark(x, y); if (x == L-1 && y == L-1) return 1; if (maze_path(x, y+1)) return 1; /* EAST */ if (maze_path(x+1, y)) return 1; /* SOUTH */ if (maze_path(x, y-1)) return 1; /* WEST */ if (maze_path(x-1, y)) return 1; /* NORTH */ ClearMark(x, y); return 0; } 主程序 printf("%s\n", maze_path(0, 0) ? "OK" : "Failure"); 汉诺(Hanoi)塔问题 汉诺(Hanoi)塔问题将 n 个盘子从 X柱移到 Z 柱，Y 柱可用 每次只能移动一个盘子 在移动过程中，大盘不许压小盘12. .nX Y Z汉诺塔问题汉诺塔问题 void hanoi(int n, char x, char y, char 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) hanoi递归算法(1) struct TOWER { int ndisk; char disk[N]; 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); hanoi(n-1, y, x, z); } } void main(int argc, char **argv) { ... hanoi(ndisk, &t[0], &t[1], &t[2]); }hanoi仿真递归(2) 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, &t[0], &t[1], &t[2]); label_0: } 定义三个宏 #define LABEL_0 0 #define LABEL_1 1 #define LABEL_2 2hanoi仿真递归(3) hanoi仿真递归(3) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); /* 模拟主程序调用*/ loop: /* 循环进入时，n, x, y, z都必须按照递归函数入口要求赋值 */ if (n == 1) move(x, z); else { /* 保留现场，记住递归结束返回位置1，为参数赋值后转下一轮调用*/ push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); /* hanoi(n-1, x, z, y); */ goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); /* hanoi(n-1, y, x, z); */ goto loop; label_2: } /* 此处应增加递归返回处理,最后一次递归返回该goto label_0 其余恢复递归前的程序现场执行,goto到LABEL_1或者LABEL_2 */ } label_0: hanoi仿真递归(4) hanoi仿真递归(4) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); loop: if (n == 1) move(x, z); else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); /* hanoi(n-1, x, z, y); */ goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); /* hanoi(n-1, y, x, z); */ goto loop; label_2: } /* 函数结尾处理:递归返回,恢复上次调用的参数n,x,y,z ， 如果label为LABEL_0该退出循环，否则goto到调用的下条语句 */ pop ( &n, &x, &y, &z, &label); if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; if (label == LABEL_2) goto label_2; } label_0: hanoi非递归算法优化(5) hanoi非递归算法优化(5) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); loop: if (n == 1) move(x, z); else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); goto loop; } label_2: pop ( &n, &x, &y, &z, &label); if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; if (label == LABEL_2) goto label_2; goto loop; } label_0: hanoi非递归算法优化(6) hanoi非递归算法优化(6) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); loop: if (n == 1) { move(x, z); label_2: pop ( &n, &x, &y, &z, &label); if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; if (label == LABEL_2) goto label_2; goto loop; } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); goto loop; } } label_0: hanoi非递归算法优化(7) hanoi非递归算法优化(7) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); for (;;) { loop: if (n == 1) { move(x, z); label_2: pop ( &n, &x, &y, &z, &label); if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; if (label == LABEL_2) goto label_2; } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } label_0: hanoi非递归算法优化(7) hanoi非递归算法优化(7) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); for (;;) { loop: if (n == 1) { move(x, z); label_2: pop ( &n, &x, &y, &z, &label); if (label == LABEL_2) goto label_2; if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } label_0: hanoi非递归算法优化(8) hanoi非递归算法优化(8) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); for (;;) loop: if (n == 1) { move(x, z); while ( (label = pop(&n, &x, &y, &z)) ==LABEL_2); /* 改pop函数*/ if (label == LABEL_0) goto label_0; if (label == LABEL_1) goto label_1; } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; label_1: move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } label_0: hanoi非递归算法优化(9) hanoi非递归算法优化(9) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); for (;;) loop: if (n == 1) { move(x, z); while ( (label = pop(&n, &x, &y, &z)) == LABEL_2); if (label == LABEL_0) goto label_0; if (label == LABEL_1) { move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); goto loop; } } label_0: hanoi非递归算法优化(10) hanoi非递归算法优化(10) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); for (;;) if (n == 1) { move(x, z); while ( (label = pop(&n, &x, &y, &z)) == LABEL_2); if (label == LABEL_0) goto label_0; if (label == LABEL_1) { move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); } } label_0: hanoi非递归算法优化(11) hanoi非递归算法优化(11) stack_init(); n = ndisk; x = &t[0]; y = &t[1]; z = &t[2]; push(n, x, y, z, LABEL_0); while (!stack_empty()) { if (n == 1) { move(x, z); while ( (label = pop(&n, &x, &y, &z)) == LABEL_2); if (label == LABEL_1) { move(x, z); push(n, x, y, z, LABEL_2); n = n-1; swap(x,y); } } else { push(n, x, y, z, LABEL_1); n = n-1; swap(y,z); } } (最终程序)经典问题:背包问题 经典问题:背包问题 设有n种物品，每种物品有一个重量Wi及一个价值Vi。但每种物品的数量是无限的. 有一个背包，最大载重量为C，今从n种物品中每样选取Xi件(Xi=0,1,2,…)，使其重量的和ΣXiWi小于等于C，而价值的和ΣXiVi为最大。经典问题:八皇后问题经典问题:八皇后问题在国际象棋的规则中，皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8*8个方格），使它们谁也不能被吃掉？ (N皇后问题)4.4 队列4.4 队列队列的定义队列的定义队列是一种特殊的线性表 限定插入和删除操作分别在表的两端进行 具有先进先出(FIFO—First In First Out)的特点。队列的操作队列的操作主要操作 增加（入队） EnQueue(Q, e); 删除（出队） DeQueue(Q, &e); 判断队列是否为空 QueueLength(Q) 其他操作 初始化队列InitQueue(Q) 获取队列长度 QueueLength(Q) 清除队列中的所有元素 ClearQueue(Q)队列的存储结构和实现队列的存储结构和实现链表方式 顺序表方式链式队列链式队列链式队列的存储结构链式队列的存储结构存储结构：选用带头的单项链表 data next^q.frontq.rear队头队尾typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; LinkQueue q;链式队列的初始化和插入算法链式队列的初始化和插入算法InitQueue(LinkQueue &Q) { Q.front = Q.rear = malloc(sizeof(QNode)); Q.front->next = NULL; } EnQueue(LinkQueue &Q, QElemType e) { p = malloc(sizeof(QNode)); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; }链式队列的删除算法链式队列的删除算法Status DeQueue(LinkQueue &Q, EElemType &e) { if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK; }链式队列的其它算法链式队列的其它算法求队列长度 遍历队列中现有所有元素 特殊算法：队中插入，队中删除 考虑其他的链表结构实现队列使用顺序表方式实现队列使用顺序表方式实现队列循环队列循环队列存储结构： 使用静态的数组或者动态申请的连续存储空间 队列描述： 队头队尾 基本算法 增加和删除元素 队列满和队列空的表示方法 方法一：浪费一个存储空间，以(rear+1)%N==front判断队列满 方法二：设置队列中的数据元素计数队列的主要用途队列的主要用途典型用法：处理当前数据时，将由当前数据引发的多个待处理数据排队等待随后处理