1、隊(duì)列及其應(yīng)用1隊(duì)列所謂隊(duì)列,就是允許在一端進(jìn)行插入,在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾。隊(duì)列是一種先進(jìn)先出(FIFO)的線性表隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列必須構(gòu)造成循環(huán)隊(duì)列的形式,否則會(huì)出現(xiàn)“假溢出” #define maxsize 隊(duì)列最大容量； struct line int amaxsize-1; int rear, front;/front隊(duì)頭;rear隊(duì)尾 2隊(duì)列操作舉例食堂排隊(duì)排隊(duì)買票吸管里的飲料作用：維持順序數(shù)組實(shí)現(xiàn)：元素a0.maxn-1，隊(duì)首front，隊(duì)尾rear入隊(duì)：rear+; arear=x;出隊(duì)：ele=afront;front+;隊(duì)空條件：f

2、rontrear問題：出隊(duì)的元素還在數(shù)組里，不是很浪費(fèi)嗎？循環(huán)隊(duì)列把隊(duì)列看成環(huán)行的，則入隊(duì)：rear= (rear + 1)%maxn; 不定義為a1.maxn的原因出隊(duì)：front= (front + 1) %maxn;可能存在隊(duì)滿的情況：條件也是front rear3用隊(duì)列實(shí)現(xiàn)圖的寬度優(yōu)先搜索算法 我們要對(duì)圖進(jìn)行分層次遍歷,遍歷的序列為1，2，7， 寬度優(yōu)先搜索算法遍歷序列圖4分析 要對(duì)圖進(jìn)行按層次遍歷，我們可采用逐層標(biāo)號(hào)法進(jìn)行。方法如下：第一步：將初始點(diǎn)放入隊(duì)列，并將該點(diǎn)設(shè)置為已標(biāo)號(hào)的點(diǎn)。第二步：從隊(duì)列中取出已標(biāo)號(hào)而未檢查的點(diǎn)，訪問該點(diǎn)的所有鄰接頂點(diǎn)，放入隊(duì)列，并進(jìn)行標(biāo)號(hào)，該頂點(diǎn)為已檢查

3、的點(diǎn)。第三步：檢查隊(duì)列中是否還有未標(biāo)號(hào)的點(diǎn)，若有，轉(zhuǎn)第二步，否則，圖便歷完畢，算法終止。5void bfs(v); /從v開始寬度有先遍歷圖 inicycque(q); /初始化隊(duì)列qq.encycque(v); vistedv:=true; /初始點(diǎn)v放入隊(duì)列,并標(biāo)號(hào)while(! q.empty) /直到隊(duì)列不為空while(v的鄰接頂點(diǎn)存在) q.encycque(v的鄰接頂點(diǎn));vistedv的鄰接頂點(diǎn):=true; q.dlcycque(v);6已知隊(duì)列(13,2,11,34,41,77,5,7,18,26,15),第一個(gè)進(jìn)入隊(duì)列的元素是13,則第五個(gè)出隊(duì)列的元素是()。(NOIP9

4、) A)5 B)41 C)77 D)13 E)18 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)閑 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,則棧S的容量至少應(yīng)該為( )。(NOIP8) A)2 B)3 C)4 D)5隊(duì)列練習(xí)試題7【培訓(xùn)試題】細(xì)胞統(tǒng)計(jì)1611Description：一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。Input：第一行為整數(shù)m,n(m = 100,n = 100分別表示

5、m行和n列) ，以下為一個(gè)mxn的矩陣 Output：細(xì)胞的個(gè)數(shù)023450006710345605002045600671898算法步驟：1、讀入m*n矩陣,將其轉(zhuǎn)換為0、1矩陣存入pic數(shù)組中；2、沿pic數(shù)組矩陣從上到下,從左到右,找到遇到的第一個(gè)細(xì)胞；將細(xì)胞的位置入隊(duì)h,并沿其上、下、左、右四個(gè)方向搜索,如果遇到細(xì)胞(picij=1)則將其位置入隊(duì),入隊(duì)后的位置picij數(shù)組置為0；3、將h隊(duì)的隊(duì)頭出隊(duì),沿其上、下、左、右四個(gè)方向上搜索,如果遇到細(xì)胞則將其位置入隊(duì),入隊(duì)后的位置pic數(shù)組置為0；4、重復(fù)3,直至h隊(duì)空為止,則此時(shí)找出了一個(gè)細(xì)胞；5、重復(fù)2,直至矩陣找不到細(xì)胞；6、輸出找

