《数据结构》(C语言版)第三章_栈和队列

1、1,通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,2,第三章 栈和队列,3.1 栈,3.2 栈的应用举例,3.4 队列,3.3 栈与递归的实现,3,学习提要： 1.掌握栈和队列这两种抽象数据类型的特点， 并能在相应的应用问题中正确选用它们。 2.熟练掌握栈类型的两种实现方法，特别应 注意栈满和栈空的条件以及它们的描述方法。 3.

2、熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。 4.理解递归算法执行过程中栈的状态变化过程。 重难点内容： 顺序栈的相关操作、循环队列的判空判满,4,3.1 栈（stack）,3.1.1 栈的类型定义,3.1.2 栈的表示和实现,5,栈的定义：限定仅在表尾进行插入或删除操作的线性表。不含元素的空表称空栈。,特点：后进先出（LIFO）,3.1.1 栈的类型定义,表尾栈顶 表头栈底,6,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1

3、端为栈底。,基本操作：, ADT Stack,栈的抽象数据类型定义：,7,InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; SqStack;,9,实现：一维数组sM,进栈Push( top=p,q=top ; top=top-next,16,3.2 栈的应用,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.3 行编辑程序问题,3.2.4 迷宫求解,3.2.5 表达式求值,17,3.2.1 数制转换,十进制N和其

4、他d进制数的转换原理: N=( N div d )*d + N mod d 其中：div为整除运算， mod为求余运算,18,例如： (1348)10=(2504)8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,19,void conversion( ) /对于输入的任意一个非负十进制整数， /打印输出与其等值的八进制数 initstack ( S ); scanf (“%d”,N); while ( N ) push (S，N%8); N = N / 8; while ( ! Stackempty(s) ) pop

5、( S,e ); printf ( “%d”, e ); /conversion,20,3.3.2 括号匹配的检验,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （）)均为不正确的格式。,21,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”；,直到结束，也没有到来所“期待”的括弧。,22,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否

