pascal-第11講-隊(duì)列及應(yīng)用

數(shù)據(jù)結(jié)構(gòu)之隊(duì)列王桐林壽光現(xiàn)代中學(xué)2009.8濰坊市2009信息學(xué)奧林匹克夏令營(yíng)數(shù)據(jù)結(jié)構(gòu)知識(shí)簡(jiǎn)單回顧數(shù)據(jù)結(jié)構(gòu)（datastructure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。

數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵“操作”的對(duì)象：數(shù)據(jù)。數(shù)據(jù)與數(shù)據(jù)間的關(guān)系。針對(duì)數(shù)據(jù)的基本操作。數(shù)據(jù)結(jié)構(gòu)的形式定義

data_structure=(D,S)D:數(shù)據(jù)元素的有限集；S:Ｄ上關(guān)系的有限集；邏輯結(jié)構(gòu)圖例數(shù)據(jù)元素間的關(guān)系結(jié)構(gòu)名特性數(shù)據(jù)元素屬于或不屬于集合集合結(jié)構(gòu)松散；用其他結(jié)構(gòu)代替數(shù)據(jù)元素一個(gè)對(duì)一個(gè)線性結(jié)構(gòu)結(jié)構(gòu)簡(jiǎn)單數(shù)據(jù)元素一個(gè)對(duì)多個(gè)樹形結(jié)構(gòu)結(jié)構(gòu)復(fù)雜數(shù)據(jù)元素多個(gè)對(duì)多個(gè)圖結(jié)構(gòu)結(jié)構(gòu)復(fù)雜物理結(jié)構(gòu)

1、順序結(jié)構(gòu)：借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理存儲(chǔ)結(jié)構(gòu)中相鄰。

——數(shù)組2、鏈?zhǔn)浇Y(jié)構(gòu)：借助元素存儲(chǔ)地址的指針(pointer）表示數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯上關(guān)聯(lián)的數(shù)據(jù)元素，物理存儲(chǔ)結(jié)構(gòu)中不一定相鄰。——指針（動(dòng)態(tài)存儲(chǔ)）邏輯結(jié)構(gòu)、物理結(jié)構(gòu)密切相關(guān)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。線性表由n個(gè)數(shù)據(jù)元素的有限序列除頭元素外，每個(gè)元素都有一個(gè)前趨除尾元素外，每個(gè)元素都有一個(gè)后繼ABCD棧棧（堆棧）是一種受限的線性表。其所有的插入和刪除操作均限定在線性表的一端進(jìn)行，允許插入和刪除的一端稱為棧頂(表尾)，不允許插入和刪除的一端稱為棧底(表頭)。棧又稱為后進(jìn)先出(LastInFirstOut，簡(jiǎn)稱LIFO)表。棧與棧的順序存儲(chǔ)棧S順序存儲(chǔ)棧的實(shí)現(xiàn)（一）Constm=棧表目數(shù)的上限；Typestack=array[1..m]ofstype；{棧類型}Vars：stack；{棧}top：integer；{棧頂指針}

棧的實(shí)現(xiàn)（二）constm=棧表目數(shù)的上限；

typestack=recordelem:array[1..m]ofelemtp;top:0..m;{棧頂指針}end;Vars：stack；{棧}棧的基本操作初始化（init）、進(jìn)棧（push）、出棧（pop）、讀取棧頂元素（top）、判斷棧是否為空或已滿。。棧的典型應(yīng)用表達(dá)式求值括號(hào)區(qū)配隊(duì)列在日常生活中的排隊(duì)現(xiàn)象：購(gòu)物、訂票、打飯、候車排隊(duì)所遵循的原則是“先來先服務(wù)”，后來者總是加到隊(duì)尾，排頭者總是先離開隊(duì)伍。隊(duì)列就是從日常生活中的排隊(duì)現(xiàn)象抽象出來的。隊(duì)列的定義隊(duì)列也是一種受限的線性表。它的所有插入都在隊(duì)列的一端進(jìn)行，所有刪除都在另一端進(jìn)行。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭(front)。隊(duì)列的插入和刪除我們稱為入隊(duì)和出隊(duì)，新元素入隊(duì)就成為新的隊(duì)尾元素，刪除元素后，其后繼元素成為新的隊(duì)首元素。

隊(duì)列是一種先進(jìn)先出(FIFO)的線性表front>=rear，則隊(duì)列空;front<rear，則隊(duì)列非空。隊(duì)列的存儲(chǔ)隊(duì)列可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)我們一般采用順序存儲(chǔ)結(jié)構(gòu)來定義隊(duì)列

——數(shù)組abcdrf空1、隊(duì)列的順序存儲(chǔ)（1）借助記錄類型來定義：constmaxn=xxxx;//隊(duì)列的最大長(zhǎng)度typequeue=record

data:array[1..maxn]ofqtype;//qtype表示隊(duì)列元素的數(shù)據(jù)類型