6、到的細(xì)胞數(shù)。9void work(int x,int y) int first,last,i,h,ll; first=1;last=1;total+;hang1=x;lie1=y; while(firstlast) for(i=0;i0&h0&ll=n&ahll) last+; hanglast=h;lielast=ll;/入隊(duì) ahll=false; first+;/出隊(duì) int main() init(); for(i=1;i=m;i+) for(j=1;j=n;j+) if(aij)work(i,j); couttotal1 且 m,n15)。Output 輸出所有可能路路徑條數(shù)，如果沒

7、有一條可行的路則輸出。 Sample Input 5 6 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 5 6 Sample Output：12 11【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的走法總是一定的，如中國(guó)象棋中馬走“日”。有一位小學(xué)生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時(shí)喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個(gè)（100*100）的圍棋盤上任選兩點(diǎn)A、B，A點(diǎn)放上黑子，B點(diǎn)放上白子，代表兩匹馬。棋子可以按“日

8、”字走，也可以按“田”字走，倆人一個(gè)走黑馬，一個(gè)走白馬。誰用最少的步數(shù)走到左上角坐標(biāo)為(1,1)的點(diǎn)時(shí)，誰獲勝。現(xiàn)在他請(qǐng)你幫忙，給你A、B兩點(diǎn)的坐標(biāo)，想知道兩個(gè)位置到（1,1）點(diǎn)的可能最少步數(shù)。輸入： 12 16 18 10輸出： 8 9121、確定出發(fā)點(diǎn) 從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從(x,y)至棋盤上所有可達(dá)點(diǎn)的最少步數(shù)。而問題中要求的是黑馬所在的（x1，y1）和白馬所在（x2，y2）到達(dá) (1,1) 目標(biāo)點(diǎn)的最少步數(shù)。雖然兩條路徑的起點(diǎn)不一樣，但是它們的終點(diǎn)卻是一樣的。如果我們將終點(diǎn)(1,1)作為起點(diǎn)，這樣只需要一次廣度優(yōu)先搜索便可以得到（x1，y1）和（x2，y2）到

