算法與數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

第三章棧與隊(duì)列第三章〔第一局部〕棧提綱棧的定義1順序棧2鏈棧3棧的應(yīng)用4BUPT3.1棧的定義[棧的定義]棧是一種特殊的線性表，限定插入和刪除操作只能在表尾進(jìn)行。具有后進(jìn)先出(LIFO—LastInFirstOut)的特點(diǎn)。a0a1an-1棧頂〔表尾〕棧底bottomtop入棧push出棧popBUPT定義在棧結(jié)構(gòu)上的根本運(yùn)算(1)生成空棧操作(2)判?？蘸瘮?shù)(3)數(shù)據(jù)元素入棧操作(4)數(shù)據(jù)元素出棧函數(shù)(5)取棧頂元素函數(shù)(6)置?？詹僮?7)求當(dāng)前棧元素個(gè)數(shù)函數(shù)BUPT3.2.順序棧[棧的順序存儲(chǔ)結(jié)構(gòu)]一個(gè)棧獨(dú)占一組地址連續(xù)的存儲(chǔ)單元[類型定義]數(shù)組(棧空間)+棧頂指示?？諚l件S.top==-1(此時(shí)退棧那么下溢)棧滿條件S.top==max-1(此時(shí)進(jìn)棧那么上溢)

Siai

...1a10a0max-1topBUPT進(jìn)棧例如

BUPT退棧例如BUPT有5個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出?！布碈第一個(gè)且D第二個(gè)出?！车拇涡蛴心膸讉€(gè)？CDEBA，CDBEA，CDBAEBUPT思考：n個(gè)元素依次入棧，可得到多少個(gè)合法的出棧序列

(2n)!/[(n+1)!*n!]不同的出棧序列實(shí)際上對(duì)應(yīng)著不同的入棧出棧操作，以1記為入棧，0為出棧。那么問題實(shí)際上是求n個(gè)1和n個(gè)0構(gòu)成的全排列，其中任意一個(gè)位置，它及它此前的數(shù)中，1個(gè)個(gè)數(shù)要大于等于0的個(gè)數(shù)。

n個(gè)1和n個(gè)0構(gòu)成的全排列數(shù)為：(2n)!/[n!*n!]在n個(gè)0和n個(gè)1構(gòu)成的2n個(gè)數(shù)的序列中，假設(shè)第一次出現(xiàn)0的個(gè)數(shù)大于1個(gè)個(gè)數(shù)〔即0的個(gè)數(shù)比1的個(gè)數(shù)大一〕的位置為k，那么k為奇數(shù)，k之前有相等數(shù)目的0和1，各為(k-1)/2.假設(shè)把這k個(gè)數(shù)，0換成1，1換成0，那么原序列唯一對(duì)應(yīng)上一個(gè)n＋1個(gè)1和n－1個(gè)0的序列。反之，任意一個(gè)由n＋1個(gè)1和n－1個(gè)0構(gòu)成的序列也唯一的對(duì)應(yīng)一個(gè)這樣不合要求的序列。由于一一對(duì)應(yīng)，故這樣不合要求的序列數(shù)實(shí)際上等于有n＋1個(gè)1和n－1個(gè)0構(gòu)成的排列數(shù)，即(2n)!/(n+1)(n-1)。因此合法的個(gè)數(shù)為：(2n)!/[n!*n!]-(2n)!/[(n+1)!*(n-1)!]=(2n)!/[(n+1)!*n!]BUPT[例]兩個(gè)棧共享一組地址連續(xù)的存儲(chǔ)單元

[類型定義]數(shù)組(棧空間)+兩個(gè)棧頂指示

