数据结构第二章答案.ppt

《数据结构第二章答案.ppt》由会员分享，可在线阅读，更多相关《数据结构第二章答案.ppt（73页珍藏版）》请在三一办公上搜索。

1、第三章 栈和队列,栈和队列是两种重要的线性结构。,从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作。队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。,线性表 栈 队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(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=5s=5*fact(4),第二层调用n=4s=4*fact(3),第三层调用n=3s=3*fact(2),第四层调用n=2s=2*fact(1),第五层调用n=1s=1,每一次递归调用并未立即得到结果，而是进一步向

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

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,栈的类型定义,InitStack(&S),DestroyStack(&S),ClearStack(&S),StackEmpty(s),StackLength(S),GetTop(S,&e),Push(&S,e),Pop(&S,&e),StackTravers(S,visit()

6、,栈的基本操作,InitStack(&S),DestroyStack(&S),操作结果：构造一个空栈 S。,初始条件：栈 S 已存在。操作结果：栈 S 被销毁。,StackLength(S),StackEmpty(S),初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。,初始条件：栈 S 已存在。操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。,GetTop(S,&e),ClearStack(&S),a1,a2,an,初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。,初始条件：栈 S 已存在。操作结果：将 S 清为空栈。,Push(&S

7、,e),a1,a2,an,e,初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。,Pop(&S,&e),a1,a2,an,an-1,初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返 回其值。,StackTravers(S,visit(),初始条件：栈 S 已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据 元素调用visit()。若visit()失败，则 操作失效。,例一、数制转换,例二、括号匹配的检验,例三、表达式求值,栈的应用举例,例一、数制转换,十进制数N和其他d进制数的转换算法基于以下原理：N=(N div d)d+N mod d,例如：

8、,计算顺序,输出顺序,（1348)10=(2504)8，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,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);/conversion,则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格

9、式。,例二、括号匹配的检验,分析可能出现的不匹配的情况:,例如：考虑下列括号序列：()1 2 3 4 5 6 7 8,直到结束，也没有到来所“期待”的括弧。,到来的右括弧并非是所“期待”的；,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空，若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,算法的设计思想：,Status matching(string exp)m=Length(exp);i=0;state=1;while(im,例三、表达式求值(算符优

10、先算法),表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。,算术四则运算的规则为：（1）先乘除、后加减；（2）同级运算时先左后右；（3）先括号内，后括号外。,表达式:=操作数+运算符+操作数 操作数:=简单变量|表达式 简单变量:=标识符|无符号整数,限于二元(双目)运算符的表达式定义:,为实现算符优先算法，设置两个栈：,(1)操作数栈（OPRD）：存放处理表达式过程中的操 作数。,(2)运算符栈（OPTR）：存放处理表达式过程中的运 算符。,假定表达式语法正确，且以“#”结束。,表达式求值的算符优先算法描述如下：,1.初始化操作数栈和运算符栈，置表达式起

11、始符“#”为运算符栈的栈底元素；2.从左到右依次读出表达式中的各个元素(操作数或运算符)，每读出一个元素后，根据运算规则作如下的处理：(1)如果是操作数，则将其压入操作数栈，并依次读下一个元素。(2)如果是运算符，则和运算符栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即运算符栈的栈顶运算符和当前读入的元素均为“#”）。最后的表达式的计算结果在操作数栈的栈顶位置。,算法见教材 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,

12、*,*,3,3,#,*,3,4,=12,12,+,12,5,=17,17,1)若为“”，则从操作数栈连续退出两个操作数，从运 算符栈中退出一个运算符，然后作相应的运算，并 将运算结果压入操作数栈。此时读出的运算符下次 重新考虑（即不读入下一个元素）。,运算符栈栈顶运算符的优先权?当前运算符的优先权,(运算符间的优先关系请看教材P.53),3.1.2栈类型的实现,顺序栈,链栈,#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct ElemType*base;ElemType*top;int stacksize;S

13、qStack;,类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。,/-栈的顺序存储表示-,/构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;,Status InitStack(SqStack&S),if(S.top-S.base=S.stacksize)/栈满，追加存储空间 S.base=(ElemType*)realloc(S.b

14、ase,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败 S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;,e,Status Push(SqStack&S,ElemType e),/若栈不空，则删除S的栈顶元素，/用e返回其值，并返回OK；/否则返回ERROR if(S.top=S.base)return ERROR;e=*-S.top;return OK;,Status Pop(SqSt

15、ack&S,ElemType&e),栈顶指针top,链栈,3.2 队列,队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。根据队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO）的原则组织数据的，因此，队列也被称为“先进先出”表。,队列的概念:,队列的示意图：,入队,出队,a1,a2,a3

16、,ai,an,front,rear,队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业作输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。,队列的应用,队列提要,3.2.1 队列的类型定义,3.2.2 队列类型的实现,ADT Queue 数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头，an 端为队列尾,基本操作

17、：,ADT Queue,3.2.1 队列的类型定义,InitQueue(&Q),DestroyQueue(&Q),QueueEmpty(Q),QueueLength(Q),GetHead(Q,&e),ClearQueue(&Q),DeQueue(&Q,&e),EnQueue(&Q,e),QueueTravers(Q,visit(),队列的基本操作：,InitQueue(&Q),DestroyQueue(&Q),操作结果：构造一个空队列Q。,初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。,QueueEmpty(Q),QueueLength(Q),初始条件：队列Q已存在。操作结果：返回

18、Q的元素个数，即队列的长度。,初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。,GetHead(Q,&e),a1,a2,an,初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。,ClearQueue(&Q),初始条件：队列Q已存在。操作结果：将Q清为空队列。,EnQueue(&Q,e),a1,a2,an,e,初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。,DeQueue(&Q,&e),a2,an,a1,初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。,QueueTravers(Q,visit(),初始条件：Q 已存

19、在且非空。操作结果：从队头到队尾依次对Q的每个数据元素 调用visit()。若visit()失败，则操作失效。,链队列链式映象,循环队列顺序映象,3.2.2 队列类型的实现,typedef struct QNode/结点类型 ElemType data;struct QNode*next;QNode,*QueuePtr;,链队列链式映象,typedef struct/链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,空队列:,/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNo

20、de);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;,Status InitQueue(LinkQueue&Q),Q.front,Q.rear,/插入元素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;,Status EnQueue(LinkQueue&Q,ElemType e),Q.front,Q.rear,

21、e,/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR if(Q.front=Q.rear)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;,Status DeQueue(LinkQueue&Q,ElemType&e),Q.front,Q.rear,队列的顺序映象,队列的顺序存储结构可以简称为顺序队列，也就是利用一组地址连续的存储单元依次存放队列中的数据元素。我们利用C语言的一维数组来作为队列的顺序存储空间

22、，另外再设立两个指示器：front和rear分别指示队头元素和队尾元素的位置。约定：初始化队列时，令front=rear=0，当插入新的数据元素时，队尾指示器rear加1，而当队头元素出队列时，队头指示器front加1。,顺序队列的概念:,例如:,由此，在非空队列中，头指示器front总是指向队列中队头元素的位置，而尾指示器rear总是指向队尾元素的后一个位置。,从上例可以看出：队列是逐渐向后移动的，当队尾元素已放到空间末尾时，若要插入元素就会出现“溢出”。但此时，并不一定空间真正放满，我们把这种队列的存储空间并没有满，但却发生了溢出的现象，称为假溢出。,解决这个问题有两种可行的方法：,（1）

23、采用平移元素的方法。当发生假溢出时，就把整个队列的元素平移到存储区的首部，然后再插入新元素。这种方法需移动大量的元素，因而效率是很低的。（2）将顺序队列的存储区假想为一个环状的空间，如图所示。我们可假想Q.base0接在Q.baseMAXQSIZE-1的后面。当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队头之前，但逻辑上队头仍然在前。入队和出队仍按“先进先出”的原则进行，这就是循环队列。很显然，方法二不需要移动元素，操作效率高，空间的利用率也很高。,循环队列示意：,在循环队列中，每插入一个新元素时，就把队尾指针沿顺时针方向移动一个位置。即：Q.rear+;if(Q.re

24、ar=MAXQSIZE)Q.rear=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存在二义性,为了解决这个

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

26、队列Q Q.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;,Status InitQueue(SqQueue&Q),/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;,Status EnQueue(SqQueue&Q,ElemType e),/

27、若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERROR if(Q.front=Q.rear)return 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.递归和栈之间存在着很强的联系。递归算法的

28、实现通常是通过设立一个“递归工作栈”来完成的。借助栈也可以将一个递归算法改写为非递归算法。,栈,1.队列操作的定义赋予了队列先进先出(FIFO)的操作特点。2.队列的插入和删除操作需要高效率地访问队列的两端。因此，链队列用一个带有头指针和尾指针的线性链表或用一个循环链表来实现。3.队列的顺序存储容易向右漂移。这会使队列出现假溢出现象。一种高效率的解决方案是使用循环数组（称循环队列）。4.如果用循环数组来实现队列，必须能够区分队列满和队列空的情况。通过计队列中元素的个数、使用一个isfull标志、或者留出一个空的数组单元可以区分。,队列,1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4.理解递归算法执行过程中须用栈来实现。,本章学习要点,作业,栈:(P.22)3.4 3.15,作业,队列:(P.23)3.12 3.13 3.28,