算法与数据结构第4章栈与队列.ppt

第四章 栈与队列,对于栈和队列上的插入、删除操作是受某种特殊限制的。因此，栈和队列也称作操作受限的表，或者限制存取点的表。 本章除了讨论栈和队列的概念、抽象数据类型、表示方法和实现算法外，还将给出一些应用的例子。,4.1 栈及其抽象数据类型 4.1.1 基本概念,栈是一种特殊的线性表，它所有的插入和删除都限制在表的同一端进行。 表中允许进行插入、删除操作的一端叫做栈的顶。 表的另一端则叫做栈的底。 当栈中没有元素时，称之为空栈。 栈的插入运算通常称为进栈或入栈， 栈的删除运算通常称为退栈或出栈。,栈又称为后进先出表（Last In First Out表，简称LIFO表）或下推表，如图所示,4.1.2 抽象数据类型,ADT Stack is operations Stack createEmptyStack ( void ) 创建一个空栈。 int isEmptyStack ( Stack st ) 判断栈st是否为空栈。 void push ( Stack st, DataType x ) 往栈st的栈顶插入一个值为x的元素。 void pop ( Stack st ) 从栈st的栈顶删除一个元素。 DataType top ( Stack st ) 求栈顶元素的值。 end ADT Stack,4.2 栈的实现 4.2.1 顺序表示,用顺序的方式表示栈时，栈的类型可定义如下： struct SeqStack /* 顺序栈类型定义 */ int MAXNUM; /* 栈中最大元素个数 */ int t; /* tMAXNUM，指示栈顶位置，而不是元素个数 */ DataType *s; ; typedef struct SeqStack *PSeqStack; /* 顺序栈的指针类型 */,用顺序存储结构表示的栈的动态示意图,由于栈是一个动态结构，而数组是静态结构，因此会出现所谓的溢出问题。 当栈中已经有 MAXNUM个元素时，如果再作进栈运算，则会产生溢出，通常称为上溢（Overflow）； 而对空栈进行出栈运算时也会产生溢出，通常称为下溢（Underflow）。,基本运算的实现,1. 创建一个空栈 PSeqStack createEmptyStack_seq( int m ) 具体实现与算法2.1类似，需要为栈结构申请空间，不同之处是将栈顶变量赋值为-1。请自己给出。,2. 判断栈是否为空栈 int isEmptyStack_seq( PSeqStack pastack ) 当pastack所指的栈为空栈时，则返回1，否则返回0。,3. 进栈运算 void push_seq( PSeqStack pastack, DataType x ) 往pastack所指的栈中插入（或称推入）一个值为的元素。 当栈不满时，先修改栈顶变量，将其值加1，然后把元素x放入栈顶变量所指的位置中。 程序实现,4. 出栈运算 void pop_seq( PSeqStack pastack ) 从pastack所指的栈中删除（或称弹出）一个元素。 当栈不空时，通过将栈顶变量减1达到元素删除的目的。 程序实现,5. 取栈顶元素运算 DataType top_seq( PSeqStack pastack ) 当pastack所指的栈不为空栈时，将栈顶元素取出，而栈本身未发生任何变化。 程序实现,4.2.2 链接表示,栈也可以采用链接方式表示，在链接栈中，每个结点的结构可如下定义： struct Node; /* 单链表结点 */ typedef struct Node *PNode; /* 指向结点的指针类型 */ struct Node /* 单链表结点定义 */ DataType info; PNode link; ;,为了强调栈顶是栈的一个属性，这里对栈增加了一层封装（后面将会看到：经过这样封装使得栈与队列的链表表示在形式上更加一致），引入LinkStack结构的定义。 struct LinkStack /* 链接栈类型定义 */ PNode top; /* 指向栈顶结点 */ ; typedef struct LinkStack *PLinkStack; /* 链接栈类型的指针类型 */,假设plstack是PLinkStack类型的变量，则plstack-top就是栈顶指针，plstack-top-info是栈顶元素，,运算的实现,1.创建空链接栈 PLinkStack createEmptyStack_link(void) 创建一空链接栈，需要申请链接栈结构(struct LinkStack)空间，将其中top置为NULL,返回该结构的地址。 程序实现,2. 判断栈是否为空栈 int isEmptyStack_link( PLinkStack plstack ) 判断plstack所指的栈是否为空栈，当plstack所指的栈为空栈时，则返回1，否则返回0。 程序实现,3. 进栈运算 void push_link( PLinkStack plstack, DataType x ) 往plstack所指的栈中插入（或称压入）一个值为x的元素。首先申请结点空间，然后通过指针修改，将结点插在栈顶。 程序实现,4. 出栈运算 void pop_link( PLinkStack plstack ) 出栈运算，表示从plstack所指的栈中删除（或称弹出）一个元素。当栈不空时，直接修改栈顶指针，删除结点。 程序实现,5. 取栈顶元素 DataType top_link( PLinkStack plstack ) 当plstack所指的栈不空时，取栈顶元素的值，栈保持不变。 程序实现,4.3 栈的应用,4.3.1 栈与递归,本节在引入递归概念的基础上，介绍栈是怎样用来实现递归，以及怎样把一个递归的函数转换成一个等价的非递归的函数。,递归,通常用来说明递归的最简单的例子是阶乘的定义，它可以表示成： 1 若n = 0 n! = n * ( n 1 )! 若n 0 这种用自身的简单情况来定义自己的方式，称为递归定义。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。,int fact( int n ) int res=n; if ( n 1 ) res=res* fact( n 1 ); return res; 函数fact( n )中又调用了函数fact，这种函数自己调用自己的作法称为递归调用。 包含直接还是间接递归调用的函数都称为递归函数。,递归函数的执行过程 假设（主）程序中包含一个k=fact(3)语句，这个语句的执行过程如下页的图所示。 在fact(3)的计算过程中，我们实际不需要生成3个相同的fact程序，只要一个程序在不同的阶段能够处理(3份)不同数据。根据后进先出的原则，只要保证把最后调用的程序使用的空间，保存在一个栈的栈顶就可以了。,递归函数到非递归函数的转换,设有一个程序sub要调用函数rout(x)，sub本身也可能是一个函数，我们称之为调用函数，而称rout为被调函数。调用函数中使用调用语句rout(a)来引起rout函数的执行，这里a称为实参。x称为形参。,一般来说，函数调用的实现可以分解成下列三步来进行： (1) 传送调用信息。 (2) 分配被调函数需要的数据区，并接收传送来的调用信息。 (3) 把控制转移到被调函数的入口。,当被调函数运行结束，需要返回到调用函数时，一般的返回处理也可以分解成下列三步： (1) 传送返回信息。 (2) 释放被调函数的数据区。 (3) 把控制按返回地址转移到调用函数中去。,在非递归调用的情况下，数据区的分配可以在程序运行前进行，一直到整个程序运行结束才释放，这种分配称为静态分配。 在递归调用的情况下，被调函数的局部量不能分配给固定的某些单元，而必须每调用一次就分配一份，当前程序使用的所有的量（包括形参、局部变量和中间工作单元等），都必须是最近一次递归调用时所分配的数据区中的量。即所谓的动态分配。,动态分配通常的处理方法是：在内存中开辟一个存储区域称为运行栈（或简称栈），每次调用时，将动态区指针下推，分配被调函数所需的数据区；在每次返回时，将内存指针上托，释放本次调用所分配的数据区，恢复到上次调用所分配的数据区中；被调函数中变量地址全部采用相对于动态区指针的位移量来表示（称为相对地址）。,根据上述思想，不难给出算法4.9阶乘计算的非递归算法。因为只有一处递归调用，返回地址（locate）和返回值(fact)都容易控制，而且局部量(res)与参数(n)关系十分清楚，所以栈中只要保存一个参数n的值就可以了。这种最简单的递归函数实现过程相当于下面的一个非递归函数。,int nfact( int n ) int res; PSeqStack st; /* 使用顺序存储结构实现的栈 */ st = createEmptyStack_seq( ); while (n0) push_seq(st,n); n = n 1; res = 1; while (! isEmptyStack_seq(st) res = res * top_seq(st); pop_seq(st); free(st); return ( res ); ,4.3.2 迷宫问题,在迷宫中求从入口到出口的所有路径是一个经典的程序设计问题。 迷宫可用图4.5（a）所示的方块来表示，其中每个元素或为通道（以空白方块表示），或为墙（以带阴影的方块表示）。迷宫问题要求的就是：从入口到出口的一个以空白方块构成的(无环)路径。,求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。这类方法统称回溯法,用回溯法求迷宫问题解的过程，可以用一个栈来保存探索的序列。其算法框架如下： mazeFrame( void ) 创建一个（保存探索过程的）空栈； 把入口位置压入栈中; while 栈不空时 取栈顶位置并设置为的当前位置; while 当前位置存在试探可能 取下一个试探位置; if (下一个位置是出口) 打印栈中保存的探索过程然后返回 if(下一个位置是通道) 把下一个位置进栈并且设置为的当前位置; ,数据结构 迷宫可用二维数组mazemn来表示， 数组中元素为0的表示通道，为1的表示墙。 迷宫的入口处为maze11， 出口处为mazem-2n-2， 它们的元素值必为0。 任意时刻在迷宫中的位置可用元素的行下标和列下标(i,j)来表示。,在某一点mazeij时，可能的运动方向有四个。可以建立一个数组direction42 给出相对于位置(i,j)的四个方向上，i与j的增量值。 若在位置(i,j)，要进入E方向的位置（g,h），则可根据由该增量值表来修改(i,j)的坐标， g = i + direction00; h = j + direction01;,栈用顺序存储结构实现，栈中的元素类型DataType说明如下： typedef struct int x,y,d; DataType;,算法的实现 求迷宫中一条路径的算法，可以从入口开始，对每个“当前位置”都从E方向（东方向）试起，若不能通过，则顺时针试S方向、W方向、N方向。 当选定一个可通的方向，即找到“下一个位置”后，要把当前所在的位置纳入到探索路径中，并将当前所在的位置以及所选的方向记录下来，以便往下走不通时可顺原路一步步地退回来，每退一步以后接着试在该点上尚未试过的方向，从“下一个位置”开始继续探索，如此重复直至到达出口。 程序实现： void mazePath(int *maze,int *direction,int x1,int y1,int x2,int y2,int M,int N),4.3.3 表达式计算,为了这里讨论的方便，在不影响问题实质的情况下，我们对表达式做如下简化： (1) 假定所有运算分量都是整数； (2) 所有运算符都是整数的二元操作，且都用一个字符表示。,例如31 (5 - 22) + 70 这类表达式中所有运算符都出现在它的两个运算分量之间，所以称为中缀表达式。 处理系统通常先把表达式转换成另一种等价形式：31 5 22 - 70 +，这种形式称为后缀表达式。 这种表达式里不再需要有括号，每个运算符都出现在它的两个运算分量后面。,中缀表达式到后缀表达式的转换,5 (27 + 3 7) + 22 转化为后缀表达式为： 5 27 3 7 + 22 +,举例：31*(5-22)+70 转换为：31 5 22 - * 70 + 31*(5-22)+70 *(5-22)+70 31 (5-22)+70 * 31 5-22)+70 (* 31 -22)+70 (* 31 5 22)+70 -(* 31 5 )+70 -(* 31 5 22 +70 * 31 5 22 - 70 + 31 5 22 - * + 31 5 22 - * 70 31 5 22 - * 70 +,后缀表达式的求值,后缀表达式的主要优点是可以写出非常简单的求值过程。使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(运算分量)进行计算，而后再把结果推入栈中。这样，到扫描结束时，留在栈顶的整数就是所求表达式的值。,31 5 22 - * 70 + 5 22 - * 70 + 31 22 - * 70 + 5 31 - * 70 + 22 5 31 * 70 + -17 31？ 70 + -527？ + 70 -527 -457？ -457 计算结束,4.4 队列及其抽象数据类型,4.4.1 基本概念 队列是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。 允许进行删除的这一端叫队列的头，允许进行插入的这一 端叫队列的尾。 当队列中没有任何元素时，称为空队列。 队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。,队列也称作先进先出表(First In First Out表，简称FIFO表）,4.4.2 抽象数据类型,ADT Queue is operations Queue createEmptyQueue (void ) 创建一个空队列。 int isEmptyQueue ( Queue qu ) 判队列qu是否为空队列。 void enQueue ( Queue qu, DataType x ) 往队列qu尾部插入一个值为x的元素。 void deQueue ( Queue qu ) 从队列qu头部删除一个元素。 DataType frontQueue ( Queue qu ) 求队列qu头部元素的值。 end ADT Queue,4.5 队列的实现,队列与栈类似，实现时通常采用顺序的表示和链接的表示。,4.5.1 顺序表示,存储结构 为了算法设计上的方便，我们约定：队头指针指出实际队头元素所在的位置，而队尾指针指出实际队尾元素所在位置的下一个位置。,struct SeqQueue /* 顺序队列类型定义 */ int MAXNUM; /* 队列中最大元素个数 */ int f,r; DataType *q; ; typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */,假设paqu是PSeqQueue类型的变量， paqu-f存放即将要被删除的元素的下标， paqu-r存放即将要被插入的元素的下标。 paqu-qpaqu-f表示当前队列头部的元素； paqu-qpaqu-r表示当前队列尾部的（即将要插入的）元素。 初始时paqu-f = paqu-r = 0。 当前队列中元素的个数=paqu-r - paqu-f 当paqu-r = paqu-f时，元素的个数为0，即为空队列。,在顺序表示的队列中，同样由于数组是静态结构，而队列是动态结构，也存在队列溢出问题，即当队列满时，再作进队操作，这种现象称为上溢；而当队空时，作删除操作，这种现象称为下溢。这些现象在运算中都要考虑。,由于队列中经常要执行插入和删除运算，而每运行一次插入或删除，paqu-r或paqu-f就增加1，使得队列中的元素被删除后，其空间就永远使用不到了。 队列的动态变化犹如使整个队列向右移动。 当paqu-r = MAXNUM时，再作插入运算就会产生溢出，而实际上这时队列的前端可能还有许多空的（可用的）位置，因此，这种现象称为假溢出。,解决假溢出通常采用的方法是： 把数组paqu-qMAXNUM从逻辑上看成一个环，这种队列也称为环形队列。 当表中已有MAXNUM 1个结点时，如果还要插入，paqu-r和paqu-f就会重合，而这与空队列的情形相混。 为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM1个结点时就称满，再要插入就发生溢出.,(a) (b) 图4.11 环形队列paqu,队列基本运算的实现,1. 创建一个空队列。 PSeqQueue createEmptyQueue_seq( int m ) 创建一个空队。具体实现与算法2.1类似，需要为队列申请空间，不同之处是需要将对变量f和r均赋值为0。请读者自己给出。,2. 判断是否为空队列 int isEmptyQueue_seq( PSeqQueue paqu ) 判断paqu所指的队列是否为空队列。当paqu-f = paqu-r时，返回1，否则返回0。,3. 进队运算 void enQueue_seq( PSeqQueue paqu, DataType x ) 入队运算，当队列不满时，将元素x插入paqu所指队列的队尾。 程序实现,4. 出队列运算 void deQueue_seq( PSeqQueue paqu ) 当队列不空时，删除paqu所指队列的队头元素。 程序实现,5. 取队列头部元素 DataType frontQueue_seq( PSeqQueue paqu ),当paqu所指的队列不空时，取队列头部元素，队列本身保持不变。 程序实现,4.5.2 链接表示,存储结构 队列的链接表示就是用一个单链表来表示队列，队列中的每个元素对应链表中的一个结点，结点的结构与单链表中结点的结构一样。 为了强调队头和队尾都是队列的属性，这里对队列增加了一层封装，引入LinkQueue结构的定义。这样存储的队列简称链接队列。,struct Node; typedef struct Node *PNode; struct Node /* 结点结构 */ DataType info; PNode link; ; struct LinkQueue /* 链接队列类型定义 */ PNode f; /* 头指针 */ PNode r; /* 尾指针 */ ; typedef struct LinkQueue *PLinkQueue; /*链接队列类型的指针类型*/,假设plqu是PLinkQueue类型的变量， plqu-f为队列的头指针，指向队列中第一个结点， plqu-r是队列尾指针，指向队列中最后一个结点(注意：这一点与顺序队列不同！)， 当plqu-f 为 NULL时队列为空。,队列的链接表示,基本运算的实现,1. 创建一个空队列 PLinkQueue createEmptyQueue_link( void ) 申请队列结构空间，创建一个空队列。 程序实现,2. 判断队列是否为空,int isEmptyQueue_link( PLinkQueue plqu ) 判断plqu所指的队列是否为空队，为空队时，则返回1，否则返回0。 程序实现,3. 进队列运算,void enQueue_link( PLinkQueue plqu, Datatype x ) 入队运算，表示往plqu所指的队列中插入一个值为x的元素。 程序实现,4. 出队列运算,void deQueue_link( PLinkQueue plqu ) 出队运算，表示从plqu所指的队列中删除队头元素。 程序实现,5.取队列头部结点的值,Datatype frontQueue_link( PLinkQueue plqu ) 当plqu所指的队列非空时，取队列头部元素的值，队列保持不变。 程序实现,4.6 队列的应用 农夫过河问题,一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。 问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。 请问农夫该采取什么方案才能将所有的东西运过河呢？,算法选择： 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。,广度优先： 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。 要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。,状态的表示,要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。 一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。 例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。,确定每个角色位置的函数,用整数location表示上述四位二进制描述的状态， 用下面的四个函数从上述状态中得到每个角色所在位置的代码。 函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。,int farmer(int location) return (0 != (location ,int cabbage(int location) return (0 != (location ,判断状态是否安全的函数,还应该分析问题中所有角色的各种可能位置构成的状态，确定其中哪些是安全的哪些是不安全的。 根据原题的描述我们知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。 由此可以编一个函数，通过位置分布的代码来判断状态是否安全。,安全状态的判断函数,int safe(int location) / 若状态安全则返回true / 羊吃白菜 if (goat(location) = cabbage(location) / 其他状态是安全的 ,问题的描述： 完成了上面的准备工作，现在的问题变成： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。 为避免不必要的瞎费功夫，要求在序列中不应该出现重复的状态.,主要数据结构的设计,为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。 另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的