Chap4算法與數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述(第2版)張乃孝編課件

1、4.1 棧及其抽象數(shù)據(jù)類型4.1.1. 定義棧是限定在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱棧頂，表頭端稱棧底。如圖。an.a2a1棧底棧頂出棧進(jìn)棧棧的修改是按的原則進(jìn)行的。第四章 棧和隊(duì)列1例1.一個(gè)棧的進(jìn)棧序列是a,b,c,d,e，則棧不可能的出棧序列是：（A）edcba (B)decba (C) dceab (D)abcde例2.已知一個(gè)棧的出棧序列是1,2,3, ，n,其輸出序列為P1,P2,P3,Pn，若P1=n,則Pi（1=i=n)為_。(A)i (B)n-i ( C) n-i+1 (D)不確定 例3.已知一個(gè)棧的出棧序列是1,2,3, ，n,其輸入序列為P1,P2,P3,Pn，

2、若Pn=n,則Pi（1=it=-1) printfElse *x=pastactk-spastack-t; pastack-t= pastack-t-1; Int judgebalance( pseqstat stack1) datatype y,z; pseqstat stack2=creakemptystack-seq( stack1-maxnum);While( ! isemptystack-Seq(stack1) popseq( stack1, &y); pushseq( stack2,y); pushseq(stack3,y)While( ! isemptystack-Seq(sta

3、ck3) popseq( stack3, &y); pushseq( stack1,y); While( ! isemptystack-Seq(stack1) popseq( stack1, &y); popseq(stack2,&z); if( y!=z) return 0; return 1;54.1.2 抽象數(shù)據(jù)類型ADT Stack isoperationsStack createEmptyStack ( void ) 創(chuàng)建一個(gè)空棧。int isEmptyStack ( Stack st ) 判斷棧st是否為空棧。void push ( Stack st, DataType x ) 往

4、棧st的棧頂插入一個(gè)值為x的元素。void pop ( Stack st ) 從棧st的棧頂刪除一個(gè)元素。DataType top ( Stack st ) 求棧頂元素的值。end ADT Stack 64.2 棧的實(shí)現(xiàn)4.2.1順序表示typedef int DataType; /* 定義棧元素的數(shù)據(jù)類型，這里定義為整型 */struct SeqStack /* 順序棧類型定義 */ int MAXNUM; /* 棧中能達(dá)到的最大元素個(gè)數(shù) */ int t; /*棧頂元素位置*/ DataType *s;typedef struct SeqStack * PSeqStack; PSeqSta

5、ck pastack;123450ABCDMAXNUM=6t =3S7棧的存儲(chǔ)結(jié)構(gòu)順序棧(實(shí)現(xiàn)：一維數(shù)組sM)t= -1123450棧空棧頂指針t,指向?qū)嶋H棧頂后的空位置，初值為-1t123450進(jìn)棧At出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,棧空，此時(shí)出棧，則下溢（underflow)top=M-1,棧滿，此時(shí)入棧，則上溢（overflow)ttttt123450ABCDEFtttttt?？?基本運(yùn)算的實(shí)現(xiàn)1. 創(chuàng)建一個(gè)空棧PSeqStack createEmptyStack_seq( int m ) 具體實(shí)現(xiàn)與算法2.1類似，需要為棧結(jié)構(gòu)申請(qǐng)空間，不同之處是將棧頂變量賦值為-1。請(qǐng)自

6、己給出。 2. 判斷棧是否為空棧 int isEmptyStack_seq( PSeqStack pastack ) 當(dāng)pastack所指的棧為空棧時(shí)，則返回1，否則返回0。93. 進(jìn)棧運(yùn)算 程序?qū)崿F(xiàn) void push_seq( PSeqStack pastack, DataType x ) 往pastack所指的棧中插入（或稱推入）一個(gè)值為的元素。當(dāng)棧不滿時(shí)，先修改棧頂變量，將其值加1，然后把元素x放入棧頂變量所指的位置中。 4. 出棧運(yùn)算程序?qū)崿F(xiàn) void pop_seq( PSeqStack pastack ) 從pastack所指的棧中刪除（或稱彈出）一個(gè)元素。 當(dāng)棧不空時(shí)，通過(guò)將棧

