第三部分數(shù)據(jù)結(jié)構(gòu)第2章隊列版

1、第二章 隊列 隊列是限定在一端進行插入，另一端進行刪除特殊線性表。就像排隊買東西，排在前面的人買完東西后離開隊伍（刪除），而后來的人總是排在隊伍未尾（插入）。通常把隊列的刪除和插入分別稱為出隊和入隊。允許出隊的一端稱為隊頭，允許入隊的一端稱為隊尾。所有需要進隊的數(shù)據(jù)項，只能從隊尾進入，隊列中的數(shù)據(jù)項只能從隊頭離去。由于總是先入隊的元素先出隊（先排隊的人先買完東西），這種表也稱為先進先出（FIFO）表。 隊列可以用數(shù)組Qm+1來存儲，數(shù)組的上界即是隊列所容許的最大容量。在隊列的運算中需設(shè)兩個指針： head：隊頭指針，指向?qū)嶋H隊頭元素的前一個位置 tail：隊尾指針，指向?qū)嶋H隊尾元素所在的位置

2、一般情況下，兩個指針的初值設(shè)為，這時隊列為空，沒有元素。圖1 (a)畫出了一個由個元素構(gòu)成的隊列，數(shù)組定義Q11。 Qi i=3,4,5,6,7,8 頭指針head2，尾指針tail8。 隊列中擁有的元素個數(shù)為:L=tail-head現(xiàn)要讓排頭的元素出隊，則需將頭指針加。即head=head+1這時頭指針向上移動一個位置，指向Q3，表示Q3已出隊。見圖1 (b)。 如果想讓一個新元素入隊，則需尾指針向上移動一個位置。即tail=tail+1這時Q9入隊，見圖1 (c)。 當隊尾已經(jīng)處理在最上面時，即tail=10，見圖1 (d)，如果還要執(zhí)行入隊操作，則要發(fā)生“上溢”，但實際上隊列中還有三個空

3、位置，所以這種溢出稱為“假溢出”。 克服假溢出的方法有兩種。一種是將隊列中的所有元素均向低地址區(qū)移動，顯然這種方法是很浪費時間的；另一種方法是將數(shù)組存儲區(qū)看成是一個首尾相接的環(huán)形區(qū)域。當存放到n地址后，下一個地址就翻轉(zhuǎn)為。在結(jié)構(gòu)上采用這種技巧來存儲的隊列稱為循環(huán)隊列，見圖2 循環(huán)隊的入隊算法如下： 1、tail=tail+1； 2、若tail=n+1，則tail=1； 3、若head=tail尾指針與頭指針重合了，表示元素已裝滿隊列， 則作上溢出錯處理； 4、否則，Qtail=x，結(jié)束（x為新入出元素）。 隊列和棧一樣，有著非常廣泛的應(yīng)用。 考慮一個分時系統(tǒng)，如果一臺計算機聯(lián)有四個終端，即允許

4、四個用戶同時使用這一臺計算機。那么，計算機系統(tǒng)必須設(shè)立一個隊列， 用以管理各終端用戶使用CPU的請求。當某個用戶要求使用CPU時，相應(yīng)的終端代號就入隊（插入隊尾），而隊頭的終端用戶則是CPU當前服務(wù)的對象。我們考慮最簡單的情況， 對于當前用戶（隊頭），系統(tǒng)每次分配一個為時間片的時間間隔，在一個時間片內(nèi)，如果當前用戶的作業(yè)沒有結(jié)束，則該終端用戶的代號出隊后重新入隊，插入隊尾，等待下一次CPU服務(wù)。如果某個用戶的作業(yè)運行結(jié)束，則先退出，出隊后不再入隊，整個運行過程就是各終端代號不斷地入隊、出隊，CPU 輪流地為（）個終端用戶服務(wù)。由于計算機的運行速度極快，所以，對于每個終端用戶來說，似乎計算機是單

