算法與數(shù)據(jù)結構-C語言描述（第二版）：第4章 棧與隊列

1、l對于棧和隊列上的插入、刪除操作是受某種特殊限制的。因此，棧和隊列也稱作操作受操作受限限的表，或者限制存取點限制存取點的表。l本章除了討論棧和隊列的概念、抽象數(shù)據(jù)類型、表示方法和實現(xiàn)算法外，還將給出一些應用的例子。l棧棧是一種特殊的線性表，它所有的插入和刪除都限制在表的同一端進行。l表中允許進行插入、刪除操作的一端叫做棧的頂頂。l表的另一端則叫做棧的底底。l當棧中沒有元素時，稱之為空?？諚?。棧的插入運算通常稱為進棧進?；蛉霔Ｈ霔?，l棧的刪除運算通常稱為退棧退棧或出棧出棧。l棧又稱為后進先出表后進先出表（Last In First Out表，簡稱LIFO表）或下推表下推表，如圖所示 ADT St

2、ack isoperationsStack createEmptyStack ( void ) 創(chuàng)建一個空棧。int isEmptyStack ( Stack st ) 判斷棧st是否為空棧。void push ( Stack st, DataType x ) 往棧st的棧頂插入一個值為x的元素。void pop ( Stack st ) 從棧st的棧頂刪除一個元素。DataType top ( Stack st ) 求棧頂元素的值。end ADT Stack l用順序的方式表示棧時，棧棧的類型可定義如下： struct SeqStack /* 順序棧類型定義 */ int MAXNUM; /

