冯毅《数据结构》ch

,实例,栈,队列,下一章,第三章栈和队列,1、停车场特点后进先出，便道特点先进先出2、如何存储3、数据操作：进场，出场,停车场管理,RailwaySwitchingNetwork,1、其特点是先进先出2、如何存储3、数据操作：到达，离开，求队长等,银行业务模拟,栈和队列是两种特殊的线性表是操作受限的线性表，称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表,线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in,栈和队列是两种常用的数据结构,栈（stack）,栈的逻辑结构,栈的存储结构,栈的应用,栈的逻辑结构栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶(top)，表头栈底(bottom)，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）,栈的运算：置空栈取栈顶元素判空栈进栈退栈,ADTStack数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。,基本操作：,ADTStack,栈的抽象数据类型定义,基本操作：,InitStack(否则FALSE,StackLength(S)初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度,ClearStack(#defineSTACK_INIT_SIZE100/顺序栈存储空间的初始分配量#defineSTACKINCREMENT10/顺序栈存储空间的分配增量typedefstructSElemType*base;/存储空间基址,栈底指针SElemType*top;/栈顶指针intstacksize;/当前分配的存储容量SqStack;,A,B,C,栈的顺序存储结构顺序栈,SqStackS;,StatusInitStack(SqStack,顺序栈结构初始化：,算法时间复杂度：,O(1),栈的基本操作在顺序栈中的实现,StatusGetTop(SqStackS,SElemType,取栈顶元素：,A,B,C,D,算法时间复杂度：,O(1),栈的基本操作在顺序栈中的实现,StatusPop(SqStack,元素出栈：,A,B,C,D,算法时间复杂度：,O(1),E,栈的基本操作在顺序栈中的实现,StatusPush(SqStack,元素入栈：,A,B,C,D,算法时间复杂度：,O(1),E,栈的基本操作在顺序栈中的实现,在一个程序中同时使用两个栈,按1,2,3,4顺序进栈，有几种出栈序列？,栈的基本操作在顺序栈中的实现,顺序栈,思考链栈是否需要另外设置头指针？建立链栈适合用哪种插入法？链栈的基本操作的实现。,top,栈的链式存储结构链栈,结点定义,typedefstructSNodeSElemTypedata;structSNode*next;SNode,*LinkStack;,an,an-1,a1,an-2,栈的链式存储结构链栈,入栈算法,StatusPush(LinkStack,栈的链式存储结构链栈,栈顶,栈顶,算法时间复杂度：,O(1),出栈算法,栈的链式存储结构链栈,栈顶,栈顶,top,StatusPop(LinkStack,算法时间复杂度：,O(1),栈的应用,函数的嵌套调用,递归的实现,回文游戏,递归函数,汉诺塔问题,斐波那契数列,多进制转换,括号匹配的检验,迷宫问题,地图四染色,表达式求值,行编辑程序,voidmain()inta,b,sum;.sum=add(a,b);.intadd(intx,inty)intsum;sum=square(x+y);returnsum;intsquare(intx)returnx*x;,栈的应用函数嵌套调用,函数嵌套调用规则:,后调用的函数先返回,内存管理实行“栈式管理”,例递归的执行情况分析,voidprint(intw)inti;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“n”);,运行结果：1，2，2，3，3，3，,递归函数：函数直接或间接的调用自身叫实现：可视为同一函数进行嵌套调用，递归工作栈,栈的应用递归函数及其实现,递归调用执行情况如下：,相传在很久很久以前，在中东地区的一个寺庙里，几个和尚整天不停地移动着64个盘子，日复一日，年复一年，移盘不止。移盘的规则是：。据说当所有64个盘子全部移完的那一天是世界的末日,每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻不能将大盘压到小盘上,TowerofHanoi,栈的应用递归实现,按直径从小到大叠放，形如宝塔,求解思路,?,求解思路,?,递归,算法,voidhanoi(intn,charx,chary,charz)if(n=1)move(1,x,z);elsehanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);,递归工作栈：,算法演示,(1)(2)(3)(4)(5)(6)(7)(8)(9),算法运行,voidhanoi(intn,charx,chary,charz)(1)(2)if(n=1)(3)move(1,x,z);(4)else(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)(9),n个盘子需要移动次，64个盘子大约需。假设每秒移动一次，约需一万亿年；一微秒一次，约需一百万年,输出斐波纳契Fibonacci数列的前n项,递归函数效率低,栈的应用递归实现,方法一：voidOutput_Fib(intn)inti;if(n1)printf(“error!”);elsefor(i=1;i=n;i+)printf(“%d”,Fib(i);intFib(intk)if(k=1)|(k=2)return1;elsereturnFib(k-1)+Fib(k-2);,F1,F2,n=5,输出：,1,1,1,1,2,i=1,2,3,5,栈的应用递归实现,方法二：voidFibonacci(intn)intf1=1,f2=1,temp,i;if(n1)printf(“error!”);elsefor(i=1;i=n;i+)printf(“%d”,f1);temp=f2;f2=f1+f2;f1=temp;,输出斐波纳契Fibonacci数列的前n项,用非递归函数效率高,顺读与逆读字符串一样,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文,字符串：“madamimadam”,a,d,a,m,i,m,a,d,a,m,m,回文,字符串：“madamimadam”,m,a,d,a,m,i,m,a,d,a,m,栈的应用回文,StatusPalindrome(stringstr)SqStackS;SElemTypech;char*p=str;InitStack(S);while(*p!=0)Push(S,*p+);while(!StackEmpty(S)Pop(S,ch);if(ch!=*str+)returnERROR;returnOK;,voidDelSpace(stringstr)inti,k;for(i=0,k=0;stri!=0;i+)if(stri!=)strk=stri;k+;strk=0;,栈的应用回文算法,3,2,7,算法基于原理：N=(Ndivd)d+Nmodd,栈的应用多进制转换,2,3,7,结束,栈的应用多进制转换算法,voidConversion()SqStackS;SElemTypee;intN;InitStack(S);scanf(%d,在表达式中:（）或（）为正确的格式（）或（）或（）)为不正确格式,括号匹配检验方法：“期待的急迫程度”,例如，考虑下面括号序列：（）12345678,栈的应用括号匹配的检验,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余；否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确；否则表明“左括弧”有余。,例如，（）12345678,(,匹配,栈的应用括号匹配的检验,例如，（）,(,(,不匹配,栈的应用括号匹配的检验,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余；否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确；否则表明“左括弧”有余。,“每接受一个字符即存入用户数据区”?,并不恰当！,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区并假设“#”为退格符，“”为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,栈的应用行编辑程序,行编辑程序功能：接收用户从终端输入的程序或数据，并存入用户数据区,例如，从终端输入两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);,则实际有效的是下列两行：while(*s)putchar(*s+);,栈的应用行编辑程序,设输入缓冲区为栈结构：1、输入普通字符，压栈；2、输入#，出栈一个字符，删去；3、输入，清为空栈；4、输入回车，将栈中字符传送至用户数据区,h,l,w,i,i,l,r,e,(,s,*,s,),用户数据区：,while(*s),o,u,t,c,h,a,p,u,t,c,h,a,r,(,*,s,=,+,+,),;,putchar(*s+);,程序设计语言编译中的一个基本问题,二元运算符表达式的三种标识方法：,设Exp=S1+OP+S2,则称OP+S1+S2为前缀表示法（PN）,S1+OP+S2为中缀表示法,S1+S2+OP为后缀表示法（RPN）,栈的应用表达式求值,5）后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。,1）操作数之间的相对次序不变;,可以看出:,2）运算符的相对次序不同;,4）前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式,3）中缀式丢失了括弧信息，致使运算的次序不确定,栈的应用表达式求值,a*b+c-d/e*f,ab*c+,abc*+,abc*d+e/+,+*abc,+a*bc,+a/+*bcde,ab*cde/-f*+,+*ab*-c/def,a*b+c,a+b*c,a+b*c+d/e,算符优先法表达式求值：按照算符优先级计算,例计算2+4-3*6,4,2,操作数,运算符,6,3,*,6,18,-12,=-12,栈的应用表达式求值,算法需要设置两个栈：操作数栈和运算符栈,若栈顶运算符优先级低，入栈若栈顶运算符优先级高，出栈,栈的应用表达式求值,算符优先级:,算符优先法,例计算2*(1+3)-4/2,#,操作数,运算符,#2*(1+3)-4/2#,*,2,(,1,+,3,栈的应用表达式求值,算符优先法,例计算2*(1+3)-4/2,后缀表达式：213+*42/-,2,1,3,后缀表达式求值：操作数栈,4,8,4,3,1,2,=6,栈的应用表达式求值,a+b*c+(d*e+f)*g,abc*+de*f+g*+,*,a,+,b,运算符栈,后缀式:,c,*,+,将表达式转换成后缀表达式,运算符栈,#,#,若当前字符是操作数：则直接发送给后缀式,若当前字符是运算符：,若当前运算符的优先数高于栈顶运算符，则进栈,否则，退出栈顶运算符发送给后缀式,转换算法步骤：依次读入中缀表达式字符,+,d,e,*,f,+,g,*,+,#,栈的应用表达式求值,栈的应用地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1#紫色2#黄色3#红色4#绿色,回溯法,栈的应用地图四染色问题,寻找一条从入口到出口的通路。,前进方向：上(北)、下(南)、左(西)、右(东),走步规则：首先从向下开始，按照逆时针方向搜索下一步可能前进的位置,栈的应用迷宫问题,栈的应用迷宫问题,回溯,深度优先搜索,设定当前位置的初值为入口位置；do若当前位置可通：则将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的下邻方块为新的当前位置；否则,当前位置不通：则若栈不空若栈顶位置尚有其他方向未被探索:设定新的当前位置为栈顶的下一相邻块,继续试探若栈顶位置的四周均不可通:删去栈顶位置；/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；若栈空：则表明迷宫没有通路while(栈不空）；,栈的应用迷宫问题算法思路,队列（Queue）,队列的逻辑结构,队列的存储结构,队列的应用,队列的逻辑结构队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),队列的运算：置空队取队头判空队进队退队,ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定a1为队头，an为队尾,基本操作：,ADTQueue,队列的抽象数据类型定义,基本操作：,InitQueue(否则FALSE,QueueLength(Q)初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列的长度,ClearQueue(structQNode*next;QNode,*QueuePtr;,链队列类型typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;,Q.rear,链队列队列的链式存储结构,StatusInitQueue(LinkQueue,建空队列：,算法时间复杂度：,O(1),队列的基本操作在链队列中的实现,入队：,Q.front,Q.rear,a1,a2,p,算法时间复杂度：,O(1),StatusEnQueue(LinkQueue,队列的基本操作在链队列中的实现,出队：,Q.front,Q.rear,a1,p,a2,算法时间复杂度：,O(1),StatusDeQueue(LinkQueue,队列的基本操作在链队列中的实现,Q.front,Q.rear,销毁队列：,StatusDestroyQueue(LinkQueue,队列的基本操作在链队列中的实现,算法时间复杂度：,O(n),从头结点开始逐个结点释放,实现,typedefintQElemType;#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/存储空间基址intfront;/队头指针，若队列不空，/指向队头元素intrear;/队尾指针，若队列不空，/指向队尾元素的下一个位置SqQueue;,J1,溢出,J2,J3,J4,J5,J6,入队列：Q.baseQ.rear+=e;,真,真溢出条件：Q.front=0;Q.rear=MAXQSIZE;,队列的顺序存储结构,SqQueueQ;,J3,J4,J5,J6,溢出,假,假溢出条件：Q.front0;Q.rear=MAXQSIZE;,typedefintQElemType;#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/存储空间基址intfront;/队头指针，若队列不空，/指向队头元素intrear;/队尾指针，若队列不空，/指向队尾元素的下一个位置SqQueue;,实现,队列的顺序存储结构,SqQueueQ;,出队列：e=Q.baseQ.front+;,方案一：队首固定，每次出队，剩余元素下移,J1出队,J1,J2,J3,J4,真溢出条件：Q.front=0;Q.rear=MAXQSIZE;,假溢出条件：Q.front0;Q.rear=MAXQSIZE;,队列的顺序存储结构,假溢出问题解决方案,缺点：浪费时间,方案二：循环队列，把队列设想成环形，首尾相接,实现：利用模运算,真溢出条件：Q.front=0;Q.rear=MAXQSIZE;,假溢出条件：Q.front0;Q.rear=MAXQSIZE;,队列的顺序存储结构,假溢出问题解决方案,利用模运算实现循环队列,J8,J9,J7,初始状态,队满,队空,循环队列中：队空条件：Q.front=Q.rear队满条件：Q.front=Q.rear,队列的顺序存储结构循环队列,利用模运算实现循环队列,J8,J7,初始状态,队满,队空,?,解决方案：1.设一个标志区分队空、队满2.少用一个元素空间：队空：Q.front=Q.rear队满：(Q.rear+1)%MAXQSIZE=Q.front,队列的顺序存储结构循环队列,StatusInitQueue(SqQueue,循环队列初始化：,算法时间复杂度：,O(1),队列的基本操作在循环队列中的实现,intQueueLength(SqQueueQ)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;,循环队列长度：,队列的基本操作在循环队列中的实现,算法时间复杂度：,O(1),StatusEnQueue(SqQueue,循环队列元素入队：,J7,队列的基本操作在循环队列中的实现,算法时间复杂度：,O(1),StatusDeQueue(SqQueue,J5,J6,队列的基本操作在循环队列中的实现,循环队列元素出队：,算法时间复杂度：,O(1),队列的应用,划分子集问题,优先级队列,迷宫问题,离散事件模拟,作业调度,基数排序,图的广度优先遍历,农夫过河问题,广度优先搜索,搜索从(1,1)到(N-2,N-2)路径的过程是:(1)首先将(1,1)入队;(2)在队列Q不为空时循环：取队头元素,称该方块为当前方块,Q.front为该方块在Q中的下标。如果当前方块是出口,则输出路径并结束。否则,按逆时针方向找出当前方块的可行相邻方块，将其均插入到队列Q中,其pre设置为当前方块的Q.front值,将其对应的maze位置置为#,以避免重复搜索(3)若队列为空仍未找到出口,即不存在路径。,算法思想:是从(1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是图的广度优先搜索方法。,队列的应用迷宫问题,typedefstructintx,y;Po