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

1、第三章 栈和队列3.1 栈3.2 栈的应用举例3.4 队列3.3 栈与递归的实现1提要：1.掌握栈和队列的特点，并能在相应的应用问 题中正确选用它们。2.熟练掌握栈类型的两种实现方法，即两种存 储结构表示时的基本操作实现算法，特别应 注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实现 算法，特别注意队满和队空的描述方法。4.熟练掌握递归算法的实现(栈的应用)重难点内容： 顺序栈的相关操作、循环队列的判空判满(假溢出)和递归算法2 栈和队列是限定插入和删除只能在表的“端点”进行的线性表。其基本操作是线性表操作的子集. 线性表 栈 队列Insert(L, i, x)

2、 Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 入栈 入队 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 出栈 出队栈和队列是两种常用和应用最广泛的数据结构33.1 栈（stack）3.1.1 栈的类型定义3.1.2 栈的表示和实现4栈的定义和特点定义：限定仅在表尾进行插入(进栈)或删除( 出栈)操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈。ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)特点：先进后出（FILO）或后进先出（LIFO）3.1.1 栈的类型定义5基于特点给出以下问题: ? 若进栈序

3、列为ABCDEF,能否得到 DCEFAB和ACEDBF出栈序列. ? 以0和1分别表示进栈和出栈,栈的 初态和终态均为栈空,进出栈操作 序列0101和0110是否合法.6 ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack 栈的类型定义7InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e

4、)Pop(&S, &e)StackTravers(S, visit()8 顺序栈3.1.2 栈的表示和实现 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;9实现：一维数组sqstack s 表示栈s.top123450进栈A栈满BCDEF栈空条件，s.top=s.base, 此时出栈，则下溢（under

5、flow)栈满条件 S.top - S.base = S.stacksize 此时入栈，则上溢（overflow)s.tops.tops.tops.tops.top123450空栈s.tops.bases.bases.top出栈s.tops.top栈空s.base栈底指针s.base,始终指向栈底位置；栈顶指针s.top,其初值指向栈底，始终在栈顶元素的下一个位置123450ABs.top10 Status InitStack (SqStack &S)/ 构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); i

6、f (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;11 Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLO

7、W); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; 12Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;130M-1栈1底栈1顶栈2底栈2顶在一个连续存储单元空间中同时使用两个栈14链栈 栈的链式存储结构。栈顶指针就是链表的

8、头指针。栈顶指针a1an注意: 链栈中指针的方向an-1注意: 链栈中指针的方向注意：链栈中的指针方向15 入栈操作 出栈操作 .栈底toptopxptop .栈底topqp-next=top ; top=p q=top ; top=top-next 163.2 栈的应用3.2.1 数制转换3.2.2 括号匹配的检验3.2.3 行编辑程序问题3.2.4 迷宫求解3.2.5 表达式求值173.2.1 数制转换十进制N和其他d进制数的转换原理: N=( N div d )*d + N mod d 其中：div为整除运算，mod为求余运算18toptop4top40top405 例如： (1348)

9、10=(2504)8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序top405219 void conversion( ) initstack(S); scanf (“%d”,N); while(N) push(S，N%8); N=N/8; while(! Stackempty(s) pop(S,e); printf(“%d”,e); /conversion203.3.2 括号匹配的检验 则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。假设在表达式中（）或（ ）等为正确的格式，（ ）或（

10、）或 （）)均为不正确的格式。21分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8直到结束，也没有到来所“期待”的括弧。22算法的设计思想：1）对表达式从左至右扫描凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余，(失败) 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配，(失败) 。3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余，(失败) 。233.2.3 行编辑程序问题如何实现？“每接受一个字符即存入存储器” ? 不恰当!

11、合理的作法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。24假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putchar(*s+);25 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = get

