數(shù)據(jù)結(jié)構(gòu)(第3章)-清華大學(xué)

第三章棧和隊列⒈教學(xué)內(nèi)容：3.1棧3.2棧應(yīng)用舉例3.3隊列3.4隊列應(yīng)用舉例⒉教學(xué)目的：⑴理解棧的定義、特征及在其上所定義的基本運(yùn)算；⑵掌握在兩種存儲結(jié)構(gòu)上對棧所施加的基本運(yùn)算的實(shí)現(xiàn)；⑶理解隊列的定義、特征及在其上所定義的基本運(yùn)算；⑷掌握在兩種存儲結(jié)構(gòu)上對隊列所施加的基本運(yùn)算的實(shí)現(xiàn)。⒊教學(xué)重點(diǎn)：⑴棧的定義及邏輯特點(diǎn)，棧的基本運(yùn)算；⑵棧的順序存儲結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)；⑶棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)；⑷隊列的定義及邏輯特點(diǎn)，隊列的基本運(yùn)算；⑸隊列的順序存儲結(jié)構(gòu)及其上的運(yùn)算實(shí)現(xiàn)；⑹隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)。⒋教學(xué)難點(diǎn)：⑴順序棧的溢出判斷條件；⑵循環(huán)隊列的隊空、隊滿判斷條件；⑶循環(huán)隊列上的插入、刪除操作。⒌教學(xué)時間：6學(xué)時2/5/20231數(shù)據(jù)結(jié)構(gòu)講義3.1棧棧的定義及基本運(yùn)算棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)2/5/20232數(shù)據(jù)結(jié)構(gòu)講義3.1.1棧的定義及基本運(yùn)算棧是限制在表的一端進(jìn)行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。

右圖所示棧中有三個元素，進(jìn)棧的順序是a1、a2、a3，當(dāng)需要出棧時其順序為a3、a2、a1，所以棧又稱為后進(jìn)先出的線性表（LastInFirstOut），簡稱LIFO表。2/5/20233數(shù)據(jù)結(jié)構(gòu)講義棧的基本操作有：⑴棧初始化：Init_Stack(s)

操作結(jié)果是構(gòu)造了一個空棧。⑵判?？眨篍mpty_Stack(s)

操作結(jié)果是若s為空棧返回為1，否則返回為0。⑶入棧：Push_Stack(s，x)

操作結(jié)果是在棧s的頂部插入一個新元素x，x成為新的棧頂元素。⑷出棧：Pop_Stack(s)

在棧s存在且非空的情況下，操作結(jié)果是將棧s的頂部元素從棧中刪除。⑸讀棧頂元素：Top_Stack(s)

在棧s存在且非空情況下，操作結(jié)果是讀棧頂元素，棧不變化。2/5/20234數(shù)據(jù)結(jié)構(gòu)講義3.1.2棧的存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn)⒈順序棧棧中的數(shù)據(jù)元素用一個預(yù)設(shè)的足夠長度的一維數(shù)組來實(shí)現(xiàn)：datatypedata[MAXSIZE]，棧底位置可以設(shè)置在數(shù)組的任一個端點(diǎn)，而棧頂是隨著插入和刪除而變化的，用一個inttop來作為棧頂?shù)闹羔槪该鳟?dāng)前棧頂?shù)奈恢?，將data和top封裝在一個結(jié)構(gòu)中，順序棧的類型描述如下：#defineMAXSIZE1024

typedefstruct

{datatypedata[MAXSIZE];inttop;}SeqStack；定義一個指向順序棧的指針：SeqStack*s;2/5/20235數(shù)據(jù)結(jié)構(gòu)講義通常0下標(biāo)端設(shè)為棧底，這樣空棧時棧頂指針top=-1;入棧時，棧頂指針加１，即s->top++;出棧時，棧頂指針減１，即s->top--。棧操作的示意圖如圖所示。

