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

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

Siai

...1a10a0max-1topBUPT進棧例如

BUPT退棧例如BUPT有5個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出?！布碈第一個且D第二個出棧〕的次序有哪幾個？CDEBA，CDBEA，CDBAEBUPT思考：n個元素依次入棧，可得到多少個合法的出棧序列

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

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

[類型定義]數(shù)組(?？臻g)+兩個棧頂指示

01m-1top[0]top[1]棧滿條件：s.top[0]+1==s.top[1]棧空條件：s.top[0]==-1〔棧0〕s.top[1]==m〔棧1〕SBUPT多棧處理棧浮動技術(shù)n棧共享一個數(shù)組空間V[m]設(shè)立棧頂指針數(shù)組t[n+1]和棧底指針數(shù)組b[n+1]t[i]和b[i]分別指示第i個棧的棧頂與棧底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插入新元素時的棧滿處理StackFull()BUPTtemplate<classType>voidPush(constint

i,constType&

item){

if(

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

else

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

i){

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

{

StackEmpty(i);return0;}

elsereturn&

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

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

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

例1.求n！

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

例2.Hanoi塔問題

PROCEDUREhanoi()[遞歸算法的特點]遞歸算法簡單明了，直觀易懂時間效率低，空間開銷大，算法不易優(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[遞歸算法的實現(xiàn)原理]123s123-利用棧，棧中每個元素稱為工作記錄，分成三個局部：返回地址實在參數(shù)表(變參和值參)局部變量-發(fā)生調(diào)用時，保護現(xiàn)場，即當(dāng)前的工作記錄入棧，然后轉(zhuǎn)入被調(diào)用的過程-一個調(diào)用結(jié)束時，恢復(fù)現(xiàn)場，即假設(shè)棧不空，那么退棧，從退出的返回地址處繼續(xù)執(zhí)行下去BUPT[遞歸時系統(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)上的運算/操作可用遞歸方式描述的解決過程[遞歸轉(zhuǎn)換為非遞歸的方法]1〕采用迭代算法遞歸—從頂?shù)降椎獜牡椎巾斃呵髇！intfact(intn){m=1;for(i=1;i<=n;i++)m=m*i;return(m);}BUPT2〕消除尾遞歸例：順序輸出單鏈表中的結(jié)點數(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;}}注：此時可確定棧中只存放n值即可。BUPT棧的應(yīng)用2-整型數(shù)簡單表達(dá)式求值[前提假設(shè)]表達(dá)式語法正確；表達(dá)式結(jié)束符為‘#’[算法思想]OPTR?！娣胚\算符OPND棧—存放操作數(shù)1)放入起始符‘#’作為OPTR棧底元素2)依次讀入表達(dá)式字符，操作數(shù)：進OPND棧；運算符：與OPTR.top元素比較優(yōu)先級后做相應(yīng)操作；直至讀入‘#’且OPTR棧只?！?’3)OPND棧底所留元素即為所求[例]5+3*(7-2)+11#OPTROPND#53(7-2+*51520+1131BUPT第三章〔第二局部〕隊列提綱隊列的定義1鏈隊列2循環(huán)隊列3雙端隊列4BUPT3.5隊列的定義隊列是一種特殊的線性表，限定插入和刪除操作分別在表的兩端進行。具有先進先出(FIFO—FirstInFirstOut)的特點。a0a1…ai…an-1

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

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

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

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

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

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