front,rear:1..maxn//隊(duì)首指針和隊(duì)尾指針

end;varq:queue;（2）實(shí)際編程中可以直接定義成如下格式：constmaxn=xxxx;//隊(duì)列的最大長(zhǎng)度var

q:array[1..maxn]ofqtype;//隊(duì)列front,rear:1..maxn;//隊(duì)首指針和隊(duì)尾指針2、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)同棧一樣，隊(duì)列也可以采用鏈?zhǔn)酱鎯?chǔ)。隊(duì)列的基本操作初始化入隊(duì)出隊(duì)1、隊(duì)列的初始化或置空將隊(duì)首指針和隊(duì)尾指針皆置為0。

proceduresetnull；front:=0;rear:=0end；fr

0123……2、入隊(duì)add(x)，也稱為進(jìn)隊(duì)首先判斷隊(duì)列q是否已滿，若未滿，則后移隊(duì)尾指針，并在隊(duì)列的尾端插入元素x。

procedureadd(x:qtype)；

beginifrear=maxnthenwriteln('queuefull!');haltend//隊(duì)滿

elsebeginrear:=rear+1；//后移隊(duì)尾指針q[rear]:=x；//插入元素xend；

end；Arf3、出隊(duì)del首先判斷隊(duì)列q是否已空，若未空，則后移隊(duì)首指針，并取出隊(duì)列q的隊(duì)首元素。

functiondel；

beginiffront=rearthenwriteln('queueempty!');haltend//隊(duì)空

elsebeginfront:=front+1;//后移隊(duì)首指針del:=q[front]；//取出隊(duì)首元素

end;end；bcdfr如果僅完成刪除操作，則只需要后移隊(duì)首指針（front:=front+1）即可。小練習(xí)①已知隊(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

小練習(xí)②設(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ì)列只能在一端插入，在另一端刪除，因此隨著入隊(duì)及出隊(duì)運(yùn)算的不斷進(jìn)行，就會(huì)出現(xiàn)一種有別于棧的情形：隊(duì)列在數(shù)組中不斷地向隊(duì)尾方向移動(dòng)，而在隊(duì)首的前面產(chǎn)生一片不能利用的空閑存儲(chǔ)區(qū)，最后會(huì)導(dǎo)致當(dāng)尾指針指向數(shù)組最后一個(gè)位置（即r=max）而不能再加入元素時(shí)，存儲(chǔ)空間的前部卻有一片存儲(chǔ)區(qū)無端浪費(fèi)，這種現(xiàn)象稱為“假溢出”?？朔僖绯龅姆椒ㄓ袃煞N一種是將隊(duì)列中的所有元素均向低地址區(qū)移動(dòng)，顯然這種方法是很浪費(fèi)時(shí)間的；另一種方法是將數(shù)組存儲(chǔ)區(qū)看成是一個(gè)首尾相接的環(huán)形區(qū)域。當(dāng)存放到max地址后，下一個(gè)地址就“翻轉(zhuǎn)”為１。在結(jié)構(gòu)上采用這種技巧來存儲(chǔ)的隊(duì)列稱為循環(huán)隊(duì)列。循環(huán)隊(duì)列隊(duì)列的應(yīng)用例7-3細(xì)胞個(gè)數(shù)【試題描述】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。【輸入】整數(shù)m,n（第一行）m<50,n<80；矩陣(m行，n列)?！据敵觥考?xì)胞的個(gè)數(shù)?！緲永斎搿?10

0234500067

1034560500

2045600671

0000000089【樣例輸出】40234500067

1034560500

2045600671

0000000089共4個(gè)細(xì)胞算法步驟：1、從文件中讀入m*n矩陣，將其轉(zhuǎn)換為0、1矩陣存入pic數(shù)組中；1表示細(xì)胞，0表示無細(xì)胞

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ù)。參考程序constdx:array[1..4]of-1..1=(-1,0,1,0);//橫坐標(biāo):左，下，右，上dy:array[1..4]of-1..1=(0,1,0,-1);//縱坐標(biāo):左，下，右，上vars:string;a:array[1..50,1..80]of0..1;//存儲(chǔ)矩陣的數(shù)組，0:無細(xì)胞；1：有細(xì)胞

m,n,i,j,num:integer;h:array[1..4000,1..2]ofbyte;//隊(duì)列：存細(xì)胞的坐標(biāo)，1：行；2：列proceduretry(p,q:integer);//處理坐標(biāo)（p,q）的細(xì)胞

vari,t,w,x,y:integer;begininc(num);//細(xì)胞數(shù)量加1a[p,q]:=0;t:=1;//隊(duì)頭

w:=1;//隊(duì)尾

h[1,1]:=p;h[1,2]:=q;//遇到的第一個(gè)細(xì)胞入隊(duì)