圖(a)是空棧，圖(c)是A、B、C、D、E5個元素依次入棧之后，圖(d)是在圖(c)之后E、D相繼出棧，此時棧中還有3個元素，或許最近出棧的元素D、E仍然在原先的單元存儲著，但top指針已經(jīng)指向了新的棧頂，則元素D、E已不在棧中了。2/5/20236數(shù)據(jù)結(jié)構(gòu)講義⑴置空棧首先建立棧空間，然后初始化棧頂指針。

SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(sizeof(SeqStack));s->top=-1;

returns;}2/5/20237數(shù)據(jù)結(jié)構(gòu)講義⑵判空棧

intEmpty_SeqStack(SeqStack*s){if(s->top==-1)

return1;elsereturn0;}2/5/20238數(shù)據(jù)結(jié)構(gòu)講義⑶入棧

intPush_SeqStack(SeqStack*s,datatypex){if(s->top==MAXSIZE-1)

return0;/*棧滿不能入棧*/

else

{s->top++;s->data[s->top]=x;return1;}}2/5/20239數(shù)據(jù)結(jié)構(gòu)講義⑷出棧

intPop_SeqStack(SeqStack*s,datatype*x){if(Empty_SeqStack(s))return0;/*?？詹荒艹鰲?/

else{*x=s->data[s->top];s->top--;

return1;

}/*棧頂元素存入*x，返回*/}2/5/202310數(shù)據(jù)結(jié)構(gòu)講義⑸取棧頂元素