01m-1top[0]top[1]棧滿條件：s.top[0]+1==s.top[1]?？諚l件：s.top[0]==-1〔棧0〕s.top[1]==m〔棧1〕SBUPT多棧處理?xiàng)８?dòng)技術(shù)n棧共享一個(gè)數(shù)組空間V[m]設(shè)立棧頂指針數(shù)組t[n+1]和棧底指針數(shù)組b[n+1]t[i]和b[i]分別指示第i個(gè)棧的棧頂與棧底b[n]作為控制量，指到數(shù)組最高低標(biāo)各棧初始分配空間s=m/n指針初始值t[0]=b[0]=-1b[n]=m-1t[i]=b[i]=b[i-1]+s,i=1,2,…,n-1BUPT插入新元素時(shí)的棧滿處理StackFull()BUPTtemplate<classType>voidPush(constint

i,constType&

item){

if(

t[i]==b[i+1])StackFull(i);

else

V[++t[i]]=item;//第i個(gè)棧進(jìn)棧}template<classType>Type*Pop(const

i){

if(t[i]==b[i])

{

StackEmpty(i);return0;}

elsereturn&

V[t[i]--];//第i個(gè)棧出棧}BUPT3.3.鏈棧top^a0an-2an-1鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作BUPT3.4.棧的應(yīng)用棧與遞歸過程[遞歸的含義]

函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)的內(nèi)部又直接或者間接地由自身定義。[適合于應(yīng)用遞歸的場(chǎng)合]規(guī)模較大的問題可以化解為規(guī)模較小的問題，且二者處理(或定義)的方式一致；當(dāng)問題規(guī)模降低到一定程度時(shí)是可以直接求解的(終止條件)例1.階乘n!=1n=0n·(n-1)!n>0BUPT例2.n階Hanoi塔問題

12..nXYZ12..nXYZ12..n-1XYZn12..n-1XYZn12..n-1nXYZBUPT[寫遞歸算法應(yīng)注意的問題]遞歸算法本身不可以作為獨(dú)立的程序運(yùn)行，需在其它的程序中設(shè)置調(diào)用初值，進(jìn)行調(diào)用；遞歸算法應(yīng)有出口(終止條件)

例1.求n！

intFactorial(intn){if(n==0)return(1);return(n*Factorial(n-1));}BUPT

例2.Hanoi塔問題

PROCEDUREhanoi()[遞歸算法的特點(diǎn)]遞歸算法簡(jiǎn)單明了，直觀易懂時(shí)間效率低，空間開銷大，算法不易優(yōu)化voidHanoi(intn,intx,inty,intz){if(n==1)Move〔x，1，z〕{出口條件}else{Hanoi(n-1,x,z,y);Move(x，n，z);Hanoi(n-1,y,x,z);}}xyz源輔助目標(biāo)BUPTvoidhanoi(3,a,b,c){if(3==1)move(a,1,c);else{hanoi(2,a,c,b);move(a,3,c);hanoi(2,b,a,c);}}voidhanoi(2,a,c,b){if(2==1)move(a,1,b);else{hanoi(1,a,b,c);

move(a,2,b);

hanoi(1,c,a,b);}}voidhanoi(1,a,b,c){if1=1move(a,1,c);

else{……}}voidhanoi(1,c,a,b){if(1==1)move(c,1,b);

else{……}}voidhanoi(2,b,a,c){if(2==1)move(b,1,c);else{hanoi(1,b,c,a);

move(b,2,c);

hanoi(1,a,b,c);}}voidhanoi(1,b,c,a){if(1==1)move(b,1,a);

else{……}}voidhanoi(1,a,b,c){if(1==1)move(a,1,c);

else{……}}abcBUPT[遞歸算法的實(shí)現(xiàn)原理]123s123-利用棧，棧中每個(gè)元素稱為工作記錄，分成三個(gè)局部：返回地址實(shí)在參數(shù)表(變參和值參)局部變量-發(fā)生調(diào)用時(shí)，保護(hù)現(xiàn)場(chǎng)，即當(dāng)前的工作記錄入棧，然后轉(zhuǎn)入被調(diào)用的過程-一個(gè)調(diào)用結(jié)束時(shí)，恢復(fù)現(xiàn)場(chǎng)，即假設(shè)棧不空，那么退棧，從退出的返回地址處繼續(xù)執(zhí)行下去BUPT[遞歸時(shí)系統(tǒng)工作原理例如]intFactorial(intn){L1:if(n==0)L2:return(1);L3:return(n*Factorial(n-1));}voidmain(){……L0:N=Factorial(3);……}

