《栈及相关算法2010》由会员分享，可在线阅读，更多相关《栈及相关算法2010（42页珍藏版）》请在金锄头文库上搜索。
1、栈及相关算法2010-3-25 胡俊峰|关于BBS链表的插入/删除操作 及相关问题汉字 KMP曹天骄 内容 提要|栈的概念与抽象数据类型定义|栈的存储结构与实现|数制转换与递归|表达式计算|迷宫问题栈的 基本 概念|栈是一种操作受限的线性表|插入、删除操作都只能对栈顶（元素）进行|其它元素对外不提供直接访问操作ztop = -1 表示空栈ztop MAXNUM 溢出出栈 pop进栈 push!OLLEHtop栈的 抽象 数据 类型 定义ADT Stack is Operations：Stack createEmptyStack ( void )/创建一个空栈。int isEmptyStack
2、( Stack st )/判断栈st是否为空栈。void push ( Stack st, DataType x )/插入一个值为x的元素。void pop ( Stack st )/删除一个元素。DataType top ( Stack st )/ 求栈顶元素的值。 end ADT Stack 顺序 结构 栈的 类型 定义#define MAXNUM 100 /* 栈的最大容量*/| typedef int DataType; /* 栈元素的数据类型* /| struct SeqStack /* 顺序栈类型定义 */DataType elementMAXNUM;int top; /*栈顶指针
3、*/；|typedef struct SeqStack *PSeqStack;|PSeqStack pastack; /*指向顺序栈的指针变量*/顺序结构栈的类型定义顺序结构栈的类型定义顺序结 构栈的 实现顺序 结构 栈的 操作 实现 （续 ）链结 构栈ki+2 ki+1 ki k0 plstacktopinfolink链结 构栈 类型 定义#define MAXNUM 100 /* 栈的最大容量*/| struct Node DataType info;Node * next; /* pointer to the previous node* / ;| typedef Node* PNode
4、; |Struct LinkStack pNode top;|typedef struct LinkStack *PLinkStack; /* 指向链接 栈的指针 */|PLinkStack pastack; /*指向链接栈的指针变量*/链接 结构 栈的 ADT ?ADT Stack is Operations：Stack createEmptyStack ( void )/创建一个空栈。int isEmptyStack ( Stack st )/判断栈st是否为空栈。void push ( Stack st, DataType x )/（栈顶）插入一个值为x的元素。void pop ( St
5、ack st )/（栈顶）删除一个元素。DataType top ( Stack st )/ 求栈顶元素的值。 end ADT Stack 链接结构栈 的类型定义压入 弹出 元素|压入元素： 在top与栈顶之间插入 （s-link = top, top = s)|弹出元素：弹出栈顶元素 ( q = top; top= q-link;free(q); ) plstackinfolinktopCB弹出应用 数制 转换|问题：对于输入的任意一个非负十进制整数，打印 输出与其等值的八进制数。 |算法：N = (N div d) * d + N mod d512 = (514 / 8) * 8 + 51
6、4 mod 8 2(64 / 8) * 8 + 64 mod 8 0 (8 / 8) * 8 + 8 mod 8 0 (1 / 8) * 8 + 1 mod 8 1 while(n != 0) /in stack push(S,n%8); n=n/8; generatein stack栈的 应用 数制 转换 与递 归（ 续）递归算法与数制转换表达 式求 值|二元运算符的表达式定义:表达式 := (算子)+(算符) + (算子 )算子 := 操作数 | 表达式操作数 := 标识符 | 无符号整数操作数、算符、界符 + 优先级 表达 式求 值2| 表达式的三种标识方法:z Exp = a b +
7、(c d / e) fz前缀式: + a b c / d e fz中缀式: a b + c d / e fz后缀式: a b c d e / f +中缀式丢失了括弧信息，致使运算的次 序不确定。后缀 式的 运算|后缀式的运算规则为:运算符在式中出现的顺序恰为 表达式 的运算顺序;每个运算符和在它之前出现，且紧靠 它的两个操作数构成一个最小表达式（算 子）。例：31 * ( 5 22 ) + 7031 5 22 - * 70 + -22531*22-1731后缀 表达 式的 求值|使用一个存放算子（运算分 量）的栈。|求值过程顺序扫描后缀表达 式，每次遇到算子便将它推 入栈中；|遇到运算符时，就
8、从栈中弹 出两个整数(算子)进行计算 ，而后再把结果推入栈中。|到扫描结束时，留在栈顶的 整数就是所求表达式的值。4 12 3+ 3 5 * / -/by 00720106 顾森逐个字符扫描空格分隔后缀表达式并求值 例： 12 3* 23 14 - +逐个字符扫描空格分隔后缀表达式并求值 例： 12 3* 23 14 - +表达式结尾几个 问题|为什么要先乘除后加减?|为什么说一个合法的前缀或后缀 表达式的运算顺序一定是唯一确 定的?|中缀如何转前后缀？中缀 式求 后缀 式的 规则1) 设立操作符栈2)设表达式的结束符为“#”, 设运算符栈的栈底为“#”；3)若当前字符串是个操作数 则直接发送
9、给后缀式。否则：若当前运算符的优先数高于栈顶运算符，则进栈；否则：退出栈顶运算符发送给后缀式； goto step3; 4) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。相遇则自动取消。3 * ( 7 + 3 * 6 / 2 5 ) #栈顶栈外栈顶 栈顶元素push();否则pop();# 优先级最低。push();pop();中缀 式转 成后 缀式2 1+运算 符优 先关 系表优先 关系 矩阵int presdence ( int op1, int op2) int precede77=1,1,0,0,0,1,1, 1,1,0,0,0,1,1, 1,1
10、,1,1,0,1,1, 1,1,1,1,0,1,1, 0,0,0,0,0,3,2, 2,2,2,2,2,2,2, 0,0,0,0,0,2,4;return precedeop1op2; - （ + #341* 6 ) / 3 #operator stack operand stackexpression?push(data); Push(oper); getResult();checkIn (oper);中缀表达式的计算栈的 应用 迷宫 老鼠问题 分析|只能看到眼前的东西|面临多种选择解决 方案|前进，尽可能前进|汲取教训，不犯重复的错误|具体：z依次探查所有可能的没有被探查 过的方向z对探查
11、过的位置进行标记z记录走过的路，以便回头数据 结构 设计|地图数组int mapij;（0-通，1 -不通）|过往路径记录（栈）|方向：1-2-3-4： ， , 算法 设计|走一步，记一步。|方向试探|前进 push (current)|无法前进 current = pop ( )求解迷宫中一条路径的方法：从入口开始，对每个当前位置沿（E,S,W,N)四个方向 逐一进行试探，当选定一个可通行的方向后，把当前所在 位置及所选的方向记录下来，然后从下一个位置开始继续 探索；若在当前位置探索不到可通行的方向，则沿原路一 步一步退回来，每后退一步，接着在该点试尚未试过的一 个方向。如此重复直到到达出口。 用一个栈记录走过的位置，栈中每个元素包括三项，分别 记录当前位置的行坐标、列坐标以及在该位置上所选的方 向（即directon数组的下标值）。 在某一位置（i, j)进行试探:N (i-1,j) w (i,j-1) (i, j) E (i,j+1) S (i+1,j) drection42令k取0,1,2,3之一，则试探位置为：g = i + directionk0; h = j + directionk1;作业|网站下载环境|大作业！