5、獨在為其服務(wù)。 和線性表一樣，棧和隊可以采用鏈表存儲結(jié)構(gòu)，當要實現(xiàn)多個棧共享內(nèi)存或多個隊共享內(nèi)存時，選擇鏈式分配結(jié)構(gòu)則更為合適?！纠?】假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。規(guī)定每個舞曲能有一對跳舞者。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲?，F(xiàn)要求寫一個程序，模擬上述舞伴配對問題。輸入：第一行兩隊的人數(shù) 第二行舞曲的數(shù)目【分析】：設(shè)計兩個隊列分別存放男士和女士。每對跳舞的人一旦跳完后就回到隊尾等待下次被選。如m=4 n=3 k=6【參考程序】#include#includeusing namespa

6、ce 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，取出數(shù)的隊列的頭指針相應(yīng)加1。 (4)重復(2)，(3)直至取出第N項為止?！緟⒖汲绦颉?includeusing namespace std;int a1001,b1001,x=1,fa=1,fb=1,ra=0,rb=0,total=1,n,i; main() p

7、rintf(N=); scanf(%d,&n); while (totalbfb) x=bfb+; else if (afabfb) x=afa+; else x=afa+; fb+; total+; return 0;【例3】設(shè)有個人依次圍成一圈，從第個人開始報數(shù)，數(shù)到第個人出列，然后從出列的下一個人開始報數(shù)，數(shù)到第個人又出列，如此反復到所有的人全部出列為止。設(shè)個人的編號分別為1，2，n，打印出列的順序?！舅惴ǚ治觥?本題我們可以用數(shù)組建立標志位等方法求解，但如果用上數(shù)據(jù)結(jié)構(gòu)中循環(huán)鏈的思想，則更貼切題意，解題效率更高。人圍成一圈，把一人看成一個結(jié)點，人之間的關(guān)系采用鏈接方式，即每一結(jié)點有一個

8、前繼結(jié)點和一個后繼結(jié)點，每一個結(jié)點有一個指針指向下一個結(jié)點，最后一個結(jié)點指針指向第一個結(jié)點。這就是單循環(huán)鏈的數(shù)據(jù)結(jié)構(gòu)。當人出列時，將結(jié)點的前繼結(jié)點指針指向結(jié)點的后繼結(jié)點指針，即把結(jié)點驅(qū)出循環(huán)鏈。1、建立循環(huán)鏈表。 當用數(shù)組實現(xiàn)本題鏈式結(jié)構(gòu)時，數(shù)組ai作為指針變量來使用，ai存放下一個結(jié)點的位置。設(shè)立指針j指向當前結(jié)點，則移動結(jié)點過程為j=aj，當數(shù)到m時，m結(jié)點出鏈，則aj=aaj。 當直接用鏈來實現(xiàn)時，則比較直觀，每個結(jié)點有兩個域：一個數(shù)值域，一個指針域，當數(shù)到m時，m出鏈，將m結(jié)點的前繼結(jié)點指針指向其后繼結(jié)點；2、設(shè)立指針，指向當前結(jié)點，設(shè)立計數(shù)器，計數(shù)數(shù)到多少人；3、沿鏈移動指針，每移動

9、一個結(jié)點，計數(shù)器值加，當計數(shù)器值為時， 則結(jié)點出鏈，計數(shù)器值置為。4、重復，直到n個結(jié)點均出鏈為止?！緟⒖汲绦颉坑脭?shù)組實現(xiàn)鏈式結(jié)構(gòu)#includeusing namespace std;const int n=10,m=4; /設(shè)有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人，形成一個環(huán) while (pn) /n個人均出隊為止 while(km) /報數(shù),計數(shù)器加1 j=aj; k+; printf(%d ,aj); p+; /數(shù)到m,此人出隊,計數(shù)器置1 a

10、j=aaj; k=1; return 0;【例4】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。如:陣列 4 10 10345605002045600671 有4個細胞?！舅惴ǚ治觥?從文件中讀入m*n矩陣陣列，將其轉(zhuǎn)換為bool矩陣存入b數(shù)組中； 沿b數(shù)組矩陣從上到下，從左到右，找到遇到的第一個細胞； 將細胞的位置入隊h，并沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的位置b數(shù)組置為flase； 將h隊的隊頭出隊，沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的位置b數(shù)組置為flase； 重復4，直

11、至h隊空為止，則此時找出了一個細胞； 重復2，直至矩陣找不到細胞； 輸出找到的細胞數(shù)。#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+) /在矩陣中尋找細胞 for (j=0;jm;j+) if (bij) bij=0; f(i,j);