返回地址nFactorialNL03//L33/L32/L31/1126BUPT[遞歸算法的用途]求解遞歸定義的數(shù)學(xué)函數(shù)在以遞歸方式定義的數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算/操作可用遞歸方式描述的解決過程[遞歸轉(zhuǎn)換為非遞歸的方法]1〕采用迭代算法遞歸—從頂?shù)降椎獜牡椎巾斃呵髇！intfact(intn){m=1;for(i=1;i<=n;i++)m=m*i;return(m);}BUPT2〕消除尾遞歸例：順序輸出單鏈表中的結(jié)點(diǎn)數(shù)據(jù)voidlinklist_output(pointerp){IF(p!=NULL){write(p->data);linklist_output(p->next);}}使用跳轉(zhuǎn)語句：voidlinklist_output1(pointerp){

1:if(p!=null){write(p->data);p=p->next;goto1;}}使用循環(huán)語句：voidlinklist_output2(pointerp){while(p!=nil){write(p->data);p:=p->next;}}p^an-1a1a0BUPT3)利用棧模擬遞歸—通用方法如果是遞歸函數(shù)，需改寫為遞歸過程例：求n!

voidfact(intn;int&f){

0:if(n==0)f=1;else{1:fact(n-1,f);2:f:=n*f;}}init_stack(s);if(top!=0){s[top].f=f;{還原本層變參值}top=top-1;n=s[top+1].n;f=s[top+1].f;gotos[top+1].rd}top=top+1;s[top].rd=2;

s[top].n=n;s[top].f=f;n=n-1;goto0;BUPT[自設(shè)棧模擬系統(tǒng)工作棧]

改寫算法在程序開頭增加棧的初始化語句改寫遞歸調(diào)用語句入棧處理；確定調(diào)用的參數(shù)值；轉(zhuǎn)至調(diào)用的開始語句改寫所有遞歸出口退棧復(fù)原參數(shù)；轉(zhuǎn)至返回地址處srdnftopBUPTvoidfact(intn,int&f){init_stack(s);0:if(n==0)f=1;{1:top=top+1;s[top].rd=2;s[top].n=n;s[top].f=f;n=n-1;goto0;2:f=n*f}if(top!=0){s[top].f=f;top=top-1;n=s[top+1].n;f=s[top+1].f;gotos[top+1].rd;}}voidfact(intn,int&f){init_stack(s);while(n!=0){top=top+1;s[top].n=n;n=n-1;}f=1;while(top!=0){top=top-1;n=s[top+1].n;f=n*f;}}注：此時(shí)可確定棧中只存放n值即可。BUPT棧的應(yīng)用2-整型數(shù)簡(jiǎn)單表達(dá)式求值[前提假設(shè)]表達(dá)式語法正確；表達(dá)式結(jié)束符為‘#’[算法思想]OPTR?！娣胚\(yùn)算符OPND?！娣挪僮鲾?shù)1)放入起始符‘#’作為OPTR棧底元素2)依次讀入表達(dá)式字符，操作數(shù)：進(jìn)OPND棧；運(yùn)算符：與OPTR.top元素比較優(yōu)先級(jí)后做相應(yīng)操作；直至讀入‘#’且OPTR棧只?！?’3)OPND棧底所留元素即為所求[例]5+3*(7-2)+11#OPTROPND#53(7-2+*51520+1131BUPT第三章〔第二局部〕隊(duì)列提綱隊(duì)列的定義1鏈隊(duì)列2循環(huán)隊(duì)列3雙端隊(duì)列4BUPT3.5隊(duì)列的定義隊(duì)列是一種特殊的線性表，限定插入和刪除操作分別在表的兩端進(jìn)行。具有先進(jìn)先出(FIFO—FirstInFirstOut)的特點(diǎn)。a0a1…ai…an-1

