数据结构课件：第3章 栈和队列1栈

1、队列类型的定义和实现第3章 栈和队列栈的类型定义栈的应用举例栈类型的实现3.1 栈的类型定义3.1 栈的类型定义3.1 栈的类型定义栈示意图3.1 栈的类型定义 a1 a2 a3 an栈顶栈底 栈的相关概念3.1 栈的类型定义1.定义与同线性表相同，仍为一对一关系。用顺序栈或链栈存储均可，但以顺序栈更常见只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则。关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。 3.存储结构4.运算规则5.实现方式 2.逻辑结构限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）栈与一般线性表有什么不同3.1 栈的类型定义栈与一般线性表

2、的区别：仅在于运算规则不同。 一般线性表 栈逻辑结构：一对一 逻辑结构：一对一存储结构：顺序表、链表 存储结构：顺序栈、链栈运算规则：随机存取 运算规则：后进先出(LIFO)“进” 压入=PUSH（x)“出” 弹出=POP ( y )栈的相关概念3.1 栈的类型定义栈 是仅在表尾进行插入、删除操作的线性表。表尾(即an端)称为栈顶 Top；表头(即a1端)称为栈底Base例如： 栈 s = (a1, a2, a3, an-1, an) a1称为栈底元素 an称为栈顶元素插入元素到栈顶(即表尾)的操作，称为入栈。从栈顶(即表尾)删除最后一个元素的操作，称为出栈。思考题一个栈的入栈序列是a, b,

3、 c, d, e，则栈的不可能的输出序列是（ ）。3.1 栈的类型定义A） e d c b a B） d e c b a C） d c e a b D） a b c d e栈的抽象数据类型定义3.1 栈的类型定义ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,.,n) 数据关系: R=|ai-1,aiD,i=2,.,n) 约定an端为栈顶，a1端为栈底 基本操作： InitStack( &S ) 操作结果：构造空栈S DestroyStack( &S ) 初始条件：栈S已存在 操作结果：销毁栈S ClearStack( &S ) 初始条件：栈S已存在 操作结果：将S置为

4、空栈 StackEmpty( S ) 初始条件：栈S已存在 操作结果：判别栈S是否为空栈 StackLength( S ) 初始条件：栈S已存在 操作结果：返回栈S中元素个数(栈长) GetTop( S,&e ) 初始条件：栈S已存在且非空 操作结果：用e返回S的栈顶元素 Push( &S, e ) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 Pop( &S, &e ) 初始条件：栈S已存在 操作结果：删除S的栈顶元素，用e返回值 ADT Stack栈的物理存储栈的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，栈的存储方式也分为两种，即顺序栈和链栈。 3.2 栈的表示和

5、实现顺序栈的定义3.2 栈的表示和实现#define STACK_INIT_SIZE 100; / 存储空间初始分配量#define STACKINCREMENT 10; / 存储空间分配增量typedef struct SElemType *base; / base的初值为NULL，表明栈结构不存在 SElemType *top; / 栈顶指针，初值指向栈底， / 即top=base作为栈空的标记 int stacksize; / 当前已分存储空间，即指示当前栈 / 可使用的最大容量，以元素为单位 SqStack; 栈顶指针和栈中元素之间的关系3.2 栈的表示和实现1）空栈中的栈顶指针的指向

6、和栈底指针一致2）非空栈中的栈顶指针始终在栈顶元素的下一个位置AABCDABbasetopbasetopbasetopbasetop栈在抽象类型中的几种操作举例3.2 栈的表示和实现例1：构造一个空栈Status InitStack(SqStack &s) /构造一个空栈S s.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemtype); If (!s.base) exit (OVERFLOW); /存储分配失败 s.top=s.base; s.stacksize= STACK_INIT_SIZE; return OK; / In

7、itStack;栈在抽象类型中的几种操作举例3.2 栈的表示和实现例2：取栈顶元素Status GetTop(SqStack s, SElemtype &e) /若栈不空，用e返回S的栈顶元素 if (s.top = = s.base) return ERROR; e = * (s.top - 1); /操作后s.top不变，并将当前栈顶元素赋给e return OK; / GetTop;等同于删除栈顶元素（出栈），区别在于： e = * - - s.top; /操作后stop减，并将当前出栈的元素赋给etopbaseACBDbasetoptop-1e=D栈在抽象类型中的几种操作举例3.2 栈

8、的表示和实现例3：插入新栈顶元素（即入栈）Status Push(SqsTack & s, SElemType e) /插入元素e为新的栈顶元素 if (s.top - s.base = s.stacksize) /栈满，追加存储空间 s.base=(SElemtype *)realloc(s.base, s.stacksize + STACKINCREMENT) * sizeof( Selemtype ); if (!s.base) exit (OVERFLOW); /存储分配失败 s.top = s.base + s.stacksize; s.stacksize += STACKINCRE

