第2章队列(C++版)

《第2章队列(C++版)》由会员分享，可在线阅读，更多相关《第2章队列(C++版)（23页珍藏版）》请在文档大全上搜索。

1、第二章第二章 队列队列 队列是限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。 队列可以用数组Qm+1来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针： head：队头指针，指向实际队头元素的前一个位置 tail：队尾指针，指向实际队尾元素所

2、在的位置 一般情况下，两个指针的初值设为，这时队列为空，没有元素。图1 (a)画出了一个由个元素构成的队列，数组定义Q11。 Qi i=3,4,5,6,7,8 头指针head2，尾指针tail8。 队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加。即head=head+1这时头指针向上移动一个位置，指向Q3，表示Q3已出队。见图1 (b)。 如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q9入队，见图1 (c)。 当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生“上溢”，但实际上队列中

3、还有三个空位置，所以这种溢出称为“假溢出”。 克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为。在结构上采用这种技巧来存储的队列称为循环队列，见图2 循环队的入队算法如下： 1、tail=tail+1； 2、若tail=n+1，则tail=1； 3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理； 4、否则，Qtail=x，结束（x为新入出元素）。 队列和栈一样，有着非常广泛的应用。 考虑一个分时系统，如果一台计算机联有四个终

4、端，即允许四个用户同时使用这一台计算机。那么，计算机系统必须设立一个队列， 用以管理各终端用户使用CPU的请求。当某个用户要求使用CPU时，相应的终端代号就入队（插入队尾），而队头的终端用户则是CPU当前服务的对象。我们考虑最简单的情况， 对于当前用户（队头），系统每次分配一个为时间片的时间间隔，在一个时间片内，如果当前用户的作业没有结束，则该终端用户的代号出队后重新入队，插入队尾，等待下一次CPU服务。如果某个用户的作业运行结束，则先退出，出队后不再入队，整个运行过程就是各终端代号不断地入队、出队，CPU 轮流地为（）个终端用户服务。由于计算机的运行速度极快，所以，对于每个终端用户来说，似乎

5、计算机是单独在为其服务。 和线性表一样，栈和队可以采用链表存储结构，当要实现多个栈共享内存或多个队共享内存时，选择链式分配结构则更为合适。【例例1】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数 第二行舞曲的数目【分析】：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=4 n=3 k=6【参考程序参考程序】#include#includeusi

6、ng namespace std;int a10001,b10001,k1=1,k,i,f1=1,r1,f2=1,r2;main() int m,n; cinmn; for (i=1;i=m;i+) ai=i; for (i=1;ik; r1=m; r2=n; while (k1bhb (B)aha=bhb (C)ahabhb 将比较的小者取出送入X，取出数的队列的头指针相应加1。 (4)重复(2)，(3)直至取出第N项为止。【参考程序】【参考程序】#includeusing namespace std;int a1001,b1001,x=1,fa=1,fb=1,ra=0,rb=0,total

7、=1,n,i; main() printf(N=); scanf(%d,&n); while (totalbfb) x=bfb+; else if (afabfb) x=afa+; else x=afa+; fb+; total+; return 0;【例例3】设有个人依次围成一圈，从第个人开始报数，数到第个人出列，然后从出列的下一个人开始报数，数到第个人又出列，如此反复到所有的人全部出列为止。设个人的编号分别为1，2，n，打印出列的顺序。【算法分析算法分析】 本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。人围成一圈，把一人看成一

8、个结点，人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当人出列时，将结点的前继结点指针指向结点的后继结点指针，即把结点驱出循环链。1、建立循环链表。 当用数组实现本题链式结构时，数组ai作为指针变量来使用，ai存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j=aj，当数到m时，m结点出链，则aj=aaj。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；2、设立指针，指向当前结点，设

9、立计数器，计数数到多少人；3、沿链移动指针，每移动一个结点，计数器值加，当计数器值为时， 则结点出链，计数器值置为。4、重复，直到n个结点均出链为止。【参考程序】用数组实现链式结构#includeusing namespace std;const int n=10,m=4; /设有10个人,报到4的人出列int an+1,j=n,k=1,p=0;main() for (int i=1;in;i+) ai=i+1; /建立链表 an=1; /第n人指向第1人，形成一个环 while (pn) /n个人均出队为止 while(km) /报数,计数器加1 j=aj; k+; printf(%d ,a

10、j); p+; /数到m,此人出队,计数器置1 aj=aaj; k=1; return 0;【例例4】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列 4 100234500067103456050020456006710000000089有4个细胞。【算法分析】 从文件中读入m*n矩阵阵列，将其转换为bool矩阵存入b数组中； 沿b数组矩阵从上到下，从左到右，找到遇到的第一个细胞； 将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置b数组置为flase； 将h队的队头出队，沿

11、其上、下、左、右四个方向上的细胞位置入队，入队后的位置b数组置为flase； 重复4，直至h队空为止，则此时找出了一个细胞； 重复2，直至矩阵找不到细胞； 输出找到的细胞数。#includeusing namespace std;char a5151;bool b5151;int n,m,i,j,s=0,c5=1,0,-1,0,1;void f(int,int);main() scanf(%d%dn,&n,&m); for (i=0;in;i+) gets(ai); for (i=0;in;i+) for (j=0;jm;j+) bij=aij-0; for (i=0;in;i

12、+) /在矩阵中寻找细胞 for (j=0;jm;j+) if (bij) bij=0; f(i,j); s+; printf(%d,s); return 0;void f(int x,int y) for (int i=0;i-1&x+ci-1&y+ci+1m&bx+ciy+ci+1) /沿细胞的上下左右四个方向搜索细胞 bx+ciy+ci+1=0; f(x+ci,y+ci+1); 【例例2-5】最少步数最少步数【问题描述问题描述】 在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走

