第3章棧和隊列.doc

第三章 棧和隊列棧和隊列是在軟件設(shè)計中常用的兩種數(shù)據(jù)結(jié)構(gòu)，它們的邏輯結(jié)構(gòu)和線性表相同。其特點(diǎn)在于運(yùn)算受到了限制：棧按“后進(jìn)先出”的規(guī)則進(jìn)行操作，隊按“先進(jìn)先出”的規(guī)則進(jìn)行操作，故稱運(yùn)算受限制的線性表。31 棧. 棧的定義及基本運(yùn)算棧是限制在表的一端進(jìn)行插入和刪除的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。如圖3.1.1所示棧中有三個元素，進(jìn)棧的順序是a1、a2、a3，當(dāng)需要出棧時其順序為a3、a2、a1，所以棧又稱為后進(jìn)先出的線性表（Last In First Out），簡稱 LIFO表。入棧出棧a3a2 a1top圖3.1 棧示意圖在日常生活中，有很多后進(jìn)先出的例子，讀者可以列舉。在程序設(shè)計中，常常需要棧這樣的數(shù)據(jù)結(jié)構(gòu)，使得與保存數(shù)據(jù)時相反順序來使用這些數(shù)據(jù)，這時就需要用一個棧來實現(xiàn)。對于棧，常做的基本運(yùn)算有： 棧初始化：Init_Stack(s)初始條件：棧s不存在操作結(jié)果：構(gòu)造了一個空棧。 判棧空：Empty_Stack(s)初始條件：棧s已存在操作結(jié)果：若s為空棧返回為1，否則返回為0。 入棧： Push_Stack(s，x)初始條件：棧s已存在 操作結(jié)果：在棧s的頂部插入一個新元素x， x成為新的棧頂元素。棧發(fā)生變化。 出棧：Pop_Stack(s)初始條件：棧s存在且非空操作結(jié)果：棧s的頂部元素從棧中刪除，棧中少了一個元素。棧發(fā)生變化。 讀棧頂元素：Top_Stack(s)初始條件：棧s存在且非空操作結(jié)果：棧頂元素作為結(jié)果返回，棧不變化。3.1.2 棧的存儲實現(xiàn)和運(yùn)算實現(xiàn)由于棧是運(yùn)算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也是適用的，只是操作不同而已。1 順序棧 利用順序存儲方式實現(xiàn)的棧稱為順序棧。類似于順序表的定義，棧中的數(shù)據(jù)元素用一個預(yù)設(shè)的足夠長度的一維數(shù)組來實現(xiàn)：datatype dataMAXSIZE，棧底位置可以設(shè)置在數(shù)組的任一個端點(diǎn)，而棧頂是隨著插入和刪除而變化的，用一個int top 來作為棧頂?shù)闹羔?，指明?dāng)前棧頂?shù)奈恢?，同樣將data和top封裝在一個結(jié)構(gòu)中，順序棧的類型描述如下：#define MAXSIZE 1024 typedef struct datatype dataMAXSIZE; int top; SeqStack定義一個指向順序棧的指針： SeqStack *s;通常0下標(biāo)端設(shè)為棧底，這樣空棧時棧頂指針top=-1; 入棧時，棧頂指針加，即s-top+; 出棧時，棧頂指針減，即s-top-。棧操作的示意圖如圖3.2所示。圖(a)是空棧，圖(c)是A、B、C、D、E 5個元素依次入棧之后，圖(d)是在圖(c)之后E、D相繼出棧，此時棧中還有3個元素，或許最近出棧的元素D、E仍然在原先的單元存儲著，但top指針已經(jīng)指向了新的棧頂，則元素D、E已不在棧中了，通過這個示意圖要深刻理解棧頂指針的作用。 在上述存儲結(jié)構(gòu)上基本操作的實現(xiàn)如下： top=-1 top=0 top=4 top=2 top=-1(a)空棧 (b)一個元素 (c)5個元素 (d)3個元素 (e)空棧 圖3.2 棧頂指針top與棧中數(shù)據(jù)元素的關(guān)系 置空棧：首先建立?？臻g，然后初始化棧頂指針。SeqStack *Init_SeqStack() SeqStack *s;s=malloc(sizeof(SeqStack);s-top= -1; return s; 判空棧 int Empty_SeqStack(SeqStack *s) if (s-top= = -1) return 1; else return 0; 入棧int Push_SeqStack (SeqStack *s, datatype x) if (s-top= =MAXSIZE-1) return 0; /*棧滿不能入棧*/ else s-top+; s-datas-top=x; return 1; 出棧 int Pop_SeqStack(SeqStack *s, datatype *x) if (Empty_SeqStack ( s ) ) return 0; /*?？詹荒艹鰲?*/ else *x=s-datas-top; s-top-; return 1; /*棧頂元素存入*x，返回*/ 取棧頂元素 datatype Top_SeqStack(SeqStack *s) if ( Empty_SeqStack ( s ) ) return 0; /*棧空*/ else return (s-datas-top ); 以下幾點(diǎn)說明： 1. 對于順序棧，入棧時，首先判棧是否滿了，棧滿的條件為：s-top= =MAXSIZE-1，棧滿時，不能入棧; 否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。 2. 出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常?？諘r常作為一種控制轉(zhuǎn)移的條件。2. 鏈棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。通常鏈棧用單鏈表表示，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同，在此用LinkStack表示，即有： typedef struct node datatype data;struct node *next;StackNode，* LinkStack; 說明top為棧頂指針： LinkStack top ;因為棧中的主要運(yùn)算是在棧頂插入、刪除，顯然在鏈表的頭部做棧頂是最方便的，而且沒有必要象單鏈表那樣為了運(yùn)算方便附加一個頭結(jié)點(diǎn)。通常將鏈棧表示成圖3.3的形式。鏈?；静僮鞯膶崿F(xiàn)如下：圖3.3 鏈棧示意圖top 置空棧 LinkStack Init_LinkStack（） return NULL; 判?？読nt Empty_LinkStack（LinkStack top ） if（top=-1） return 1; else return 0; 入棧 LinkStack Push_LinkStack（LinkStack top, datatype x） StackNode *s; s=malloc（sizeof（StackNode）; s-data=x; s-next=top; top=s; return top; 出棧LinkStack Pop_LinkStack (LinkStack top, datatype *x) StackNode *p; if （top= =NULL） return NULL; else *x = top-data; p = top; top = top-next; free (p); return top; 32 棧的應(yīng)用舉例由于棧的“先進(jìn)先出”特點(diǎn)，在很多實際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行求解，下面通過幾個例子進(jìn)行說明。例 3.1 簡單應(yīng)用：數(shù)制轉(zhuǎn)換問題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456，r=8為例轉(zhuǎn)換方法如下： N N / 8 （整除） N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：（3456）10 =（6563）8我們看到所轉(zhuǎn)換的8進(jìn)制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想如下：當(dāng)N0時重復(fù)1，21 若 N0，則將N % r 壓入棧s中 ，執(zhí)行2;若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。2 用N / r 代替 N算法如下： typedef int datatype; #define L 10void conversion(int N，int r) void conversion(int N，int r) SeqStack s; int sL,top; /*定義一個順序棧*/datetype x; int x;Init_SeqStack(&s); top =-1; /*初始化棧*/while ( N ) while ( N ) Push_SeqStack ( &s ，N % r ); s+top=N%r; /*余數(shù)入棧 */ N=N / r ; N=N / r ; /* 商作為被除數(shù)繼續(xù) */ while ( Empty_SeqStack(& s ) ) while (top!=-1) Pop_SeqStack (&s ，&x ) ; x=stop-; printf ( “ %d ”，x ) ; printf(“%d”,x); 算法3.1(a) 算法3.1(b)算法3.1(a)是將對棧的操作抽象為模塊調(diào)用，使問題的層次更加清楚。而算法3.1(b)中的直接用int向量S和int 變量top作為一個棧來使用，往往初學(xué)者將棧視為一個很復(fù)雜的東西，不知道如何使用，通過這個例子可以消除棧的“神秘”，當(dāng)應(yīng)用程序中需要一個與數(shù)據(jù)保存時相反順序使用數(shù)據(jù)時，就要想到棧。通常用順序棧較多，因為很便利。在后面的例子中，為了在算法中表現(xiàn)出問題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，如象算法3.1(a)那樣，對余數(shù)的入棧操作：Push_SeqStack ( &s ，N % r ); 因為是用c語言描述，第一個參數(shù)是棧的地址才能對棧進(jìn)行加工。在后面的例子中，為了算法的清楚易讀，在不至于混淆的情況下，不再加地址運(yùn)算符，請讀者注意。例 3.2 利用棧實現(xiàn)迷宮的求解。問題： 這是實驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜索方法。下面的求解過程采用回溯法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向 ; 若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時，能正確返回前一點(diǎn)以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。 需要解決的四個問題：1 表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用mazemn來表示一個迷宮，mazeij=0或1; 其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時，中間點(diǎn)有8個方向可以試探，（見圖3.4）而四個角點(diǎn)有3個方向，其它邊緣點(diǎn)有5個方向，為使問題簡單化我們用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點(diǎn)的試探方向全部為8，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相一致。 如圖3.4表示的迷宮是一個68的迷宮。 入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。 入口(1,1) 01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111 出口 (6,8) 圖 3.4 用mazem+2n+2表示的迷宮迷宮的定義如下：#define m 6 /* 迷宮的實際行 */#define n 8 /* 迷宮的實際列 */int maze m+2n+2 ;2試探方向：在上述表示迷宮的情況下，每個點(diǎn)有8個方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x,y)，與其相鄰的8個點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到，如圖3.5所示。因為出口在（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ù)組如圖3.6所示。Move數(shù)組定義如下：typedef struct int x，y item ; item move8 ;這樣對move的設(shè)計會很方便地求出從某點(diǎn) (x，y) 按某一方向 v (0=v5,8,25,7,05,6,04,5,1top 3,6,03,6,3 3,5,03,5,0 3,4,03,4,0 3,3,03,3,0 2,2,12,2,1 1,1,11,1,1棧中每一組數(shù)據(jù)是所到達(dá)的每點(diǎn)的坐標(biāo)及從該點(diǎn)沿哪個方向向下走的，對于圖3.4迷宮，走的路線為：(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)。棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：typedef structint x , y , d ;/* 橫縱坐標(biāo)及方向*/datatype ;棧的定義仍然為： SeqStack s ;4 如何防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)： 一種方法是另外設(shè)置一個標(biāo)志數(shù)組markmn，它的所有元素都初始化為0，一旦到達(dá)了某一點(diǎn) ( i , j )之后，使markij 置1，下次再試探這個位置時就不能再走了。另一種方法是當(dāng)?shù)竭_(dá)某點(diǎn)（i , j）后使mazeij 置 -1，以便區(qū)別未到達(dá)過的點(diǎn)，同樣也能起到防止走重復(fù)點(diǎn)的目的，本書采用后者方法，算法結(jié)束前可恢復(fù)原迷宮。迷宮求解算法思想如下：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 ; else d+ ; 算法如下： int path(maze，move) int mazemn ; item move8 ; SeqStack s ; datetype temp ; int x, 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 (d8) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d ; Push_SeqStack ( s, temp ) ; x=i ; y=j ; mazexy= -1 ; if (x=m&y= =n) return 1 ; /*迷宮有路*/ else d=0 ; else d+ ; /*while (d 、/、%+、-；有括號出現(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)前字符，直到遇到結(jié)束符。根據(jù)運(yùn)算規(guī)則，左括號“（”在棧外時它的級別最高，而進(jìn)棧后它的級別則最低了; 乘方運(yùn)算的結(jié)合性是自右向左，所以，它的棧外級別高于棧內(nèi); 就是說有的運(yùn)算符棧內(nèi)棧外的級別是不同的。當(dāng)遇到右括號“）”時，一直需要對運(yùn)算符棧出棧，并且做相應(yīng)的運(yùn)算，直到遇到棧頂為左括號“(”時，將其出棧，因此右括號“）”級別最低但它是不入棧的。對象棧初始化為空，為了使表達(dá)式中的第一個運(yùn)算符入棧，算符棧中預(yù)設(shè)一個最低級的運(yùn)算符“（”。根據(jù)以上分析，每個運(yùn)算符棧內(nèi)、棧外的級別如下：算符 棧內(nèi)級別 棧外級別 3 4*、/、% 2 2+、- 1 1( 0 4） -1 -1中綴表達(dá)式表達(dá)式 “3*2（4+2*2-*3）-5”求值過程中兩個棧的狀態(tài)情況見圖3.7所示。讀字符 對象棧s1 算符棧s2 說明33(3入棧s1*3(*入棧s223，2(*2入棧s13，2(*入棧s2(3，2(*(入棧s243，2，4(*(4入棧s1+3，2，4(*(+入棧s223，2，4，2(*(+2入棧s1*3，2，4，2(*(+*入棧s223，2，4，2，2(*(+*2入棧s1-3，2，4，4(*(+做2+2=4，結(jié)果入棧s13，2，8(*(做4+4=8，結(jié)果入棧s23，2，8(*(-入棧s23，2，8，1(*(-1入棧s1*3，2，8，1(*(-*入棧s233，2，8，1，3(*(-*3入棧s1)3，2，8，3(*(-做1*3，結(jié)果3入棧s13，2，5(*(做8-3，結(jié)果5入棧s23，2，5(*( 出棧-3，32(*做25，結(jié)果32入棧s196(做3*32，結(jié)果96入棧s196(-入棧s2596，5(-5入棧s1結(jié)束符91(做96-5, 結(jié)果91入棧s1 圖 3.7 中綴表達(dá)式3*2（4+2*2-*3）-5 的求值過程為了處理方便，編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換成等價的后綴表達(dá)式，后綴表達(dá)式的運(yùn)算符在運(yùn)算對象之后。在后綴表達(dá)式中，不在引入括號，所有的計算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行，而不用再考慮運(yùn)算規(guī)則和級別。中綴表達(dá)式“3*2（4+2*2-1*3）-5 ”的后綴表達(dá)式為：“32422*+13*-*5-”。2 后綴表達(dá)式求值計算一個后綴表達(dá)式，算法上比計算一個中綴表達(dá)式簡單的多。這是因為表達(dá)式中即無括號又無優(yōu)先級的約束。具體做法：只使用一個對象棧，當(dāng)從左向右掃描表達(dá)式時，每遇到一個操作數(shù)就送入棧中保存，每遇到一個運(yùn)算符就從棧中取出兩個操作數(shù)進(jìn)行當(dāng)前的計算，然后把結(jié)果再入棧，直到整個表達(dá)式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)，每個表達(dá)式是合乎語法的，并且假設(shè)后綴表達(dá)式已被存入一個足夠大的字符數(shù)組A中，且以#為結(jié)束字符，為了簡化問題，限定運(yùn)算數(shù)的位數(shù)僅為一位且忽略了數(shù)字字符串與相對應(yīng)的數(shù)據(jù)之間的轉(zhuǎn)換的問題。typedef char datetype ; double calcul_exp(char *A) /*本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運(yùn)算結(jié)果*/ Seq_Starck s ; 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). case ch= =+： c =a+b ; break ; case ch= =-： c=a-b ; break ; case ch= =*： c=a*b ; break ; case ch= =/ ： c=a/b ; break ; case ch= =%： c=a%b ; break ; Push_SeqStack (s, c) ; ch=*A+ ; Pop _SeqStack ( s , result ) ;return result ;算法3.3棧中狀態(tài)變化情況：當(dāng)前字符 棧中數(shù)據(jù) 說明3入棧3，入棧3，2，4入棧3，2，4，2入棧3，2，4，2，2入棧3，2，4，4計算，將結(jié)果入棧3，2，8計算，將結(jié)果入棧3，2，8，1入棧3，2，8，1，3入棧3，2，8，3計算，將結(jié)果入棧3，2，5計算，將結(jié)果入棧 3，32計算25，將結(jié)果32入棧*96計算32，將結(jié)果96入棧596，55入棧-96計算96-5，結(jié)果入棧結(jié)束符空結(jié)果出棧圖 3.8 后綴表達(dá)式求值過程3 中綴表達(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中存放。讀者不難寫出算法，在此不在贅述。例3.4 棧與遞歸：棧的一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸過程?，F(xiàn)實中，有許多實際問題是遞歸定義的，這時用遞歸方法可以使許多問題的結(jié)果大大簡化，以 n!為例：n!的定義為：n! =1 n=0 /*遞歸終止條件*/n*(n-1) n0 /*遞歸步驟*/根據(jù)定義可以很自然的寫出相應(yīng)的遞歸函數(shù)int fact (int n) if (n= =0) return 1 ; else return (n* fact (n-1) ) ; 遞歸函數(shù)都有一個終止遞歸的條件，如上例n=0時，將不再繼續(xù)遞歸下去。遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個函數(shù)而已。在每次調(diào)用時系統(tǒng)將屬于各個遞歸層次的信息組成一個活動記錄（ActivaTion Record），這個記錄中包含著本層調(diào)用的實參、返回地址、局部變量等信息，并將這個活動記錄保存在系統(tǒng)的“遞歸工作棧”中，每當(dāng)遞歸調(diào)用一次，就要在棧頂為過程建立一個新的活動記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動記錄出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。下面以求3!為例說明執(zhí)行調(diào)用時工作棧中的狀況。為了方便將求階乘程序修改如下： main () int m，n= ; m=fact (n) ; R1： printf (“%d!=%dn”，n，m) ;參數(shù) 返回地址fact(0)0R2fact(1)1R2 fact(2)2R2fact(3)3R int fact (int n) int f ; if (n= =0) f=1 ; else f=n*fact (n-1) ; 圖3.9 遞歸工作棧示意圖 R2: return f ; 算法3.4其中R1為主函數(shù)調(diào)用fact 時返回點(diǎn)地址，R2為fact函數(shù)中遞歸調(diào)用fact (n -1)時返回點(diǎn)地址。程序的執(zhí)行過程可用圖3.10來示意。設(shè)主函數(shù)中n=3： n=3 n=2 n=1 n=0m=fact(n) f=3*fact(2) f=2*fact(1) f=1*fact(0) f=1 return f； return f return f return f f=3*2*1*1 f=2*1*1 f=1*1 f=1 圖 3.10 fact(3) 的執(zhí)行過程3.3 隊列3.3.1 隊列的定義及基本運(yùn)算前面所講的棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，而在實際問題中還經(jīng)常使用一種“先進(jìn)先出” (FIFO-First In First Out)的數(shù)據(jù)結(jié)構(gòu)：即插入在表一端進(jìn)行，而刪除在表的另一端進(jìn)行，我們將這種數(shù)據(jù)結(jié)構(gòu)稱為隊或隊列，把允許插入的一端叫隊尾(rear) ，把允許刪除的一端叫隊頭(front)。如圖3.11所示是一個有5 個元素的隊列。入隊的順序依次為a1、 a2 、a3 、a4 、 a5 ，出隊時的順序?qū)⒁廊皇莂1、 a2 、a3 、a4 、 a5 。圖3.11 隊列示意圖a1 a2 a3 a4 a5 入隊出隊 顯然，隊列也是一種運(yùn)算受限制的線性表，所以又叫先進(jìn)先出表。 在日常生活中隊列的例子很多，如排隊買東西，排頭的買完后走掉，新來的排在隊尾。在隊列上進(jìn)行的基本操作有：隊列初始化：Init_Queue(q)初始條件： 隊q不存在。操作結(jié)果：構(gòu)造了一個空隊。入隊操作：In_Queue(q,x),初始條件：隊q存在。操作結(jié)果：對已存在的隊列q，插入一個元素x到隊尾，隊發(fā)生變化。出隊操作：Out_Queue(q,x)初始條件: 隊q存在且非空操作結(jié)果：刪除隊首元素，并返回其值，隊發(fā)生變化。讀隊頭元素：Front_Queue(q,x)初始條件: 隊q存在且非空操作結(jié)果：讀隊頭元素，并返回其值，隊不變；判隊空操作：Empty_Queue(q)初始條件：隊q存在操作結(jié)果：若q為空隊則返回為1，否則返回為0。3.3.2 隊列的存儲實現(xiàn)及運(yùn)算實現(xiàn) 與線性表、棧類似，隊列也有順序存儲和鏈?zhǔn)酱鎯煞N存儲方法。 1 順序隊順序存儲的隊稱為順序隊。因為隊的隊頭和隊尾都是活動的，因此，除了隊列的數(shù)據(jù)區(qū)外還有隊頭、隊尾兩個指針。順序隊的類型定義如下：define MAXSIZE 1024 /*隊列的最大容量*/typedef struct datatype dataMAXSIZE; /*隊員的存儲空間*/ int rear,front; /*隊頭隊尾指針*/ SeQueue; 定義一個指向隊的指針變量： SeQueue *sq; 申請一個順序隊的存儲空間： sq=malloc(sizeof(SeQueue); 隊列的數(shù)據(jù)區(qū)為：sq-data0-sq-dataMAXSIZE -1 隊頭指針：sq-front 隊尾指針：sq-rear設(shè)隊頭指針指向隊頭元素前面一個位置，隊尾指針指向隊尾元素（這樣的設(shè)置是為了某些運(yùn)算的方便，并不是唯一的方法）。置空隊則為：sq-front=sq-rear=-1;在不考慮溢出的情況下，入隊操作隊尾指針加1，指向新位置后，元素入隊。操作如下： sq-rear+; sq-datasq-rear=x; /*原隊頭元素送x中*/在不考慮隊空的情況下，出隊操作隊頭指針加1，表明隊頭元素出隊。操作如下： sq-front+; x=sq-datasq-front;隊中元素的個數(shù)：m=(sq-rear)-(q-front);隊滿時：m= MAXSIZE； 隊空時：m=0。按照上述思想建立的空隊及入隊出隊示意圖如圖3.12所示，設(shè)MAXSIZE=10。 從圖中可以看到，隨著入隊出隊的進(jìn)行，會使整個隊列整體向后移動，這樣就出現(xiàn)了圖3.12(d)中的現(xiàn)象：隊尾指針已經(jīng)移到了最后,再有元素入隊就會出現(xiàn)溢出，而事實上此時隊中并未真的“滿員”，這種現(xiàn)象為“假溢出”，這是由于“隊尾入隊頭出”這種受限制front=rear=-1 front=-1 rear=2 front=5 rear=8 front=5 rear=9(a) 空隊 (b)有3個元素 (c)一般情況 (d) 假溢出現(xiàn)象 圖3.12 隊列操作示意圖 的操作所造成。解決假溢出的方法之一是將隊列的數(shù)據(jù)區(qū)data0.MAXSIZE-1看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱為“循環(huán)隊”，“循環(huán)隊”的示意圖如圖3.13所示。圖3.13 循環(huán)隊列示意圖因為是頭尾相接的循環(huán)結(jié)構(gòu)，入隊時的隊尾指針加1操作修改為：sq-rear=(sq-rear+1) % MAXSIZE; 出隊時的隊頭指針加1操作修改為：sq-front=(sq-front+1) % MAXSIZE;設(shè)MAXSIZE=10，圖3.14是循環(huán)隊列操作示意圖。 front=4 rear=8 front=-1 rear=2 front=5 rear=8 front=5 rear=9(a) 有4個元素 (b) 隊滿 (c) 隊空 (d) 隊滿 圖3.1 循環(huán)隊列操作示意圖 從圖3.14所示的循環(huán)隊可以看出，(a)中具有 a5 、a6 、a7 、a8四個元素，此時front=4,rear=8；隨著a9a14相繼入隊，隊中具有了10個元素-隊滿，此時 front=4,rear=4,如（b）所示，可見在隊滿情況下有：front=rear。若在（a）情況下，a5a8相繼出隊，此時隊空， 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ū)別開。下面的循環(huán)隊列及操作按第一種方法實現(xiàn)。循環(huán)隊列的類型定義及基本運(yùn)算如下：typedef struct datatype dataMAXSIZE; /*數(shù)據(jù)的存儲區(qū)*/ int front,rear; /*隊頭隊尾指針*/ int num; /*隊中元素的個數(shù)*/ c_SeQueue; /*循環(huán)隊*/ 置空隊c_SeQueue* Init_SeQueue() q=malloc(sizeof(c_SeQueue);q-front=q-rear=MAXSIZE-1;q-num=0;return q; 入隊 int In_SeQueue ( c_SeQueue *q , datatype x) if (num=MAXSIZE) printf(隊滿);return 1; /*隊滿不能入隊*/ else q-rear=(q-rear+1) % MAXSIZE; q-dataq-rear=x; num+; return 1; /*入隊完成*/ 出隊int Out_SeQueue (c_SeQueue *q , datatype *x) if (num=0) printf(隊空)；return 1; /*隊空不能出隊*/ else q-front=(q-front+1) % MAXSIZE; *x=q-dataq-front; /*讀出隊頭元素*/ num-; return 1; /*出隊完成*/ 判隊空int Empty_SeQueue(c_SeQueue *q) if (num=0) return 1; else return 0; 2 鏈隊鏈?zhǔn)酱鎯Φ年牱Q為鏈隊。和鏈棧類似，用單鏈表來實現(xiàn)鏈隊，根據(jù)隊的FIFO原則，為了操作上的方便，我們分別需要一個頭指針和尾指針，如圖3.15所示。 圖3.15 鏈隊示意圖a2rearfronta1an圖3.15中頭指針front和尾指針rear是兩個獨(dú)立的指針變量，從結(jié)構(gòu)性上考慮，通常將二者封裝在一個結(jié)構(gòu)中。鏈隊的描述如下： typedef struct node datatype data