9、MENT; * s.top + = e; /*s.top =e; s.top+;栈顶指针始终在栈顶元素的下一个位置 return OK; / Push;acbdtope栈在抽象类型中的几种操作举例3.2 栈的表示和实现例4：删除栈顶元素（即出栈）Status Pop(SqStack & s, SElemType &e) / 若栈不空，删除S的栈顶元素，用e返回其/ 值 ，并返回0K，否则返回ERROR if (s.top = = s.base) return (ERROR); e = * - - s.top; /-s.top; e=*stop;栈顶指针始终在栈顶元素的下一位置 return O

10、K; / Pop;topbaseERRORACBDbasetope=D栈的链式存储结构栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在表头进行操作，故没必要附加头结点，栈顶指针就是链表的头指针。 3.2 栈的表示和实现栈的链式存储结构3.2 栈的表示和实现链栈示意图 an an-1 a1 / Top栈顶栈底链栈的类型说明如下3.2 栈的表示和实现typedef struct StackNode ElemType data struct StackNode *next StackNode; typedef struct StackNode *to

11、p LinkStack;Data next an an-1 a1 / Top链栈的基本操作3.2 栈的表示和实现Void InitStack(LinkStack *s) /初始化链栈 stop=null; Int StackEmpty(LinkStack *s) /判断是否空栈 return stop=null; ElemType Gettop(LinkStack *s) /返回栈顶元素 if(StackEmpty(s) return (ERROR); return stopdata; 链栈插入新栈顶元素（即入栈）3.2 栈的表示和实现Status Push(LinkStack *s, Ele

12、mType e) /插入元素e为新的栈顶元素 q=(StackNode*)malloc(sizeof(StackNode); qdata=e; qnext=stop; stop=q; 链栈删除栈顶元素（即出栈）3.2 栈的表示和实现Status Pop( LinkStack *s, ElemType &e) /若栈不空，则删除链栈栈顶元素，用e返回其值 if (StackEmpty(s) return (Error); q=stop; e=qdata; stop=qnext; free(q); return OK; 1.数制转换2.括号匹配的检验3.行编辑程序4.迷宫求解5.表达式求值3.3

13、栈的应用举例数制转换3.3 栈的应用举例十进制数 N 和其它 D 进制数的转换 N = ( N div d )d + N mod d (其中：div 为整除运算，mod 为求余运算）数制转换3.3 栈的应用举例例如：(1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 对应的8进制数 1348 168 4 4 168 21 0 0 21 2 5 5 2 0 2 2数制转换3.3 栈的应用举例void Conversion ( ) / 对于输入的任意一个非负十进制整数，输出等值的八进制数 InitStack(&S); / 构造空栈 scanf (%d,N)

14、; while (N) Push(&S, N % 8); N = N/8; while (!StackEmpty(S) Pop(&S,&e); printf ( %d, e ); / conversion括号匹配的检验3.3 栈的应用举例 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即： 1.（）或（ ）为正确格式； 2.（ ） 为错误格式； 3.（ ）或 ( ) )为错误格式。括号匹配的检验3.3 栈的应用举例考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 ( ( ) 分析可能出现的不匹配的情况（以“(”为例）：到来的右括弧不是所“期待”的,如“”；直到结束，

15、也没有到来右括弧“）”；算法思想3.3 栈的应用举例1)凡出现左括弧，则进栈2)凡出现右括弧，首先检查栈是否空 是：该“右括弧”多余； 否：和栈顶元素比较，若相匹配，则“左括弧 出栈”，否则表明不匹配；3)表达式检验结束时， 若栈空，匹配正确； 否则表明“左括弧”有余。括号匹配的检验3.3 栈的应用举例status matching(string &exp) / 检验表达式中所含括弧是否正确嵌套， int state = 1; while ( i -*/(#=21表达式求值3.3 栈的应用举例+、-、*、/为1时的优先性均低于“(”但高于“)”当1=2时，“#”是表达式的结束符。为了算法简洁，

16、在表达式的最左边也虚设一个“#”构成整个表达式的一对括号“(”=“)”表示括号内的运算已经完成“#”=“#”表示整个表达式求值完毕“)”与“(”、“#”与“)”以及“(”与“#”之间无优先关系，可认为出了现语法错误3.3 栈的应用举例步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#PUSH(OPND,3)2#3 *(7-2)#PUSH(OPTR,*)3#*3 (7-2)#PUSH(OPTR,()4#*(3 7-2)#PUSH(OPND,7)5#*(3 7 -2)#PUSH(OPTR,-)6#*(-3 7 2)#PUSH(OPND,2)7#*(-3 7 2 )#operate(7,-

17、,2)8#*(3 5 )#POP(OPTR)消去一对括号9#*3 5 #operate(3,*,5)10#15 #RETURN(GETTOP(OPND)3.3 栈的应用举例OperandType EvaluateExpression() /设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while(c!=#|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch(Precede

18、(GetTop(OPTR),c) case : /退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; /switch /while return GetTop(OPND);/ EvaluateExpression表达式的三种标识方法3.3 栈的应用举例设 Exp = S1 + OP + S2则称 OP + S1 + S2 为前缀表示法 S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法 例如: Exp = a b + (c d

19、 / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息， 致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式; 5)后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。如何从后缀式求值3.3 栈的应用举例先找运算符，再找操作数例如： a b c d e / f +abd/ec-d