datatypeTop_SeqStack(SeqStack*s){if(Empty_SeqStack(s))return0;

/*?？?/

elsereturn(s->data[s->top]);}2/5/202311數(shù)據(jù)結(jié)構(gòu)講義幾點(diǎn)說明：1.對于順序棧，入棧時，首先判棧是否滿了，棧滿時，不能入棧;否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。棧滿的條件為：s->top==MAXSIZE-12.出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常棧空時常作為一種控制轉(zhuǎn)移的條件。2/5/202312數(shù)據(jù)結(jié)構(gòu)講義

通常鏈棧用單鏈表表示，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同：

typedefstructnode{datatypedata;

structnode*next;}StackNode，*LinkStack;

說明top為棧頂指針：LinkStacktop;

因為棧中的主要運(yùn)算是在棧頂插入、刪除，顯然在鏈表的頭部做棧頂是最方便的，而且沒有必要象單鏈表那樣為了運(yùn)算方便附加一個頭結(jié)點(diǎn)。通常將鏈棧表示成圖的形式。⒉鏈棧2/5/202313數(shù)據(jù)結(jié)構(gòu)講義⑴置空棧

LinkStackInit_LinkStack(){returnNULL;}⑵判?？?/p>

intEmpty_LinkStack(LinkStacktop){if(top==-1)return1;else

return0;}2/5/202314數(shù)據(jù)結(jié)構(gòu)講義⑶入棧

LinkStackPush_LinkStack(LinkStacktop,datatypex){StackNode*s;s=malloc(sizeof(StackNode));s->data=x;s->next=top;top=s;returntop;}2/5/202315數(shù)據(jù)結(jié)構(gòu)講義⑷出棧LinkStackPop_LinkStack(LinkStacktop,datatype*x){StackNode*p;if(top==NULL)returnNULL;else{*x=top->data;p=top;top=top->next;free(p);returntop;}}2/5/202316數(shù)據(jù)結(jié)構(gòu)講義3.2棧的應(yīng)用舉例由于棧的“后進(jìn)先出”特點(diǎn)，在很多實(shí)際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行求解，下面通過幾個例子進(jìn)行說明。2/5/202317數(shù)據(jù)結(jié)構(gòu)講義例3.1

簡單應(yīng)用：數(shù)制轉(zhuǎn)換問題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3467，r=8為例轉(zhuǎn)換方法如下：

NN/8（整除）N%8（求余）34674333低4335415466606高所以：（3467）10=（6613）8我們看到所轉(zhuǎn)換的8進(jìn)制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。2/5/202318數(shù)據(jù)結(jié)構(gòu)講義算法思想如下：當(dāng)N>0時重復(fù)1，21.若N≠0，則將N%r壓入棧s中，執(zhí)行2;若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。2.用N/r代替Ntypedefintdatatype;voidconversion(intN，intr){SeqStacks;

datetypex;Init_SeqStack(&s);while(N){Push_SeqStack(&s，N%r);N=N/r;}while(Empty_SeqStack(&s)){Pop_SeqStack(&s，&x);

printf(“%d”，x);

}}2/5/202319數(shù)據(jù)結(jié)構(gòu)講義例3.2

利用棧實(shí)現(xiàn)迷宮的求解。問題：這是實(shí)驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解思想：采用回溯法?；厮莘ㄊ且环N不斷試探且及時糾正錯誤的搜索方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向;若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。2/5/202320數(shù)據(jù)結(jié)構(gòu)講義⒈表示迷宮的數(shù)據(jù)結(jié)構(gòu)設(shè)迷宮為m行n列，利用maze[m][n]來表示一個迷宮，maze[i][j]=0或1;其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時，中間點(diǎn)有8個方向可以試探，而四個角點(diǎn)有3個方向，其它邊緣點(diǎn)有5個方向，為使問題簡單化我們用maze[m+2][n+2]來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點(diǎn)的試探方向全部為8，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個，同時與迷宮周圍是墻壁這一實(shí)際問題相一致。迷宮的定義如下：#definem6/*迷宮的實(shí)際行*/#definen8/*迷宮的實(shí)際列*/intmaze[m+2][n+2];如圖表示的是一個6×8的迷宮。入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。2/5/202321數(shù)據(jù)結(jié)構(gòu)講義⒉試探方向在上述表示迷宮的情況下，每個點(diǎn)有8個方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x,y)，與其相鄰的8個點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進(jìn)行。為了簡化問題，方便地求出新點(diǎn)的坐標(biāo)，將從正東開始沿順時針進(jìn)行的這8個方向的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move[8]中，在move數(shù)組中，每個元素有兩個域組成，x：行坐標(biāo)增量，y：列坐標(biāo)增量。Move數(shù)組定義如下：

typedefstruct

{intx，y}item;itemmove[8];2/5/202322數(shù)據(jù)結(jié)構(gòu)講義⒊棧的設(shè)計

當(dāng)?shù)竭_(dá)了某點(diǎn)而無路可走時需返回前一點(diǎn)，再從前一點(diǎn)開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向。對于下圖所示迷宮，依次入棧為：棧中每一組數(shù)據(jù)是所到達(dá)的每點(diǎn)的坐標(biāo)及從該點(diǎn)沿哪個方向向下走的，對于下圖所示迷宮，走的路線為：(1,1)1(2,2)1(3,3)0(3,4)0(3,5)0(3,6)0（下腳標(biāo)表示方向），當(dāng)從點(diǎn)(3,6)沿方向0到達(dá)點(diǎn)(3,7)之后，無路可走，則應(yīng)回溯，即退回到點(diǎn)(3,6)，對應(yīng)的操作是出棧，沿下一個方向即方向1繼續(xù)試探，方向１、２試探失敗，在方向３上試探成功，因此將(3,6,3)壓入棧中，即到達(dá)了（4,5）點(diǎn)。2/5/202323數(shù)據(jù)結(jié)構(gòu)講義棧中元素是一個由行、列、方向組成的三元組，棧中元素的設(shè)計如下：

typedefstruct

{intx,y,d;/*行列坐標(biāo)及方向*/}datatype;棧的定義仍然為：

SeqStacks;2/5/202324數(shù)據(jù)結(jié)構(gòu)講義⒋如何防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)一種方法是另外設(shè)置一個標(biāo)志數(shù)組mark[m][n]，它的所有元素都初始化為0，一旦到達(dá)了某一點(diǎn)(i,j)之后，使mark[i][j]置1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_(dá)某點(diǎn)（i,j）后使maze[i][j]置-1，以便區(qū)別未到達(dá)過的點(diǎn)，同樣也能起到防止走重復(fù)點(diǎn)的目的，本書采用后者方法，算法結(jié)束前可恢復(fù)原迷宮。2/5/202325數(shù)據(jù)結(jié)構(gòu)講義迷宮求解算法思想如下：

