數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用

數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用第一頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第1頁(yè)。隊(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)“假溢出”#definemaxsize隊(duì)列最大容量；structline{inta[maxsize-1];intrear,front;//front隊(duì)頭;rear隊(duì)尾}第二頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第2頁(yè)。隊(duì)列操作舉例食堂排隊(duì)排隊(duì)買票吸管里的飲料作用：維持順序數(shù)組實(shí)現(xiàn)：元素a[0..maxn-1]，隊(duì)首front，隊(duì)尾rear入隊(duì)：rear++;a[rear]=x;出隊(duì)：ele=a[front];front++;隊(duì)空條件：front>rear問題：出隊(duì)的元素還在數(shù)組里，不是很浪費(fèi)嗎？循環(huán)隊(duì)列把隊(duì)列看成環(huán)行的，則入隊(duì)：rear=(rear+1)%maxn;不定義為a[1..maxn]的原因出隊(duì)：front=(front+1)%maxn;可能存在隊(duì)滿的情況：條件也是front>rear第三頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第3頁(yè)。用隊(duì)列實(shí)現(xiàn)圖的寬度優(yōu)先搜索算法我們要對(duì)圖進(jìn)行分層次遍歷,遍歷的序列為1，2，…，7，…寬度優(yōu)先搜索算法遍歷序列圖第四頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第4頁(yè)。分析要對(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)為已檢查的點(diǎn)。第三步：檢查隊(duì)列中是否還有未標(biāo)號(hào)的點(diǎn)，若有，轉(zhuǎn)第二步，否則，圖便歷完畢，算法終止。第五頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第5頁(yè)。voidbfs(v);//從v開始寬度有先遍歷圖{inicycque(q);//初始化隊(duì)列qq.encycque(v);visted[v]:=true;//初始點(diǎn)v放入隊(duì)列,并標(biāo)號(hào)while(!q.empty)//直到隊(duì)列不為空while(v的鄰接頂點(diǎn)存在){q.encycque(v的鄰接頂點(diǎn));visted[v的鄰接頂點(diǎn)]:=true;}q.dlcycque(v);}第六頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第6頁(yè)。①已知隊(duì)列(13,2,11,34,41,77,5,7,18,26,15),第一個(gè)進(jìn)入隊(duì)列的元素是13,則第五個(gè)出隊(duì)列的元素是(

)。(NOIP9)

A)5

B)41

C)77

D)13

E)18②設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若出隊(duì)的順序?yàn)閑2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該為()。(NOIP8)A)2B)3C)4D)5隊(duì)列練習(xí)試題第七頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第7頁(yè)。【培訓(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分別表示m行和n列)，以下為一個(gè)mxn的矩陣Output：細(xì)胞的個(gè)數(shù)0234500067

1034560500

2045600671