7、頂變量減1達(dá)到元素刪除的目的。 5. 取棧頂元素運(yùn)算 程序?qū)崿F(xiàn) DataType top_seq( PSeqStack pastack ) 當(dāng)pastack所指的棧不為空棧時(shí)，將棧頂元素取出，而棧本身未發(fā)生任何變化。104.2.2鏈接表示typedef int DataType ;/* 定義棧中元素類型為整型，也可定義為其他類型 */struct Node;typedef struct Node * Pnode;struct Node/* 單鏈表結(jié)點(diǎn)結(jié)構(gòu) */DataType info;PNode link;struct LinkStack/* 鏈接棧類型定義 */PNode top;/* 指

8、向棧頂結(jié)點(diǎn) */;typedef struct LinkStack *PLinkStack ;11假設(shè)plstack是PLinkStack類型的變量，則plstack-top就是棧頂指針，plstack-top-info是棧頂元素， 12運(yùn)算的實(shí)現(xiàn)1.創(chuàng)建空鏈接棧 程序?qū)崿F(xiàn)PLinkStack createEmptyStack_link(void) 創(chuàng)建一空鏈接棧，需要申請(qǐng)鏈接棧結(jié)構(gòu)(struct LinkStack)空間，將其中top置為NULL,返回該結(jié)構(gòu)的地址。 2. 判斷棧是否為空棧 程序?qū)崿F(xiàn) int isEmptyStack_link( PLinkStack plstack ) 判斷

9、plstack所指的棧是否為空棧，當(dāng)plstack所指的棧為空棧時(shí)，則返回1，否則返回0。 133. 進(jìn)棧運(yùn)算程序?qū)崿F(xiàn) void push_link( PLinkStack plstack, DataType x ) 往plstack所指的棧中插入（或稱壓入）一個(gè)值為x的元素。首先申請(qǐng)結(jié)點(diǎn)空間，然后通過(guò)指針修改，將結(jié)點(diǎn)插在棧頂。 4. 出棧運(yùn)算程序?qū)崿F(xiàn) void pop_link( PLinkStack plstack ) 出棧運(yùn)算，表示從plstack所指的棧中刪除（或稱彈出）一個(gè)元素。當(dāng)棧不空時(shí)，直接修改棧頂指針，刪除結(jié)點(diǎn)。 5. 取棧頂元素程序?qū)崿F(xiàn) DataType top_link(

10、PLinkStack plstack ) 當(dāng)plstack所指的棧不空時(shí)，取棧頂元素的值，棧保持不變。141. 數(shù)制轉(zhuǎn)換void Conversion( )PSeqStackps;intm,n; scanf(“%d”, &m);ps = createEmptyStack_seq(m);scanf(“%d”, &n);while(n)push_seq(ps, n%8);n /= 8;while(!isEmptyStack_seq(ps)n= pop_seq(ps);printf(“%d”, n);free(ps);4.3 棧的應(yīng)用舉例1538192088余1（最低位）余3余2（最高位）十進(jìn)制轉(zhuǎn)換

11、八進(jìn)制13215例 遞歸的執(zhí)行情況分析 2. 遞歸過(guò)程及其實(shí)現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸實(shí)現(xiàn)：建立遞歸工作棧void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i rpaqu fJ1J2J3p fp rp rp fJ6J5隊(duì)列空隊(duì)列數(shù)組越界（）普通情況PSeqQueue paqu;paqu-qpaqu-f表示當(dāng)前隊(duì)列頭部的元素；paqu-qpaqu-r表示當(dāng)前隊(duì)列尾部的（即將要插入的）元素。當(dāng)前隊(duì)列中元素的個(gè)數(shù)=paqu-r - paqu-f32當(dāng)表中已有MAXNUM 1個(gè)結(jié)點(diǎn)時(shí)，如果還要插入，paqu-r和paqu-f 就

12、會(huì)重合，而這與空隊(duì)列的情形相混。為區(qū)分空隊(duì)列與滿隊(duì)列兩種情況的環(huán)形隊(duì)列，一般是犧牲隊(duì)列中的一個(gè)結(jié)點(diǎn)，當(dāng)隊(duì)列中已有MAXNUM1個(gè)結(jié)點(diǎn)時(shí)就稱滿，再要插入就發(fā)生溢出.隊(duì)列滿判斷(paqu r+1 )%MAXNUM= paqu f（）環(huán)形隊(duì)列33隊(duì)列基本運(yùn)算的實(shí)現(xiàn)1. 創(chuàng)建一個(gè)空隊(duì)列。PSeqQueue createEmptyQueue_seq( int m ) 創(chuàng)建一個(gè)空隊(duì)。具體實(shí)現(xiàn)與算法2.1類似，需要為隊(duì)列申請(qǐng)空間，不同之處是需要將對(duì)變量f和r均賦值為0。2. 判斷是否為空隊(duì)列 int isEmptyQueue_seq( PSeqQueue paqu ) 判斷paqu所指的隊(duì)列是否為空隊(duì)列。當(dāng)

13、paqu-f = paqu-r時(shí)，返回1，否則返回0。343. 進(jìn)隊(duì)運(yùn)算 程序?qū)崿F(xiàn) void enQueue_seq( PSeqQueue paqu, DataType x ) 入隊(duì)運(yùn)算，當(dāng)隊(duì)列不滿時(shí)，將元素x插入paqu所指隊(duì)列的隊(duì)尾。 4. 出隊(duì)列運(yùn)算 程序?qū)崿F(xiàn) void deQueue_seq( PSeqQueue paqu ) 當(dāng)隊(duì)列不空時(shí)，刪除paqu所指隊(duì)列的隊(duì)頭元素。 5. 取隊(duì)列頭部元素程序?qū)崿F(xiàn) DataType frontQueue_seq( PSeqQueue paqu )當(dāng)paqu所指的隊(duì)列不空時(shí)，取隊(duì)列頭部元素，隊(duì)列本身保持不變。354.5.2 鏈接表示 存儲(chǔ)結(jié)構(gòu) 隊(duì)列