1．棧初始化;2．將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為－１）入棧3．while(棧不空){棧頂元素＝＞（x,y,d）出棧;求出下一個要試探的方向d++;while（還有剩余試探方向時）{if（d方向可走）則{（x,y,d）入棧;求新點(diǎn)坐標(biāo)(i,j);

將新點(diǎn)（i,j）切換為當(dāng)前點(diǎn)（x,y）;if((x,ｙ)==(ｍ,n))結(jié)束;

else重置d=0;}elsed++;}}2/5/202326數(shù)據(jù)結(jié)構(gòu)講義intpath(intmaze[m][n],itemmove[8]){SeqStacks;datetypetemp;intx,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Push_SeqStack(s，temp);while(!Empty_SeqStack(s)){Pop_SeqStack(s,＆temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<8){i=x+move[d].x;j=y+move[d].y;if(maze[i][j]==0){temp={x,y,d};Push_SeqStack(s,temp);x=i;y=j;maze[x][y]=-1;if(x==m&&y==n)return1;/*迷宮有路*/

elsed=0;}elsed++;}/*while(d<8)*/}/*while*/return0;/*迷宮無路*/}2/5/202327數(shù)據(jù)結(jié)構(gòu)講義例3.3

中綴表達(dá)式求值設(shè)運(yùn)算規(guī)則為：

運(yùn)算符的優(yōu)先級為：（）→^→×、/、%→+、-；有括號出現(xiàn)時先算括號內(nèi)的，后算括號外的，多層括號，由內(nèi)向外進(jìn)行；乘方連續(xù)出現(xiàn)時先算最右面的；表達(dá)式作為一個滿足表達(dá)式語法規(guī)則的串存儲，如表達(dá)式“3*2^（4+2*2-１*3）-5”,它的的求值過程為：自左向右掃描表達(dá)式，當(dāng)掃描到3*2時不能馬上計算，因為后面可能還有更高的運(yùn)算。正確的處理過程是：需要兩個棧：對象棧s1和算符棧s2。當(dāng)自左至右掃描表達(dá)式的每一個字符時，若當(dāng)前字符是運(yùn)算對象，入對象棧，是運(yùn)算符時，若這個運(yùn)算符比棧頂運(yùn)算符高則入棧，繼續(xù)向后處理，若這個運(yùn)算符比棧頂運(yùn)算符低則從對象棧出棧兩個運(yùn)算量，從算符棧出棧一個運(yùn)算符進(jìn)行運(yùn)算，并將其運(yùn)算結(jié)果入對象棧，繼續(xù)處理當(dāng)前字符當(dāng)前字符，直到遇到結(jié)束符。2/5/202328數(shù)據(jù)結(jié)構(gòu)講義中綴表達(dá)式表達(dá)式“3*2^（4+2*2-１*3）-5”求值過程中兩個棧的狀態(tài)情況如圖所示。2/5/202329數(shù)據(jù)結(jié)構(gòu)講義例3.4

后綴表達(dá)式求值計算一個后綴表達(dá)式，算法上比計算一個中綴表達(dá)式簡單的多。具體做法：只使用一個對象棧，當(dāng)從左向右掃描表達(dá)式時，每遇到一個操作數(shù)就送入棧中保存，每遇到一個運(yùn)算符就從棧中取出兩個操作數(shù)進(jìn)行當(dāng)前的計算，然后把結(jié)果再入棧，直到整個表達(dá)式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。2/5/202330數(shù)據(jù)結(jié)構(gòu)講義typedefchardatetype;doublecalcul_exp(char*A)

/*本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運(yùn)算結(jié)果*/{Seq_Starcks;ch=*A++;Init_SeqStack(s);while(ch!=’#’){if(ch!=運(yùn)算符)Push_SeqStack(s,ch);else{Pop_SeqStack(s,&a);Pop_SeqStack(s,&b);/*取出兩個運(yùn)算量*/

switch(ch).{casech==’+’：c=b+a;break;casech==’-’：c=b-a;break;casech==’*’：c=b*a;break;casech==’/’：c=b/a;break;casech==’%’：c=b%a;break;}

Push_SeqStack(s,c);}

ch=*A++;

}Pop_SeqStack(s,result);returnresult;}2/5/202331數(shù)據(jù)結(jié)構(gòu)講義后綴表達(dá)式“32422*+13*-^*5-”，棧中狀態(tài)變化情況：2/5/202332數(shù)據(jù)結(jié)構(gòu)講義例3.5

