数据结构6栈和队列B

传智播客数据结构教程（6）,讲师：尹成QQ:77025077博客:,C/C+,算法+实战,传智播客,高薪就业,第2页,第三章栈和队列,3.2队（Queue）,队的基本理论定义、逻辑结构、存储结构、基本运算规则、队的应用2.基本操作的C程序实现方法,第3页,3.2队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),第4页,ADTQueue数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitQueue(Queue/遍历队PrintQueue/ADTQueue,队的抽象数据类型定义严书P59,第5页,队列的顺序存储结构实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,队列会满吗？,这样操作有没有问题？,第6页,存在问题设数组容量为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出,解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,实现：利用“求模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件？,第7页,队空：front=rear队满：front=rear,真溢出,假溢出,第8页,解决方案有三：加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear人为浪费一个单元，令队满特征为front=(rear+1)%N；使用一个计数器记录队列中元素个数（即队列长度）；,选用空闲单元法：即front和rear之一指向实元素，另一指向空闲元素。,队空条件:front=rear(初始化时：front=rear)队满条件：front=(rear+1)%N(N=maxsize)队列长度：L=（Nrearfront）%N,rear,第9页,例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,front,解：由图可知，队头和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4,入队：rear=(rear+1)%M;出队：front=(front+1)%M;,第10页,例2：数组n用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（）rf（）（nfr）%n（）nrf（）（nrf）%n,4种公式哪种合理？当rf时（A）合理；当rnext=S;rear=S;出队（头部删除）：front-next=p-next;,队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,第15页,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）;实时监控系统（循环队列）操作系统中多道作业的处理（一个CPU执行多个作业）；4.简化程序设计。舞伴问题，迷宫的最短路径问题,答：只要是存储和使用顺序相同，两端受限操作就应该想到用队列这种数据结构。,第16页,在周末舞会上，男士们（m人）和女士们（n人,nm）进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。（1）在第t首曲子时，第x个女生和第几个男生配对跳舞？（2）在什么条件下，第x个（1=x=m）男生才有可能和他心仪的第y个（1=x=n）女生跳舞，在第几首曲子时？,舞伴问题,第17页,typedefcharQElemType;/假定队元素的数据类型为字符typedefstructQElemType*base;/数据域intfront;/队头指针intrear;/队尾指针LoopQueue;,循环队列的操作实现,1）循环队列的结构体定义,第18页,2）初始化一空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间设置队列为空队列，即front=rear=1（也可为任意单元，如2，或4）;,两个指针front,rear,约定：rear指示队尾元素；front指示队头元素下一位置,第19页,算法：基于严书P64队结构体的定义！,intInitQueue(SqQueue,新开单元的地址为0则表示内存不足,第20页,算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满if(q.rear+1)%QUEUE_MAXSIZE)=q.front)returnERROR;(2）插入动作q.rear=(q.rear+1)%QUEUE_MAXSIZE;q.baseq.rear=e;,3）入队操作,第21页,intEnQueue(SqQueue/EnQueue,3）入队操作（完整函数）,第22页,4）出队操作,算法说明：删除队头元素，返回其值e分析：（1）在删除前应当判断队列是否空；if(q.front=q.rear)return0;（2）插入动作分析；因为队头指针front指向队头元素的位置，所以：q.front=(q.front+1)%QUEUE_MAXSIZE;e=q.baseq.front;,第23页,intDeQueue(SqQueue/DeQueue,算法：,第24页,讨论：线性表、栈与队的异同点,相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。,不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,第25页,本章小结,第26页,有奖课后练习:,试将课件中所列的栈的基本操作用c语言编写完整代码，并尝试利用这些基本操作编制“回文”程序。舞伴问题的程序实现,第27页,迷宫问题：这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。,附录1：,第28页,设迷宫为m行n列，利用mazemn来表示一个迷宫，mazeij=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有8个方向可以试探，而四个角点有3个方向，其它边缘点有5个方向，为使问题简单化我们用mazem+2n+2来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为8，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。,1.表示迷宫的数据结构,求解思想：回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。,第29页,2试探方向：在上述表示迷宫的情况下，每个点有8个方向去试探，因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move8中，在move数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。Move数组定义如下：typedefstructintx，yitem;itemmove8;这样对move的设计会很方便地求出从某点(x，y)按某一方向v(0=v=7)到达的新点（i，j）的坐标：i=x+movev.x;j=y+movev.y;,第30页,3.栈的设计：当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedefstructintx,y,d;/*横纵坐标及方向*/datatype;栈的定义仍然为：SeqStacks;,第31页,4.防止重复到达某点，以避免发生死循环：一种方法是另外设置一个标志数组markmn，它的所有元素都初始化为0，一旦到达了某一点(i,j)之后，使markij置1，下次再试探这个位置时就不能再走了。另一种方法是当到达某点（i,j）后使mazeij置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的.这里采用后者方法，以使得算法结束前可恢复原迷宫。,第32页,迷宫求解算法思想如下：栈中保存的就是一条迷宫的通路。1栈初始化;2将入口点坐标及到达该点的方向入栈3while(栈不空)栈顶元素（x,y,d）出栈;求出下一个要试探的方向d+;while（还有剩余试探方向时）if（d方向可走）则（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if(x,)=(,n)结束;else重置d=0;elsed+;,第33页,例4求迷宫的最短路径：现要求设计一个算法找一条从迷宫入口到出口的最短路径。,本算法要求找一条迷宫的最短路径，算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路