6、则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,23,3.2.3 行编辑程序问题,如何实现？,“每接受一个字符即存入存储器” ?,不恰当!,合理的作法是：,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。,24,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,25,while (ch != EO

7、F / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的 数据区；,26,3.2.4 迷宫求解,通常用的是“穷举求解”的方法。,27,求迷宫路径算法的基本思想是：,若当前位置“可通”，则纳入路径， 继续前进;,若当前位置“不可通”，则后退，换方向继续探索;,若四周“均无通路”，则将当前位置从路径中删除出去。,28,设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算

8、法结束； 否则切换当前位置的东邻方块为 新的当前位置； 否则 while (栈不空）；,求迷宫中一条从入口到出口的路径的算法：, ,29,若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；,若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ,若栈空，则表明迷宫没有通路。,30,typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中 的 “坐标位置” int di

9、; / 从此通道块走向下一 通道块的“方向” SElemType; / 栈的元素类型,31,Status MazePath ( MazeType maze, PosType start, PosType end ) InitStack(S); curpos = start; / 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当前位置可以通过，即是未曾走到过的通道块 else while ( !StackEmpty(S) ); return (FALSE); / MazePath,32,FootPrint (curpos)

10、; e = ( curstep, curpos, 1 ); Push (S,e); / 加入路径 if ( curpos = end ) return (TRUE); / 到达终点 curpos = NextPos ( curpos, 1 ); / 下一位置是当前位置的东邻 curstep+;,33,else / 当前位置不能通过 if (!StackEmpty(S) Pop (S,e); while (e.di=4 / 设定当前位置是该新方向上的相邻块 / if / if / else,34,限于二元运算符的表达式定义: Exp = S1 OP S2 操作数 : 变量、常量、表达式 运算符

11、: 算术运算符、关系运算符、 逻辑运算符 界限符：括号、结束符,3.2.5 表达式求值,35,表达式求值的算法： 算符优先法根据运算优先关系的规定来实现对表达式的编译或解释执行。,36,例：3 * ( 7 2 ),3,*,(,7,2,2,7,5,*,5,3,15,37,例：3 * ( 7 2 ),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

12、 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, ) 6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 ) 8 # * ( 3 5 ) # POP( OPTR ) 9 # * 3 5 # operate( 3, *, 5 ) 10 # 15 # return GetTop( OPND ),38,OperandType EvaluateExpression( ) / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, #);

13、 initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是运算符则进栈 else / while return GetTop(OPND); / EvaluateExpression, ,39,switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operat

14、e(a, theta, b); break; / switch,40,3.3 栈与递归的实现,41,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事: (1)将所有的实在参数、返回地址等信息传递给被调用函数保存; (2)为被调用函数的局部变量分配存储区; (3)将控制转移到被调用函数的入口。,42,从被调用函数返回调用函数之前，应该完成: (1)保存被调函数的计算结果; (2)释放被调函数的数据区; (3)依照被调函数保存的返回地址将控制转移到调用函数。,43,多个函数嵌套调用的规则是：后调用先返回 此时的内存管理实行“栈式管理”。,递归过程指向过程中占用的数据区

15、， 称之为递归工作栈 每一层的递归参数合成一个记录， 称之为递归工作记录 栈顶记录指示当前层的执行情况， 称之为当前活动记录 栈顶指针， 称之为当前环境指针,44,例：递归的执行情况分析,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); ,运行结果： 1， 2，2， 3，3，3，,45,递归调用执行情况如下：,例：n阶Hanoi问题。 问题描述：有X,Y,Z三个塔座，X上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔，编号1,2,3n。要求将n个圆

16、盘从X移到Z，叠放顺序不变，移动过程中遵循下列原则： (1)每次只能移一个圆盘; (2)圆盘可在三个塔座上任意移动; (3)任何时刻都不能将大盘压到小盘上;,解决方法： n=1时，直接把圆盘从X移到Z； n1时，先把上面n-1个圆盘从X移到Y，然后将n号盘从X移到Z，再将n-1个盘从Y移到Z。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅

17、助塔座。 1 2 if (n=1) 3 move(x, 1, z); / 将编号为的圆盘从x移到z 4 else 5 hanoi(n-1, x, z, y); / 将x上编号为至n-1的圆 / 盘移到y, z作辅助塔 6 move(x, n, z); / 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); / 将y上编号为至n-1的圆 /盘移到z, x作辅助塔 8 9 ,执行情况： 递归工作栈保存内容：形参n, x, y, z和返回地址（返回地址用语句行号表示）。 工作记录结构：,void hanoi(int n,char x,char y,char z) 1 2 if(n=

18、1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 han

19、oi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,void hanoi(int n,char x,char y,char z) 1 2 if(n=1) 3 move(x,1,z); 4 else 5 hanoi(n-1,x,z,y); 6 move(x, n, z); 7 hanoi(n-1,y,x,z); 8 9 ,54,3.4 队列,3.4.1 队列的类型定义,3.4.2 链队列,3.4.3 循环队列,55,队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。,队列特点：先进先出(FIFO),3.4.1 队列的类型

20、定义,队尾(rear)允许插入的一端 队头(front)允许删除的一端,56,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：,队列的抽象数据类型定义：, ADT Queue,57,队列的基本操作：,InitQueue( struct QNode *next ; QNode, *QueuePtr;,typedef struct /链队列类型 QueuePtr *front ; /队头指针 QueuePtr *rear ; /队尾指针

21、 LinkQueue;,3.4.2 链队列队列的链式表示和实现,59,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,60,Status InitQueue (LinkQueue ,61,Status EnQueue (LinkQueue ,62,Status DeQueue (LinkQueue ,63,3.4.3 循环队列队列的顺序表示和实现,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,64,实现：用一维数组实现baseM,J1,J2,J3,存在问题： 当front=0,rear=M时，再有元素入队发生溢出真溢出 当front0,rear=M时，再有元素入队发生溢出假溢出,65,解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让base0接在baseM-1 之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： baserear = e; rear = (rear+1)%M;