14、的鏈接表示就是用一個(gè)單鏈表來(lái)表示隊(duì)列，隊(duì)列中的每個(gè)元素對(duì)應(yīng)鏈表中的一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)一樣。為了強(qiáng)調(diào)隊(duì)頭和隊(duì)尾都是隊(duì)列的屬性，這里對(duì)隊(duì)列增加了一層封裝，引入LinkQueue結(jié)構(gòu)的定義。這樣存儲(chǔ)的隊(duì)列簡(jiǎn)稱鏈接隊(duì)列。 36struct Node;typedef struct Node *PNode;struct Node /* 結(jié)點(diǎn)結(jié)構(gòu) */ DataType info; PNode link; ;struct LinkQueue /* 鏈接隊(duì)列類型定義 */ PNode f; /* 頭指針 */ PNode r; /* 尾指針 */ ;typedef struct Link

15、Queue *PLinkQueue;/*鏈接隊(duì)列類型的指針類型*/37基本運(yùn)算的實(shí)現(xiàn)1. 創(chuàng)建一個(gè)空隊(duì)列程序?qū)崿F(xiàn)PLinkQueue createEmptyQueue_link( void ) 申請(qǐng)隊(duì)列結(jié)構(gòu)空間，創(chuàng)建一個(gè)空隊(duì)列。2. 判斷隊(duì)列是否為空程序?qū)崿F(xiàn)int isEmptyQueue_link( PLinkQueue plqu )判斷plqu所指的隊(duì)列是否為空隊(duì)，為空隊(duì)時(shí)，則返回1，否則返回0。 38 3. 進(jìn)隊(duì)列運(yùn)算程序?qū)崿F(xiàn)void enQueue_link( PLinkQueue plqu, Datatype x ) 入隊(duì)運(yùn)算，表示往plqu所指的隊(duì)列中插入一個(gè)值為x的元素。 4.