隊(duì)頭front隊(duì)尾rear出隊(duì)入隊(duì)BUPT定義在隊(duì)列結(jié)構(gòu)上的根本運(yùn)算

(1)構(gòu)造空隊(duì)列操作(2)判隊(duì)空否函數(shù)(3)元素入隊(duì)操作(4)元素出隊(duì)函數(shù)(5)取隊(duì)頭元素函數(shù)(6)隊(duì)列置空操作(7)求隊(duì)中元素個(gè)數(shù)函數(shù)BUPT隊(duì)列的進(jìn)隊(duì)和出隊(duì)

進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)一rear=rear+1，再將新元素按rear指示位置參加。出隊(duì)時(shí)隊(duì)頭指針先進(jìn)一front=front+1，再將front指示的元素取出。隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)；隊(duì)空時(shí)再出隊(duì)將隊(duì)空處理。思考：可否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列？如何實(shí)現(xiàn)？BUPT利用兩個(gè)棧sl、s2〔等容量〕模擬一個(gè)隊(duì)列,實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。初始時(shí)設(shè)棧s1和棧s2均為空?！?〕用棧s1和s2模擬隊(duì)列的輸入：設(shè)s1和s2容量相等。分以下三種情況討論：假設(shè)s1未滿，那么元素入s1棧；假設(shè)s1滿，s2空，那么將s1全部元素退棧，再壓棧入s2，之后元素入s1棧；假設(shè)s1滿，s2不空〔已有出隊(duì)列元素〕，那么不能入隊(duì)?！?〕用棧s1和s2模擬隊(duì)列出隊(duì)〔刪除〕：假設(shè)棧s2不空，退棧，即是隊(duì)列的出隊(duì)；假設(shè)s2為空且s1不空，那么將s1棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當(dāng)于隊(duì)列的出隊(duì)。假設(shè)棧s1為空并且s2也為空，隊(duì)列空，不能出隊(duì)?！?〕判隊(duì)空假設(shè)棧s1為空并且s2也為空，才是隊(duì)列空。討論：s1和s2容量之和是隊(duì)列的最大容量。其操作是，s1棧滿后，全部退棧并壓棧入s2〔設(shè)s1和s2容量相等〕。再入棧s1直至s1滿。這相當(dāng)隊(duì)列元素“入隊(duì)〞完畢。出隊(duì)時(shí)，s2退棧完畢后，s1棧中元素依次退棧到s2，s2退棧完畢，相當(dāng)于隊(duì)列中全部元素出隊(duì)。在棧s2不空情況下，假設(shè)要求入隊(duì)操作，只要s1不滿，就可壓入s1中。假設(shè)s1滿和s2不空狀態(tài)下要求隊(duì)列的入隊(duì)時(shí)，按出錯(cuò)處理。BUPT3.6鏈隊(duì)列用單鏈表表示的隊(duì)列類型定義：隊(duì)頭指針+隊(duì)尾指針datanext^frontrear隊(duì)頭隊(duì)尾隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。隊(duì)空條件為

front->next==NULLBUPT用單循環(huán)鏈表定義的隊(duì)列類型定義：隊(duì)尾指針datanextrear隊(duì)尾BUPT3.7循環(huán)隊(duì)列一般用法的順序存儲(chǔ)結(jié)構(gòu)之缺陷出隊(duì)列操作后大量移動(dòng)數(shù)據(jù)或存在“假上溢〞現(xiàn)象：即存在空閑空間但無法入隊(duì)。解決方法平移元素法，當(dāng)發(fā)生假溢出時(shí)，就把整個(gè)隊(duì)列的元素平移到存儲(chǔ)區(qū)的首部，然后再插入新元素。這種方法需移動(dòng)大量的元素，因而效率是很低的。循環(huán)隊(duì)列a0a1a2a3a4frontrear空閑空間BUPT[循環(huán)隊(duì)列]將順序隊(duì)列的存儲(chǔ)區(qū)假想為一個(gè)環(huán)狀空間[類型定義]