3、* 棧中最大元素個數(shù) */ int t; /* ttop就是棧頂指針，plstack-top-info是棧頂元素， l1.創(chuàng)建空鏈接棧PLinkStack createEmptyStack_link(void) 創(chuàng)建一空鏈接棧，需要申請鏈接棧結構(struct LinkStack)空間，將其中top置為NULL,返回該結構的地址。 程序實現(xiàn)l2. 判斷棧是否為空棧 int isEmptyStack_link( PLinkStack plstack ) 判斷plstack所指的棧是否為空棧，當plstack所指的棧為空棧時，則返回1，否則返回0。 程序實現(xiàn)l3. 進棧運算 void push_l

4、ink( PLinkStack plstack, DataType x ) 往plstack所指的棧中插入（或稱壓入）一個值為x的元素。首先申請結點空間，然后通過指針修改，將結點插在棧頂。 程序實現(xiàn)l4. 出棧運算 void pop_link( PLinkStack plstack ) 出棧運算，表示從plstack所指的棧中刪除（或稱彈出）一個元素。當棧不空時，直接修改棧頂指針，刪除結點。 程序實現(xiàn)l5. 取棧頂元素取棧頂元素 DataType top_link( PLinkStack plstack ) 當plstack所指的棧不空時，取棧頂元素的值，棧保持不變。 程序實現(xiàn)l本節(jié)在引入遞歸

5、概念的基礎上，介紹棧是怎樣用來實現(xiàn)遞歸，以及怎樣把一個遞歸的函數(shù)轉換成一個等價的非遞歸的函數(shù)。l通常用來說明遞歸的最簡單的例子是階乘的定義，它可以表示成： 1 若n = 0n! = n * ( n 1 )! 若n 0這種用自身的簡單情況來定義自己的方式，稱為遞歸定義遞歸定義。在n階乘的定義中，當n為0時定義為1，它不再用遞歸來定義，稱為遞歸定義的出口，簡稱為遞歸出口。遞歸出口。lint fact( int n )l int res=n;l if ( n 1 )lres=res* fact( n 1 );l return res;l 函數(shù)fact( n )中又調用了函數(shù)fact，這種函數(shù)自己調用

6、自己的作法稱為遞歸調用遞歸調用。 包含直接還是間接遞歸調用的函數(shù)都稱為遞歸函數(shù)遞歸函數(shù)。 l遞歸函數(shù)的執(zhí)行過程 假設（主）程序中包含一個k=fact(3)語句，這個語句的執(zhí)行過程如下頁的圖所示。 在fact(3)的計算過程中，我們實際不需要生成3個相同的fact程序，只要一個程序在不同的階段能夠處理(3份)不同數(shù)據(jù)。根據(jù)后進先出的原則，只要保證把最后調用的程序使用的空間，保存在一個棧的棧頂就可以了。 l設有一個程序sub要調用函數(shù)rout(x)，sub本身也可能是一個函數(shù)，我們稱之為調用函數(shù)調用函數(shù)，而稱rout為被調函數(shù)被調函數(shù)。調用函數(shù)中使用調用語句rout(a)來引起rout函數(shù)的執(zhí)行，

7、這里a稱為實參實參。x稱為形參形參。l一般來說，函數(shù)調用的實現(xiàn)可以分解成下列三步來進行： (1) 傳送調用信息。(2) 分配被調函數(shù)需要的數(shù)據(jù)區(qū)，并接收傳送來的調用信息。(3) 把控制轉移到被調函數(shù)的入口。l當被調函數(shù)運行結束，需要返回到調用函數(shù)時，一般的返回處理也可以分解成下列三步：(1) 傳送返回信息。(2) 釋放被調函數(shù)的數(shù)據(jù)區(qū)。(3) 把控制按返回地址轉移到調用函數(shù)中去。l在非遞歸調用的情況下，數(shù)據(jù)區(qū)的分配可以在程序運行前進行，一直到整個程序運行結束才釋放，這種分配稱為靜態(tài)分配靜態(tài)分配。在遞歸調用的情況下，被調函數(shù)的局部量不能分配給固定的某些單元，而必須每調用一次就分配一份，當前程序使

8、用的所有的量（包括形參、局部變量和中間工作單元等），都必須是最近一次遞歸調用時所分配的數(shù)據(jù)區(qū)中的量。即所謂的動態(tài)分配動態(tài)分配。l動態(tài)分配通常的處理方法是：在內存中開辟一個存儲區(qū)域稱為運行棧運行棧（或簡稱棧棧），每次調用時，將動態(tài)區(qū)指針下推，分配被調函數(shù)所需的數(shù)據(jù)區(qū)；在每次返回時，將內存指針上托，釋放本次調用所分配的數(shù)據(jù)區(qū)，恢復到上次調用所分配的數(shù)據(jù)區(qū)中；被調函數(shù)中變量地址全部采用相對于動態(tài)區(qū)指針的位移量來表示（稱為相對地址相對地址）。 根據(jù)上述思想，不難給出算法4.9階乘計算的非遞歸算法。因為只有一處遞歸調用，返回地址（locate）和返回值(fact)都容易控制，而且局部量(res)與參數(shù)(

9、n)關系十分清楚，所以棧中只要保存一個參數(shù)n的值就可以了。這種最簡單的遞歸函數(shù)實現(xiàn)過程相當于下面的一個非遞歸函數(shù)。 lint nfact( int n ) int res; PSeqStack st; /* 使用順序存儲結構實現(xiàn)的棧 */ st = createEmptyStack_seq( ); while (n0) push_seq(st,n); n = n 1; res = 1; while (! isEmptyStack_seq(st)res = res * top_seq(st); pop_seq(st); free(st); return ( res );l在迷宮中求從入口到出口的

10、所有路徑是一個經典的程序設計問題。 迷宮可用圖4.5（a）所示的方塊來表示，其中每個元素或為通道（以空白方塊表示），或為墻（以帶陰影的方塊表示）。迷宮迷宮問題問題要求的就是：從入口到出口的一個以空白方塊構成的(無環(huán))路徑。 l求解迷宮問題的簡單方法是：從入口出發(fā)，沿某一方向進行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進行探索，直到所有可能的通路都探索到為止。這類方法統(tǒng)稱回溯法回溯法用回溯法求迷宮問題解的過程，可以用一個棧來保存探索的序列。其算法框架如下： mazeFrame( void ) 創(chuàng)建一個（保存探索過程的）空棧；把入口位置壓入棧中;while 棧不空時 取棧頂位置并設

11、置為的當前位置; while 當前位置存在試探可能 取下一個試探位置; if (下一個位置是出口) 打印棧中保存的探索過程然后返回 if(下一個位置是通道) 把下一個位置進棧并且設置為的當前位置; 數(shù)據(jù)結構數(shù)據(jù)結構 迷宮可用二維數(shù)組mazemn來表示，數(shù)組中元素為0的表示通道，為1的表示墻。迷宮的入口處為maze11，出口處為mazem-2n-2，它們的元素值必為0。任意時刻在迷宮中的位置可用元素的行下標和列下標(i,j)來表示。在某一點mazeij時，可能的運動方向有四個。可以建立一個數(shù)組direction42 給出相對于位置(i,j)的四個方向上，i與j的增量值。若在位置(i,j)，要進入

12、E方向的位置（g,h），則可根據(jù)由該增量值表來修改(i,j)的坐標，g = i + direction00; h = j + direction01; l棧用順序存儲結構實現(xiàn)，棧中的元素類型DataType說明如下： l typedef struct int x,y,d; DataType;算法的實現(xiàn)算法的實現(xiàn)求迷宮中一條路徑的算法，可以從入口開始，對每個“當前位置”都從E方向（東方向）試起，若不能通過，則順時針試S方向、W方向、N方向。當選定一個可通的方向，即找到“下一個位置”后，要把當前所在的位置納入到探索路徑中，并將當前所在的位置以及所選的方向記錄下來，以便往下走不通時可順原路一步步地退

13、回來，每退一步以后接著試在該點上尚未試過的方向，從“下一個位置”開始繼續(xù)探索，如此重復直至到達出口。 程序實現(xiàn)：void mazePath(int *maze,int *direction,int x1,int y1,int x2,int y2,int M,int N) l為了這里討論的方便，在不影響問題實質的情況下，我們對表達式做如下簡化：l(1) 假定所有運算分量都是整數(shù)；(2) 所有運算符都是整數(shù)的二元操作，且都用一個字符表示。l例如31 (5 - 22) + 70l這類表達式中所有運算符都出現(xiàn)在它的兩個運算分量之間，所以稱為中綴表達式中綴表達式。l處理系統(tǒng)通常先把表達式轉換成另一種等價

14、形式：31 5 22 - 70 +，這種形式稱為后綴表達式后綴表達式。l這種表達式里不再需要有括號，每個運算符都出現(xiàn)在它的兩個運算分量后面。l5 5 (27 + 3 (27 + 3 7) + 22 7) + 22轉化為后綴表達式為：5 27 3 7 5 27 3 7 + + 22 + 22 +舉例：舉例：31*(5-22)+70 轉換為：31 5 22 - * 70 +31*(5-22)+70 *(5-22)+70 31 (5-22)+70 * 31 5-22)+70 (* 31 -22)+70 (* 31 5 22)+70 -(* 31 5 )+70 -(* 31 5 22 +70 * 31

15、 5 22 - 70 + 31 5 22 - * + 31 5 22 - * 70 31 5 22 - * 70 +l后綴表達式的主要優(yōu)點是可以寫出非常簡單的求值過程。使用一個存放運算分量的棧，求值過程順序掃描后綴表達式，每次遇到運算分量便將它推入棧中；遇到運算符時，就從棧中彈出兩個整數(shù)(運算分量)進行計算，而后再把結果推入棧中。這樣，到掃描結束時，留在棧頂?shù)恼麛?shù)就是所求表達式的值。l31 5 22 - * 70 + l 5 22 - * 70 + 31l 22 - * 70 + 5 31l - * 70 + 22 5 31l * 70 + -17 31？l 70 + -527？l + 70

