算法與數(shù)據(jù)結(jié)構(gòu)課件DSC3

S3§3.1棧第三章.棧和隊(duì)列（Chapter3.StackandQueue)

棧（stack）是插入和刪除操作受限的線性表，是一種后進(jìn)先出（LastInFirstOut--LIFO）的線性表。表頭端稱為棧底（bottom），表尾端稱為棧頂（top），插入和刪除都在棧頂進(jìn)行。bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSHS3§3.1棧第三章.棧和隊(duì)列1棧的基本操作：InistackClearGettopEmptyPushPop棧的實(shí)現(xiàn)：#defineSTACK_INIT_SIZEuser_supply#defineSTACKINCREMENTuser_supplytypedefstruct{elemtype*bottom;elemtype*top;intstackzise;}sqstack;順序存儲結(jié)構(gòu)表示棧Full棧的基本操作：InistackClearGettopEmpt2typedefstrcutlnode{elemtypedata;structlnode*next;}*linkedstack;鏈?zhǔn)酱鎯Y(jié)構(gòu)表示棧----鏈棧（Linked_stack）上溢（overflow）：若棧的容量已全部用完，再進(jìn)行插入操作（PUSH），就會發(fā)生上溢錯誤。下溢（underflow）：若棧已空，再進(jìn)行刪除操作（POP），就會發(fā)生下溢錯誤。typedefstrcutlnode{鏈?zhǔn)酱鎯Y(jié)3§3.2棧的應(yīng)用----表達(dá)式求值任一表達(dá)式（expression）都是由操作數(shù)（operand）、操作符（operator）和界限符（delimiter）組成。我們通常習(xí)慣使用中綴表達(dá)式（infixexpression），但中綴表達(dá)式離不開括號（bracket)。若使用前綴表達(dá)式（prefixexpression）或后綴表達(dá)式（postfixexpression）則不需要括號。利用棧，可以將中綴表達(dá)式變?yōu)榍熬Y表達(dá)式或后綴表達(dá)式，再用棧進(jìn)行運(yùn)算即可得到表達(dá)式的值（value）?！?.3棧與遞歸遞歸（recursive）：一個程序直接調(diào)用自己或通過其它程序調(diào)用自己就稱為遞歸。根據(jù)調(diào)用關(guān)系可分為直接遞歸（directrecursive）和間接遞歸（indirectrecursive）?！?.2棧的應(yīng)用----表達(dá)式求值任一4第一次上機(jī)作業(yè)輸入表達(dá)式字符串，以“=”表示結(jié)束，計(jì)算并輸出表達(dá)式值。操作數(shù)可以是整數(shù)或?qū)崝?shù)，操作符有“+”、“-”、“*”、“/”、“^”（乘方）和“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。第一次上機(jī)作業(yè)5棧在程序的過程或函數(shù)調(diào)用中的作用：過程一過程二過程三過程四斷點(diǎn)三斷點(diǎn)一斷點(diǎn)二斷點(diǎn)一斷點(diǎn)二斷點(diǎn)三stack調(diào)用子程序返回?cái)帱c(diǎn)程序執(zhí)行

棧在程序的過程或函數(shù)調(diào)用中的作用：過程一過程二過程三過程四斷6遞歸是程序設(shè)計(jì)中一種強(qiáng)有力的工具。下面三種情況可用遞歸解決：1、有些數(shù)學(xué)函數(shù)是遞歸定義的，對其求解可用遞歸；2、有些數(shù)據(jù)結(jié)構(gòu)具有遞歸特性，對其操作可用遞歸；3、有些問題的解決方法用遞歸描述，對其求解也可用遞歸。