一維數(shù)組(隊(duì)列空間)+頭指針+尾指針隊(duì)頭指針front指向隊(duì)頭元素的前一位置，而隊(duì)尾指針rear指向隊(duì)尾元素.01m-1m-2frontrear優(yōu)點(diǎn)：不需要移動(dòng)元素，操作效率高，空間的利用率也很高。typedefstruct{Elemtypequeue[MAX];intfront;/*隊(duì)頭指針*/intrear;/*隊(duì)尾指針*/}sqqueue;sqqueue*q；BUPT循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)實(shí)例BUPT存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。為解決如何判斷隊(duì)列的滿與空問題：犧牲一個(gè)存儲(chǔ)單元。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。出隊(duì):

front=(front+1)%maxSize;入隊(duì):rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxSize==front思考：循環(huán)隊(duì)列中當(dāng)前元素的個(gè)數(shù)為多少？當(dāng)前元素個(gè)數(shù)n=(rear-front+maxsize)%maxsizeBUPT[例]假設(shè)以數(shù)組sq[8]存放循環(huán)隊(duì)列元素,變量front指向隊(duì)頭元素的前一位置,變量rear指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作。請(qǐng)給出：執(zhí)行操作序列A3D1A5D2A1D2A4時(shí)的狀態(tài)。隊(duì)空的初始條件：front=rear=0；執(zhí)行操作A3后，rear=3；//A3表示三次入隊(duì)操作執(zhí)行操作D1后，front=1；//D1表示一次出隊(duì)操作執(zhí)行操作A5后，rear=0；執(zhí)行操作D2后，front=3；執(zhí)行操作A1后，rear=1；執(zhí)行操作D2后，front=5；執(zhí)行操作A4后，溢出。因?yàn)閳?zhí)行A3后，rear=4，這時(shí)隊(duì)滿，假設(shè)再執(zhí)行A操作，那么出錯(cuò)。BUPT3.8雙端隊(duì)列[雙端隊(duì)列]限定插入和刪除操作在線性表的兩端進(jìn)行。可以將它看成是棧底連在一起的兩個(gè)棧，但它與兩個(gè)棧共享存儲(chǔ)空間是不同的。共享存儲(chǔ)空間中的兩個(gè)棧的棧頂指針是向兩端擴(kuò)展的，因而每個(gè)棧只需一個(gè)指針；而雙端隊(duì)列允許兩端進(jìn)行插入和刪除元素，因而每個(gè)端點(diǎn)必須設(shè)立兩個(gè)指針。BUPT實(shí)際應(yīng)用中的特殊隊(duì)列輸出受限的雙端隊(duì)列〔即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許插入〕；輸入受限的雙端隊(duì)列〔即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許刪除〕。如果限定雙端隊(duì)列從某個(gè)端點(diǎn)插入的元素只能從該端點(diǎn)刪除，那么雙端隊(duì)列就蛻變?yōu)閮蓚€(gè)棧底相鄰接的棧了。BUPT如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作，其結(jié)構(gòu)如下：#defineM隊(duì)列可能到達(dá)的最大長(zhǎng)度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;請(qǐng)寫出“從隊(duì)尾刪除〞和“從隊(duì)頭插入〞的算法。elemtpdelqueue(cycqueueQ)voidenqueue(cycqueueQ,elemtpx)[分析]用一維數(shù)組v[M]實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，(rear+1)%m=front為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向開展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向開展。BUPTelemtpdelqueue(cycqueueQ)//Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，假設(shè)刪除成功，返回被刪除元素，否那么給出出錯(cuò)信息。 { if(Q.front==Q.rear) { printf(“隊(duì)列空〞);exit(0);} Q.rear=(Q.rear-1+M)%M;//修改隊(duì)尾指針。return(Q.data[(Q.r