中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式和前述對中綴表達(dá)式求值的方法完全類似，但只需要運(yùn)算符棧，遇到運(yùn)算對象時直接放后綴表達(dá)式的存儲區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲在字符數(shù)組B中。具體做法：遇到運(yùn)算對象順序向存儲后綴表達(dá)式的B數(shù)組中存放，遇到運(yùn)算符時類似于中綴表達(dá)式求值時對運(yùn)算符的處理過程，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是將其送入B中存放。2/5/202333數(shù)據(jù)結(jié)構(gòu)講義3.3隊列隊列的定義及基本運(yùn)算隊列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)2/5/202334數(shù)據(jù)結(jié)構(gòu)講義3.3.1隊列的定義及基本運(yùn)算在實(shí)際問題中經(jīng)常使用一種“先進(jìn)先出”(FIFO---FirstInFirstOut)的數(shù)據(jù)結(jié)構(gòu)：即插入在表一端進(jìn)行，刪除在表的另一端進(jìn)行，這種數(shù)據(jù)結(jié)構(gòu)稱為隊或隊列，把允許插入的一端叫隊尾(rear)，把允許刪除的一端叫隊頭(front)。如圖所示是一個有5個元素的隊列。入隊的順序依次為a1、a2、a3、a4、

a5，出隊時的順序?qū)⒁廊皇莂1、a2、a3、a4、

a5。隊列也是一種運(yùn)算受限制的線性表，又叫先進(jìn)先出表。2/5/202335數(shù)據(jù)結(jié)構(gòu)講義在隊列上進(jìn)行的基本操作有：⑴隊列初始化：Init_Queue(q)

操作結(jié)果是構(gòu)造一個空隊。⑵入隊操作：In_Queue(q,x),

在隊q存在情況下，操作結(jié)果是對已存在的隊列q，插入一個元素x到隊尾。

⑶出隊操作：Out_Queue(q,x)

隊q存在且非空情況下，操作結(jié)果是刪除隊首元素，并返回其值。⑷讀隊頭元素：Front_Queue(q,x)

隊q存在且非空情況下，操作結(jié)果是讀出隊頭元素，并返回其值。⑸判隊空操作：Empty_Queue(q)

隊q存在時，操作結(jié)果是若q為空隊則返回為1，否則返回為0。2/5/202336數(shù)據(jù)結(jié)構(gòu)講義3.3.2隊列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)⒈順序隊順序存儲的隊稱為順序隊。因為隊的隊頭和隊尾都是活動的，因此，除了隊列的數(shù)據(jù)區(qū)外還有隊頭、隊尾兩個指針。順序隊的類型定義如下：

defineMAXSIZE1024/*隊列的最大容量*/

typedefstruct

{datatypedata[MAXSIZE];/*隊員的存儲空間*/

intrear,front;/*隊頭隊尾指針*/}SeQueue;

定義一個指向隊的指針變量：

SeQueue*sq;2/5/202337數(shù)據(jù)結(jié)構(gòu)講義申請一個順序隊的存儲空間：

sq=malloc(sizeof(SeQueue));

隊列的數(shù)據(jù)區(qū)為：

sq->data[0]---sq->data[MAXSIZE-1]

隊頭指針：sq->front

隊尾指針：sq->rear

設(shè)隊頭指針指向隊頭元素前面一個位置，隊尾指針指向隊尾元素（這樣的設(shè)置是為了某些運(yùn)算的方便，并不是唯一的方法）。置空隊則為：sq->front=sq->rear=-1;2/5/202338數(shù)據(jù)結(jié)構(gòu)講義在不考慮溢出的情況下，入隊操作隊尾指針加1，指向新位置后，元素入隊。操作如下：

sq->rear++;sq->data[sq->rear]=x;