12、 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】最少步數(shù)【問題描述】 在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個（100*100）的圍棋盤上任選兩點A、B，A點放上黑

13、子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個走黑馬，一個走白馬。誰用最少的步數(shù)走到左上角坐標為(1,1)的點時，誰獲勝。現(xiàn)在他請你幫忙，給你A、B兩點的坐標，想知道兩個位置到（1,1）點可能的最少步數(shù)?！据斎霕永?12 16 18 10【輸出樣例】 8 9【算法分析】 由于A、B兩點是隨機輸入的，因此無法找到計算最少步數(shù)的數(shù)學規(guī)律，只能通過廣度優(yōu)先搜索的辦法求解。 1、確定出發(fā)點從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從(x,y)至棋盤上所有可達點的最少步數(shù)。而問題中要求的是黑馬所在的（x1，y1）和白馬所在（x2，y2）到達 (1,1) 目標點的最

14、少步數(shù)。雖然兩條路徑的起點不一樣，但是它們的終點卻是一樣的。如果我們將終點(1,1)作為起點，這樣只需要一次廣度優(yōu)先搜索便可以得到（x1，y1）和（x2，y2）到達(1,1)的最少步數(shù)。2、數(shù)據(jù)結(jié)構(gòu)設(shè)queue隊列，存儲從(1,1)可達的點（queuek1.2）以及到達該點所需要的最少步數(shù)（queuek3）（0k192+1）。隊列的首指針為open，尾指針為closed。初始時，queue中只有一個元素為(1,1)，最少步數(shù)為0。S記錄(1,1)到每點所需要的最少步數(shù)。顯然，問題的答案是sx1y1和sx2y2。初始時，s11為0，除此之外的所有元素值設(shè)為-1。dx、dy移動后的位置增量數(shù)組。馬

15、有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方向上的位置增量存入常量數(shù)組dxi、dyi中（0i11）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;3、約束條件 不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴展

16、過，且(1,1)到達其最少需要0步”。這看上去是荒謬的，但可以簡單而有效地避免馬再次落入這些界外點。該點在以前的擴展中沒有到達過。如果曾經(jīng)到達過，則根據(jù)廣度優(yōu)先搜索的原理，先前到達該點所需的步數(shù)一定小于當前步數(shù)，因此完全沒有必要再擴展下去。由此得出，馬的跳后位置（x,y）是否可以入隊的約束條件是sxy04、算法流程#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 s1011

17、01,que100004=0,x1,y1,x2,y2; memset(s,0 xff,sizeof(s); /s數(shù)組的初始化 int head=1,tail=1; /初始位置入隊 que11=1;que12=1;que13=0; cinx1y1x2y2; /讀入黑馬和白馬的出發(fā)位置 while(head=tail) /若隊列非空，則擴展隊首結(jié)點 for(int d=0;d0&y0) if(sxy=-1) /若（x,y）滿足約束條件 sxy=quehead3+1; /計算(1,1)到(x,y)的最少步數(shù) tail+; /（1,1）至（x,y）的最少步數(shù)入隊 quetail1=x; quetail

18、2=y; quetail3=sxy; if(sx1y10&sx2y20) /輸出問題的解 coutsx1y1endl; coutsx2y2endl; system(pause); 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

19、 0 0 0 0 0【樣例輸出】area.out151、編程計算由“*”號圍成的下列圖形的面積。面積計算方法是統(tǒng)計*號所圍成的閉合曲線中水平線和垂直線交點的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個點，因此面積為15?！旧蠙C練習】2、奇怪的電梯(lift.cpp)【問題描述】大樓的每一層樓都可以停電梯，而且第i層樓（1=i=N）上有一個數(shù)字Ki（0=Ki=N）。電梯只有四個按鈕：開，關(guān)，上，下。上下的層數(shù)等于當前樓層上的那個數(shù)字。當然，如果不能滿足要求，相應(yīng)的按鈕就會失靈。例如：3 3 1 2 5代表了Ki（K1=3,K2=3,），從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？【輸入格式】lift.in輸入文件共有二行，第一行為三個用空格隔開的正整數(shù)，表示N,A,B(1N200, 1A,BN)，第二行為N個用空格隔開的正整數(shù)，表示Ki。【輸出格式】lift.out輸出文件僅