《《算法與數(shù)據(jù)結(jié)構(gòu)》教學課件第4章 棧和隊列C語言描述（第2版）張乃孝編著》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學課件第4章 棧和隊列C語言描述（第2版）張乃孝編著（62頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、4.1棧及其基本運算4.2棧的實現(xiàn)4.3棧的應(yīng)用*4.4隊列4.5隊列的實現(xiàn)4.6隊列的應(yīng)用農(nóng)夫過河問題*4.7限制存取點的表* 棧和隊列也是線性表，只不過是操作受限的特殊的線性表。線性表的插入、刪除操作是不受限制的；而棧的插入、刪除操作只能在表的同一端進行；隊列的插入操作在表的一端進行，刪除操作在表的另一端進行。 但從數(shù)據(jù)類型角度看，它們是和線性表不相同的兩種重要的數(shù)據(jù)結(jié)構(gòu)。在計算機科學和程序設(shè)計中有廣泛的應(yīng)用。4.1.1 基本概念棧是限定在表的同一端進行插入或刪除操作的線性表。進行插入或刪除操作的一端稱為棧頂，另一端稱為棧底。如圖4.1。棧的操作是按后進先出的原則進行的。又稱為后進先出（L

2、IFO）表。k0k1.Kn-1棧頂棧底進棧出棧圖4.1 棧4.1棧及其抽象數(shù)據(jù)類型 ADT Stack isoperations Stack 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 4.2.1順序表示 4.2.2鏈接表示順序表示的棧的定義：struc

3、t SeqStack /* 順序棧類型定義 */int MAXNUM;int t; /指示棧頂位置DataType *s;；typedef struct SeqStack, *PSeqStack;PSeqStack pastack; /*指向順序棧的指針變量*/4.2.1順序表示 由于棧是一個動態(tài)結(jié)構(gòu)，而數(shù)組是靜態(tài)結(jié)構(gòu)，因此會出現(xiàn)所謂的溢出溢出問題。為了避免溢出，在對棧進行進棧運算和出棧運算前，應(yīng)分別檢測棧是否已滿或是否已空。 算法算法 創(chuàng)建空棧創(chuàng)建空棧PSeqStack createEmptyStack_seq( intPSeqStack createEmptyStack_seq( int

4、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

5、=-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 進棧進棧void push_s

6、eq( 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;

7、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 -

8、1;-t - 1; 算法算法4.3 4.3 取棧頂元素取棧頂元素DataType top_seq( PSeqStack pastackDataType top_seq( PSeqStack pastack ) ) / /當當pastackpastack所指的棧不為空棧時，求棧頂元素的值所指的棧不為空棧時，求棧頂元素的值 return (pastack-spastack return (pastack-spastack-t);-t); 鏈接表示的棧的定義：structstruct Node; Node;typedef struct Node typedef struct Node * *PNod

9、ePNode; ; structstruct Node / Node /* * 單鏈表結(jié)點結(jié)構(gòu)單鏈表結(jié)點結(jié)構(gòu) * */ / DataType DataType info; info; PNode PNode link; link;struct LinkStackstruct LinkStack/ /* * 鏈接棧類型定義鏈接棧類型定義 * */ / PNodePNode top; top; / /* * 指向棧頂結(jié)點指向棧頂結(jié)點 * */ /;typedef struct LinkStack typedef struct LinkStack * *PLinkStackPLinkStack; ;

10、PLinkstack plstack; /*變量聲明*/ plstacktopinfolink圖4.3 棧的鏈接表示算法算法4.4 4.4 創(chuàng)建一個空鏈棧創(chuàng)建一個空鏈棧PLinkStack createEmptyStack_link(voidPLinkStack createEmptyStack_link(void) ) PLinkStack plstack PLinkStack plstack; ; plstack = new struct LinkStack plstack = new struct LinkStack; ; if (plstack if (plstack != NULL)

11、 != 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 = N

12、ULL);-top = NULL); 算法算法4.6 4.6 進棧進棧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 = NUL

13、L ) 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

14、( 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( P

15、LinkStack plstack ) ) / /* * 對非空棧求棧頂元素對非空棧求棧頂元素 * */ / 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ù)習題 2，3l算法題 7l補充題目：l1、編寫一個算法，識別依次讀入的一個以為結(jié)束符的字符序列是否是形如“序列1&序列2”模式的字符序列，其中序列1和序列2都不含字符“&”，且序列1是序列2的逆序列。例如，“a+b&b+a”是屬于該模式的字符