例：求階乘（factorial）：Fact(n)=1當(dāng)n=0n·Fact(n-1)當(dāng)n>0{intFact(intn){if(!n)return1;//出口條件returnn*Fact(n–1);//遞歸調(diào)用部分}遞歸是程序設(shè)計(jì)中一種強(qiáng)有力的工具。下面三種情7

例：求n個數(shù)的最小值：intMin(sqlistS,intn){if(n==1)returnS[1];//出口條件x=Min(S,n-1);if(x<S[n])returnx;elsereturnS[n];//遞歸調(diào)用部分}例：求n個數(shù)的最小值：intMin(sqli8

例：

河內(nèi)塔（HanoiTower）問題求解：ABCABC如何解決這個問題呢？真?zhèn)X筋啊！題目要求：1、將n個盤子從A柱移到B柱，C柱可用；

2、每次只能移動一個盤子；

3、在移動過程中，不得將大盤壓在小盤上。解決該問題可分三步走：1、將A柱上面的n-1個盤子從A柱移到C柱；2、將第n個盤子從A柱移到B柱；3、再將C柱上面的n-1個盤子移到B柱。例：河內(nèi)塔（HanoiTower）問題求解：ABCA9voidHanoi(intn,intx,inty,intz){If(n){//出口條件Hanoi(n–1,x,z,y);//遞歸調(diào)用部分Move(n,x,y);Hanoi(n-1,z,y,x);}}求費(fèi)波拉契數(shù)列（Fibonacci）、迷宮問題（Maze）、八皇后（EightQueens）、騎士遍歷（Cavaliertravel）等等。以下這些問題也可用遞歸程序解決：voidHanoi(intn,int10程序設(shè)計(jì)常用方法之一：分治法（DivideandConquer）

亦即“分而治之”的方法：把原問題分成若干個子問題，對每一個子問題分別求解，然后把這些解連結(jié)成原問題的解。如果子問題仍然比較復(fù)雜，還可遞歸使用分治法，直到每個子問題都得出解為止。2、下面求S中n個元素最大值的方法也是使用的分治法：intMax(intS[MAXLEN],intn){if(n==1)returnS[0];m=Max(S,n–1);if(m>S[n])returnm;returnS[n];}1、河內(nèi)塔問題的解決方法應(yīng)用的就是分治法；例：程序設(shè)計(jì)常用方法之一：分治法（DivideandConq11程序設(shè)計(jì)常用方法之二：回溯法（Backtracking）

回溯法是一種滿足一定條件的窮舉搜索法：在求解過程中，不斷利用可供選擇的規(guī)則擴(kuò)展部分解，一旦當(dāng)前的部分解不成立，就停止擴(kuò)展，退回到上一個較小的部分解繼續(xù)試探，直到找到問題所有的解或無解為止。1、地圖染色（四色定理）問題：例：0001020304050600020606010503020401111101000010100110010101101011010110110000000000123456R0132456程序設(shè)計(jì)常用方法之二：回溯法（Backtracking）12voidMapColor(intR[n][n],ints[n]){s[0]=1;//00區(qū)染1色i=1;j=1;//i為區(qū)域號，j為染色號while(i<n){while((j≤4)&&(i<n)){k=0;//k指示已染色區(qū)域號while((k<i)&&(s[k]*R[i][k]!=j))k++;//判相鄰區(qū)是否已染色且不同色if(k<i)j++;//用j+1色繼續(xù)試探else{s[i++]=j;j=1;}//該區(qū)染色成功，結(jié)果進(jìn)棧，繼續(xù)染色下一區(qū)voidMapColor(intR[n13}if(j>4){j=s[--i]+1;};//（回溯）變更棧頂區(qū)域的染色色數(shù)，用新顏色重試}}0123456s：}0123456s：142、過河問題：某人帶了一條狗、一只雞和一筐菜過河，因船小，每次只能帶一樣?xùn)|西過河。若單獨(dú)留下狗和雞，則狗會吃雞；若單獨(dú)留下雞和菜，則雞會吃菜。試問他如何過河？結(jié)果如下：1、人+雞過河；2、人空手返回；3、人+狗過河；4、人+雞返回；5、人+菜過河；6、人空手返回；7、人+雞過河。前面說到的迷宮問題、八皇后問題、騎士遍歷問題均可應(yīng)用回溯法求解。2、過河問題：某人帶了一條狗、一只雞和一筐菜過河15作業(yè)2.試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的移動操作move次數(shù)。3.一個簡化的背包問題：一個背包能裝總重量為T，現(xiàn)有n個物件，其重量分別為（W1、W2、…、Wn）。問能否從這n個物件中挑選若干個物件放入背包中，使其總重量正好為T？若有解則給出全部解，否則輸出無解。作業(yè)16作業(yè)4.已知以字符型順序表表示的表達(dá)式含有三種擴(kuò)號“（”、“）”、“[”、“]”、“{”和“}”，它們可嵌套使用，試寫出算法判斷給定表達(dá)式中所含擴(kuò)號是否正確配對出現(xiàn)。作業(yè)17第二次上機(jī)作業(yè)八皇后問題或騎士遍歷問題任選一個。第二次上機(jī)作業(yè)18遞歸過程的模擬以下的方法可對大多數(shù)遞歸程序進(jìn)行模擬：1、定義記錄R，由返回地址、全部的參數(shù)和局部變量組成；2、為每個返回地址定義一個標(biāo)號#i（1≤i≤n-1）；3、為過程體開頭定義一個標(biāo)號#0，作為遞歸入口；4、在結(jié)尾處定義標(biāo)號#n，將所有變參出棧并退棧，過程結(jié)束；5、在過程頭定義R型棧S，并保存#n和參數(shù)等，以便過程結(jié)束；6、將每個遞歸調(diào)用語句用下面四個語句替換：A、將返回地址和實(shí)參進(jìn)棧；B、GoTo#0；C、#i:將變參賦值給局部變量；D、退棧操作。7、在所有遞歸出口處增加語句GoToTOP(S,#i)，返回?cái)帱c(diǎn)；8、各參數(shù)和局部變量均使用棧頂記錄中相應(yīng)數(shù)據(jù)項(xiàng)代替；9、將得到的上述算法優(yōu)化，即可得到結(jié)構(gòu)清晰的非遞歸算法。遞歸過程的模擬以下的方法可對大多數(shù)遞歸程序進(jìn)行模19對有些具有尾遞歸的過程，由于尾遞歸后不需保留參數(shù)和局部變量，可直接用循環(huán)代替遞歸。例如：voidRW(intn){voidRW(intn){if(!n){while(!n){cin>>x;cin>>x;cout<<x;cout<<x;RW(n–1);n=n–1;}}}}§3.3隊(duì)列對有些具有尾遞歸的過程，由于尾遞歸后不需保留20

隊(duì)列（queue）也是插入和刪除操作受限的線性表，但是一種先進(jìn)先出（FirstInFirstOut--FIFO）的線性表。表頭端稱為隊(duì)頭（front），表尾端稱為隊(duì)尾（rear），插入在隊(duì)尾進(jìn)行，而刪除則在隊(duì)頭進(jìn)行。q3frontrearq1q2q5q6q4q1q2q2EnqueueEnqueueEnqueueDequeueEnqueueDequeueEnqueueEnqueueq1隊(duì)列的基本操作：IniqueueClearGetheadEmptyEnqueueDequeueFullSize隊(duì)列（queue）也是插入和刪除操作受限的線21隊(duì)列的實(shí)現(xiàn)：鏈?zhǔn)酱鎯Y(jié)構(gòu)表示隊(duì)列typedefstructnode{elemtypedata;structnode*next;}*pointer;typedefstruct{pointerfront,rear;}linkedqueue;q1q2qiqn……frontrear∧隊(duì)列的實(shí)現(xiàn)：鏈?zhǔn)酱鎯Y(jié)構(gòu)表示隊(duì)列typedefstru22順序存儲結(jié)構(gòu)表示隊(duì)列#defineMAXLENuser_supplytypedefstruct{elemtypeelem[MAXLEN];intfront,rear;}queue;q3q1q2q5q6q4q1q2q2q1q7ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8OF順序存儲結(jié)構(gòu)表示隊(duì)列#defineMAXLENus23[0][1][2][3][4][5]ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8q1q2q3

q4

q5q6q7q8循環(huán)隊(duì)列（circularqueue）i=(i+1)%n入隊(duì)列rear+1，出隊(duì)列front+1,元素個數(shù)=（rear–front+n)%n滿空?FRFRFRRRRRRR

[0][1][2][3][4][5]ENQUEUE1ENQU24判斷循環(huán)隊(duì)列滿和空的三種方法：1、設(shè)置標(biāo)志信號（flag）-----flag=0表示空，flag=1表示滿：front追上rear則flag=0，rear追上front則flag=1；2、留下一個單元不使用，則rear永遠(yuǎn)也追不上front；３、只使用一個指針front和元素個數(shù)size，則可用size的值來判斷隊(duì)列的滿和空。判斷循環(huán)隊(duì)列滿和空的三種方法：1、設(shè)置標(biāo)志信號（flag）-25作業(yè)5.若棧的輸入序列為1234，給出所有可能的輸出序列。6.已知有兩個棧S1和S2及其基本操作Push(S,x)、Pop(S)、Full(S)和Empty(S)，給出用此二棧實(shí)現(xiàn)隊(duì)列操作Enqueue、Dequeue、Fullq和Emptyq的算法作業(yè)26S3§3.1棧第三章.棧和隊(duì)列（Chapter3.StackandQueue)

棧（stack）是插入和刪除操作受限的線性表，是一種后進(jìn)先出（LastInFirstOut--LIFO）的線性表。表頭端稱為棧底（bottom），表尾端稱為棧頂（top），插入和刪除都在棧頂進(jìn)行。bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSHS3§3.1棧第三章.棧和隊(duì)列27棧的基本操作：InistackClearGettopEmptyPushPop棧的實(shí)現(xiàn)：#defineSTACK_INIT_SIZEuser_supply#defineSTACKINCREMENTuser_supplytypedefstruct{elemtype*bottom;elemtype*top;intstackzise;}sqstack;順序存儲結(jié)構(gòu)表示棧Full棧的基本操作：InistackClearGettopEmpt28typedefstrcutlnode{elemtypedata;structlnode*next;}*linkedstack;鏈?zhǔn)酱鎯Y(jié)構(gòu)表示棧----鏈棧（Linked_stack）上溢（overflow）：若棧的容量已全部用完，再進(jìn)行插入操作（PUSH），就會發(fā)生上溢錯誤。下溢（underflow）：若棧已空，再進(jìn)行刪除操作（POP），就會發(fā)生下溢錯誤。typedefstrcutlnode{鏈?zhǔn)酱鎯Y(jié)29§3.2棧的應(yīng)用----表達(dá)式求值任一表達(dá)式（expression）都是由操作數(shù)（operand）、操作符（operator）和界限符（delimiter）組成。我們通常習(xí)慣使用中綴表達(dá)式（infixexpression），但中綴表達(dá)式離不開括號（bracket)。若使用前綴表達(dá)式（prefixexpression）或后綴表達(dá)式（postfixexpression）則不需要括號。利用棧，可以將中綴表達(dá)式變?yōu)榍熬Y表達(dá)式或后綴表達(dá)式，再用棧進(jìn)行運(yùn)算即可得到表達(dá)式的值（value）?！?.3棧與遞歸遞歸（recursive）：一個程序直接調(diào)用自己或通過其它程序調(diào)用自己就稱為遞歸。根據(jù)調(diào)用關(guān)系可分為直接遞歸（directrecursive）和間接遞歸（indirectrecursive）?！?.2棧的應(yīng)用----表達(dá)式求值任一30第一次上機(jī)作業(yè)輸入表達(dá)式字符串，以“=”表示結(jié)束，計(jì)算并輸出表達(dá)式值。操作數(shù)可以是整數(shù)或?qū)崝?shù)，操作符有“+”、“-”、“*”、“/”、“^”（乘方）和“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。第一次上機(jī)作業(yè)31棧在程序的過程或函數(shù)調(diào)用中的作用：過程一過程二過程三過程四斷點(diǎn)三斷點(diǎn)一斷點(diǎn)二斷點(diǎn)一斷點(diǎn)二斷點(diǎn)三stack調(diào)用子程序返回?cái)帱c(diǎn)程序執(zhí)行

棧在程序的過程或函數(shù)調(diào)用中的作用：過程一過程二過程三過程四斷32遞歸是程序設(shè)計(jì)中一種強(qiáng)有力的工具。下面三種情況可用遞歸解決：1、有些數(shù)學(xué)函數(shù)是遞歸定義的，對其求解可用遞歸；2、有些數(shù)據(jù)結(jié)構(gòu)具有遞歸特性，對其操作可用遞歸；3、有些問題的解決方法用遞歸描述，對其求解也可用遞歸。

例：求階乘（factorial）：Fact(n)=1當(dāng)n=0n·Fact(n-1)當(dāng)n>0{intFact(intn){if(!n)return1;//出口條件returnn*Fact(n–1);//遞歸調(diào)用部分}遞歸是程序設(shè)計(jì)中一種強(qiáng)有力的工具。下面三種情33

例：求n個數(shù)的最小值：intMin(sqlistS,intn){if(n==1)returnS[1];//出口條件x=Min(S,n-1);if(x<S[n])returnx;elsereturnS[n];//遞歸調(diào)用部分}例：求n個數(shù)的最小值：intMin(sqli34

例：

河內(nèi)塔（HanoiTower）問題求解：ABCABC如何解決這個問題呢？真?zhèn)X筋?。☆}目要求：1、將n個盤子從A柱移到B柱，C柱可用；

2、每次只能移動一個盤子；

3、在移動過程中，不得將大盤壓在小盤上。解決該問題可分三步走：1、將A柱上面的n-1個盤子從A柱移到C柱；2、將第n個盤子從A柱移到B柱；3、再將C柱上面的n-1個盤子移到B柱。例：河內(nèi)塔（HanoiTower）問題求解：ABCA35voidHanoi(intn,intx,inty,intz){If(n){//出口條件Hanoi(n–1,x,z,y);//遞歸調(diào)用部分Move(n,x,y);Hanoi(n-1,z,y,x);}}求費(fèi)波拉契數(shù)列（Fibonacci）、迷宮問題（Maze）、八皇后（EightQueens）、騎士遍歷（Cavaliertravel）等等。以下這些問題也可用遞歸程序解決：voidHanoi(intn,int36程序設(shè)計(jì)常用方法之一：分治法（DivideandConquer）

亦即“分而治之”的方法：把原問題分成若干個子問題，對每一個子問題分別求解，然后把這些解連結(jié)成原問題的解。如果子問題仍然比較復(fù)雜，還可遞歸使用分治法，直到每個子問題都得出解為止。2、下面求S中n個元素最大值的方法也是使用的分治法：intMax(intS[MAXLEN],intn){if(n==1)returnS[0];m=Max(S,n–1);if(m>S[n])returnm;returnS[n];}1、河內(nèi)塔問題的解決方法應(yīng)用的就是分治法；例：程序設(shè)計(jì)常用方法之一：分治法（DivideandConq37程序設(shè)計(jì)常用方法之二：回溯法（Backtracking）

回溯法是一種滿足一定條件的窮舉搜索法：在求解過程中，不斷利用可供選擇的規(guī)則擴(kuò)展部分解，一旦當(dāng)前的部分解不成立，就停止擴(kuò)展，退回到上一個較小的部分解繼續(xù)試探，直到找到問題所有的解或無解為止。1、地圖染色（四色定理）問題：例：0001020304050600020606010503020401111101000010100110010101101011010110110000000000123456R0132456程序設(shè)計(jì)常用方法之二：回溯法（Backtracking）38voidMapColor(intR[n][n],ints[n]){s[0]=1;//00區(qū)染1色i=1;j=1;//i為區(qū)域號，j為染色號while(i<n){while((j≤4)&&(i<n)){k=0;//k指示已染色區(qū)域號while((k<i)&&(s[k]*R[i][k]!=j))k++;//判相鄰區(qū)是否已染色且不同色if(k<i)j++;//用j+1色繼續(xù)試探else{s[i++]=j;j=1;}//該區(qū)染色成功，結(jié)果進(jìn)棧，繼續(xù)染色下一區(qū)voidMapColor(intR[n39}if(j>4){j=s[--i]+1;};//（回溯）變更棧頂區(qū)域的染色色數(shù)，用新顏色重試}}0123456s：}0123456s：402、過河問題：某人帶了一條狗、一只雞和一筐菜過河，因船小，每次只能帶一樣?xùn)|西過河。若單獨(dú)留下狗和雞，則狗會吃雞；若單獨(dú)留下雞和菜，則雞會吃菜。試問他如何過河？結(jié)果如下：1、人+雞過河；2、人空手返回；3、人+狗過河；4、人+雞返回；5、人+菜過河；6、人空手返回；7、人+雞過河。前面說到的迷宮問題、八皇后問題、騎士遍歷問題均可應(yīng)用回溯法求解。2、過河問題：某人帶了一條狗、一只雞和一筐菜過河41作業(yè)2.試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的移動操作move次數(shù)。3.一個簡化的背包問題：一個背包能裝總重量為T，現(xiàn)有n個物件，其重量分別為（W1、W2、…、Wn）。問能否從這n個物件中挑選若干個物件放入背包中，使其總重量正好為T？若有解則給出全部解，否則輸出無解。作業(yè)42作業(yè)4.已知以字符型順序表表示的表達(dá)式含有三種擴(kuò)號“（”、“）”、“[”、“]”、“{”和“}”，它們可嵌套使用，試寫出算法判斷給定表達(dá)式中所含擴(kuò)號是否正確配對出現(xiàn)。作業(yè)43第二次上機(jī)作業(yè)八皇后問題或騎士遍歷問題任選一個。第二次上機(jī)作業(yè)44遞歸過程的模擬以下的方法可對大多數(shù)遞歸程序進(jìn)行模擬：1、定義記錄R，由返回地址、全部的參數(shù)和局部變量組成；2、為每個返回地址定義一個標(biāo)號#i（1≤i≤n-1）；3、為過程體開頭定義一個標(biāo)號#0，作為遞歸入口；4、在結(jié)尾處定義標(biāo)號#n，將所有變參出棧并退棧，過程結(jié)束；5、在過程頭定義R型棧S，并保存#n和參數(shù)等，以便過程結(jié)束；6、將每個遞歸調(diào)用語句用下面四個語句替換：A、將返回地址和實(shí)參進(jìn)棧；B、GoTo#0；C、#i:將變參賦值給局部變量；D、退棧操作。7、在所有遞歸出口處增加語句GoToTOP(S,#i)，返回?cái)帱c(diǎn)；8、各參數(shù)和局部變量均使用棧頂記錄中相應(yīng)數(shù)據(jù)項(xiàng)代替；9、將得到的上述算法優(yōu)化，即可得到結(jié)構(gòu)清晰的非遞歸算法。遞歸過程的模擬以下的方法可對大多數(shù)遞歸程序進(jìn)行模45對有些具有尾遞歸的過程，由于尾遞歸后不需保留參數(shù)和局部變量，可直接用循環(huán)代替遞歸。例如：voidRW(intn){voidRW(intn){if(!n){while(!n){cin>>x;cin>>x;cout<<x;cout<<x;RW(n–1);n=n–1;}}}}§3.3隊(duì)列對有些具有尾遞歸的過程，由于尾遞歸后不需保留46