20、/e(c-d/e)f如何从原表达式求得后缀式3.3 栈的应用举例 每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f 从原表达式求得后缀式的规律为3.3 栈的应用举例1) 设立操作数栈；2) 设表达式的结束符为“#”，预设运算符栈的栈底为“#”3) 若当前字符是操作数，则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离

21、作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为3.3 栈的应用举例void transform(char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree从原表达式求得后缀式的规律为3.3 栈的应用

22、举例switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch3.4 栈与递归的实现 当求解一个问题时，是通过求解与它同样解法的子问题而得到的，这就是递归。 或理解为子程序或函数反复的调用自己，并传入

23、不同的变量来执行的一种程序设计技巧。 递归是程序设计及解题的一种有力的、重要的工具，帮助程序设计者解决复杂问题，并精简程序结构。例：设计一个乘法器，可以计算出两个数相乘的乘积。但是此时计算机不能提供乘法运算（仅知道任何数乘 1，其值不变），则唯一可以使用的运算方式就是加法运算。3.4 栈与递归的实现 11 3是 11 连加 3 次 (11 3) = 11 + （11 2） = 11 + （11 + （11 1）) = 11 + （11 + 11） = 11 + 22 = 33使用递归的一个重要问题一个递归的求解问题必然包含有终止递归的条件，当满足一定条件时就终止向下递归，从而使问题得以解决。3

24、.4 栈与递归的实现使用递归的一个重要问题解决递归问题的算法称递归算法，在递归算法中需要根据递归条件直接或间接地调用算法本身，当满足某种条件时结束递归调用。当然对于一些简单的递归问题，很容易把它转换为循环问题解决，从而使编写出的算法更为有效。3.4 栈与递归的实现实现递归3.4 栈与递归的实现将所有的实参、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：实现递归3.4 栈与递归的实现保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制

25、转移到调用函数。 从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是3.4 栈与递归的实现此时的内存管理实行“栈式管理”后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的数据区函数a的数据区函数b的数据区实现递归3.4 栈与递归的实现递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。 递归函数执行的过程可视为同一函数进行嵌套调用，例如：例：采用递归算法求解

26、正整数n的阶乘(n!)3.4 栈与递归的实现用C语言编写出求解n!的递归函数为： long f (int n) if （n = = 0） return 1; else return n * f（n 1）; 进行f (4)调用的系统栈的变化状态3.4 栈与递归的实现4r13r24r12r33r24r10r41r42r33r24r11r42r33r24r1进行f (4)调用的系统栈的变化状态3.4 栈与递归的实现4r13r24r12r33r24r11r42r33r24r1例：最大公因子问题数学上利用辗转相除法解决。同时此种方法也称为欧几理德定理，其定义为：3.4 栈与递归的实现GCD(M，N) =

27、GCD（N，M % N） （N0）M （N=0）写出求解最大公因子的递归函数为3.4 栈与递归的实现long GCD( int M，int N ) / 前提条件：MN if （N = = 0） /递归结束条件 return M ； else return GCD( N，M % N )； 汉诺( hanoi )塔问题汉诺塔问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小

28、的上面。3.4 栈与递归的实现汉诺( hanoi )塔问题假设有三个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1、2、n的圆盘。现要求将X轴上的n个圆盘移到塔座Z上并仍按同样的顺序叠排，圆盘移动时必须遵循下列规则： 1）每次只能移动一个圆盘； 2）圆盘可以插在X、Y、Z的任一塔座上； 3）任何时刻都不能将一个较大的圆盘压在较 小的圆盘上。3.4 栈与递归的实现3.4 栈与递归的实现void hanoi (int n, char x, char y, char z)/ 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助

29、塔座。 if (n=1) move(x, 1, z); / 将编号为的圆盘从x移到z else hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 move(x, n, z); / 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 1234567893.4 栈与递归的实现递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc主函数： 执行调用语句hanoi (3,a,b,c) ，入栈。层1： 执行1,2,4,5语句，产生向下调用，进层2

30、。3.4 栈与递归的实现层2 入栈，记录层1的返回地址6等信息； 执行2层的1,2,4,5语句，执行到语句再向下调用，进入层3递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b3.4 栈与递归的实现递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c层3 入栈，记录层2的返回地址6等信息； 执行1,2,3,9语句，过程执行完。3.4 栈与递归的实现层2 第3层调用结束，出栈，返回第2层； 从第2层的断点语句6执行； 执行到语句7，又开始向下递归调用到第3层。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c3.4 栈与递归的实现层3 入栈,记录层2的返回地址8等信息； 执行语句1,2,3,9,过程执行完。 出栈，返回第2层断点语句8。递归工作栈状态(返址,n值,x值,y值,z值)塔与圆盘的状态0, 3, a, b, cabc6, 2, a, c, b8, 1, c, a, b3.4 栈与递归的实现层 从第3层返回后，从断点开始执行，执行语句8,9，过程执行完，出栈，返回第1层。层 从第2层返回后，从断点