16、序列，而“1+2&2-1”則不是。l2、假設(shè)一個算術(shù)表達式可以包含三種括號：圓括號“（”和“）”、方括號“”和“”和花括號“”和“”，且這三種括號可按任意的次序嵌套使用。編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。l實驗3.1 鏈棧的設(shè)計與實現(xiàn)l網(wǎng)絡(luò)課堂：4 棧和隊列（1） 4.3.1棧與遞歸 遞歸 遞歸函數(shù)到非遞歸函數(shù)的轉(zhuǎn)換 簡化的背包問題* 4.3.2迷宮問題 4.3.3表達式計算 后綴表達式的求值 中綴表達式到后綴表達式的轉(zhuǎn)換 如果一個對象部分的由自己組成，或者是按它自己定義的，則稱為遞歸的。 一個遞歸定義必須一步比一步簡單，最后是有終

17、結(jié)的，決不能無限循環(huán)下去。在n階乘的定義中，當n為0時定義為1，它不再用遞歸來定義，稱為遞歸定義的出口，簡稱為遞歸出口。 4.3.1 棧與遞歸一. 遞歸的定義1. 自然數(shù) （a）1是自然數(shù)； （b）自然數(shù)的后繼是自然數(shù)3. 階乘函數(shù) n! 1 n=0 n*f(n-1) n0 遞歸算法主要適用于要解決的問題,要計算的函數(shù),要處理的數(shù)據(jù)結(jié)構(gòu)已是遞歸定義的場合.F(n)= 2. 簡單算術(shù)表達式（a）常數(shù)，變量，函數(shù)引用是表達式；（b) 若e1,e2是表達式, op為運算符，則 e1 op e2, op e1, (e1) 也是表達式。算法4.11 階乘的遞歸計算 int fact (int n) if

18、 (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ù)的局部變量分配存儲區(qū)； （活動記錄， 數(shù)據(jù)區(qū)）（2）將所有的實參、返回地址傳遞給被調(diào)用函數(shù)； 實參和形參的結(jié)合，傳值。（2）（3）將控制轉(zhuǎn)移到被調(diào)用函數(shù)入口。調(diào)用后返回：（1）保存被調(diào)用函數(shù)的計算結(jié)果；（2）釋放被調(diào)用函數(shù)的存儲區(qū)；（3）依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn) 移到調(diào)用函數(shù)。二. 遞歸函數(shù)到非遞歸函數(shù)的

19、轉(zhuǎn)換 函數(shù)嵌套調(diào)用時，按照“后調(diào)用先返回”的原則進行。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 階乘的非遞歸計算程序員自己管理一個棧，并模擬函數(shù)調(diào)用的執(zhí)行過程。 int nfact(int n); int res; pSeqStack st

20、; 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); 一個背包可以放入的物品重量為s，現(xiàn)有n件物品，重量分別為w1,w2,wn,問能否從這些物品中選若干件放入背包中，使得放入的重量之和正好是s。如果存在一種符合上述要求的選擇，則稱此背包問題有解，否則此問題無解。 背包問題表示： int knap(int s, int n ) 其中，s=0,

21、n=1 如果有解： 1. 選擇的一組物品中不包含wn; knap( s, n-1 ) 的解就是knap( s, n)的解； 2. 選擇的一組物品中包含wn; knap( s-wn, n -1 )的解就是knap( s, n)的解.三 . 簡化的背包問題*背包問題可遞歸定義如下： 1 s = 0 0 s 0 , n 0,n=1 算法4.13 背包問題的遞歸算法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

22、”, n, n-1, wn-1); return 1; else return (knap(s, n-1); 1. 設(shè)計一個棧st，棧中的每個結(jié)點包含以下四個字段：參數(shù)s, n,返回地址r和結(jié)果單元k。由于knap算法中有兩處要遞歸調(diào)用knap算法，所以返回地址一共有三種情況：第一，計算knap( s0 , n0 )完畢，返回到調(diào)用本函數(shù)的其它函數(shù)；第二，計算knap( s wn-1 , n - 1 )完畢，返回到本調(diào)用函數(shù)中繼續(xù)計算；第三，計算knap( s , n - 1 )完畢，返回到本調(diào)用函數(shù)繼續(xù)計算。 為區(qū)分三種返回，r分別用1，2，3表示，另外引入一個變量x作為進出棧的緩沖。 棧用

23、順序存儲結(jié)構(gòu)實現(xiàn)，棧中元素和變量的說明如下：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ī)律進行，凡調(diào)用語句 knap( s1 , n1 )均代換成： (1) x.s = s1 ； x.n = n1 ； x.r = 返回地址編號； (2) push_seq( st, x ); (3) goto 遞歸入口。將調(diào)用返回統(tǒng)一處理成： (1) x = top