0000000089第八頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第8頁(yè)。算法步驟：1、讀入m*n矩陣,將其轉(zhuǎn)換為0、1矩陣存入pic數(shù)組中；2、沿pic數(shù)組矩陣從上到下,從左到右,找到遇到的第一個(gè)細(xì)胞；將細(xì)胞的位置入隊(duì)h,并沿其上、下、左、右四個(gè)方向搜索,如果遇到細(xì)胞(pic[i][j]=1)則將其位置入隊(duì),入隊(duì)后的位置pic[i][j]數(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、輸出找到的細(xì)胞數(shù)。第九頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第9頁(yè)。voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first<last){for(i=0;i<4;i++){h=hang[first]+dx[i];ll=lie[first]+dy[i];

if(h>0&&h<=m&&ll>0&&ll<=n&&a[h][ll])

{last++;hang[last]=h;lie[last]=ll;//入隊(duì)a[h][ll]=false;}}

first++;//出隊(duì)}}intmain(){init();for(i=1;i<=m;i++)

for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<<total<<endl;}第十頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第10頁(yè)?！九嘤?xùn)試題】走迷宮2349Description有一個(gè)m*n格的迷宮(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件讀入這m*n個(gè)數(shù)據(jù)和起始點(diǎn)、結(jié)束點(diǎn)(起始點(diǎn)和結(jié)束點(diǎn)都是用兩個(gè)數(shù)據(jù)來(lái)描述的，分別表示這個(gè)點(diǎn)的行號(hào)和列號(hào))。現(xiàn)在要你編程找出所有可行的道路，要求所走的路中沒有重復(fù)的點(diǎn)，走時(shí)只能是上下左右四個(gè)方向。如果一條路都不可行，則輸出相應(yīng)信息(用-l表示無(wú)路)。Input第一行是兩個(gè)數(shù)m，n，接下來(lái)是m行n列由1和0組成的數(shù)據(jù)，最后兩行是起始點(diǎn)和結(jié)束點(diǎn)(m,n>1且m,n<15)。Output輸出所有可能路路徑條數(shù)，如果沒有一條可行的路則輸出０。SampleInput561001011111110011101111101110111156SampleOutput：12

第十一頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第11頁(yè)。【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的走法總是一定的，如中國(guó)象棋中馬走“日”。有一位小學(xué)生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時(shí)喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個(gè)（100*100）的圍棋盤上任選兩點(diǎn)A、B，A點(diǎn)放上黑子，B點(diǎn)放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個(gè)走黑馬，一個(gè)走白馬。誰(shuí)用最少的步數(shù)走到左上角坐標(biāo)為(1,1)的點(diǎn)時(shí)，誰(shuí)獲勝。現(xiàn)在他請(qǐng)你幫忙，給你A、B兩點(diǎn)的坐標(biāo)，想知道兩個(gè)位置到（1,1）點(diǎn)的可能最少步數(shù)。輸入：12161810輸出：8

9第十二頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第12頁(yè)。1、確定出發(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）到達(dá)(1,1)的最少步數(shù)。2、數(shù)據(jù)結(jié)構(gòu)設(shè)queue—隊(duì)列，存儲(chǔ)從(1,1)可達(dá)的點(diǎn)（queue[k][1..2]）以及到達(dá)該點(diǎn)所需要的最少步數(shù)（queue[k][3]）（0≤k≤192+1）。隊(duì)列的首指針為open，尾指針為closed。初始時(shí)，queue中只有一個(gè)元素為(1,1)，最少步數(shù)為0。S—記錄(1,1)到每點(diǎn)所需要的最少步數(shù)。顯然，問題的答案是s[x1][y2]和s[x2][y2]。初始時(shí)，s[1][1]為0，除此之外的所有元素值設(shè)為-1。第十三頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第13頁(yè)。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,y+1)(x+1,y+2)馬走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我們將i方向上的位置增量存入常量數(shù)組dx[i]、dy[i]中（1≤i≤12）intdx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-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á)過，則根據(jù)廣度優(yōu)先搜索的原理，先前到達(dá)該點(diǎn)所需的步數(shù)一定小于當(dāng)前步數(shù)，因此完全沒有必要再擴(kuò)展下去。由此得出，馬的跳后位置（x,y）是否可以入隊(duì)的約束條件是s[x][y]<0第十四頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第14頁(yè)。海上葬禮有一片被大海包圍的群島，島上居住著一個(gè)食人部族。很多年前部落里有一位巫師接受了神的召喚跳入海中，從此，那一片海域就被打上了神的烙印，被這片海域所包圍的陸地也被賦予了神圣的意義（包圍關(guān)系滿足傳遞性，即海域A包圍了島B，島B包圍了海域C，而海域C中包含了島D，則我們說海域A也包含了島D）。從那以后，部落里的巫師死后都必須葬在這片神圣海域所包圍的島上，而且每一個(gè)島都只能埋葬一位巫師（否則就會(huì)被視為對(duì)神的不敬，從而給部族帶來(lái)災(zāi)難）?，F(xiàn)在給你群島的地圖和最初那位巫師跳海的地方，請(qǐng)你計(jì)算一下最多可以埋葬多少巫師。第十五頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第15頁(yè)。地圖是一個(gè)n*m的字符矩陣，’#’代表陸地，’.’代表海洋。連通的一片陸地為一個(gè)島，連通的一片海洋為一個(gè)海域。其中，陸地從上、下、左、右4個(gè)方向連通，海洋從上、下、左、右、左上、左下、右上、右下8個(gè)方向連通。如下圖。圖3中有4個(gè)島，2片海域。如果在A處落水，則落水的海域包圍了除右上、左下兩個(gè)頂角外的3個(gè)島嶼；如果在B處落水，則只包含了中間的2個(gè)島。數(shù)據(jù)范圍是n,m<=500。第十六頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第16頁(yè)。分析這道題目的思路比較簡(jiǎn)單。根據(jù)題意,可分三個(gè)步驟處理問題：做一遍floodfill,將最初的巫師落水的海域設(shè)立標(biāo)記,假設(shè)為S再做一遍floodfill，將S區(qū)域所包圍的所有區(qū)域（包括海洋和陸地）設(shè)立標(biāo)記，假設(shè)為E。在E區(qū)域中做一遍floodfill，統(tǒng)計(jì)有多少塊連通的陸地（即島的個(gè)數(shù)）現(xiàn)在的問題就是，用什么樣的算法實(shí)現(xiàn)floodfill。我們很容易想到深度優(yōu)先遍歷(DFS)的遞歸算法。由于要用遞歸，使用系統(tǒng)堆棧，因此對(duì)于500*500個(gè)結(jié)點(diǎn)的最壞情況下，會(huì)造成堆棧溢出，而且所需空間>1000kb，無(wú)法滿足題設(shè)的空間限制。在這種情況下，我們考慮深度優(yōu)先遍歷的非遞歸過程。第十七頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第17頁(yè)。分析首先給8個(gè)方向矢量定一個(gè)序號(hào)，用一個(gè)常量數(shù)組進(jìn)行記錄： CONSTd:array[1..8,1..2]ofshortint =((-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)先遍歷了。第十八頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第18頁(yè)。PROCDfs(startX,startY:integer);初始化棧Current_xstartXCurrent_ystartYtop1;s[top]0;{初始結(jié)點(diǎn)入棧}標(biāo)記(Current_x,Current_y)為已擴(kuò)展結(jié)點(diǎn)whiletop>0do【s[top]st[top]+1if（s[top]<=8）and（按s[top]方向擴(kuò)展的結(jié)點(diǎn)屬于海洋區(qū)域）and（之前沒有擴(kuò)展過）then【Current_xCurrent_x+d[s[top],1]Current_yCurrent_y+d[s[top],2]標(biāo)記(Current_x,Current_y)為已擴(kuò)展結(jié)點(diǎn)toptop+1;s[top]0{新結(jié)點(diǎn)入棧}】else【toptop-1{當(dāng)前結(jié)點(diǎn)退棧}iftop>0then【Current_xCurrent_x–d[s[top],1]Current_yCurrent_y–d[s[top],2]】】】ENDP

第十九頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第19頁(yè)?！九嘤?xùn)試題】最大子序和問題描述輸入一個(gè)長(zhǎng)度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的長(zhǎng)度不超過M的子序列，使得這個(gè)序列的和最大。第二十頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第20頁(yè)。最大子序和例如：