repeatfori:=1to4do//沿細(xì)胞的上下左右四個(gè)方向搜索細(xì)胞

beginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x>0)and(x<=m)and(y>0)and(y<=n)and(a[x,y]=1)thenbegininc(w);h[w,1]:=x;h[w,2]:=y;a[x,y]:=0;end;//為細(xì)胞的入隊(duì)

end;inc(t);//隊(duì)頭指針加1，出隊(duì)

untilt>w;//直至隊(duì)空為止

end;beginfillchar(a,sizeof(a),0);//初始化數(shù)組

fillchar(h,sizeof(h),0);//初始化隊(duì)列

num:=0;readln(m,n);fori:=1tomdo//讀入矩陣

beginreadln(s);forj:=1tondoifs[j]='0'thena[i,j]:=0elsea[i,j]:=1;end;fori:=1tomdoforj:=1tondoifa[i,j]=1thentry(i,j);//在矩陣中尋找細(xì)胞

writeln(num);//輸出細(xì)胞個(gè)數(shù)end.廣度優(yōu)先搜索算法（bfs）1、適合的題目類型：

1）、求從給定初始狀態(tài)到目標(biāo)狀態(tài)最少需要的步數(shù)。

2）、給定初始狀態(tài)，經(jīng)過k步后能夠到達(dá)哪些狀態(tài)。2、利用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列。3、狀態(tài)的最大值：決定隊(duì)列的大小（非常重要）4、隊(duì)列里需要記住哪些狀態(tài)：一般使用記錄數(shù)據(jù)類型。5、狀態(tài)的轉(zhuǎn)移：不能遺漏。6、狀態(tài)的判重：避免重復(fù)進(jìn)入隊(duì)列。從初始結(jié)點(diǎn)開始，應(yīng)用算符生成第一層結(jié)點(diǎn)，檢查目標(biāo)結(jié)點(diǎn)是否在其中出現(xiàn)，若沒有，再用算符將第一層結(jié)點(diǎn)逐一擴(kuò)展，得第二層結(jié)點(diǎn)，逐一檢查第二層中是否包含目標(biāo)結(jié)點(diǎn)。若沒有，依次擴(kuò)展、檢查……直到發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止。這就是所謂的廣度優(yōu)先搜索。abcdefjk用隊(duì)列的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)搜索過程中產(chǎn)生的結(jié)點(diǎn)，取隊(duì)頭元素?cái)U(kuò)展，產(chǎn)生的結(jié)點(diǎn)插入隊(duì)尾。Bfs的基本框架：初始化；建立數(shù)據(jù)庫(kù)（隊(duì)列）；初始狀態(tài)進(jìn)入隊(duì)列；f=0;隊(duì)列的首指針；r=1;隊(duì)列的尾指針(開始時(shí)指向初始狀態(tài))；q[1];初始結(jié)點(diǎn);While（f<r）do{還有未擴(kuò)展的結(jié)點(diǎn)，隊(duì)列不空}BeginInc（f）；{移動(dòng)隊(duì)列的首指針：出隊(duì)列}

記錄f狀態(tài)；

Fori=1tomethoddo{按規(guī)則擴(kuò)展下一層新的子結(jié)點(diǎn)}Begin

生成新的結(jié)點(diǎn);If新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)then輸出目標(biāo)，搜索結(jié)束；

If新結(jié)點(diǎn)是以前沒出現(xiàn)過then保存新結(jié)點(diǎn)(入隊(duì))；

EndEnd；【問題描述：】在n*n的棋盤上有一匹馬在第x行第y列的格子上。棋盤上有些格子上有障礙物，馬不能達(dá)到有障礙物的格子。已知馬在棋盤中的走法按“日“字8個(gè)方向可走，如下圖所示：?jiǎn)枺耗男└褡幽艿竭_(dá)，到達(dá)這些格子的最小步數(shù)是多少。【輸入：】第一行:n（n<=100）,x,y

(馬的開始位置)。接下來n行為棋盤的描述：“-“為空格子，”+“表示該格子有障礙物?！据敵觯骸縩行，每行n個(gè)用空格隔開的數(shù)，表示馬到達(dá)該格子的最少步數(shù)，如果無法到達(dá)則用-1表示。2、馬的遍歷422----------+-----【樣例輸入：】4321303223-111214【樣例輸出：】０

const

dx:array[1..8]ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array[-1..maxn+2,-1..maxn+2]ofboolean;//加邊界，方便判斷是否出界

dist:array[1..maxn,1..maxn]ofinteger;//記錄最少步數(shù)

n,i,j,x0,y0:integer;procedureinit;//輸入vars:string;beginreadln(n,x0,y0);fillchar(can,sizeof(can),false);//初始化fori:=1tondobeginreadln(s);forj:=1tondocan[i,j]:=s[j]='-';end;end;procedurebfs;//廣度優(yōu)先搜索

varq:array[1..maxn*m