4.1棧及其基本運(yùn)算4.2棧的實(shí)現(xiàn)4.3棧的應(yīng)用*4.4隊(duì)列4.5隊(duì)列的實(shí)現(xiàn)4.6隊(duì)列的應(yīng)用農(nóng)夫過(guò)河問(wèn)題*4.7限制存取點(diǎn)的表* 棧和隊(duì)列也是線性表，只不過(guò)是操作受限的特殊的線性表。線性表的插入、刪除操作是不受限制的；而棧的插入、刪除操作只能在表的同一端進(jìn)行；隊(duì)列的插入操作在表的一端進(jìn)行，刪除操作在表的另一端進(jìn)行。 但從數(shù)據(jù)類型角度看，它們是和線性表不相同的兩種重要的數(shù)據(jù)結(jié)構(gòu)。在計(jì)算機(jī)科學(xué)和程序設(shè)計(jì)中有廣泛的應(yīng)用。4.1.1 基本概念棧是限定在表的同一端進(jìn)行插入或刪除操作的線性表。進(jìn)行插入或刪除操作的一端稱為棧頂，另一端稱為棧底。如圖4.1。棧的操作是按后進(jìn)先出的原則進(jìn)行的。又稱為后進(jìn)先出（LIFO）表。k0k1.Kn-1棧頂棧底進(jìn)棧出棧圖4.1 棧4.1棧及其抽象數(shù)據(jù)類型 ADT Stack isoperations Stack createEmptyStack(void) 創(chuàng)建一個(gè)空棧 int isEmptyStack(Stack st) 判斷棧st是否為空棧 void push(Stack st,DataType x) 在棧st的棧頂插入一個(gè)值為x的元素 void pop(Stack st) 從棧st的棧頂刪除一個(gè)元素； DataType top(Stack st) 求棧頂元素的值end ADT Stack 4.2.1順序表示 4.2.2鏈接表示順序表示的棧的定義：struct SeqStack /* 順序棧類型定義 */int MAXNUM;int t; /指示棧頂位置DataType *s;；typedef struct SeqStack, *PSeqStack;PSeqStack pastack; /*指向順序棧的指針變量*/4.2.1順序表示 由于棧是一個(gè)動(dòng)態(tài)結(jié)構(gòu)，而數(shù)組是靜態(tài)結(jié)構(gòu)，因此會(huì)出現(xiàn)所謂的溢出溢出問(wèn)題。為了避免溢出，在對(duì)棧進(jìn)行進(jìn)棧運(yùn)算和出棧運(yùn)算前，應(yīng)分別檢測(cè)棧是否已滿或是否已空。 算法算法 創(chuàng)建空棧創(chuàng)建空棧PSeqStack createEmptyStack_seq( intPSeqStack createEmptyStack_seq( int m ) m ) PSeqStack pastack PSeqStack pastack; ; pastack = new struct SeqStack pastack = new struct SeqStack; ; if (pastack if (pastack!=NULL)!=NULL) pastack-s = new DataTypem pastack-s = new DataTypem; if (pastack if (pastack-s!=NULL)-s!=NULL) pastackpastack-MAXNUM = m; -MAXNUM = m; pastack pastack-t=-1;-t=-1; return (pastackreturn (pastack);); else delete pastack else delete pastack; ; return NULL: return NULL: 算法算法 判斷棧是否為空棧判斷棧是否為空棧int isEmptyStack_seq( PSeqStack pastackint isEmptyStack_seq( PSeqStack pastack ) ) return ( pastack return ( pastack-t = -1 );-t = -1 ); 算法算法4.1 4.1 進(jìn)棧進(jìn)棧void push_seq( PSeqStack pastack, DataTypevoid push_seq( PSeqStack pastack, DataType x ) x ) / /* * 在棧中壓入一元素在棧中壓入一元素x x * */ / if( pastack-t = pastack if( pastack-t = pastack-MAXNUM - 1 )-MAXNUM - 1 ) printf printf( Overflow! n );( Overflow! n ); else else pastack-t = pastack pastack-t = pastack-t + 1;-t + 1; pastack-spastack pastack-spastack-t = x;-t = x; 算法算法4.2 4.2 出棧出棧void pop_seq( PSeqStack pastackvoid pop_seq( PSeqStack pastack ) ) / /* * 刪除棧頂元素刪除棧頂元素 * */ / if (pastack if (pastack-t = -1 )-t = -1 ) printf printf( Underflow!n );( Underflow!n ); else else pastack-t = pastack pastack-t = pastack-t - 1;-t - 1; 算法算法4.3 4.3 取棧頂元素取棧頂元素DataType top_seq( PSeqStack pastackDataType top_seq( PSeqStack pastack ) ) / /當(dāng)當(dāng)pastackpastack所指的棧不為空棧時(shí)，求棧頂元素的值所指的棧不為空棧時(shí)，求棧頂元素的值 return (pastack-spastack return (pastack-spastack-t);-t); 鏈接表示的棧的定義：structstruct Node; Node;typedef struct Node typedef struct Node * *PNodePNode; ; structstruct Node / Node /* * 單鏈表結(jié)點(diǎn)結(jié)構(gòu)單鏈表結(jié)點(diǎn)結(jié)構(gòu) * */ / DataType DataType info; info; PNode PNode link; link;struct LinkStackstruct LinkStack/ /* * 鏈接棧類型定義鏈接棧類型定義 * */ / PNodePNode top; top; / /* * 指向棧頂結(jié)點(diǎn)指向棧頂結(jié)點(diǎn) * */ /;typedef struct LinkStack typedef struct LinkStack * *PLinkStackPLinkStack; ;PLinkstack plstack; /*變量聲明*/ plstacktopinfolink圖4.3 棧的鏈接表示算法算法4.4 4.4 創(chuàng)建一個(gè)空鏈棧創(chuàng)建一個(gè)空鏈棧PLinkStack createEmptyStack_link(voidPLinkStack createEmptyStack_link(void) ) PLinkStack plstack PLinkStack plstack; ; plstack = new struct LinkStack plstack = new struct LinkStack; ; if (plstack if (plstack != NULL) != NULL) plstack plstack-top = NULL;-top = NULL; else else printf(Out printf(Out of space! n); of space! n); return (plstack return (plstack);); 算法算法4.5 4.5 判斷棧是否為空棧判斷棧是否為空棧int isEmptyStack_link( PLinkStack plstackint isEmptyStack_link( PLinkStack plstack ) ) return (plstack return (plstack-top = NULL);-top = NULL); 算法算法4.6 4.6 進(jìn)棧進(jìn)棧void push_link( PLinkStack plstack, DataTypevoid push_link( PLinkStack plstack, DataType x ) x ) / /* * 在棧中壓入一元素在棧中壓入一元素x x * */ / PNode PNode p; p; p = (PNode)malloc( sizeof( struct p = (PNode)malloc( sizeof( struct Node ) ); Node ) ); if ( p = NULL ) if ( p = NULL ) printf(Out printf(Out of space!n); of space!n); else else p-info = x; p-info = x; p-link = plstack p-link = plstack-top;-top; plstack plstack-top = p;-top = p; 算法算法4.7 4.7 出棧出棧void pop_link( PLinkStack plstackvoid pop_link( PLinkStack plstack ) ) PNodePNode p; p; if( isEmptyStack_link( plstackif( isEmptyStack_link( plstack ) ) ) ) printf printf( Empty stack pop.n );( Empty stack pop.n ); elseelse p = plstack p = plstack-top; -top; plstack-top = plstack plstack-top = plstack-top-link;-top-link; free(p free(p);); 算法算法4.8 4.8 取棧頂元素取棧頂元素DataType top_link( PLinkStack plstackDataType top_link( PLinkStack plstack ) ) / /* * 對(duì)非空棧求棧頂元素對(duì)非空棧求棧頂元素 * */ / if (pastack if (pastack-top=NULL)-top=NULL) cout”Stack is empty!”endl cout”Stack is empty!”top-info);-top-info); l作業(yè)：p114 l復(fù)習(xí)題 2，3l算法題 7l補(bǔ)充題目：l1、編寫一個(gè)算法，識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否是形如“序列1&序列2”模式的字符序列，其中序列1和序列2都不含字符“&”，且序列1是序列2的逆序列。例如，“a+b&b+a”是屬于該模式的字符序列，而“1+2&2-1”則不是。l2、假設(shè)一個(gè)算術(shù)表達(dá)式可以包含三種括號(hào)：圓括號(hào)“（”和“）”、方括號(hào)“”和“”和花括號(hào)“”和“”，且這三種括號(hào)可按任意的次序嵌套使用。編寫判別給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法（已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中）。l實(shí)驗(yàn)3.1 鏈棧的設(shè)計(jì)與實(shí)現(xiàn)l網(wǎng)絡(luò)課堂：4 棧和隊(duì)列（1） 4.3.1棧與遞歸 遞歸 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換 簡(jiǎn)化的背包問(wèn)題* 4.3.2迷宮問(wèn)題 4.3.3表達(dá)式計(jì)算 后綴表達(dá)式的求值 中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換 如果一個(gè)對(duì)象部分的由自己組成，或者是按它自己定義的，則稱為遞歸的。 一個(gè)遞歸定義必須一步比一步簡(jiǎn)單，最后是有終結(jié)的，決不能無(wú)限循環(huán)下去。在n階乘的定義中，當(dāng)n為0時(shí)定義為1，它不再用遞歸來(lái)定義，稱為遞歸定義的出口，簡(jiǎn)稱為遞歸出口。 4.3.1 棧與遞歸一. 遞歸的定義1. 自然數(shù) （a）1是自然數(shù)； （b）自然數(shù)的后繼是自然數(shù)3. 階乘函數(shù) n! 1 n=0 n*f(n-1) n0 遞歸算法主要適用于要解決的問(wèn)題,要計(jì)算的函數(shù),要處理的數(shù)據(jù)結(jié)構(gòu)已是遞歸定義的場(chǎng)合.F(n)= 2. 簡(jiǎn)單算術(shù)表達(dá)式（a）常數(shù)，變量，函數(shù)引用是表達(dá)式；（b) 若e1,e2是表達(dá)式, op為運(yùn)算符，則 e1 op e2, op e1, (e1) 也是表達(dá)式。算法4.11 階乘的遞歸計(jì)算 int fact (int n) if (n = = 0) return 1;else return(n*fact(n-1); ; r2main( ) int n; scanf(“%dn”,&n); printf(“%8d%8dn”,n,fact(n); r133r12r21r20r21126調(diào)用前：（1）為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)； （活動(dòng)記錄， 數(shù)據(jù)區(qū)）（2）將所有的實(shí)參、返回地址傳遞給被調(diào)用函數(shù)； 實(shí)參和形參的結(jié)合，傳值。（2）（3）將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口。調(diào)用后返回：（1）保存被調(diào)用函數(shù)的計(jì)算結(jié)果；（2）釋放被調(diào)用函數(shù)的存儲(chǔ)區(qū)；（3）依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn) 移到調(diào)用函數(shù)。二. 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換 函數(shù)嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則進(jìn)行。int main() int m,n; . first(m,n);1: int first(int s, int t) int i; second(i);2: int second(int d) intx,y;3: 聲明部分； int i, j; 函數(shù)1； int i, j; 函數(shù)2；intmain()intm,n;.inti;intx,y;3:2:1:firstmainsecond 算法4.12 階乘的非遞歸計(jì)算程序員自己管理一個(gè)棧，并模擬函數(shù)調(diào)用的執(zhí)行過(guò)程。 int nfact(int n); int res; pSeqStack st; st=createEmptyStack-seq(); while (n0) while (!isEmptyStack-seq(st) push-seq(st,n); res=res*top-seq(st); n=n-1; pop-seq(st); res=1; free(st); return(st); 一個(gè)背包可以放入的物品重量為s，現(xiàn)有n件物品，重量分別為w1,w2,wn,問(wèn)能否從這些物品中選若干件放入背包中，使得放入的重量之和正好是s。如果存在一種符合上述要求的選擇，則稱此背包問(wèn)題有解，否則此問(wèn)題無(wú)解。 背包問(wèn)題表示： int knap(int s, int n ) 其中，s=0, n=1 如果有解： 1. 選擇的一組物品中不包含wn; knap( s, n-1 ) 的解就是knap( s, n)的解； 2. 選擇的一組物品中包含wn; knap( s-wn, n -1 )的解就是knap( s, n)的解.三 . 簡(jiǎn)化的背包問(wèn)題*背包問(wèn)題可遞歸定義如下： 1 s = 0 0 s 0 , n 0,n=1 算法4.13 背包問(wèn)題的遞歸算法int knap(int s, int n) if( s=0) return 1; else if(s0 & n1) return 0; else if(knap(s-wn-1, n-1) = 1) printf(“n=%d,w%d=%dn”, n, n-1, wn-1); return 1; else return (knap(s, n-1); 1. 設(shè)計(jì)一個(gè)棧st，棧中的每個(gè)結(jié)點(diǎn)包含以下四個(gè)字段：參數(shù)s, n,返回地址r和結(jié)果單元k。由于knap算法中有兩處要遞歸調(diào)用knap算法，所以返回地址一共有三種情況：第一，計(jì)算knap( s0 , n0 )完畢，返回到調(diào)用本函數(shù)的其它函數(shù)；第二，計(jì)算knap( s wn-1 , n - 1 )完畢，返回到本調(diào)用函數(shù)中繼續(xù)計(jì)算；第三，計(jì)算knap( s , n - 1 )完畢，返回到本調(diào)用函數(shù)繼續(xù)計(jì)算。 為區(qū)分三種返回，r分別用1，2，3表示，另外引入一個(gè)變量x作為進(jìn)出棧的緩沖。 棧用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，棧中元素和變量的說(shuō)明如下：struct NodeBag /* 棧中元素的定義 */ int s , n ; int r ; /* r的值為1,2,3 */ int k; ;typedef struct NodeBag DataType;PSeqStack st;struct NodeBag x;2. 轉(zhuǎn)換的做法按以下規(guī)律進(jìn)行，凡調(diào)用語(yǔ)句 knap( s1 , n1 )均代換成： (1) x.s = s1 ； x.n = n1 ； x.r = 返回地址編號(hào)； (2) push_seq( st, x ); (3) goto 遞歸入口。將調(diào)用返回統(tǒng)一處理成： (1) x = top_seq( st ); (2) pop_seq( st ); (3) 根據(jù)x.r的值,進(jìn)行相應(yīng)處理 x.r = 1 , 返回; x.r = 2 , 繼續(xù)處理1; x.r = 3 , 繼續(xù)處理2; 并將算法中的所有局部量都改用棧st中棧頂結(jié)點(diǎn)的相應(yīng)字段，為了在算法中直接引入棧，并在書寫上一致，算法開(kāi)頭增加將結(jié)點(diǎn)( s , n , 1 )推入棧st中的動(dòng)作. 算法4.14 背包問(wèn)題的非遞歸算法 (a) 迷宮的圖形表示 (b) 迷宮的二維數(shù)組表示 求解迷宮中一條路徑的方法： 從入口出發(fā)，沿某一方向進(jìn)行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進(jìn)行探索，直到所有可能的通路都探索到為止。這類方法統(tǒng)稱回溯法。 用一個(gè)棧記錄走過(guò)的位置，棧中每個(gè)元素包括三項(xiàng)，分別記錄當(dāng)前位置的行坐標(biāo)、列坐標(biāo)以及在該位置上所選的方向（即directon數(shù)組的下標(biāo)值） 把入口壓入棧中;while 棧不空時(shí) 取棧頂元素; while 存在試探方向 求下一個(gè)方塊位置mazegh; if (mazegh是出口塊) 打印路徑上的每一個(gè)方塊;return; if(mazegh= =0) /*可前進(jìn)*/ 標(biāo)記mazegh;(g,h,方向)進(jìn)棧; 前進(jìn)到下一個(gè)位置; 討論在某一位置進(jìn)行試探，討論在某一位置進(jìn)行試探，設(shè)迷宮中任一位置（i, j)N(i-1,j)w(i,j-1) (i, j) E(i,j+1) S(i+1,j) i 增值 j 增值 方向 0 0 1 E 1 1 0 S 2 0 -1 W 3 -1 0 N Drection42棧用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，棧中元素的說(shuō)明如下： struct NodeMaze int x,y,d;typedef struct NodeMaze DataType;令k取0,1,2,3之一，表示試探方向，則試探位置為： g=i+directionk0; h=j+directionk1;算法4.15 求迷宮中一條路徑的算法 3*（7+3*6/2-5） $*(+/ =3*（7+18/2-5） $*(+-=3*（7+9-5） $ *(-=3*（16-5） $ *()=3*11 op1op2 : op1優(yōu)先于op2 4.3.3 表達(dá)式求值(1) 假定所有運(yùn)算分量都是整數(shù)；(2) 所有運(yùn)算符都是整數(shù)的二元操作，且都用一個(gè)字符表示。 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式： 優(yōu)先關(guān)系表+op1op2輸入：3 *（7 + 3 * 6 / 2-5$)運(yùn)算對(duì)象棧運(yùn)算符棧3$*(7+3*618/2916-51133 實(shí)現(xiàn)這個(gè)轉(zhuǎn)換的基本思想是：順序掃描中綴表達(dá)式，當(dāng)讀入一個(gè)運(yùn)算分量時(shí)就立即輸出;而在讀入一個(gè)操作符(如 + 或 -)時(shí)，首先把它放進(jìn)一個(gè)運(yùn)算符棧，一直等到這個(gè)運(yùn)算符的兩個(gè)運(yùn)算分量都讀到后，才能將它輸出。當(dāng)掃描遇到一個(gè)左括號(hào)時(shí)立刻將它推入棧中，棧中左括號(hào)的優(yōu)先級(jí)被視為比任何操作符都低。繼續(xù)掃描直到出現(xiàn)右括號(hào)時(shí)，才將留在棧中這對(duì)括號(hào)之間的操作符逐一彈出并輸出，最后彈出左括號(hào)。注意，在后綴表達(dá)式中不再需要任何括號(hào)，所以不必將左右括號(hào)輸出。最后，當(dāng)處理達(dá)到輸入串的末尾時(shí)，將棧中操作符全部彈出并輸出。 隊(duì)列也是一種特殊的線性表，對(duì)于它所有的插入都在表的一端進(jìn)行，所有的刪除都在表的另一端進(jìn)行。進(jìn)行刪除的這一端叫隊(duì)列的頭，進(jìn)行插入的這一 端叫隊(duì)列的尾。當(dāng)隊(duì)列中沒(méi)有任何元素時(shí)，稱為空隊(duì)列。隊(duì)列也稱作先進(jìn)先出表。 k1 k2 k3 . kn-1隊(duì)頭隊(duì)尾進(jìn)隊(duì)出隊(duì)4.4.2 抽象數(shù)據(jù)類型 ADT Queue isoperation Queue createEmptyQueue ( void ) 創(chuàng)建一個(gè)空隊(duì)列 int isEmptyQueue ( Queue qu ) 判隊(duì)列是否為空隊(duì)列 void enQueue ( Queue qu, DataType x ) 往隊(duì)列中插入一個(gè)值為x的元素 void deQueue ( Queue qu ) 從隊(duì)列中刪除一個(gè)元素DataType frontQueue ( Queue qu ) 求隊(duì)列頭部元素的值end ADT Queue4.5隊(duì)列的實(shí)現(xiàn) 4.5.1順序表示 4.5.2鏈接表示StructSeqQueueintMAXNUM;intf,r;DataType*q;TypedefstructSeqQueue*PSeqQueue;PSeqQueuepaqu;76543210paqu.fpaqu.rk1k2k3paqu.fpaqu.rpaqu.rpaqu.fk8k7隊(duì)列空隊(duì)列數(shù)組越界普通情況paqu.rpaqu.fk1k2k7k6k5k4k3paqu.fpaqu.r圖(a)空隊(duì)列圖(b)隊(duì)列滿，判斷paqu.r+1 = = paqu.f循環(huán)隊(duì)列 圖4.11 循環(huán)隊(duì)列創(chuàng)建一個(gè)空隊(duì)列創(chuàng)建一個(gè)空隊(duì)列PSeqQueue createEmptyQueue_seq( intPSeqQueue createEmptyQueue_seq( int m ) m ) PSeqQueue paqu PSeqQueue paqu; ; paqu = new struct SeqQueue paqu = new struct SeqQueue; ; if (paqu if (paqu!=NULL) !=NULL) paqu-q = new DataTypem paqu-q = new DataTypem; if (paqu if (paqu-q != NULL)-q != NULL) paqu paqu-MAXNUM = m;-MAXNUM = m; paqu paqu-f = 0;-f = 0; paqu paqu-r = 0;-r = 0; return (paqu return (paqu);); else delete paqu else delete paqu; ; coutOut of space!endl coutOut of space!f = paqu return (paqu-f = paqu-r);-r); 算法算法4.13 4.13 進(jìn)隊(duì)列運(yùn)算進(jìn)隊(duì)列運(yùn)算void enQueue_seq( PSeqQueue paqu, DataTypevoid enQueue_seq( PSeqQueue paqu, DataType x ) x )/ /* * 在隊(duì)列中插入一元素在隊(duì)列中插入一元素x x * */ / if( (paqu-r + 1) % paqu-MAXNUM = paqu if( (paqu-r + 1) % paqu-MAXNUM = paqu-f )-f ) printf printf( Full queue.n );( Full queue.n ); else else paqu-qpaqu paqu-qpaqu-r = x;-r = x; paqu-r = (paqu-r + 1) % paqu paqu-r = (paqu-r + 1) % paqu-MAXNUM;-MAXNUM; 算法算法4.14 4.14 出隊(duì)出隊(duì)void deQueue_seq( PSeqQueue paquvoid deQueue_seq( PSeqQueue paqu ) )/ /* * 刪除隊(duì)列頭部元素刪除隊(duì)列頭部元素 * */ / if( paqu-f = paqu if( paqu-f = paqu-r )-r ) printf printf( Empty Queue.n );( Empty Queue.n ); else else paqu-f = (paqu-f + 1) % paqu paqu-f = (paqu-f + 1) % paqu-MAXNUM;-MAXNUM; 算法算法4.15 4.15 取隊(duì)列的頭元素取隊(duì)列的頭元素DataType frontQueue_seq( PSeqQueue paquDataType frontQueue_seq( PSeqQueue paqu ) )/ /* * 對(duì)非空隊(duì)列對(duì)非空隊(duì)列, ,求隊(duì)列頭部元素求隊(duì)列頭部元素 * */ / if( paqu-f = paqu if( paqu-f = paqu-r )-r ) printf printf( Empty Queue.n );( Empty Queue.n ); else else return (paqu-qpaqu return (paqu-qpaqu-f);-f); structNode;typedefstructNode*PNode;structNodeDataTypeinfo;PNodelink;structLinkQueuePNodef;PNoder;typedefstructLinkQueue,*PLinkQueue;4.5.2鏈接表示鏈接表示 k0k1k2kn-1. 圖4.12 隊(duì)列的鏈接表示plqu fr算法算法4.16 4.16 創(chuàng)建一個(gè)空隊(duì)列創(chuàng)建一個(gè)空隊(duì)列PLinkQueue createEmptyQueue_linkPLinkQueue createEmptyQueue_link( )( ) PLinkQueue plqu PLinkQueue plqu; ; plqu = (PLinkQueue )malloc(sizeof(struct plqu = (PLinkQueue )malloc(sizeof(struct LinkQueueLinkQueue);); if (plqu if (plqu!=NULL)!=NULL) plqu plqu-f = NULL;-f = NULL; plqu plqu-r = NULL;-r = NULL; else else printf(Out printf(Out of space! n); of space! n); return (plqu return (plqu);); 運(yùn)算的實(shí)現(xiàn)算法算法4.17 4.17 判斷鏈接表示隊(duì)列是否為空隊(duì)列判斷鏈接表示隊(duì)列是否為空隊(duì)列 int isEmptyQueue_link( PLinkQueue plquint isEmptyQueue_link( PLinkQueue plqu ) ) return (plqu return (plqu-f = NULL);-f = NULL); 算法算法4.18 4.18 入隊(duì)入隊(duì)void enQueue_link( PLinkQueue plqu, DataTypevoid enQueue_link( PLinkQueue plqu, DataType x ) x ) PNode PNode p; p; p = (PNode )malloc( sizeof( struct p = (PNode )malloc( sizeof( struct Node ) ); Node ) ); if ( p = NULL ) printf(Out if ( p = NULL ) printf(Out of space!); of space!); else p-info = x; else p-info = x; p-link = NULL; p-link = NULL; if (plqu-f = NULL) plqu if (plqu-f = NULL) plqu-f = p;-f = p; else plqu else plqu-r-link = p;-r-link = p; plqu plqu-r = p;-r = p; 算法算法4.19 4.19 出隊(duì)出隊(duì)void deQueue_link( PLinkQueue plquvoid deQueue_link( PLinkQueue plqu ) ) PNode PNode p; p; if( plqu-f = NULL ) printf if( plqu-f = NULL ) printf( Empty queue.n );( Empty queue.n ); else else p = plqu p = plqu-f;-f; plqu-f = plqu plqu-f = plqu-f-link;-f-link; free(p free(p);); 算法算法4.20 4.20 取隊(duì)列頭部結(jié)點(diǎn)的值取隊(duì)列頭部結(jié)點(diǎn)的值DataType frontQueue_link( PLinkQueue plquDataType frontQueue_link( PLinkQueue plqu ) )/ /* * 在非空隊(duì)列中求隊(duì)頭元素在非空隊(duì)列中求隊(duì)頭元素 * */ / if( plqu-f = NULL ) printf if( plqu-f = NULL ) printf( Empty queue.n );( Empty queue.n ); else return (plqu else return (plqu-f-info);-f-info); 農(nóng)夫過(guò)河問(wèn)題 : 一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問(wèn)題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。顯然，因?yàn)槔悄艹匝颍驉?ài)吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開(kāi)，也不能留下狼和羊自己離開(kāi)。好在狼屬于食肉動(dòng)物，它不吃白菜。請(qǐng)問(wèn)農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過(guò)河 4.6隊(duì)列的應(yīng)用農(nóng)夫過(guò)河問(wèn)題* 用計(jì)算機(jī)實(shí)現(xiàn)上述求解的搜索過(guò)程可以采用兩種不同的策略：一種是廣度優(yōu)先廣度優(yōu)先(breadth_first)搜索，另一種是深度優(yōu)先(depth_first)。而實(shí)現(xiàn)這兩種策略所依賴的數(shù)據(jù)結(jié)構(gòu)正好是前面介紹的隊(duì)列和棧。本節(jié)討論隊(duì)列的應(yīng)用，所以下面重點(diǎn)介紹廣度優(yōu)先的策略。 農(nóng)夫過(guò)河問(wèn)題具體算法Path：15，6，14，2，11，1，9，0從初始狀態(tài)0到最終狀態(tài)15的動(dòng)作序列為： 農(nóng)夫把羊帶到北岸; 1 0000 農(nóng)夫獨(dú)自回到南岸; 2 1001 農(nóng)夫把白菜帶到北岸; 3 0001 農(nóng)夫帶著羊返回南岸; 5 1101 4 1011 農(nóng)夫把狼帶到北岸; 7 0100 6 0010 農(nóng)夫獨(dú)自返回南岸; 8 1110 農(nóng)夫把羊帶到北岸。 9 0110 10 1111 圖 4.11 廣度優(yōu)先搜索的結(jié)果和順序 小小 結(jié)結(jié)本章主要討論了兩種操作受限的線性表：棧和隊(duì)列。討論了它們的基本概念、存儲(chǔ)結(jié)構(gòu)、基本運(yùn)算的實(shí)現(xiàn)以及一些應(yīng)用實(shí)例。對(duì)于棧來(lái)說(shuō)，它的插入和刪除都是在表的同一端進(jìn)行的，用順序存儲(chǔ)結(jié)構(gòu)時(shí)，要注意棧滿、?？盏臈l件；用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要注意鏈的方向。對(duì)隊(duì)列來(lái)說(shuō)，它的插入運(yùn)算在表的一端進(jìn)行，而刪除運(yùn)算卻在表的另一端進(jìn)行。根據(jù)隊(duì)列的這一特點(diǎn)，在使用順序存儲(chǔ)結(jié)構(gòu)時(shí)，用了環(huán)形隊(duì)列，這樣可解決假溢出問(wèn)題，但要特別注意隊(duì)列滿和隊(duì)列空的條件及描述。 作業(yè)：p.115 算法題 8，9 補(bǔ)充3. 假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如“abba”和“abcba”是回文，“abcde”和“ababab”則不是回文。試寫一個(gè)算法判別讀入的一個(gè)以“”為結(jié)束符的字符序列是否是回文。l實(shí)驗(yàn)l3.2 循環(huán)隊(duì)列的設(shè)計(jì)與實(shí)現(xiàn)l3.3 鏈隊(duì)列的設(shè)計(jì)與實(shí)現(xiàn)l3.4 病人看病模擬程序l網(wǎng)絡(luò)課堂：4 棧和隊(duì)列（2）