在不考慮隊空的情況下，出隊操作隊頭指針加1，表明隊頭元素出隊。操作如下：

sq->front++;x=sq->data[sq->front];

/*原隊頭元素送x中*/

隊中元素的個數(shù)：m=(sq->rear)-(q->front);

隊滿時：m=MAXSIZE；隊空時：m=0。2/5/202339數(shù)據(jù)結(jié)構(gòu)講義按照上述思想建立的空隊及入隊出隊示意圖如圖所示，設(shè)MAXSIZE=10。2/5/202340數(shù)據(jù)結(jié)構(gòu)講義從圖中可以看到，隨著入隊出隊的進(jìn)行，會使整個隊列整體向后移動，這樣就出現(xiàn)了圖(d)中的現(xiàn)象：隊尾指針已經(jīng)移到了最后,再有元素入隊就會出現(xiàn)溢出，而事實(shí)上此時隊中并未真的“滿員”，這種現(xiàn)象為“假溢出”，這是由于“隊尾入隊頭出”這種受限制的操作所造成。解決假溢出的方法之一是將隊列的數(shù)據(jù)區(qū)data[0..MAXSIZE-1]看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱為“循環(huán)隊列”，“循環(huán)隊列”如下圖所示。2/5/202341數(shù)據(jù)結(jié)構(gòu)講義因為是頭尾相接的循環(huán)結(jié)構(gòu)，入隊時的隊尾指針加1操作修改為：

sq->rear=(sq->rear+1)%MAXSIZE;出隊時的隊頭指針加1操作修改為：

sq->front=(sq->front+1)%MAXSIZE;設(shè)MAXSIZE=10，下圖是循環(huán)隊列操作示意圖。2/5/202342數(shù)據(jù)結(jié)構(gòu)講義從上圖所示的循環(huán)隊可以看出，(a)中具有a5、a6、a7、a8四個元素，此時front=4,rear=8；隨著a9~a14相繼入隊，隊中具有了10個元素---隊滿，此時

front=4,rear=4,如（b）所示，可見在隊滿情況下有：front==rear。若在(a)情況下，a5~a8相繼出隊，此時隊空，

front=4，rear=4，如(c)所示，即在隊空情況下也有：front==rear。就是說“隊滿”和“隊空”的條件是相同的了。這顯然是必須要解決的一個問題。方法之一是附設(shè)一個存儲隊中元素個數(shù)的變量如num，當(dāng)num==0時隊空，當(dāng)num==MAXSIZE時為隊滿。另一種方法是少用一個元素空間，把圖(d)所示的情況就視為隊滿，此時的狀態(tài)是隊尾指針加1就會從后面趕上隊頭指針，這種情況下隊滿的條件是：(rear+1)%MAXSIZE==front，也能和空隊區(qū)別開。2/5/202343數(shù)據(jù)結(jié)構(gòu)講義循環(huán)隊列的類型定義如下：

typedefstruct{

datatypedata[MAXSIZE];

/*數(shù)據(jù)的存儲區(qū)*/

intfront,rear;/*隊頭隊尾指針*/

intnum;

/*隊中元素的個數(shù)*/}c_SeQueue;/*循環(huán)隊*/2/5/202344數(shù)據(jù)結(jié)構(gòu)講義⑴置空隊c_SeQueue*Init_SeQueue(){q=malloc(sizeof(c_SeQueue));q->front=q->rear=MAXSIZE-1;q->num=0;returnq;}2/5/202345數(shù)據(jù)結(jié)構(gòu)講義⑵入隊

intIn_SeQueue(c_SeQueue*q,datatypex){if(num==MAXSIZE){printf(＂隊滿＂);

return–1;/*隊滿不能入隊*/}

else{q->rear=(q->rear+1)%MAXSIZE;q->data[q->rear]=x;num++;

return1;

/*入隊完成*/}}2/5/202346數(shù)據(jù)結(jié)構(gòu)講義⑶出隊intOut_SeQueue(c_SeQueue*q,datatype*x){if(num==0){printf(＂隊空＂)；

return–1;

/*隊空不能出隊*/}

else{q->front=(q->front+1)%MAXSIZE;*x=q->data[q->front];

/*讀出隊頭元素*/

num--;

return1;

/*出隊完成*/}}2/5/202347數(shù)據(jù)結(jié)構(gòu)講義⑷判隊空intEmpty_SeQueue(c_SeQueue*q){if(num==0)

return1;elsereturn0;}2/5/202348數(shù)據(jù)結(jié)構(gòu)講義⒉鏈隊