16、-527l -457？l -457 計算結束 l4.4.1 基本概念基本概念 l隊列隊列是一種只允許在表的一端進行插入操作，而在另一端進行刪除操作的線性表。l允許進行刪除的這一端叫隊列的頭頭，允許進行插入的這一 端叫隊列的尾尾。l當隊列中沒有任何元素時，稱為空隊列空隊列。l隊列的插入操作通常稱為進隊列進隊列或入隊列入隊列，隊列的刪除操作通常稱為退隊列退隊列或出隊列出隊列。l隊列也稱作先進先出表先進先出表(First In First Out表，簡稱FIFO表）l4.4.2 抽象數(shù)據(jù)類型ADT Queue isoperationsQueue createEmptyQueue (void ) 創(chuàng)建

17、一個空隊列。int isEmptyQueue ( Queue qu ) 判隊列qu是否為空隊列。void enQueue ( Queue qu, DataType x ) 往隊列qu尾部插入一個值為x的元素。void deQueue ( Queue qu ) 從隊列qu頭部刪除一個元素。DataType frontQueue ( Queue qu ) 求隊列qu頭部元素的值。end ADT Queue l隊列與棧類似，實現(xiàn)時通常采用順序的表示和鏈接的表示。l存儲結構 為了算法設計上的方便，我們約定：隊頭指針指出實際隊頭元素所在的位置，而隊尾指針指出實際隊尾元素所在位置的下一個位置。struct

18、 SeqQueue /* 順序隊列類型定義 */int MAXNUM; /* 隊列中最大元素個數(shù) */int f,r;DataType *q;typedef struct SeqQueue *PSeqQueue;/* 順序隊列類型的指針類型 */l假設paqu是PSeqQueue類型的變量，lpaqu-f存放即將要被刪除的元素的下標，lpaqu-r存放即將要被插入的元素的下標。lpaqu-qpaqu-f表示當前隊列頭部的元素；lpaqu-qpaqu-r表示當前隊列尾部的（即將要插入的）元素。l初始時paqu-f = paqu-r = 0。l當前隊列中元素的個數(shù)=paqu-r - paqu-fl

19、當paqu-r = paqu-f時，元素的個數(shù)為0，即為空隊列。l在順序表示的隊列中，同樣由于數(shù)組是靜態(tài)結構，而隊列是動態(tài)結構，也存在隊列溢出問題，即當隊列滿時，再作進隊操作，這種現(xiàn)象稱為上溢上溢；而當隊空時，作刪除操作，這種現(xiàn)象稱為下溢下溢。這些現(xiàn)象在運算中都要考慮。由于隊列中經常要執(zhí)行插入和刪除運算，而每運行一次插入或刪除，paqu-r或paqu-f就增加1，使得隊列中的元素被刪除后，其空間就永遠使用不到了。隊列的動態(tài)變化猶如使整個隊列向右移動。當paqu-r = MAXNUM時，再作插入運算就會產生溢出，而實際上這時隊列的前端可能還有許多空的（可用的）位置，因此，這種現(xiàn)象稱為假溢出假溢出

20、。 解決假溢出通常采用的方法是： 把數(shù)組paqu-qMAXNUM從邏輯上看成一個環(huán)，這種隊列也稱為環(huán)形隊列環(huán)形隊列。當表中已有MAXNUM 1個結點時，如果還要插入，paqu-r和paqu-f就會重合，而這與空隊列的情形相混。為區(qū)分空隊列與滿隊列兩種情況的環(huán)形隊列，一般是犧牲隊列中的一個結點，當隊列中已有MAXNUM1個結點時就稱滿，再要插入就發(fā)生溢出. (a) (b) 圖4.11 環(huán)形隊列paqu 隊列基本運算的實現(xiàn)l1. 創(chuàng)建一個空隊列。 PSeqQueue createEmptyQueue_seq( int m ) 創(chuàng)建一個空隊。具體實現(xiàn)與算法2.1類似，需要為隊列申請空間，不同之處是需

21、要將對變量f和r均賦值為0。請讀者自己給出。 l2. 判斷是否為空隊列 int isEmptyQueue_seq( PSeqQueue paqu ) 判斷paqu所指的隊列是否為空隊列。當paqu-f = paqu-r時，返回1，否則返回0。l3. 進隊運算 void enQueue_seq( PSeqQueue paqu, DataType x ) 入隊運算，當隊列不滿時，將元素x插入paqu所指隊列的隊尾。 程序實現(xiàn)l4. 出隊列運算 void deQueue_seq( PSeqQueue paqu ) 當隊列不空時，刪除paqu所指隊列的隊頭元素。 程序實現(xiàn)l5. 取隊列頭部元素 Dat

22、aType frontQueue_seq( PSeqQueue paqu ) 當paqu所指的隊列不空時，取隊列頭部元素，隊列本身保持不變。 程序實現(xiàn)l存儲結構 隊列的鏈接表示就是用一個單鏈表來表示隊列，隊列中的每個元素對應鏈表中的一個結點，結點的結構與單鏈表中結點的結構一樣。l為了強調隊頭和隊尾都是隊列的屬性，這里對隊列增加了一層封裝，引入LinkQueue結構的定義。這樣存儲的隊列簡稱鏈接隊列鏈接隊列。 struct Node;typedef struct Node *PNode;struct Node /* 結點結構 */ DataType info; PNode link; ;stru

23、ct LinkQueue /* 鏈接隊列類型定義 */ PNode f; /* 頭指針 */ PNode r; /* 尾指針 */ ;typedef struct LinkQueue *PLinkQueue;/*鏈接隊列類型的指針類型*/l假設plqu是PLinkQueue類型的變量，lplqu-f為隊列的頭指針，指向隊列中第一個結點，lplqu-r是隊列尾指針，指向隊列中最后一個結點(注意：這一點與順序隊列不同！)，l當plqu-f 為 NULL時隊列為空。 隊列的鏈接表示 1. 創(chuàng)建一個空隊列 PLinkQueue createEmptyQueue_link( void ) 申請隊列結構空

24、間，創(chuàng)建一個空隊列。 程序實現(xiàn)l2. 判斷隊列是否為空int isEmptyQueue_link( PLinkQueue plqu )判斷plqu所指的隊列是否為空隊，為空隊時，則返回1，否則返回0。 程序實現(xiàn)l3. 進隊列運算void enQueue_link( PLinkQueue plqu, Datatype x ) 入隊運算，表示往plqu所指的隊列中插入一個值為x的元素。 程序實現(xiàn)l4. 出隊列運算void deQueue_link( PLinkQueue plqu ) 出隊運算，表示從plqu所指的隊列中刪除隊頭元素。 程序實現(xiàn)l5.取隊列頭部結點的值 Datatype front

25、Queue_link( PLinkQueue plqu ) 當plqu所指的隊列非空時，取隊列頭部元素的值，隊列保持不變。 程序實現(xiàn)l一個農夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運到北岸。l問題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農夫能撐船。l請問農夫該采取什么方案才能將所有的東西運過河呢？l算法選擇：算法選擇：l求解這個問題的最簡單的方法是一步一步進行試探，每一步都搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。l用計算機實現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：一種是廣度優(yōu)先廣度優(yōu)先(breadth_first) 搜索，另一

26、種是深度優(yōu)先深度優(yōu)先(depth_first) 。l廣度優(yōu)先：廣度優(yōu)先：l廣度優(yōu)先的含義就是在搜索過程中總是首先搜索下面一步的所有可能狀態(tài)，然后再進一步考慮更后面的各種情況。l要實現(xiàn)廣度優(yōu)先搜索，一般都采用隊列作為輔助結構。把下一步所有可能達到的狀態(tài)都列舉出來，放在這個隊列中，然后順序取出來分別進行處理，處理過程中把再下一步的狀態(tài)放在隊列里。l由于隊列的操作遵循先進先出的原則，在這個處理過程中，只有在前一步的所有情況都處理完后，才能開始后面一步各情況的處理。l要模擬農夫過河問題，首先需要選擇一個對問題中每個角色的位置進行描述的方法。l一個很方便的辦法是用四位二進制數(shù)順序分別表示農夫、狼、白菜和

27、羊農夫、狼、白菜和羊的位置。l例如用0表示農夫或者某東西在河的南岸，1表示在河的北岸。因此整數(shù)5(其二進制表示為0101) 表示農夫和白菜在河的南岸，而狼和羊在北岸。l用整數(shù)location表示上述四位二進制描述的狀態(tài)，l用下面的四個函數(shù)從上述狀態(tài)中得到每個角色所在位置的代碼。l函數(shù)返回值為真表示所考察的人或物在河的北岸，否則在南岸。 lint farmer(int location) return (0 != (location & 0 x08); int wolf(int location) return (0 != (location & 0 x04);lint cabb

28、age(int location) return (0 != (location & 0 x02); int goat(int location) return (0 !=(location & 0 x01);l還應該分析問題中所有角色的各種可能位置構成的狀態(tài)，確定其中哪些是安全的哪些是不安全的。l根據(jù)原題的描述我們知道，單獨留下白菜和羊，或單獨留下狼和羊在某一岸的狀態(tài)是不安全的。l由此可以編一個函數(shù)，通過位置分布的代碼來判斷狀態(tài)是否安全。 lint safe(int location) / 若狀態(tài)安全則返回true / 羊吃白菜 if (goat(location) = ca

29、bbage(location) & (goat(location) != farmer(location) ) return (0); / 狼吃羊 if (goat(location) = wolf(location) & (goat(location) != farmer(location) return (0); return (1); / 其他狀態(tài)是安全的l問題的描述問題的描述：l完成了上面的準備工作，現(xiàn)在的問題變成：l從初始狀態(tài)二進制從初始狀態(tài)二進制0000(全部在河的南岸全部在河的南岸) 出發(fā)，出發(fā)，尋找一種全部由安全狀態(tài)構成的狀態(tài)序列，它尋找一種全部由安全狀態(tài)構成的

30、狀態(tài)序列，它以二進制以二進制1111(全部到達河的北岸全部到達河的北岸) 為最終目標，為最終目標，并且在序列中的每一個狀態(tài)都可以從前一狀態(tài)并且在序列中的每一個狀態(tài)都可以從前一狀態(tài)通過農夫（可以帶一樣東西）劃船過河的動作通過農夫（可以帶一樣東西）劃船過河的動作到達。到達。l為避免不必要的瞎費功夫，要求在序列中不應該出現(xiàn)重復的狀態(tài).l為了實現(xiàn)廣度優(yōu)先搜索，算法中需要使用了一個整數(shù)隊列moveTo，它的每個元素表示一個可以安全到達的中間狀態(tài)。l另外還需要一個數(shù)據(jù)結構記錄已被訪問過的各個狀態(tài)，以及已被發(fā)現(xiàn)的能夠到達當前這個狀態(tài)的路徑。l由于在這個問題的解決過程中需要列舉的所有狀態(tài)(二進制0000 1111)一共16種，所以可以構造一個包含16個元素的整數(shù)順序表來滿足以上的要求。l用順序表的第i個元素記錄狀態(tài)i是否已被訪問過，若已被訪問過則在這個順序表元素中記入前驅狀態(tài)值，算法中把這個順序表叫做route。lroute的每個分量初始化值均為-1，每當我們在隊列中加入一個新狀態(tài)時，就把順序表中以該