24、_seq( st ); (2) pop_seq( st ); (3) 根據(jù)x.r的值,進行相應(yīng)處理 x.r = 1 , 返回; x.r = 2 , 繼續(xù)處理1; x.r = 3 , 繼續(xù)處理2; 并將算法中的所有局部量都改用棧st中棧頂結(jié)點的相應(yīng)字段，為了在算法中直接引入棧，并在書寫上一致，算法開頭增加將結(jié)點( s , n , 1 )推入棧st中的動作. 算法4.14 背包問題的非遞歸算法 (a) 迷宮的圖形表示 (b) 迷宮的二維數(shù)組表示 求解迷宮中一條路徑的方法： 從入口出發(fā)，沿某一方向進行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進行探索，直到所有可能的通路都探索到為止。這

25、類方法統(tǒng)稱回溯法。 用一個棧記錄走過的位置，棧中每個元素包括三項，分別記錄當前位置的行坐標、列坐標以及在該位置上所選的方向（即directon數(shù)組的下標值） 把入口壓入棧中;while 棧不空時 取棧頂元素; while 存在試探方向 求下一個方塊位置mazegh; if (mazegh是出口塊) 打印路徑上的每一個方塊;return; if(mazegh= =0) /*可前進*/ 標記mazegh;(g,h,方向)進棧; 前進到下一個位置; 討論在某一位置進行試探，討論在某一位置進行試探，設(shè)迷宮中任一位置（i, j)N(i-1,j)w(i,j-1) (i, j) E(i,j+1) S(i+1

26、,j) i 增值 j 增值 方向 0 0 1 E 1 1 0 S 2 0 -1 W 3 -1 0 N Drection42棧用順序存儲結(jié)構(gòu)實現(xiàn)，棧中元素的說明如下： 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 op

