数据结构第二章答案.ppt

1、第三章 栈和队列,栈和队列是两种重要的线性结构。,从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。 栈只允许在表的一端进行插入或删除操作。 队列只允许在表的一端进行插入操作、而在另一端进行删除操作。 因而，栈和队列也可以被称作为操作受限的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i, x) Delete(S, n, x) Delete(Q, 1, x) 1in,栈和队列的插入、删除操作与线性表的插入、删除操作的比较：,3.1 栈,栈（stack）是一种只允许在一

2、端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。 根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。,栈的示意图：,若输入序列是1,2,3， 则可能的输出序列有 哪些？,1,3,2,1,2,3,2,1,3,3,2,1,2,3,1,栈的应用,在各种程序设计语言

3、中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自身，即递归。,相应的算法： float fact(int n) if (n=0|n=1) s=1; else s=n*fact(n-1); return s; ,下面以求阶乘的递归方法为例，来分析计算机系统是如何处理这种递归调用关系的。 求n！的递推公式：,若求5!，递归调用执行过程：,主函数 mani() printf(“fact(5)”),第一层调用 n=5 s=5*fact(4),第二层调用 n=4 s=4*fact(3),第三层调用 n=3 s=3*fact(2),第四层调用 n=2 s=

4、2*fact(1),第五层调用 n=1 s=1,每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact才有结果为1，然后再一一返回计算，最终得到结果。,计算机系统处理上述过程时，其关键是要正确处理执行过程中的递归调用层次和返回路径，也就是要记住每一次递归调用时的返回地址。在系统中用一个线性表动态记忆调用过程中的路径，其处理原则为：,（1）在开始执行程序前，建立一个线性表，其初始状态为空。 （2）当发生调用（递归）时，将当前调用的返回点地址插入到线性表的末尾； （3）当调用（递归）返回时，其返回地址从线性表的末尾取出。,根据以上的原则，可以给出线性表中的元素

5、变化状态如下图所示（以递归调用时n值的变化为例）：,4,5,4,5,3,4,5,3,2,4,5,3,2,1,该线性表就是栈,3.1.1 栈的类型定义,3.1.3 栈的应用举例,3.1.2 栈类型的实现,栈提要,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,3.1.1 栈的类型定义,InitStack( scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (

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

7、“左括弧出栈”， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,算法的设计思想：,Status matching(string exp) m= Length(exp) ; i=0; state = 1; while (im ,例三、 表达式求值(算符优先算法),表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。,算术四则运算的规则为： （1）先乘除、后加减； （2）同级运算时先左后右； （3）先括号内，后括号外。,表达式 := 操作数 + 运算符 + 操作数 操作数 := 简单变量 | 表达式 简单变量

8、 : = 标识符 | 无符号整数,限于二元(双目)运算符的表达式定义:,为实现算符优先算法，设置两个栈：,(1)操作数栈（OPRD）：存放处理表达式过程中的操 作数。,(2)运算符栈（OPTR）：存放处理表达式过程中的运 算符。,假定表达式语法正确，且以“#”结束。,表达式求值的算符优先算法描述如下：,1.初始化操作数栈和运算符栈，置表达式起始符“#”为运算符栈的栈底元素； 2.从左到右依次读出表达式中的各个元素(操作数或运算符)，每读出一个元素后，根据运算规则作如下的处理： (1)如果是操作数，则将其压入操作数栈，并依次读下一个元素。 (2)如果是运算符，则和运算符栈的栈顶运算符比较优先权后

9、作相应操作，直至整个表达式求值完毕（即运算符栈的栈顶运算符和当前读入的元素均为“#”）。最后的表达式的计算结果在操作数栈的栈顶位置。,算法见教材 P.53,算法的计算过程:,以表达式: 5+(6-4/2)*3# 为例,OPRD,OPTR,5,5,#,+,+,(,(,6,6,-,-,4,4,/,/,2,),/,2,4,2,=2,2,-,2,6,=4,4,*,*,3,3,#,*,3,4,=12,12,+,12,5,=17,17,1)若为“”，则从操作数栈连续退出两个操作数，从运 算符栈中退出一个运算符，然后作相应的运算，并 将运算结果压入操作数栈。此时读出的运算符下次 重新考虑（即不读入下一个元素

10、）。,运算符栈栈顶运算符的优先权?当前运算符的优先权,(运算符间的优先关系请看教材P.53),3.1.2栈类型的实现,顺序栈,链栈,#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct ElemType *base; ElemType *top; int stacksize; SqStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,/- 栈的顺序存储表示 -,/ 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(Elem

11、Type); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; ,Status InitStack (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; ,e,Status Push (SqStack e = *-S.top; return OK;

12、 ,Status Pop (SqStack struct QNode *next; QNode, *QueuePtr;,链队列链式映象,typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,空队列:,/ 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK; ,Status InitQue

13、ue (LinkQueue if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; ,Status EnQueue (LinkQueue p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK; ,Status DeQueue (LinkQueue if(Q.rear=MAXQSIZE) Q.re

14、ar=0; 可表示为：Q.rear=(Q.rear+1) % MAXQSIZE; 每删除一个元素时，就把队头指针沿顺时针方向移动一个位置。即： Q.front+; if(Q.front=MAXQSIZE) Q.front=0; 可表示为：Q.front=(Q.front+1) % MAXQSIZE;,但这里，还需要注意两个问题：,下图所示，为循环队列的三种状态，（a）为队列空时，有Q.front=Q.rear；（c）为队列满时，也有Q.front=Q.rear；因此仅凭Q.front=Q.rear不能判定队列是空还是满。,问题一,Q.front=Q.rear存在二义性,为了解决这个问题，可以采

15、用以下方法之一：,2.用一个标志变量isfull： 当isfull=0时为空队列，当isfull=1时队列非空。,1.设置一个队列长度信息。,问题二,不能动态分配空间,设定一个最大队列长度，以后不再改变空间大小。,3.只用MAXQSIZE-1个元素空间，浪费一个元素的空间。,#define MAXQSIZE 100 /最大队列长度 typedef struct ElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素的后一个位置 SqQueue;,循环队列的类型定义

16、,/ 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; ,Status InitQueue (SqQueue /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; ,Status EnQueue (SqQueue 否则返回ERROR if (Q.front = Q.rear) return

17、ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK; ,Status DeQueue (SqQueue &Q, ElemType &e),其它形式的队列:,a1,a2,a3,ai,an,front,rear,a1,a2,a3,ai,an,front,rear,输入受限的双端队列,输出受限的双端队列,双端队列,本章小结,1.栈的操作有后进先出(LIFO)的操作特点。 2.递归和栈之间存在着很强的联系。递归算法的实现通常是通过设立一个“递归工作栈”来完成的。借助栈也可以将一个递归算法改写为非递归算法。,栈,1.队列操作的定义赋予了队列先进先出(FIFO)的操作特点。 2.队列的插入和删除操作需要高效率地访问队列的两端。因此，链队列用一个带有头指针和尾指针的线性链表或用一个循环链表来实现。 3.队列的顺序存储容易向右漂移。这会使队列出现假溢出现象。一种高效率的解决方案是使用循环数组（称循环队列）。