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