27、1op2 : op1優(yōu)先于op2 4.3.3 表達式求值(1) 假定所有運算分量都是整數(shù)；(2) 所有運算符都是整數(shù)的二元操作，且都用一個字符表示。 中綴表達式轉(zhuǎn)換成后綴表達式： 優(yōu)先關(guān)系表+op1op2輸入：3 *（7 + 3 * 6 / 2-5$)運算對象棧運算符棧3$*(7+3*618/2916-51133 實現(xiàn)這個轉(zhuǎn)換的基本思想是：順序掃描中綴表達式，當讀入一個運算分量時就立即輸出;而在讀入一個操作符(如 + 或 -)時，首先把它放進一個運算符棧，一直等到這個運算符的兩個運算分量都讀到后，才能將它輸出。當掃描遇到一個左括號時立刻將它推入棧中，棧中左括號的優(yōu)先級被視為比任何操作符都低。繼

28、續(xù)掃描直到出現(xiàn)右括號時，才將留在棧中這對括號之間的操作符逐一彈出并輸出，最后彈出左括號。注意，在后綴表達式中不再需要任何括號，所以不必將左右括號輸出。最后，當處理達到輸入串的末尾時，將棧中操作符全部彈出并輸出。 隊列也是一種特殊的線性表，對于它所有的插入都在表的一端進行，所有的刪除都在表的另一端進行。進行刪除的這一端叫隊列的頭，進行插入的這一 端叫隊列的尾。當隊列中沒有任何元素時，稱為空隊列。隊列也稱作先進先出表。 k1 k2 k3 . kn-1隊頭隊尾進隊出隊4.4.2 抽象數(shù)據(jù)類型 ADT Queue isoperation Queue createEmptyQueue ( void )

29、創(chuàng)建一個空隊列 int isEmptyQueue ( Queue qu ) 判隊列是否為空隊列 void enQueue ( Queue qu, DataType x ) 往隊列中插入一個值為x的元素 void deQueue ( Queue qu ) 從隊列中刪除一個元素DataType frontQueue ( Queue qu ) 求隊列頭部元素的值end ADT Queue4.5隊列的實現(xiàn) 4.5.1順序表示 4.5.2鏈接表示StructSeqQueueintMAXNUM;intf,r;DataType*q;TypedefstructSeqQueue*PSeqQueue;PSeqQu

30、euepaqu;76543210paqu.fpaqu.rk1k2k3paqu.fpaqu.rpaqu.rpaqu.fk8k7隊列空隊列數(shù)組越界普通情況paqu.rpaqu.fk1k2k7k6k5k4k3paqu.fpaqu.r圖(a)空隊列圖(b)隊列滿，判斷paqu.r+1 = = paqu.f循環(huán)隊列 圖4.11 循環(huán)隊列創(chuàng)建一個空隊列創(chuàng)建一個空隊列PSeqQueue createEmptyQueue_seq( intPSeqQueue createEmptyQueue_seq( int m ) m ) PSeqQueue paqu PSeqQueue paqu; ; paqu = new

31、 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

32、 delete paqu; ; coutOut of space!endl coutOut of space!f = paqu return (paqu-f = paqu-r);-r); 算法算法4.13 4.13 進隊列運算進隊列運算void enQueue_seq( PSeqQueue paqu, DataTypevoid enQueue_seq( PSeqQueue paqu, DataType x ) x )/ /* * 在隊列中插入一元素在隊列中插入一元素x x * */ / if( (paqu-r + 1) % paqu-MAXNUM = paqu if( (paqu-r + 1)

33、 % 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 出隊出隊void deQueue_seq( PSeqQueue paquvoid deQueue_seq( PSeqQueue paqu ) )/ /* * 刪除隊列頭部元素刪

34、除隊列頭部元素 * */ / 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 取隊列的頭元素取隊列的頭元素DataType frontQueue_seq( PSeqQueue paquDataType frontQueue_seq( PSeqQueue paqu

35、) )/ /* * 對非空隊列對非空隊列, ,求隊列頭部元素求隊列頭部元素 * */ / 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;typedefs

36、tructLinkQueue,*PLinkQueue;4.5.2鏈接表示鏈接表示 k0k1k2kn-1. 圖4.12 隊列的鏈接表示plqu fr算法算法4.16 4.16 創(chuàng)建一個空隊列創(chuàng)建一個空隊列PLinkQueue createEmptyQueue_linkPLinkQueue createEmptyQueue_link( )( ) PLinkQueue plqu PLinkQueue plqu; ; plqu = (PLinkQueue )malloc(sizeof(struct plqu = (PLinkQueue )malloc(sizeof(struct LinkQueueLi

37、nkQueue);); 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);); 運算的實現(xiàn)算法算法4.17 4.17 判斷鏈接表示隊列是否為空隊列判斷鏈接表示隊列是否為空隊列 int isEmptyQueue_link( PLinkQueue plquint isEmptyQueue_lin

38、k( PLinkQueue plqu ) ) return (plqu return (plqu-f = NULL);-f = NULL); 算法算法4.18 4.18 入隊入隊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

39、 = 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 出隊出隊void deQueue_lin

40、k( 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 取隊列頭部結(jié)點的值取隊列頭部結(jié)點的值DataTyp

41、e frontQueue_link( PLinkQueue plquDataType frontQueue_link( PLinkQueue plqu ) )/ /* * 在非空隊列中求隊頭元素在非空隊列中求隊頭元素 * */ / 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)夫過河問題 : 一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些

42、東西全部運到北岸。問題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。顯然，因為狼能吃羊，而羊愛吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開。好在狼屬于食肉動物，它不吃白菜。請問農(nóng)夫該采取什么方案才能將所有的東西運過河 4.6隊列的應(yīng)用農(nóng)夫過河問題* 用計算機實現(xiàn)上述求解的搜索過程可以采用兩種不同的策略：一種是廣度優(yōu)先廣度優(yōu)先(breadth_first)搜索，另一種是深度優(yōu)先(depth_first)。而實現(xiàn)這兩種策略所依賴的數(shù)據(jù)結(jié)構(gòu)正好是前面介紹的隊列和棧。本節(jié)討論隊列的應(yīng)用，所以下面重點介紹廣度優(yōu)先的策略。 農(nóng)夫過河問題具體算法Path：15，

43、6，14，2，11，1，9，0從初始狀態(tài)0到最終狀態(tài)15的動作序列為： 農(nóng)夫把羊帶到北岸; 1 0000 農(nóng)夫獨自回到南岸; 2 1001 農(nóng)夫把白菜帶到北岸; 3 0001 農(nóng)夫帶著羊返回南岸; 5 1101 4 1011 農(nóng)夫把狼帶到北岸; 7 0100 6 0010 農(nóng)夫獨自返回南岸; 8 1110 農(nóng)夫把羊帶到北岸。 9 0110 10 1111 圖 4.11 廣度優(yōu)先搜索的結(jié)果和順序 小小 結(jié)結(jié)本章主要討論了兩種操作受限的線性表：棧和隊列。討論了它們的基本概念、存儲結(jié)構(gòu)、基本運算的實現(xiàn)以及一些應(yīng)用實例。對于棧來說，它的插入和刪除都是在表的同一端進行的，用順序存儲結(jié)構(gòu)時，要注意棧滿、棧空的條件；用鏈式存儲結(jié)構(gòu)時，要注意鏈的方向。對隊列來說，它的插入運算在表的一端進行，而刪除運算卻在表的另一端進行。根據(jù)隊列的這一特點，在使用順序存儲結(jié)構(gòu)時，用了環(huán)形隊列，這樣可解決假溢出問題，但要特別注意隊列滿和隊列空的條件及描述。 作業(yè)：p.115 算法題 8，9 補充3. 假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如“abba”和“abcba”是回文，“abcde”和“ababab”則不是回文。試寫一個算法判別讀入的一個以“”為結(jié)束符的字符序列是否是回文。l實驗l3.2 循環(huán)隊列的設(shè)計與實現(xiàn)l3.3 鏈隊列的設(shè)計與實現(xiàn)l3.4 病人看病模擬程序l網(wǎng)絡(luò)課堂：4 棧和隊列（2）