搜索
第二章队列队列是限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。队列可以用数组Q[m+1]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tail：队尾指针，指向实际队尾元素所在的位置一般情况下，两个指针的初值设为０，这时队列为空，没有元素。图1(a)画出了一个由６个元素构成的队列，数组定义Q[11]。Q[i]i=3,4,5,6,7,8头指针head＝2，尾指针tail＝8。队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加１。即head=head+1这时头指针向上移动一个位置，指向Q[3]，表示Q[3]已出队。见图1(b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q[9]入队，见图1(c)。当队尾已经处理在最上面时，即tail=10，见图1(d)，如果还要执行入队操作，则要发生“上溢”，但实际上队列中还有三个空位置，所以这种溢出称为“假溢出”。克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为１。在结构上采用这种技巧来存储的队列称为循环队列，见图2循环队的入队算法如下：1、tail=tail+1；2、若tail=n+1，则tail=1；3、若head=tail尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理；4、否则，Q[tail]=x，结束（x为新入出元素）。队列和栈一样，有着非常广泛的应用。考虑一个分时系统，如果一台计算机联有四个终端，即允许四个用户同时使用这一台计算机。那么，计算机系统必须设立一个队列，用以管理各终端用户使用CPU的请求。当某个用户要求使用CPU时，相应的终端代号就入队（插入队尾），而队头的终端用户则是CPU当前服务的对象。我们考虑最简单的情况，对于当前用户（队头），系统每次分配一个为时间片的时间间隔，在一个时间片内，如果当前用户的作业没有结束，则该终端用户的代号出队后重新入队，插入队尾，等待下一次CPU服务。如果某个用户的作业运行结束，则先退出，出队后不再入队，整个运行过程就是各终端代号不断地入队、出队，CPU轮流地为ｎ（ｎ≤４）个终端用户服务。由于计算机的运行速度极快，所以，对于每个终端用户来说，似乎计算机是单独在为其服务。和线性表一样，栈和队可以采用链表存储结构，当要实现多个栈共享内存或多个队共享内存时，选择链式分配结构则更为合适。【例1】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数第二行舞曲的数目【分析】：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=4n=3k=6【参考程序】#includecstdio#includeiostreamusingnamespacestd;inta[10001],b[10001],k1=1,k,i,f1=1,r1,f2=1,r2;main(){intm,n;cinmn;for(i=1;i=m;i++)a[i]=i;for(i=1;i=n;i++)b[i]=i;cink;r1=m;r2=n;while(k1=k){printf(%d%d\n,a[f1],b[f2]);r1++;a[r1]=a[f1];f1++;//第一次a[m+1]=a[1]=1,第二次a[m+2]=a[2]=2,如此循环r2++;b[r2]=b[f2];f2++;//第一次b[n+1]=b[1]=1,第二次b[n+2]=b[2]=2,如此循环。k1++;}return0;}【例2】Blah数集【3.4数据结构之队列2729】大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：(1)a是集合Ba的基，且a是Ba的第一个元素；(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；(3)没有其他元素在集合Ba中了。现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？输入:输入包括很多行，每行输入包括两个数字，集合的基a(1=a=50))以及所求元素序号n(1=n=1000000)输出:对于每个输入，输出集合Ba的第n个元素值样例输入:1100285437样例输出:418900585分析：题目要求输出集合中第n小的数，我们可以按照从小到大的顺序把序列中的前n个数计算出来，注意数集中除了第一个数a以外，其余每一个数y一定可以表示成2x+1或者3x+1的形式，其中x是数集中某一个数。因此除了第一数a以外，可以把数集q[]的所有数分成两个子集，一个是用2x+1来表示的数的集合1，另一个是用3x+1来表示的数的集合2，两个集合要保持有序非常容易，只需用两个指针two和three来记录，其中two表示集合1下一个要产生的数是由q[two]*2+1得到，three表示集合2下一个要产生的数是由q[three]*3+1得到。接下来比较q[two]*2+1和q[three]*3+1的大小关系：(1)q[two]*2+1q[three]*3+1：如果q[two]*2+1与q[rear-1]不等，则把q[two]*2+1加到数集中，即：q[rear++]=q[two]*2+1；two++；如果q[two]*2+1与q[rear-1]相等，因为集合的唯一性，q[two]*2+1不能加入数集，但two同样要加1。(2)q[two]*2+1=q[three]*3+1：处理方法同上。如此循环直到产生出数集的第n个数。【参考程序】#includeiostream#includealgorithmusingnamespacestd;constintN=1000100;longlongq[N];inta,n;voidwork(inta,intn){intrear=2;q[1]=a;inttwo=1,three=1;while(rear=n){longlongt1=q[two]*2+1,t2=q[three]*3+1;intt=min(t1,t2);if(t1t2)two++;elsethree++;if(t==q[rear-1])continue;q[rear++]=t;}coutq[n]endl;}intmain(){while(cinan)work(a,n);return0;}【例3】设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。【算法分析】本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。1、建立循环链表。当用数组实现本题链式结构时，数组a[i]作为指针变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j=a[j]，当数到m时，m结点出链，则a[j]=a[a[j]]。当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；2、设立指针，指向当前结点，设立计数器，计数数到多少人；3、沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时，则ｍ结点出链，计数器值置为１。4、重复３，直到n个结点均出链为止。【参考程序】用数组实现链式结构#includecstdiousingnamespacestd;constintn=10,m=4;//设有10个人,报到4的人出列inta[n+1],j=n,k=1,p=0;main(){for(inti=1;in;i++)a[i]=i+1;//建立链表a[n]=1;//第n人指向第1人，形成一个环while(pn)//n个人均出队为止{while(km)//报数,计数器加1{j=a[j];k++;}printf(%d,a[j]);p++;//数到m,此人出队,计数器置1a[j]=a[a[j]];k=1;}return0;}【例4】连通块描述:一个n*m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。输入:第一行两个整数n,m(1=n,m=100)，表示一个n*m的方格图。接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。输出:一行一个整数ans，表示图中有ans个黑色格子连通块。样例输入33111010101样例输出3分析：我们可以枚举每个格子，若它是被涂黑的，且它不属于已经搜索过的联通块，则由它开始，扩展搜索它所在的联通块，并把联通块里的所有黑色格子标记为已搜索过。如何扩展搜索一个联通块呢？我们用一个搜索队列，存储要搜索的格子。每次取出队首的格子，对其进行四连通扩展，若有黑格子，将其加入队尾,扩展完就把该格子删除。当队列为空时，一个联通块就搜索完了。如样例所对应的方格图如下所示：现在我们以样例为例模拟出这个方格图的搜索顺序：①将(1,1)加入队列，(1,1)表示左上角这个格子，当前队列为：{(1,1)}，联通块加1等于1。②取出队首的(1,1)，标记为已搜索并对其进行四连通扩展，扩展出(1,2)，删除(1,1)队列变为：{(1,2)}。③取出队首的(1,2)，标记为已搜索并对其进行四连通扩展，扩展到了(1,1)，(1,3)，(2,2)，(1,1)已经被标记搜索过，所以只将(1,3)，(2,2)加入队列，删除队首(1,2),队列变为：{(1,3)，(2,2)}。④取出队首的(1,3)，没有扩展出新格子，删除队首队列变为：{(2,2)}⑤取出队首的(2,2)，没有扩展出新格子，队列变为{}。完成以(1,1)开始的搜索。⑥将(3,1)加入队列，队列变为：{(3,1)}，联通块数加1变为2。⑦取出队首的(3,1)，没有扩展出新格子，删除队首队列变为{}。完成以(3,1)开始的搜索。⑧将(3,3)加入队列，队列变为：{(3,3)}，联通块数加1变为3。⑨取出队首的(3,3)，没有扩展出新格子，删除队首队列变为{}。完成以(3,3)开始的搜索。无法再加入新的元素，程序结束。【参考程序】#includeiostreamusingnamespacestd;constintN=110;constintflag[4][2]={{0,1},{0,-1},{1,0},{-1,0}};inta[N][N],queue[N*N][2];intn,m,ans;boolp[N][N];voidbfs(intx,inty){intfront=0,rear=2;queue[1][0]=x,queue[1