《数据结构》堆栈和队.ppt

数据结构,堆栈与队,堆栈,客栈：住人；货栈：存货。,堆栈：存货的方式是把货物堆码存放,我想把红色的球拿出来,指示货物码放的位置,堆栈溢出,最先进入堆栈的货物压在最底层,栈：一个存放东西的空间,破坏规则,进栈方向,出栈方向,先进后出的工作方式,元素只能在栈顶进出,指示栈顶元素的指针,是操作受限的线性表,堆栈要素,先进的后出,堆栈操作,栈结构如同摞盘子，先放的后出,除去头、尾元素，栈内元素只有唯一的后继和前趋，所以堆栈是线性表.,存储结构,顺序存储结构,链式存储结构,堆栈是线性表,逻辑结构,顺序栈,链栈,堆栈结构,空栈top=-1;,a1,a2,直到栈满,am,元素进栈top=push(stack,x,top);,top+=1;,元素出栈top=pop(stack,top-=1;,if(top=m-1)不能入栈,am-1,直到栈空,if(top0)无元素出栈,程序1.12进栈函数,int push（struct node*p,struct node x,int top）if(top=M-1)printf(“overflow”);esletop+;*(p+top)=x;return(top);,程序1.13出栈函数,int pop（struct node*p,struct node*x,int top）if(top0)printf(“overflow”);else*x=*(p+top);top-;return(top);,顺序结构的堆栈,进栈元素,栈顶指针,栈满处理,元素进栈,总是指向栈顶,更新栈顶指针,栈空处理,栈非空则元素出栈,指向当前栈顶,更新栈顶指针,倒序,a0,a1,an-1,an-1,an-2,an-2,a0,初始栈空,数组an-1,数组an-1依次进栈,栈顶元素依次出栈,习题：线性表A=a1,a2,.,an，元素为字符类型，用向量结构存放，请编写程序，将它倒序为A=an,an-1,.,a1。,一进出栈的过程就能完成序列的倒序。C程序设计强调把算法编程程序，数据结构注重设计算法与逻辑结构实现,回文识别,a0,a1,an-1,an-2,初始栈空,字符串an-1,元素依次进栈,栈顶元素依次出栈,习题：回文是指一字符串从前读和从后读都有一样的字母顺序。设长度为n的字符串在数组arrayn中，求判别arrayn中的字符串是否为回文的C程序实现。,if(strcmp(A,B)printf(flasen);,还有什么更简洁的方法？,比较两个字符串，相等则是回文,回文也是在C程序设计中遇见过的，从过去强调技巧，转变为现在的数据结构方法，注重算法与逻辑结构的实现,编译程序扫描问题堆栈结构在程序编译中被广泛应用。一段程序需要编译成为CPU可执行的机器码才能运行，称为执行文件（*.exe）。编译程序扫描每一行语句时，首先要检查是否存在语法错误，下面的问题说明了利用栈结构检查左右括弧是否匹配的方法。,(1)程序从左至右扫描字符串时判别该字符串中左、右圆括弧是否平衡。如果字符串不平衡，返回字符串中第一个不匹配的圆括弧位置；若平衡则返回正常匹配信息。即遇见第一个不匹配的右圆括弧时，中断扫描并返回其在字符串中的位置.如有多个左圆括弧不匹配就返回第一个不匹配的左圆括弧在字符串中的位置。(2)设长度0至n-1的字符串在数组str80中，写出用栈函数实现该算法的c程序。,括弧匹配,i,f,(,(,a,b,),&,&,(,c,d,),c,=,10,;,问题：从左至右扫描字符串时判别左、右圆括弧是否平衡。,扫描中每遇见一左圆括弧则将其位置进栈，每遇见一个右圆括弧就弹出一个栈顶元素匹配。,当前是右圆括弧且栈空，则右圆括弧不匹配。,扫描结束且栈不空，则有左圆括弧不匹配,算法,top,0,3,扫描指针i,1,4,2,1,11,2,1,输入数组pn,栈stackM,if(i=n)&(stack0!=0)左圆括弧多余,栈底是第一个非法左圆括弧位置,把i=3入栈,弹出栈顶,平衡进出,int balance(char*p,int n,char*message)int i,val,stackLENGTH;stack0=0;for(i=0;in;i+)if(*(p+i)=()push(stack,i);else if(*(p+i)=)if(pop(stack,数组p及n,匹配信息,top=0,循环匹配,是左括弧就把i入栈,右括弧则应弹出栈顶,平衡进出,栈空？,失衡信息,失衡位置,如扫描结束且栈非空,搜索第一个不匹配的左圆括弧在字符串中的位置,失衡信息,失衡位置,-1时栈空,大于零返回的是失衡位置，小于零是匹配正常,括弧匹配程序,一个直接调用自己，或通过一系列的过程调用语句间接的调用自己的过程（函数）称为递归调用过程（函数）。栈在递归调用中有着重要作用，调用一个函数需要完成：将实参与断点地址传送给被调用函数；为被调用函数的局部变量在栈中分配数据区；从被调用函数入口地址开始执行。从被调用函数返回时正好相反：传递被调用函数的运行结果给调用函数；释放被调函数的数据区；由保存的断点地址返回调用函数。在C语言中已学习过递归的概念，它的每一步都由其前身来定义。递归调用过程中，主调函数又是被调函数。执行递归函数将反复调用其自身。每调用一次就进入新的一层，如果编程中没有设定可以中止递归调用的出口条件，则递归过程会无限制的进行下去，造成系统溢出错误。所以，程序必须有递归出口，即在满足一定条件时不再递归调用。,堆栈与递归,递归应用对象,解决一个现实问题的算法是否应该设计成一个递归调用的形式，完全取决于实际应用问题本身的特性，只有在待处理对象本身具有递归结构特征的情况下，程序才应该设计为递归结构。比如在现实世界中描述一棵树的定义说，树是一个或多个节点组成的有限集合，其中：必有且仅有一个特定的称为根（root）的节点；剩下的节点被分成m0个互不相交的集合T1，T2，Tm，而且其中的每一元素又都是一棵树，称为根的子树（Subtree）。显然树的定义是递归的。,一棵树,一棵树的子树,递归与分治算法,分治法的基本设计思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。如原问题可分割成k个子问题，1kn，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决。否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地求解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。,分治算法适用条件,（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题相互独立，即子问题之间不包含公共的子问题。分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。,void main(void)long i,n,sum=1;printf(请输入n:n);scanf(%d,递推求n的阶乘,阶乘的递归求解,分治法处理问题的一个例子是求n的阶乘。从减小n的规模考虑，n的阶乘可以看成是n(n-1)!(n-1)!与求n!之间互相独立且问题形式相同:(n-1)!=(n-1)(n-2)!。显然，这是一个递归求解过程。因为我们追求将问题的规模一直分解到它的原子形式，也就是1！=1，同时这就是出口条件。从底层回头，再将各子问题的解合并得到原问题的解，于是，2!=2，3!=6，。,int main(void)long n,sum=1;n=read();if(n0)sum=f(n);printf(n!=%dn,sum);,int f(int n)if(n=1)return(1);return(n*f(n-1);,int read()int n;printf(请输入n值:n);scanf(%d,阶乘函数,分解到最小问题之后的递归出口条件,问题规模的递归分解过程,递归求n的阶乘,f(3),3*f(2),2*f(1),f(1)=1,2*1,3*2*1,6,问题规模的递归分解过程,分解到最小问题之后的递归出口条件,回朔合并,n=3的阶乘递归求解,递归求Fibonacci数列,f(5),f(4),f(3),f(3),f(2)=1,f(2)=1,f(1)=1,f(2)=1,f(1)=1,分解到最小问题之后的递归出口条件,if(n=1)|(n=2)return(1);,递归进行规模分解,return(f(n-1)+f(n-2);,递归是否存在问题?,n=3，需要调用函数f(n)2次n=4，需要调用函数f(n)4次n=5，需要调用函数f(n)8次.调用次数与n是指数关系，即f(n+1)的运行时间是f(n)的运行时间的1.6倍。,时间开销与问题的规模成指数关系的程序不可运行,递归简化结构的同时增加了运算时间,进出栈元素序列的排列组合问题,一个进栈元素序列是a1，a2，an，如问出栈的元素序列有多少种排列？栈的工作方式是按先进后出。那么，是否可以认为该序列其出栈排列就只有一种，即：an，an-1，a1？我们说栈的先进后出方式只是限定了元素进出栈规则，并没有限定元素进出栈之间的操作时序。问题：现有一栈的深度为n，设进栈元素序列是a1，a2，an，问出栈的元素序列有多少种排列？显然，当n=1时只有一种出栈序列。当n=2时，出栈元素序列有2种可能，操作方式对应的2种排列顺序是：a1进栈a2进栈 a2出栈a1出栈，出栈序列是a2，a1；a1进栈a1出栈 a2进栈a2出栈，出栈序列是a1，a2；n=3的情况如图所示。由于排列a3，a1，a2逆序无法实现，该排列不可 能实现，故出栈排列数不是3的全排列数6，而是5。,如何寻找它的规律？,进出栈元素序列排列的递归求解,n4后，其出栈序列很难遍历。根据分治法的设计思想，若能将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题是可能的。分解：设n个元素进栈的出栈排列有xn种。根据堆栈的原理，从元素a1进栈，再到a1出栈（a1）之间有i个元素进出栈。则必有下式成立：a1,(ai，ai),a1(an-i-1)设(ai，ai)的排列有xi种，则有：a1(xi)a1(xn-i-1)关系成立。所以，xixn-i-1是在a1，a1间进栈了i个元素后，所余的n-i-1个元素可能的排列组合。现在，我们寻找最小子问题的解：若n=1，显然xi=1，若n=2，已知x2=2，并且我们定义n=0时x0=1。合并：将各个子问题的解合并为原问题的解是：,典型的递归求解形式,进出栈元素序列排列的模型分析,模型转化：假设在一个直角坐标系中，从(0,0)出发走到（n,n），每次只能向右、或者向上走一个单位长度，并且不能走到对角线之上，也就是(0,0)和(n,n)连接而成的线段。向右走可以看成是元素进栈；向上走可以看成是元素出栈；之所以要求不能走到对角线之上，是为了保证堆栈里有元素可出。这样进出栈的排列问题就转化为格路问题，这是典型的组合数学问题。从（0,0）走到（n,n）路径组合是：要想排除对角线以上（不包含对角线上的点）的路径组合，就是：而C2nn-C2nn+1的表达式是：对于任意给定的n，它和前面的x(n)求解结果完全相同。,格路问题,从原点出发走到（n,n）,每次只能水平向右，或者向上走一步,不允许走对角线,a1,a1,a2,a2,an,an,一共有多少种走法？,水平向右是进栈,向上是出栈,n,n-1,n-2,1,汉诺塔算法一个平面上有三根立柱：A，B，C。A柱上套有n个大小不等的圆盘，大的在下，小的在上。把n个圆盘从A柱上移动C柱上，每次只能移动一个圆盘，移动可以借助B柱进行。但在任何时候，任何柱上的圆盘都必须保持大盘在下，小盘在上。,A,B,C,如果只有一个盘子,直接移动到c柱,这是递归出口,否则,假设已有一处理函数,能借助C柱按规则移动盘子到B柱,if(n=1)cn=an;,move(n-1,a,c,b);,n-1,n-2,1,移动盘子n,规模缩小一个,n,只剩一个盘子n,cn=an;,与原问题形式相同且相互独立的子问题,递归地解各个子问题,void move(int n,int a,int b,int c)if(n=1)cn=an;else move(n-1,a,c,b);cn=an;move(n-1,b,a,c);,1,2,n,用一个数组c装盘子,c0元素对应盘子n,c1对应盘子n-1,cn对应盘子1.,队列,一个管道，是可以存放物品的空间,队列：有顺序存放物品的一个管道,rear:队尾指针，指向下一个入队元素的位置,入队方向，只能从队尾进入,我想把黄球取出来,出队方向，只能从队头出队,继续出队,if(front=rear)回到队顶位置,队列内元素只有一个前趋和后继，端点元素只有前趋或者后继。是线性表。,rear和front是相同方向运动(+1),队空不能出队，队满不能进队,front:队头指针，总是指向队头元素位置,先进先出的操作方式,循环队列,rear指向下一个入队位置,继续进队？,rear=front，和初始队空状态相同,队满还是空？,现在队满,初始rear=front,循环中，如何正确计算队指针的位置？,循环队长度是8，称为模,除模取余，是计算循环队指针的正确方法,front=(front+1)%8,rear=(rear+1)%8,元素出队,元素入队,循环队列程序,int queue_in(int front,int*rear,int*Q,int x)if(*rear+1)%M)=front)return(-1);Q*rear=x;*rear=(*rear+1)%M;return(0);,队头指针,队尾指针,顺序队列,入队元素,判断是否队满,从队尾入队,更新队尾指针,正常返回,int queue_out(int*front,int rear,int*Q,int*x)if(rear=*front)return(-1);*x=Q*front;Q*front=0;*front=(*front+1)%M;return(0);,出队元素,判断是否队空,从队头出队,零表示没有元素,更新队头指针,正常返回,工业记录仪,工业记录仪和心电图仪的波形是队列结构的先进先出的滚动显示方式；滚动采样方式有两个指针：指针scan指向队头，sampling指向队列。设循环队列深度为n，满屏时指针sampling指向队列尾端。采样信号到来时刻，当前采样数据被写入队列尾部，最旧的数据点在队列头部（屏幕顶端）被推出。显示是周期重复的。指针scan总是从头部开始扫描输出整个队列的n点数据，并且，在没有最新数据点写入时，队列的数据被重复扫描输出。所以，显示画面只在有新采样点进入时被逐点滚动更新，如图所示。,求（1）：根据题图画出长度为n的循环队列结构，标出Sampling和Scan指针位置求（2）：请描述最新采样数据点被写入时，Sampling和Scan指针的动作过程。,a0,a1,a2,a3,an-1,显示屏幕,ai是最新进入元素,数据在循环队,队头指针scanf对应显示原点,屏幕长度是n,an,新元素要进队,an,samp,scanf同步加一,队头元素出队,an+1,an+1,an+4,an+2,an+3,an+4,scanf指向队头,samp指向队尾,波形向前滚动显示,循环队列实例-滚动显示,待显示波形,迷宫问题,n*m迷宫是一矩形区域，如下表所示（绿色区域是后续程序搜索路径）；矩阵元素（1，1）为入口，（n，m）为出口，0表示该方格可通过，1表示该方格有阻碍不能通过；规则是每次只能从一个无障碍方格向其周围8各方向的邻接任一无障碍方格移动一步；问，当迷宫有解时如何寻找一条由入口到出口的路径并返回这个序列，或者不能连通时给出无解标志。求提出思想；给出算法。,设定的迷宫边界,迷宫区域,迷宫算法队列结构,用2维数组arraynm表示迷宫，其中array00array0m，array00arrayn0,arrayn0arraynm,array0marraynm，是算法设置的边界哨，取值为1。初始，我们不知道从哪一个方格沿哪个方向走、并通过邻接的方格逐步可以达到最后出口。但是，如果把它每一步所有可能走的方向上的邻接方格都排列起来，下一步是把那些邻接方格它们所有可能走的方向上的所有邻接方格也继续排列起来，于是：如一个方格任何方向上都没有可走的邻接方格，就不再需要它，剔除；同样，一个方格所有可能走的方向上的邻接方格都已经列出来后，我们已经知道了后续搜索方向，也就不再需要这个方格，也可以剔除；重复下去，会搜索到所有能走的到方格，当发现有一个方格已是出口后停止；选择数据结构。因为先搜索到的方格在排列出其后续要搜索的邻接方格之后，先被剔除，如果把排列方格看成是按顺序进入一个队列，剔除方格就等于是队列头部元素的出队操作，所以可以用队列结构解决迷宫路径搜索问题。搜索方向设置。设置一个队列sq记录搜索路径，从数组array11开始搜索时将每个方格下标推入队列，以（i,j）为中心向8个邻域搜索时下标变化如下表所示。,迷宫问题求解,寻找一条由入口到出口的路径,每次从一个无障碍(0)方格向其周围8个方向的邻接任一无障碍方格移动一步,解题思路,把每一步所有可能走的方向上的邻接方格都排列起来,方格(i,j)的邻域,1,1,10,1,1,15,10,15,方位,方位修正,i=1,j=1,一次搜索排列,搜索过者出队，开始下一步,a1,1+1,a1+1,1,a1,2+1,a1,1,front为起点继续搜索,a1+1,2+1,a2+1,1,回朔路径,front为起点继续搜索,a1+1,3+1,标记,周围均搜索过，没有进队元素,死路，出队，继续搜索,a2-1,4+1,a2,4+1,if(frontrear)继续搜索,if(i=N)&(j=M)出口,由回朔路径排列搜索线路,if(frontrear)搜索失败,初始化问题,设置边界,节点结构：struct nodeint x,y;/方格点坐标 int pre;/回朔点指示；,int seartch(int arrayN+2M+2,struct node*q,int zx8,int zy8)int x,y,i,j,v,front=1,rear=1;struct node sqN*M;sq1.x=1;sq1.y=1;sq1.pre=0;*(*(array+1)+1)=-1;while(frontx=sqi.x;(q+j)-y=sqi.y;i=sqi.pre;j+;return(-j);front+;return(-1);,搜索路径,x,y方位,原点入队,没有前趋,搜索标记,搜索条件,队头i,j,用方位修正下标,该点没有障碍或标记就入队,该搜索点前趋,标记该搜索点,到达出口？,从队尾回朔路径,队头的前趋为零,要返回的搜索路径由当前队尾的前趋记录,队尾前趋的队列下标,返回搜索路径的长度,未到出口，继续搜索,搜索失败，返回路径长度为-1,迷宫,