序列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ù)據(jù)N,M<=1000100%的數(shù)據(jù)N,M<=20000第二十一頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第21頁(yè)。一個(gè)簡(jiǎn)化的問題[序列的最大連續(xù)和]輸入一個(gè)長(zhǎng)度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的子序列，使得這個(gè)序列的和最大。和原問題相比沒有M這個(gè)序列長(zhǎng)度的限制！第二十二頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第22頁(yè)。分析：

設(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)=max{Ai,F(i-1)+Ai}邊界：F(1)=A1要求的結(jié)果為max{F(i)|1<=i<=n}該算法的時(shí)間復(fù)雜度為O(n)一個(gè)簡(jiǎn)化的問題第二十三頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第23頁(yè)。枚舉算法設(shè)

F(i)為以Ai結(jié)尾長(zhǎng)度不超過M的最大子序和對(duì)于每個(gè)F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時(shí)間復(fù)雜度為O(n2)問題初步分析第二十四頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第24頁(yè)。簡(jiǎn)化方程第二十五頁(yè)，共29頁(yè)數(shù)據(jù)結(jié)構(gòu)隊(duì)列及其應(yīng)用全文共29頁(yè)，當(dāng)前為第25頁(yè)。隊(duì)列優(yōu)化在算法中，考慮用隊(duì)列來(lái)維護(hù)決策值S(i-k)。每次只需要在隊(duì)首刪掉S(