数据结构与算法。第3章 栈和队列(3)

2020年2月26日数据结构讲义1•从上图所示的循环队可以看出：•可见在队满和队空情况下都有：front==rear，这显然是必须要解决的一个问题。方法之一是：•附设一个存储队中元素个数的变量如num，当num==0时队空，当num==MAXSIZE时为队满。•另一种方法是：•少用一个元素空间，把图(d)所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，这种情况下队满的条件是：(rear+1)%MAXSIZE==front，也能和空队区别开。我们采用第一种方法。2020年2月26日数据结构讲义2循环队列的类型定义如下：typedefstruct{datatypedata[MAXSIZE];/*数据的存储区*/intfront,rear;/*队头队尾指针*/intnum;/*队中元素的个数*/}CSeQueue;/*循环队*/2020年2月26日数据结构讲义3⑴置空队【算法3-14】构建一个空的循环队算法CSeQueue*Init_SeQueue(){CSeQueue*q;q=(CSeQueue*)malloc(sizeof(CSeQueue));qfront=qrear=MAXSIZE-1;qnum=0;returnq;}2020年2月26日数据结构讲义4⑵入队【算法3-15】循环队入队算法intIn_SeQueue(CSeQueue*q,datatypex){if(qnum==MAXSIZE){printf(队满);return-1;/*队满不能入队*/}else{q-rear=(qrear+1)%MAXSIZE;qdata[qrear]=x;qnum++;return1;/*入队完成*/}}2020年2月26日数据结构讲义5⑶出队【算法3-16】循环队出队算法intOut_SeQueue(CSeQueue*q,datatype*x){if(qnum==0){printf(队空)；return-1;/*队空不能出队*/}else{qfront=(qfront+1)%MAXSIZE;*x=qdata[qfront];/*读出队头元素*/qnum--;return1;/*出队完成*/}}2020年2月26日数据结构讲义6⑷判队空【算法3-17】判循环队空队算法intEmpty_SeQueue(CSeQueue*q){if(qnum==0)return1;elsereturn0;}2020年2月26日数据结构讲义7⒉链队链式存储的队称为链队。和链栈类似，用单链表来实现链队，根据队的FIFO原则，为了操作上的方便，我们分别需要一个头指针和尾指针，如图所示。图中头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。2020年2月26日数据结构讲义8链队的描述如下：typedefstructnode{datatypedata;structnode*next;}QNode;/*链队结点的类型*/typedefstruct{QNnode*front,*rear;}LQueue;/*将头尾指针封装在一起的链队*/定义一个指向链队的指针：LQueue*q;2020年2月26日数据结构讲义9带头结点的链队如图所示：2020年2月26日数据结构讲义10(1)创建一个带头结点的空队【算法3-18】置一个空链队算法LQueue*Init_LQueue(){LQueue*q;Qnode*p;q=(LQueue*)malloc(sizeof(LQueue));/*申请头尾指针结点*/p=(QNode*)malloc(sizeof(QNode));/*申请链队头结点*/pnext=NULL;qfront=p;qrear=p;returnq;}2020年2月26日数据结构讲义11(2)入队【算法3-19】链队入队算法voidIn_LQueue(LQueue*q,datatypex){QNode*p;p=(QNode*)malloc(sizeof(QNode));pdata=x;pnext=NULL;qrearnext=p;qrear=p;}2020年2月26日数据结构讲义12(3)判队空【算法3-20】判链队空算法intEmpty_LQueue(LQueue*q){if(qfront==qrear)return1;elsereturn0;}2020年2月26日数据结构讲义13(4)出队【算法3-21】链队出队算法intOut_LQueue(LQueue*q,datatype*x){QNode*p;if(Empty_LQueue(q)){printf(队空);return0;/*队空，出队失败*/}else{p=qfrontnext;qfrontnext=pnext;*x=pdata;/*队头元素放x中*/free(p);if(qfrontnext==NULL)qrear=qfront;/*只有一个元素时，出队后队空，此时还要要修改队尾指针*/return1;}}2020年2月26日数据结构讲义14队列是一种应用广泛的数据结构，凡具有“先进先出”需要排队处理的问题，都可以使用队列来解决。1.队列在输入、输出管理中的应用在计算机进行数据输入、输出处理时，由于外部设备的速度远远低于CPU数据处理的速度，此时可以设定一个“队列缓冲区”进行缓冲。当计算机要输出数据时，将计算机的数据按块（例如每块512B）逐个添加到“队列缓冲区”的尾端，而外部设备则按照其输出速度从队首逐个取出数据块输出。这样，虽然输出数据速度较慢，但却能保证与计算机输出的数据有完全相同的次序，而不致发生输出次序的混乱或数据的丢失。3.4队列应用举例2020年2月26日数据结构讲义152.对CPU的分配管理一般的计算机系统只有一个CPU，如果在系统中有多个进程都满足运行条件，可以用一个就绪队列来进行管理。当某个进程需要运行时，它的进程名就被插入到就绪队列的尾端。CPU总是首先执行排在队首的进程，一个进程分配的一段时间执行完了，又将它插入到队尾等待。如此，按“先进先出”的原则一直进行下去，直到执行完的进程从队列中逐个删除掉。2020年2月26日数据结构讲义163.4队列应用举例例3-5设计一个算法找一条从迷宫入口到出口的最短路径。算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路。2020年2月26日数据结构讲义17有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与例3.2处理相同，不同的是：如何存储搜索路径。在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点先向下搜索，故引进一个队列来保存已到达的坐标点。2020年2月26日数据结构讲义18到达迷宫的出口点(m,n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，用一个结构数组sq[num]作为队列的存储空间。sq的每一个结构有三个域：x,y和pre。其中x,y分别为所到达的点的坐标，pre为前驱点在sq中的坐标，还有队头、队尾指针。队的定义如下：typedefstruct{intx,y;intpre;}sqtype;sqtypesq[num];intfront,rear;2020年2月26日数据结构讲义19初始状态：队列中只有一个元素sq[1]记录的是入口点的坐标(1,1)，因为该点是出发点，因此没有前驱点，pre域为-1，队头指针front和队尾指针rear均指向它。此后搜索时都是以front所指点为搜索的出发点，当搜索到一个可到达点时，即将该点的坐标及front所指点的位置入队，不但记下了到达点的坐标，还记下它的前驱点。front所指点的８个方向搜索完毕后，则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束；或者当前队空即没有搜索点了，表明没有路径算法也结束。2020年2月26日数据结构讲义20算法描述入口点入队标记入口点为已到达while队列不空：队头元素front出队对与front相邻的每个点：如果该点可达：将该点坐标及其前驱点front入队标记该点为已到达如果该点是出口点：打印路径；结束算法示例2020年2月26日数据结构讲义21入口点入队标记入口点为已到达while队列不空：队头元素front出队对与front相邻的每个点：如果该点可达：将该点坐标及其前驱点front入队标记该点为已到达如果该点是出口点：打印路径；结束2020年2月26日数据结构讲义22入口点入队标记入口点为已到达while队列不空：队头元素front出队对与front相邻的每个点：如果该点可达：将该点坐标及其前驱点front入队标记该点为已到达如果该点是出口点：打印路径；结束voidpath(intmaze[m][n];itemmove[8]){SqTypesq[NUM];sq[0].x=1;sq[0].y=1;sq[0].pre=-1;front=rear=0;maze[1,1]=-1;while(front=rear)/*队列不空*/{x=sq[front++].x;y=sq[front++].y;for(v=0;v8;v++){i=x+move[v].x;j=x+move[v].y;if(maze[i][j]==0){rear++;sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front;maze[i][j]=-1;}if(i==m&&j==n){printpath(sq,rear);return1;}}}return0;}2020年2月26日数据结构讲义23入口点入队标记入口点为已到达while队列不空：队头元素front出队对与front相邻的每个点：如果该点可达：将该点坐标及其前驱点front入队标记该点为已到达如果该点是出口点：打印路径；结束voidpath(intmaze[m][n];itemmove[8]){SqTypesq[NUM];sq[0].x=1;sq[0].y=1;sq[0].pre=-1;front=rear=0;maze[1,1]=-1;while(front=rear)/*队列不空*/{x=sq[front++].x;y=sq[front++].y;for(v=0;v8;v++){i=x+move[v].x;j=x+move[v].y;if(maze[i][j]==0){rear++;sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front;maze[i][j]=-1;}if(i==m&&j==n){printpath(sq,rear);return1;}}}return0;}2020年2月26日数据结构讲义24入口点入队标记入口点为已到达while队列不空：队头元素front出队对与front相邻的每个点：如果该点可达：将该点坐标及其前驱点front入队标记该点为已到达如果该点是出口点：打印路径；结束voidpath(intmaze[m][n];itemmove[8]){SqTypesq[NUM];sq[0].x=1;sq[0].y=1;sq[0].pre=-1;front=rear=0;maze[1,1]=-1;while(front=rear)/*队列不空*/{x=sq[front++].x;y=sq[front++].y;for(v=0;v8;v++){i=x+move[v].x;j=x+move[v].y;if(maze[i][j]==0){rear++;sq[rea