12、char(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = getchar();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；263.2.4 迷宫求解通常用的是“穷举求解”的方法27求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径， 继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。28 限于二元运算符的表达式定义: Exp = S1 OP S2 操作数 : 变量、常量、表达式 运算符 : 算术运算符、关系运

13、算符、 逻辑运算符 界限符：括号、结束符3.2.5 表达式求值29一种表达式求值的算法思想(算符优先法): 将运算符和界限符统称为算符,用OPTR栈存储算符,用OPND栈存储运算结果和操作数.设OPTR栈顶元素为1,算法实现步骤为: 1.OPND栈置空,OPTR栈底元素置为#”.表达式尾 置为#”. 2.依此读入表达式字符,若是操作数一律进OPND栈, 若是算符则设为2,参照P53表3.1进行以下比较: 若2 1,则2 进OPTR栈,继续2 若2 1则OPTR栈顶出栈(括弧配对),继续2若2 1则OPTR栈顶出栈作为运算符(OP),同时OPND栈连续出二个元素作为S2和S1进行 S1 OP S

14、2 运算,结果进OPND栈,继续2.结束条件是 2 =130例：3 * ( 7 2 )OPND栈OPTR栈CCC3*(C7CC2C275C*531531例：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 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND,

15、 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )32OperandType EvaluateExpression() / 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if

16、(!In(c, OP) Push(OPND, c); c = getchar(); / 不是运算符则进栈 else / while return GetTop(OPND); / EvaluateExpression 33switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch34 3.3 栈与递归的实现递归的概念: 一个直接调用自己或通过一系列的调用语句调用

17、自己 的函数,称为递归函数.具有递归特征的问题可分为以下几类: 1. 数学函数本身是递归定义的,如阶乘函数、 Fibonacci 数列和Ackerman 函数等. 2. 有些数据结构本身具有递归特征,如二叉树,广义表 等.对它们的操作可递归的描述(后面可见). 3. 问题本身递归结构不明显,但用递归求解比迭代更 简单.如八皇后,Hanoi塔问题,关键是如何抽象出 递归特征.35栈在递归函数实现中的应用: 如下图,函数调用的过程是先调用后返回,而栈的特 征是先进后出.因此,函数调用过程可用栈来实现.MAINSUB1SUB2SUB3断点1断点2断点3调用调用调用返回返回返回结束36函数调用和返回过

18、程中栈存储内容:调用函数和被调用函数之间的连接和形参与实参 之间的内容传递是通过栈来完成. 当一个函数运行期间调用另一函数时,在运行 被调用函数之前完成以下三件事: (1) 将所有的实参和返回地址(断点)入栈,供 实参到形参信息传递和被调用函数运行 完后返回调用函数继续运行. (2) 为被调用函数的局部变量分配存储区 (3) 将控制转移到被调用函数的入口地址当从被调用函数返回之前也完成以下二件事: (1) 保存被调用函数的计算结果,释放数据区. (2) 返回地址(断点)出栈,将控制转移到调用函数注意 : 当前运行的函数的数据区必在栈顶.37例子 汉诺塔算法的实现及递归工作栈的变化 从汉诺塔问题

19、中抽象出递归规律(问题需求和 规则见P55)12nnn-11XYZXYZ(问题的规模为 n)(问题的规模为 n-1,仅供移动的辅助塔发生变化)38求解n阶汉诺塔问题的C函数 void hanoi(int n , char x, char y, char z) 将塔 X 上 1 至 n 个圆盘按规则搬到Z塔上 , Y为辅助塔1 2 if ( n =1 )3 move ( x , 1 , z) ; 将编号为 1 的圆盘从 x 移到 z4 else 5 hanoi ( n-1 , x , z , y) ;将 X 上 1 至 n-1 个圆盘 按规则搬到 Y 塔上 , Z为辅助塔6 move ( x ,

20、 n , z); 将编号为 n的圆盘从 x 移到 z7 hanoi ( n-1 , y , x , z) ;将 y 上 1 至 n-1 个圆盘 按规则搬到 z 塔上 , x 为辅助塔8 9 设n=3,则调用该递归函数为 hanoi(3, a , b, c) . 栈的变化见P57393.4 队列3.4.1 队列的类型定义3.4.2 链队列3.4.3 循环队列40队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)队列特点：先进先出(FIFO)3.4.1 队列的类型定义队尾(rear)允许插入的一端队头(fr

21、ont)允许删除的一端41 ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾基本操作：队列的类型定义 ADT Queue42队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()43typedef struct

22、QNode/ 结点类型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /链队列类型 QueuePtr front ; /队头指针 QueuePtr rear ; /队尾指针 LinkQueue;3.4.2 链队列队列的链式表示和实现44a1anQ.frontQ.rearQ.frontQ.rear空队列45Q.frontQ.rearx入队xQ.frontQ.reary入队xyQ.frontQ.rearx出队xyQ.frontQ.rear空队frontreary出队Q.rear - next=pQ.re

23、ar=pp= Q.front - nextQ.front - next = p - next P 指向待入队或出队的结点注意:若出队的为最后一个结点需做以下操作,避免rear指针丢失:If (Q.rear=p) Q.rear=Q.frant46 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK;47 Status EnQ

24、ueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;48 Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear

25、) 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;493.4.3 循环队列队列的顺序表示和实现 #define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， /指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;?

26、为什么没有说明增量50用一维数组SqQueue Q顺序表示队列123450空队列Q.rear=0 Q.front=0J1J2J3Q.rearQ.rear123450J4,J5,J6入队J4J5J6Q.frontrearQ.rear123450Q.frontJ1,J1,J3入队Q.rear123450J1,J2,J3出队J1J2J3Q.frontQ.frontQ.frontQ.front存在问题：当front=0,rear=Maxqsize时再有元素入队发生溢出为真溢出当front0,rear=Maxqsize时再有元素入队发生溢出为假溢出Q.rear应采用定长分配(为什么)51假溢出的解决方案

27、(循环队列)队首固定，每次出队剩余元素向下移动浪费时间循环队列(设M=MaxQSIZE) 基本思想：把队列设想成环形，让Q.base0接在Q.baseM-1之后,若Q.rear+1=M,则令Q.rear=0;实现：利用“模”运算入队： Q.baserear=x; Q.rear=(Q.rear+1)%M; 出队： x=Q.basefront; Q.front=(Q.front+1)%M; 52012345Q.rearQ.frontJ5J6J7012345Q.rearQ.frontJ4J9J8J4,J5,J6出队J7,J8,J9入队队空：Q.front=Q.rear队满：Q.front=Q.rea

28、r解决方案：1.另外设一个标志位以区别队空、队满2.少用一个元素空间：(以下算法采用) 队空: Q.front=Q.rear 队满: (Q.rear+1)%M=front3.使用一个计数器记录队列中元素的总数J5J6012345Q.rearQ.front初始状态J4队满、队空判定条件53 Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0