16、出隊(duì)列運(yùn)算程序?qū)崿F(xiàn)void deQueue_link( PLinkQueue plqu ) 出隊(duì)運(yùn)算，表示從plqu所指的隊(duì)列中刪除隊(duì)頭元素。5.取隊(duì)列頭部結(jié)點(diǎn)的值程序?qū)崿F(xiàn)Datatype frontQueue_link( PLinkQueue plqu ) 當(dāng)plqu所指的隊(duì)列非空時(shí)，取隊(duì)列頭部元素的值，隊(duì)列保持不變。 39例1.用單鏈表表示的鏈隊(duì)的隊(duì)頭在鏈表的_位置.例2.最不適合用作鏈隊(duì)的鏈表是_A.只帶隊(duì)頭指針的非循環(huán)雙鏈表B.只帶頭指針的循環(huán)雙鏈表C.只帶尾指針的循環(huán)雙鏈表D.只帶隊(duì)尾指針的循環(huán)單鏈表40例3.鏈表HQ中判定只有一個(gè)結(jié)點(diǎn)的條件是_HQ-front=HQ-rear414

17、.6 隊(duì)列的應(yīng)用農(nóng)夫過(guò)河問(wèn)題42 一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北岸。問(wèn)題是他面前只有一條小船，船小到只能容下他和一件物品，另外只有農(nóng)夫能撐船。請(qǐng)問(wèn)農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過(guò)河呢？43算法選擇：求解這個(gè)問(wèn)題的最簡(jiǎn)單的方法是一步一步進(jìn)行試探，每一步都搜索所有可能的選擇，對(duì)前一步合適的選擇再考慮下一步的各種方案。用計(jì)算機(jī)實(shí)現(xiàn)上述求解的搜索過(guò)程可以采用兩種不同的策略：一種是廣度優(yōu)先(breadth_first) 搜索，另一種是深度優(yōu)先(depth_first) 。44廣度優(yōu)先：廣度優(yōu)先的含義就是在搜索過(guò)程中總是首先搜索下面一步的所有可能狀態(tài)，然

18、后再進(jìn)一步考慮更后面的各種情況。要實(shí)現(xiàn)廣度優(yōu)先搜索，一般都采用隊(duì)列作為輔助結(jié)構(gòu)。把下一步所有可能達(dá)到的狀態(tài)都列舉出來(lái)，放在這個(gè)隊(duì)列中，然后順序取出來(lái)分別進(jìn)行處理，處理過(guò)程中把再下一步的狀態(tài)放在隊(duì)列里。由于隊(duì)列的操作遵循先進(jìn)先出的原則，在這個(gè)處理過(guò)程中，只有在前一步的所有情況都處理完后，才能開始后面一步各情況的處理。45狀態(tài)的表示要模擬農(nóng)夫過(guò)河問(wèn)題，首先需要選擇一個(gè)對(duì)問(wèn)題中每個(gè)角色的位置進(jìn)行描述的方法。一個(gè)很方便的辦法是用四位二進(jìn)制數(shù)順序分別表示農(nóng)夫、狼、白菜和羊的位置。例如用0表示農(nóng)夫或者某東西在河的南岸，1表示在河的北岸。因此整數(shù)5(其二進(jìn)制表示為0101) 表示農(nóng)夫和白菜在河的南岸，而狼和