9、達(dá)(1,1)的最少步數(shù)。2、數(shù)據(jù)結(jié)構(gòu) 設(shè)queue隊(duì)列，存儲(chǔ)從(1,1)可達(dá)的點(diǎn)（queuek1.2）以及到達(dá)該點(diǎn)所需要的最少步數(shù)（queuek3）（0k192+1）。隊(duì)列的首指針為open，尾指針為closed。初始時(shí)，queue中只有一個(gè)元素為(1,1)，最少步數(shù)為0。 S記錄(1,1)到每點(diǎn)所需要的最少步數(shù)。顯然，問題的答案是sx1y2和sx2y2。初始時(shí)，s11為0，除此之外的所有元素值設(shè)為-1。13 dx、dy移動(dòng)后的位置增量數(shù)組。馬有12種不同的擴(kuò)展方向：馬走“日”：(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

10、,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中（1i12） 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、約束條件 不能越出界外。由于馬的所有可能的落腳點(diǎn)s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴(kuò)展過，且(1,1)到達(dá)其最少需要0步”。這看上去是荒謬的，但可以簡(jiǎn)單而有效地避免馬再次落入這些界外點(diǎn)。 該點(diǎn)在以前的擴(kuò)展中沒有到達(dá)過。如果曾經(jīng)到達(dá)過

11、，則根據(jù)廣度優(yōu)先搜索的原理，先前到達(dá)該點(diǎn)所需的步數(shù)一定小于當(dāng)前步數(shù)，因此完全沒有必要再擴(kuò)展下去。 由此得出，馬的跳后位置（x,y）是否可以入隊(duì)的約束條件是sxy014海上葬禮 有一片被大海包圍的群島，島上居住著一個(gè)食人部族。很多年前部落里有一位巫師接受了神的召喚跳入海中，從此，那一片海域就被打上了神的烙印，被這片海域所包圍的陸地也被賦予了神圣的意義（包圍關(guān)系滿足傳遞性，即海域A包圍了島B，島B包圍了海域C，而海域C中包含了島D，則我們說海域A也包含了島D）。從那以后，部落里的巫師死后都必須葬在這片神圣海域所包圍的島上，而且每一個(gè)島都只能埋葬一位巫師（否則就會(huì)被視為對(duì)神的不敬，從而給部族帶來災(zāi)難

12、）?，F(xiàn)在給你群島的地圖和最初那位巫師跳海的地方，請(qǐng)你計(jì)算一下最多可以埋葬多少巫師。 15地圖是一個(gè)n*m的字符矩陣，#代表陸地，.代表海洋。連通的一片陸地為一個(gè)島，連通的一片海洋為一個(gè)海域。其中，陸地從上、下、左、右4個(gè)方向連通，海洋從上、下、左、右、左上、左下、右上、右下8個(gè)方向連通。如下圖。 圖3中有4個(gè)島，2片海域。如果在A處落水，則落水的海域包圍了除右上、左下兩個(gè)頂角外的3個(gè)島嶼；如果在B處落水，則只包含了中間的2個(gè)島。數(shù)據(jù)范圍是n,m1000kb，無法滿足題設(shè)的空間限制。在這種情況下，我們考慮深度優(yōu)先遍歷的非遞歸過程。17分析首先給8個(gè)方向矢量定一個(gè)序號(hào)，用一個(gè)常量數(shù)組進(jìn)行記錄：CO

13、NST d :array1.8, 1.2of shortint=(-1, -1), (0, -1), (-1, 1), (0, 1), (1, 1), (0, 1), (1, -1), (0, -1);建立一個(gè)順序棧S，棧的每個(gè)元素代表深度優(yōu)先遍歷路徑中的一個(gè)結(jié)點(diǎn)位置，記錄該位置當(dāng)前擴(kuò)展到的方向矢量的序號(hào)，再用一對(duì)變量Current_x，Current_y記錄棧頂元素所代表的具體位置，就可以以非遞歸的方式完成深度優(yōu)先遍歷了。 18PROC Dfs(startX, startY : integer); 初始化棧 Current_xstartX Current_ystartY top1; stop

14、0; 初始結(jié)點(diǎn)入棧 標(biāo)記(Current_x, Current_y)為已擴(kuò)展結(jié)點(diǎn) while top0 do 【 stopsttop+1 if （stop0 then 【 Current_xCurrent_x dstop, 1 Current_yCurrent_y dstop, 2 】 】 】ENDP 19【培訓(xùn)試題】最大子序和問題描述 輸入一個(gè)長(zhǎng)度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的長(zhǎng)度不超過M的子序列，使得這個(gè)序列的和最大。20最大子序和例如： 序列 1， -3， 5， 1， -2， 3當(dāng)M=2或3時(shí)S=5+1=6當(dāng)M=4時(shí)S=5+1+(-2)+3=7數(shù)據(jù)范圍: 50%的數(shù)

15、據(jù)N,M=1000 100%的數(shù)據(jù)N,M=2000021一個(gè)簡(jiǎn)化的問題序列的最大連續(xù)和 輸入一個(gè)長(zhǎng)度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個(gè)序列的和最大。 和原問題相比沒有M這個(gè)序列長(zhǎng)度的限制！22分析： 設(shè) F(i)表示以第i個(gè)數(shù)結(jié)尾的最大連續(xù)和 以第i個(gè)數(shù)結(jié)尾的最大連續(xù)和序列，可能存在兩種選擇： 情形一：只包含Ai 情形二：包含Ai和以Ai-1結(jié)尾的最大連續(xù)和序列動(dòng)態(tài)規(guī)劃：轉(zhuǎn)移方程： F(i)=maxAi , F(i-1)+Ai邊界：F(1)=A1要求的結(jié)果為maxF(i)|1=i=n該算法的時(shí)間復(fù)雜度為O(n)一個(gè)簡(jiǎn)化的問題23枚舉算法設(shè) F(i)為以Ai結(jié)尾

16、長(zhǎng)度不超過M的最大子序和 對(duì)于每個(gè)F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時(shí)間復(fù)雜度為O(n2)問題初步分析24簡(jiǎn)化方程25隊(duì)列優(yōu)化 在算法中，考慮用隊(duì)列來維護(hù)決策值S(i-k)。每次只需要在隊(duì)首刪掉S(i-m-1)，在隊(duì)尾添加S(i-1) 。但是取最小值操作還是需要O(n)時(shí)間復(fù)雜度的掃描。 考察在添加S(i-1)的時(shí)候，設(shè)現(xiàn)在隊(duì)尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出隊(duì)。若此時(shí)S(i-1)=S(k)，則S(k)這個(gè)決策永遠(yuǎn)不會(huì)在以后用到，可以將S(k)從隊(duì)尾刪除掉（此時(shí)隊(duì)列的尾部形成了一個(gè)類似棧的結(jié)構(gòu)）26隊(duì)列優(yōu)化 同理，若隊(duì)列中兩個(gè)元素S(i)和S(j)，若i=S(j)，則我們可以刪掉S(i)（因?yàn)镾(i)永遠(yuǎn)不會(huì)被用到）。此時(shí)的隊(duì)列中的元素構(gòu)成了一個(gè)單調(diào)遞增的序列，即：S1S2S3Sk27 我們來整理在求F(i)的時(shí)候，用隊(duì)列維護(hù)