13、，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。【输入样例输入样例】 12 16 18 10【输出样例输出样例】 8 9【算法分析算法分析】 由于A、B两点是随机输入的，因此无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。 1、确定出发点、确定出发

14、点从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达 (1,1) 目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。2、数据结构、数据结构设queue队列，存储从(1,1)可达的点（queuek1.2）以及到达该点所需要的最少步数（queuek3）（0k192+1）。队列的首指针为open，尾指针为closed。初始时，queue中只有一个元素为

15、(1,1)，最少步数为0。S-记录(1,1)到每点所需要的最少步数。显然，问题的答案是sx1y1和sx2y2。初始时，s11为0，除此之外的所有元素值设为-1。dx、dy移动后的位置增量数组。马有12种不同的扩展方向：马走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我们将i方向上的位置增量存入常量数组dxi、dyi中（0i11）int dx12=-2,-2,-1,1,2,2,2,2,1,-1,-2,-2,

16、 dy12=-1,-2,-2,-2,-2,-1,1,2,2,2,2,1;3、约束条件、约束条件 不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且(1,1)到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。由此得出，马的跳后位置（x,y）是否可以入队的约束条件是sxy0马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)4、算法

17、流程、算法流程#include #include #include using namespace std;int dx12=-2,-2,-1,1,2,2,2,2,1,-1,-2,-2, dy12=-1,-2,-2,-2,-2,-1,1,2,2,2,2,1;int main() int s101101,que100004=0,x1,y1,x2,y2; memset(s,0 xff,sizeof(s); /s数组的初始化数组的初始化 int head=1,tail=1; /初始位置入队初始位置入队 que11=1;que12=1;que13=0; cinx1y1x2y2; /读入黑马和白马的出发

18、位置读入黑马和白马的出发位置 while(head=tail) /若队列非空，则扩展队首结点若队列非空，则扩展队首结点 for(int d=0;d0&y0) if(sxy=-1) /若（若（x,y）满足约束条件）满足约束条件 sxy=quehead3+1; /计算计算(1,1)到到(x,y)的最少步数的最少步数 tail+; /（1,1）至（x,y）的最少步数入队 quetail1=x; quetail2=y; quetail3=sxy; if(sx1y10&sx2y20) /输出问题的解 coutsx1y1endl; coutsx2y2endl; system(pause);

19、 return 0; head+; 【样例输入样例输入】area.in0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 0 0 00 0 0 0 1 0 0 1 0 00 0 0 0 0 1 0 0 1 00 0 1 0 0 0 1 0 1 00 1 0 1 0 1 0 0 1 00 1 0 0 1 1 0 1 1 00 0 1 0 0 0 0 1 0 00 0 0 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 0【样例输出样例输出】area.out151、编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。

20、如下图所示，在10*10的二维数组中，有“*”围住了15个点，因此面积为15。【上机练习】2、奇怪的电梯、奇怪的电梯(lift.cpp)【问题描述问题描述】大楼的每一层楼都可以停电梯，而且第i层楼（1=i=N）上有一个数字Ki（0=Ki=N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki（K1=3,K2=3,），从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？【输入格式输入格式】lift.in输入文件共有二行，第一行为三个用

21、空格隔开的正整数，表示N,A,B(1N200, 1A,BN)，第二行为N个用空格隔开的正整数，表示Ki。【输出格式输出格式】lift.out输出文件仅一行，即最少按键次数,若无法到达，则输出-1。【输入样例输入样例】5 1 53 3 1 2 5【输出样例输出样例】33、产生数、产生数(Produce.cpp)【问题描述问题描述】给出一个整数n（n=2000）和k个变换规则（k15）。规则： 1个数字可以变换成另1个数字； 规则中，右边的数字不能为零。例如：n=234，k=2规则为2 53 6上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数

22、。求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。【输入格式输入格式】Produce.innkx1 y1x2 y2 xn yn【输出格式输出格式】Produce.out格式为一个整数（满足条件的整数个数）。【输入样例输入样例】23422 53 6【输出样例输出样例】44、家庭问题、家庭问题【问题描述问题描述】有n个人，编号为1,2,n，另外还知道存在K个关系。一个关系的表达为二元组（，）形式，表示，为同一家庭的成员。当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？例如：n6，k3，三个关系为（1,2），(1,3)，(4,5)此时，6个人组成三个家庭，即：1,2,3为一个家庭，4,5为一个家庭，6单独为一个家庭，第一个家庭的人数为最多。【输入格式输入格式】文件的第一行为n,k二个整数（1n100）（用空格分隔）接下来的k行，每行二个整数（用空格分隔）表示关系【输出格式输出格式】二个整数（分别表示家庭个数和最大家庭人数）【输入样例输入样例】6 31 21 34 5【输出样例输出样例】3 3