《栈和队列 .ppt》由会员分享，可在线阅读，更多相关《栈和队列 .ppt（93页珍藏版）》请在三一办公上搜索。
1、第3章 栈和队列,主要内容,栈 栈的应用举例 栈与递归的实现 队列 离散事件模拟（选讲）,重点与难点,本章的重点掌握栈和队列的基本运算在两种存储结构下的实现 本章的难点栈的应用算法、循环队列中对边界条件的处理,主要内容,从数据结构角度：操作受限的线性表限定性的数据结构，其基本操作是线性表操作的子集：只能在线性表的表尾进行插入和删除先进后出只能在线性表的表尾进行插入，在表头进行删除先进先出从数据类型角度：与线性表不同的抽象数据类型（多型）,3.1 栈,栈的定义限定仅在表尾进行插入或删除操作的线性表,栈的表尾称为栈顶，表头称为栈底。不含元素的空表称为空栈。栈称为后进先出的线性表（Last In F
2、irst Out，LIFO）。,3.1 栈,抽象数据类型栈的定义 ADT Stack数据对象:D=ai|ai(-ElemSet,i=1,2,.,n,n=0数据关系:R1=|ai-1,ai(-D,i=2,.,n基本操作：InitStack(&S)操作结果：构造一个空的栈S。DestroyStack(&S)初始条件：栈S已经存在。操作结果：销毁栈S。,ClearStack(&S)初始条件：栈S已经存在。操作结果：将栈S重置为空栈。StackEmpty(S)初始条件：栈S已经存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已经存在。操作结果：
3、返回S的元素个数,即栈的长度。,3.1 栈,GetTop(S,&e)初始条件：栈S已经存在。操作结果：栈S存在且非空则返回S的栈顶元素。Push(&S,e)初始条件：栈S已经存在。操作结果：插入元素e为新的栈顶元素入栈Pop(&S,&e)栈S存在 初始条件：栈S已经且非空。操作结果：删除S的栈顶元素并用e返回其值出栈StackTraverse(S,visit()初始条件：栈S已经且非空。操作结果：则从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失败ADT Stack,3.1 栈,3.2 栈的表示和实现,顺序栈栈的常用存储结构（为什么？）链栈,由于栈的插
4、入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。,3.2 栈的表示和实现,顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。栈所需最大空间很难估计，一般来说，在初始化设空栈时不应限定栈的最大容量。设定两个常量：存储空间初始分配量MAX_STACK存储空间分配增量STACKINCREMENT,3.2 栈的表示和实现,C语言中，顺序栈也可以采用静态分配 typedef struct SElemType baseMAX_STACK;int top;/指示栈
5、顶位置 SqStack；动态分配 typedef struct SElemType*base;SElemType*top;/设两指针便于判断栈是否为空 int StackSize;/栈的当前可使用的最大容量.SqStack；,3.2 栈的表示和实现,C语言中，顺序栈也可以采用静态分配 typedef struct SElemType baseSTACK_INIT_SIZE;int top;/指示栈顶位置 SqStack；动态分配 typedef struct SElemType*base;SElemType*top;/设两指针便于判断栈是否为空 int StackSize;/栈的当前可使用的最
6、大容量.SqStack；,建议！,3.2 栈的表示和实现,顺序栈InitStack(,3.2 栈的表示和实现,顺序栈Push(,3.2 栈的表示和实现,顺序栈Pop(,3.2 栈的表示和实现,顺序栈GetTop(S,3.2 栈的表示和实现,链栈若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。链栈通常用一个无头结点的单链表表示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,3.2 栈的表示和实现,链栈,3.2 栈的表示和实现,链栈的类型说明动态分配
7、typedef struct stacknode SElemType data;struct stacknode*next；stacknode,*LinkStack;,3.3 栈的应用,字符逆置数制转换括号匹配的检验行编辑程序表达式求值栈与递归的实现,3.3 栈的应用字符逆置,将从键盘输入的字符序列逆置输出。比如，从键盘上输入：tset a si sihT；算法将输出：This is a test typedef char SElemType;,3.3 栈的应用字符逆置,void ReverseRead()InitStack(,3.3 栈的应用,字符逆置数制转换括号匹配的检验行编辑程序表达式求
8、值栈与递归的实现,3.3 栈的应用数制转换,十进制数值转换成二进制。使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。,3.3 栈的应用数制转换,数制转换(692)10=(1010110100)2,3.3 栈的应用数制转换,void Decimal _ Binary()InitStack(,3.3 栈的应用括号匹配的检验,字符逆置数制转换括号匹配的检验行编辑程序表达式求值栈与递归的实现,3.3 栈的应用括号匹配的检验,检验表达式中的括号匹配情况假设在一个算术表达式中，可以包
9、含三种括号：“（”和“）”、“”和“”、“”和“”，并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。,3.3 栈的应用括号匹配的检验,算术表达式中各种括号的使用规则出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。,3.3 栈的应用括号匹配的检验,在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论:当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；从栈中弹出的左括号与
10、当前检验的右括号类型不同，说明出现了括号交叉情况；算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。,3.3 栈的应用括号匹配的检验,int Check()InitStack(,3.3 栈的应用括号匹配的检验,case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(,3.3 栈的应用,字符逆置数制转换括号匹配的检验行编辑程序表达式求值栈与递归的实现,3.3 栈的应用行编辑程序,一个简单的行编辑程序的功能接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，为退行符，
11、表示当前行所有字符均无效。,3.3 栈的应用行编辑程序,示例 在终端上用户输入为:whli#ilr#e(s#*s)应为:while(*s)在终端上用户输入为:Outchaputchar(*s=#+)应为:putchar(*s+),3.3 栈的应用行编辑程序,可以将输入缓冲区设为一个栈结构,每当从终端接受了一个字符之后先作如下判别:如是它既不是退格符也不是退行符,则将该字符压入栈顶;如果是一个退格符,则从栈顶删去一个字符;如果它是一个退行符,则将字符栈清空。,3.3 栈的应用行编辑程序,void LineEdit()/利用字符栈s，从终端接收一行并传送至调用过程的数据区 InitStack(S)
12、；/构造空栈Sch=getchar()；/从终端接收第一个字符while(ch!=EOF)/EOF为全文结束符 while(ch!=EOFch!=n)switch(ch)case#：Pop(S，c)；break；/仅当栈非空时退栈case：ClearStack(S)；break；/重置S为空栈default：Push(S，ch)；break；/有效字符进栈，未考虑栈满情形 ch=getchar()；/从终端接收下一个字符/将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S)；/重置S为空栈if(ch!=EOF)ch=getchar()；DestoryStack(S)；,3.
13、3 栈的应用,字符逆置数制转换括号匹配的检验行编辑程序表达式求值栈与递归的实现,3.3 栈的应用,表达式求值无括号算术表达式求值 带括号算术表达式求值,3.3 栈的应用,表达式求值无括号算术表达式求值 带括号算术表达式求值,3.3 栈的应用带括号算术表达式求值,直接对带括号的算术表达式求值可分解为二步求值（重点掌握）第一步 将该算术表达式转化为后缀表达式第二步 对后缀表达式求值,3.3 栈的应用带括号算术表达式求值,实现算符优先算法时需要使用两个工作栈：一个称作运算符栈operator；另一个称作操作数栈operand。算法的基本过程如下：初始化操作数栈operand和运算符栈operator
14、，并将表达式起始符“#”压入运算符栈；读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：,3.3 栈的应用带括号算术表达式求值,1 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；2 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈；3 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括
15、号）退栈即可。当operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求值完毕。,3.3 栈的应用带括号算术表达式求值,表3.1 算符间的优先关系,3.3 栈的应用带括号算术表达式求值,求3*（7-2）的值,3.3 栈的应用带括号算术表达式求值,char EvaluateExpression()SqStack*OPND,*OPTR;char c,x,theta;char a,b;InitStack(else switch(Precede(GetTop(*OPTR),c),3.3 栈的应用带括号算术表达式求值,case:Pop(OPT
16、R,3.3 栈的应用,字符逆置数制转换括号匹配的检验行编辑程序表达式求值栈与递归的实现,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归（recursive）的定义若在一个函数、过程或者数据结构定义的内部，直接或间接出现定义本身的应用。递归的分类直接递归(direct recursive)：函数F的代码中直接包含了调用F的语句；间接递归(indi
17、rcet recursive)：间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用。,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归的应用 有很多数学函数是递归定义的，如:阶乘函数 1(n=0)Fact(n)=n*Fact(n-1)(n0)Fibonacci数列 0(n=0)Fib(n)=1(n=1)Fib(n-1)+Fib(n-2)其它,3.3 栈的应用栈与递归的实现,递归的应用 有的数据结构，如二叉树，广义表，由于结构本身固有的递归特性，也可以用
18、递归描述；还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如：八皇后问题，Hanoi塔问题等。,3.3 栈的应用栈与递归的实现,Hanoi塔问题传说印度教的主神梵天创造世界时，在印度北部佛教圣地贝拿勒斯圣庙里，安放了一块黄铜板，板上插着三根宝石针，在其中一根宝石针上，自下而上地放着由大到小的 64 个金盘。这就是所谓的梵塔（Hanoi）。梵天要求僧侣们坚持不渝地按下面的规则把 64 个盘子移到另一根针上。梵天宣称，当把他创造世界之时所安放的 64 个盘子全部移到另一根针上时，世界将在一声霹雳声中毁灭。那时，他的虔诚的信徒都可以升天。,3.3 栈的应用栈与递归的实现,
19、Hanoi塔问题假设有三个分别命名为X,Y,Z的塔座，在塔座X上插有N个直径大小个不相同，以小到大编号为1，2，.的圆盘.现在要求将X轴上的N个圆盘移至塔座Z上并且仍按同样的顺序叠排，圆盘移动是必须遵循下列规则：每次只能移动一个圆盘。圆盘可以插在X,Y,Z中的任意一个塔座上。任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。,3.3 栈的应用栈与递归的实现,Hanoi塔问题的分析当N=1时，只要将编号为1的圆盘从塔座X上直接移至塔座Z上即可；当N1时，需利用塔座Y作辅助塔座，若能设法将压在编号为N的圆盘之上的N-1个圆盘从塔座X移至塔座Y上，则可先将编号为N的圆盘从塔座X移至塔座Z上，然后再将
20、塔座Y上的N-1个圆盘移至塔座Z上。而如何将N-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解。,3.3 栈的应用栈与递归的实现,Void hanoi(int n,char x,char y,char z)if(n=1)move(x,1,z);else hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归模型反映一
21、个递归问题的递归结构，由递归出口和递归体两部分组成，前者确定递归何时为止，后者确定递归的方式。递归出口的一般格式为：f(s0)=m0/s0与m0均为常量，有的递归问题可能有几个递归出口。递归体的一般格式为：f(s)=g(f(s1),f(s2),.,f(sn),c1,c2.,cm)/s是一个递归“大问题”，s1,s2.sn为递归“小问题”，c1,是若干个可以直接解决的问题，g是一个非递归函数，反映了递归问题的结构。,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归的执行过程 把
22、一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进问题进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。递归的执行过程可以由以下两部分构成：分解求值,3.3 栈的应用栈与递归的实现,递归的执行过程 int fact(int n)if(n=0)return(1);else return(n*fact(n-1);,3.3 栈的应用栈与递归的实现,递归的执行过程 求f(s0)的分解过程如下：（量变过程）f(sn)f(sn-1)f(s1)f(s0)遇到递归出口，发生了“质变”，分解过程结束，开始求值过程，既原来递归的问题便转化成直接问
23、题：f(s0)=m0 f(s1)=g(f(s0),c0)f(s2)=g(f(s1),c1)f(sn)=g(f(sn-1),cn-1),3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,栈在递归算法的内部实现中所起的作用调用函数时：将实在参数、所有局部变量和返回地址组成的活动记录压入由系统提供的运行时刻栈的栈顶；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。,3.3 栈的应用栈与递归的实现,栈在递归算法的内部实现中所起的作用被调函数执行完毕时：保存被调函数的计算结果
24、；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。,3.3 栈的应用栈与递归的实现,递归的定义及分类递归的应用 递归的模型 递归的执行过程 栈在递归算法的内部实现中所起的作用递归设计,3.3 栈的应用栈与递归的实现,递归设计的执行先要给出递归模型，再转化成对应的C过程或函数。由此得出递归设计的步骤如下：对原问题f(s)进行分析，假设出合理的“较小问题”f(s)；假设f(s)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s)之间的关系；确定一个特定情况(如f(0)或f(1)的解，由此作为递归出口。,3.4 队列,队列的定义只允许在一端（队尾，Rear）。进行插入
25、，而在另一端（队头，Front）进行删除的运算受限的线性表。当队列中没有元素时称为空队列。队列称为后进先出的线性表FIFO（First In First Out）,3.4 队列,抽象数据类型队列的定义 ADT Queue数据对象:D=ai|ai(-ElemSet,i=1,2,.,n,n=0数据关系:R1=|ai-1,ai(-D,i=2,.,n基本操作：InitQueue(&Q)操作结果：构造一个空的队列Q。DestroyQueue(&Q)初始条件：队列Q已经存在。操作结果：销毁队列Q。,ClearQueue(&Q)初始条件：队列Q已经存在。操作结果：将队列Q重置为空队列。QueueEmpty(
26、Q)初始条件：队列Q已经存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已经存在。操作结果：返回Q的元素个数,即队列的长度。,3.4 队列,GetHead(Q,&e)初始条件：队列Q已经存在。操作结果：队列Q存在且非空则返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已经存在。操作结果：插入元素e为新的队头元素入队DeQueue(&Q,&e)初始条件：队列Q已经存在且非空。操作结果：删除队列Q的队头元素并用e返回其值出队QueueTraverse(Q,visit()初始条件：队列Q已经存在且非空。操作结果：则从队头到队尾
27、依次对Q的每个数据元素调用函数visit()，一旦visit()失败，则操作失败ADT Queue,3.4 队列,3.5 队列的表示和实现,顺序队列运算受限的顺序表，用一个向量空间来存放当前队列中的元素。链队列用链表表示的队列简称为链队列。,顺序队列由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。,3.5 队列的表示和实现,顺序队列中的溢出现象“下溢”现象当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。“真上溢”现象当队列满时，做入队运算产生空间溢出的现象
28、。“真上溢”是一种出错状态，应设法避免。“假上溢”现象由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。,3.5 队列的表示和实现,解决“假上溢”现象循环队列,3.5 队列的表示和实现,循环队列中的问题判空、判满条件一样，典型解决方案：另设一个布尔变量以匹别队列的空和满；少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；使用一个计数器记录队列中元素的总数（实际上是
29、队列长度）。,3.5 队列的表示和实现,3.5 队列的表示和实现,C语言中，循环队列的表示 typedef struct QElemType*base;int front;/指示队头位置 int rear;/指示队尾位置 SqQueue；循环队列的实现（P64）,链队列用链表表示的队列简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针。,3.5 队列的表示和实现,银行业务的模拟（P65）舞伴问题模拟打印机缓冲区CPU分时系统,3.6 队列的应用离散事件模拟,舞伴问题假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初
30、始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。,3.6 队列的应用,模拟打印机缓冲区在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。,3.6 队列的应用,CPU分时系统在一个
31、带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。,3.6 队列的应用,3.7 综合实例,背包问题迷宫问题,3.7 综合实例,背包问题有不同价值,不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,是选中的物品总重量不超过指定的限制重量,但是选
32、中的物品的价值之和最大。常用解法递归法贪婪法搜索法,3.7 综合实例,最简单的背包问题用一个一维数组W0.n-1,存放n个物体的体积值。用一个栈S，记录当前背包内装载物体的序号变量T记录当前背包的剩余体积,3.7 综合实例,最简单的背包问题void knapsack(int w,int T,int n)InitStack(S);k=0;do while(T0,3.7 综合实例,迷宫问题假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为(1，1)，出口坐标为(m，n)，试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。常用解法递归法搜
33、索法,3.7 综合实例,迷宫问题出自希腊神话。阿莉阿德尼公主是克里特国王米诺斯的长女。传说其母曾生下一个牛首人身的怪物米诺妥。国王为了掩丑，令巧匠代达罗斯建造了一座地下迷宫，将此怪物关在里面。任何人只要走进迷宫，就永远无法出来。米诺斯每9年强迫雅典贡奉7对童男童女供怪物米诺妥食用。到第3次进贡时，雅典王子提修斯(Theseus)决心自己前往，铲除怪物，彻底解除雅典人的苦难。,3.7 综合实例,迷宫问题提修斯先到阿波罗神庙请求神谕，神谕指示他去向爱神阿芙洛狄特献祭并祈求庇护。提修斯和另外13名童男童女一起来到克里特岛。由于爱神的帮助，公主阿莉阿德尼爱上了王子。为了帮助王子杀死怪物公主给了他一个线球，这是修建迷宫的巧匠代达罗斯送给她的。提修斯先将线球的一端拴在迷宫的大门上，然后一边往里走一边放线。他通过曲折复杂的路径，终于找到了怪物并用公主为他准备的魔刀除掉了怪物。然后他顺着公主的“线”路顺利地走出了迷宫。,第3章作业,P46P70以下题目做在书本上：3.4.1、3.4.2以下题目做在习题本上，必须抄题：例3.5、3.4.3（2.）、3.4.4（4.、5.、7.、8.）,The End,Data Structure,