19、羊在北岸。46確定每個(gè)角色位置的函數(shù)用整數(shù)location表示上述四位二進(jìn)制描述的狀態(tài)，用下面的四個(gè)函數(shù)從上述狀態(tài)中得到每個(gè)角色所在位置的代碼。函數(shù)返回值為真表示所考察的人或物在河的北岸，否則在南岸。47int farmer(int location) return (0 != (location & 0 x08);int wolf(int location) return (0 != (location & 0 x04);48int cabbage(int location) return (0 != (location & 0 x02);int goat(int location) ret

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

21、; / 狼吃羊 if (goat(location) = wolf(location) & (goat(location) != farmer(location) return (0); return (1); / 其他狀態(tài)是安全的51問(wèn)題的描述：完成了上面的準(zhǔn)備工作，現(xiàn)在的問(wèn)題變成：從初始狀態(tài)二進(jìn)制0000(全部在河的南岸) 出發(fā)，尋找一種全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，它以二進(jìn)制1111(全部到達(dá)河的北岸) 為最終目標(biāo)，并且在序列中的每一個(gè)狀態(tài)都可以從前一狀態(tài)通過(guò)農(nóng)夫（可以帶一樣?xùn)|西）劃船過(guò)河的動(dòng)作到達(dá)。為避免不必要的瞎費(fèi)功夫，要求在序列中不應(yīng)該出現(xiàn)重復(fù)的狀態(tài).52主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)為了實(shí)現(xiàn)

22、廣度優(yōu)先搜索，算法中需要使用了一個(gè)整數(shù)隊(duì)列moveTo，它的每個(gè)元素表示一個(gè)可以安全到達(dá)的中間狀態(tài)。另外還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄已被訪問(wèn)過(guò)的各個(gè)狀態(tài)，以及已被發(fā)現(xiàn)的能夠到達(dá)當(dāng)前這個(gè)狀態(tài)的路徑。53由于在這個(gè)問(wèn)題的解決過(guò)程中需要列舉的所有狀態(tài)(二進(jìn)制0000 1111)一共16種，所以可以構(gòu)造一個(gè)包含16個(gè)元素的整數(shù)順序表來(lái)滿足以上的要求。用順序表的第i個(gè)元素記錄狀態(tài)i是否已被訪問(wèn)過(guò)，若已被訪問(wèn)過(guò)則在這個(gè)順序表元素中記入前驅(qū)狀態(tài)值，算法中把這個(gè)順序表叫做route。route的每個(gè)分量初始化值均為-1，每當(dāng)我們?cè)陉?duì)列中加入一個(gè)新狀態(tài)時(shí)，就把順序表中以該狀態(tài)作下標(biāo)的元素的值改為達(dá)到這個(gè)狀態(tài)的路徑上前

23、一狀態(tài)的下標(biāo)值。route的一個(gè)元素具有非負(fù)值表示這個(gè)狀態(tài)已訪問(wèn)過(guò)，或是正被考慮。最后我們可以利用route順序表元素的值建立起正確的狀態(tài)路徑。54算法4.27 農(nóng)夫過(guò)河問(wèn)題的求解基于以上分析,可以寫出農(nóng)夫過(guò)河問(wèn)題的程序 void farmerProblem( )55圖4.13標(biāo)出了送入隊(duì)列的各個(gè)狀態(tài)(位置分布)和搜索過(guò)程中經(jīng)歷該結(jié)點(diǎn)的順序編號(hào)。請(qǐng)讀者注意看廣度優(yōu)先搜索法在面臨多個(gè)選擇時(shí)采用怎樣的訪問(wèn)順序。算法4.23執(zhí)行結(jié)果輸出如下:Path：15，6，14，2，11，1，9，056從初始狀態(tài)0到最終狀態(tài)15的動(dòng)作序列為： 農(nóng)夫把羊帶到北岸; 1 0000 農(nóng)夫獨(dú)自回到南岸; 2 1001

24、農(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 57遞歸 在定義一個(gè)過(guò)程或函數(shù)時(shí)出現(xiàn)調(diào)用本過(guò)程或本函數(shù)的成分,稱之為遞歸.若調(diào)用自身,稱為自接遞歸. 若過(guò)程或函數(shù)P調(diào)用過(guò)程或函數(shù)Q,而Q又調(diào)用P,稱為間接遞歸.58 從遞歸的執(zhí)行過(guò)程看,要解決f(s),不是直接求其解,而是轉(zhuǎn)化為計(jì)算f(s)和一個(gè)常量C,求解f(s)的方法與f(s)相似.遞歸設(shè)計(jì)步驟(1)對(duì)原問(wèn)題f(s)進(jìn)行分析,假設(shè)出合理的較小問(wèn)題f(s).(2)假設(shè)f(s)

25、是可解的,在此基礎(chǔ)上確定f(s)的解,即給出f(s)與f(s)的關(guān)系.(3)確定一個(gè)特定情況(如f(1)或f(0)的解)用此作為遞歸出口.59例1.將f=1+1/2+1/3+1/n轉(zhuǎn)化成遞歸函數(shù)，其遞歸出口是_,其遞歸體是_.解： （1）1 （2）f(n)=f(n-1)+1/n60例2.有如下遞歸過(guò)程:Void print(int w) int i; if (w!=0) print(w-1); for (i=1;i1時(shí)試寫出計(jì)算Fn(x)的值的遞歸函數(shù)過(guò)程.63解: float f(int n,float x) float s; if(n=0) return 1; else if(n=1) return(2*x); else s=2*x*f(n-1,x)-2*(n-1)*f(n-2,x); return