鏈?zhǔn)酱鎯Φ年牱Q為鏈隊。和鏈棧類似，用單鏈表來實(shí)現(xiàn)鏈隊，根據(jù)隊的FIFO原則，為了操作上的方便，我們分別需要一個頭指針和尾指針，如圖所示。圖中頭指針front和尾指針rear是兩個獨(dú)立的指針變量，從結(jié)構(gòu)性上考慮，通常將二者封裝在一個結(jié)構(gòu)中。2/5/202349數(shù)據(jù)結(jié)構(gòu)講義鏈隊的描述如下：

typedefstructnode{datatypedata;structnode*next;}QNode;/*鏈隊結(jié)點(diǎn)的類型*/

typedefstruct

{QNnode*front,*rear;}LQueue;/*將頭尾指針封裝在一起的鏈隊*/定義一個指向鏈隊的指針：

LQueue*q;2/5/202350數(shù)據(jù)結(jié)構(gòu)講義按這種思想建立的帶頭結(jié)點(diǎn)的鏈隊如圖所示。2/5/202351數(shù)據(jù)結(jié)構(gòu)講義(1)創(chuàng)建一個帶頭結(jié)點(diǎn)的空隊：

LQueue*Init_LQueue(){LQueue*q;QNode*p;q=malloc(sizeof(LQueue));/*申請頭尾指針結(jié)點(diǎn)*/

p=malloc(sizeof(QNode));/*申請鏈隊頭結(jié)點(diǎn)*/

p->next=NULL;q->front=q->rear=p;returnq;}2/5/202352數(shù)據(jù)結(jié)構(gòu)講義(2)入隊

voidIn_LQueue(LQueue*q,datatypex){QNode*p;p=malloc(sizeof(QNnode));/*申請新結(jié)點(diǎn)*/

p->data=x;p->next=NULL;q->rear->next=p;q->rear=p;}2/5/202353數(shù)據(jù)結(jié)構(gòu)講義(3)判隊空intEmpty_LQueue(LQueue*q){if(q->front==q->rear)

return1;elsereturn0;}2/5/202354數(shù)據(jù)結(jié)構(gòu)講義(4)出隊

intOut_LQueue(LQueue*q,datatype*x){QNode*p;if(Empty_LQueue(q))

{printf(＂隊空＂)；return0;}/*隊空，出隊失敗*/

else{p=q->front->next;q->front->next=p->next;*x=p->data;/*隊頭元素放x中*/

free(p);if(q->front->next==NULL)

q->rear=q->front;

/*只有一個元素時，出隊后隊空，此時要修改隊尾指針*/

return1;}}2/5/202355數(shù)據(jù)結(jié)構(gòu)講義3.4隊列應(yīng)用舉例

例3.6

現(xiàn)要求設(shè)計一個算法找一條從迷宮入口到出口的最短路徑。本算法要求找一條迷宮的最短路徑，算法的基本思想為：從迷宮入口點(diǎn)（1,1）出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然后依次再從這些點(diǎn)出發(fā)，再記下所有一步能到達(dá)的坐標(biāo)點(diǎn)，…，依此類推，直到到達(dá)迷宮的出口點(diǎn)(m,n)為止，然后從出口點(diǎn)沿搜索路徑回溯直至入口。這樣就找到了一條迷宮的最短路徑，否則迷宮無路徑。2/5/202356數(shù)據(jù)結(jié)構(gòu)講義有關(guān)迷宮的數(shù)據(jù)結(jié)構(gòu)、試探方向、如何防止重復(fù)到達(dá)某點(diǎn)以避免發(fā)生死循環(huán)的問題與例3.2處