安徽農(nóng)業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)課件

1、* 棧棧* 棧的應(yīng)用棧的應(yīng)用* 隊(duì)列隊(duì)列* 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用 3.1.1 3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算 棧棧(Stack)(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂線性表，通常稱插入、刪除的這一端為棧頂(Top)(Top)，另一，另一端為棧底端為棧底(Bottom)(Bottom)。當(dāng)表中沒有元素時稱為空棧。當(dāng)表中沒有元素時稱為空棧。假設(shè)棧假設(shè)棧S=(a1S=(a1，a2a2，a3a3，an)an)，則，則a1a1稱為棧底稱為棧底元素，元素，anan為棧頂元素。棧中元素按為棧頂元素。棧中元

2、素按a1a1，a2a2，a3a3，anan的次序進(jìn)棧，退棧的第一個的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。即，棧的修改元素應(yīng)為棧頂元素。即，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（稱為后進(jìn)先出表（LIFOLIFO）。 3.1.2 3.1.2 順序棧順序棧 由于棧是運(yùn)算受限的線性表，因此線性表的存儲結(jié)構(gòu)由于棧是運(yùn)算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng)。對棧也適應(yīng)。 棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實(shí)現(xiàn)順序棧。因?yàn)闂５孜恢檬枪绦员?。因此，可用?shù)組來實(shí)現(xiàn)順序

3、棧。因?yàn)闂５孜恢檬枪潭ú蛔兊?，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何定不變的，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而一個端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而 變化的，故需用一個整型變量變化的，故需用一個整型變量toptop來指示當(dāng)前來指示當(dāng)前 棧頂?shù)奈恢?，通常稱棧頂?shù)奈恢?，通常稱toptop為棧頂指針。為棧頂指針。 因此，順序棧的類型定義只需將順序表因此，順序棧的類型定義只需將順序表 的類型定義中的長度屬性改為的類型定義中的長度屬性改為toptop即可即可。順序棧的類型定義如下：順序棧的類型定義如下： # define StackSize 100 t

4、ypedef char datatype; typedef struct datatype datastacksize; int top; seqstack; top6 5 4 3 2 1 0-1例、例、一疊書或一疊盤子。一疊書或一疊盤子。 棧的抽象數(shù)據(jù)類型的定義如下：棧的抽象數(shù)據(jù)類型的定義如下： a n a n-1 a2 a1棧頂棧頂 棧底棧底棧棧s=(a1,a2,s=(a1,a2,an),an) 設(shè)設(shè)S是是SeqStack類型的指針變量。若棧底位置在向量類型的指針變量。若棧底位置在向量的低端，即的低端，即sdata0是棧底元素，那么棧頂指針是棧底元素，那么棧頂指針stop是正向增加的，即進(jìn)

5、棧時需將是正向增加的，即進(jìn)棧時需將stop加加1，退棧時需將，退棧時需將stop 減減1。因此，。因此，stoptop =stacksize-1表示棧滿。當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生表示棧滿。當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡稱空間溢出，簡稱“上溢上溢”;當(dāng)棧空時再做退棧運(yùn)算也將產(chǎn)當(dāng)?？諘r再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱生溢出，簡稱“下溢下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免法避免 之；下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ谥幌乱鐒t可能是正?，F(xiàn)象，因?yàn)闂Ｔ?程序中使用時，其初態(tài)或終態(tài)都是程序中使用時，其初態(tài)或終態(tài)都是 空棧，所以下溢常常用來作為程序控制空棧，所以下溢

6、常常用來作為程序控制 轉(zhuǎn)移的條件。轉(zhuǎn)移的條件。 void initstack ( seqstack *s ) s top = 0; int stackempty ( seqstack *s ) return ( s top = 0 ); int stackfull ( seqstack *s ) return ( s top = stacksize - 1 ); void push ( seqstack *s，datatype x ) if ( stackfull (s) ) error ( “stack overflow” ); s data +stop = x; datatype pop

7、( seqstack *s ) if ( stackempty (s) ) error ( “stack underflow” ); x = s data top; s top -; return (x) /return(sdatastop-); Datatype gettop ( seqstack *s ) if ( stackempty (s) ) error ( “stack is empty” ); return s data s top ; 例：例：對于一個棧，給出輸入項(xiàng)對于一個棧，給出輸入項(xiàng)A A、B B、C C，如果輸入項(xiàng)序列，如果輸入項(xiàng)序列由由ABCABC組成，試給出所有可能的

8、輸出序列。組成，試給出所有可能的輸出序列。 A進(jìn)進(jìn) A出出 B進(jìn)進(jìn) B出出 C進(jìn)進(jìn) C出出 ABC A進(jìn)進(jìn) A出出 B進(jìn)進(jìn) C進(jìn)進(jìn) C出出 B出出 ACB A進(jìn)進(jìn) B進(jìn)進(jìn) B出出 A出出 C進(jìn)進(jìn) C出出 BAC A進(jìn)進(jìn) B進(jìn)進(jìn) B出出 C進(jìn)進(jìn) C出出 A出出 BCA A進(jìn)進(jìn) B進(jìn)進(jìn) C進(jìn)進(jìn) C出出 B出出 A出出 CBA 不可能產(chǎn)生輸出序列不可能產(chǎn)生輸出序列CAB 3.1.3 3.1.3 鏈棧鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它的運(yùn)算是受限的棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它的運(yùn)算是受限的單鏈表，插入和刪除操作僅限制在表頭位置上進(jìn)行。單鏈表，插入和刪除操作僅限制在表頭位置上進(jìn)行。由于只能在鏈表頭部進(jìn)行

9、操作，故鏈表沒有必要像單由于只能在鏈表頭部進(jìn)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。 鏈棧的類型說明如下：鏈棧的類型說明如下：棧的鏈接存儲結(jié)構(gòu)棧的鏈接存儲結(jié)構(gòu)鏈棧的結(jié)點(diǎn)定義鏈棧的結(jié)點(diǎn)定義 typedef int datatype; typedef struct node datatype data; struct node *next; linkstack; 棧的鏈接表示棧的鏈接表示 鏈?zhǔn)綏ｆ準(zhǔn)綏?鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充 插入與刪除僅在棧頂處執(zhí)行插入與刪除僅在棧頂處執(zhí)行 鏈?zhǔn)綏５臈ｍ?/p>

10、在鏈頭鏈?zhǔn)綏５臈ｍ斣阪滎^ 適合于多棧操作適合于多棧操作linkstack *PUSHLSTACK ( linkstack *top, datatype x ) linkstack *p; p malloc ( sizeof ( linkstack ) ); p - data x; p - next top; top = p; return p; linkstack *POPLSTACK ( linkstack *top, datatype datap ) linkstack *p; if ( top = NULL ) printf( “under flown” ); return NULL;

11、else *datap top - data; p top; top top - next; free ( p ); return top; 3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。以下是幾個棧應(yīng)用的例子。為程序設(shè)計(jì)中常用的工具。以下是幾個棧應(yīng)用的例子。 十進(jìn)制十進(jìn)制N N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn) 計(jì)算的基本問題計(jì)算的基本問題, ,其解決方法很多其解決方法很多, ,其中一個其中一個 簡單算法基于下列原理簡單算法基于下列原理: : N =( n d

12、iv d ) N =( n div d ) * * d + n mod d d + n mod d ( ( 其中其中:div:div為整除運(yùn)算為整除運(yùn)算,mod,mod為求余運(yùn)算為求余運(yùn)算) )棧的應(yīng)用舉例棧的應(yīng)用舉例-數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例如例如 ( (1348)1348)1010=(2504)=(2504)8 8，其運(yùn)算過程如下其運(yùn)算過程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack ( s ); scanf ( “ % ” , n); while( n ) push ( s

13、 , n % 8 ); n = n / 8; while( ! Stackempty ( s ) pop ( s , e ); printf ( “ % d ” , e ); seqstack s ;EDIT( ) char c ; SETNULL ( & s ) ; c getchar ( ); while ( c ! = * ) if ( c = = # ) POP ( & s ) ; else if ( c = = ) SETNULL ( & s ) ; else PUSH ( & s , c ) ; c getchar ( ) ; 棧棧的的應(yīng)應(yīng)用用舉舉例例文文字字編編輯輯器器棧的應(yīng)用舉

14、例表達(dá)式計(jì)算棧的應(yīng)用舉例表達(dá)式計(jì)算中綴表達(dá)式：中綴表達(dá)式：A + ( B C / D) E后綴表達(dá)式：后綴表達(dá)式：ABCD/E+后綴表達(dá)式特點(diǎn)后綴表達(dá)式特點(diǎn)1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同2、沒有括號、沒有括號后綴表達(dá)式的處理過程后綴表達(dá)式的處理過程操作順序操作順序后綴表達(dá)式后綴表達(dá)式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式()#(#=當(dāng)前運(yùn)算符當(dāng)前運(yùn)算符棧頂運(yùn)算符棧頂運(yùn)算符1 1、如為操作數(shù)，直接輸出到（鏈表）隊(duì)列；、如為操作數(shù)，

15、直接輸出到（鏈表）隊(duì)列；2 2、如當(dāng)前運(yùn)算符高于棧頂運(yùn)算符，入棧；、如當(dāng)前運(yùn)算符高于棧頂運(yùn)算符，入棧；3 3、如當(dāng)前運(yùn)算符低于棧頂運(yùn)算符，棧頂運(yùn)算符退棧，并輸、如當(dāng)前運(yùn)算符低于棧頂運(yùn)算符，棧頂運(yùn)算符退棧，并輸出到（鏈表）隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較；出到（鏈表）隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較；4 4、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，且棧頂運(yùn)算、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，且棧頂運(yùn)算符為符為“（”，當(dāng)前運(yùn)算符為，當(dāng)前運(yùn)算符為“）”，則棧頂運(yùn)算符，則棧頂運(yùn)算符退棧，繼續(xù)讀下一符號；退棧，繼續(xù)讀下一符號；5 5、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，、如當(dāng)前運(yùn)算符等于棧頂運(yùn)算符，且棧頂運(yùn)算符為且棧頂運(yùn)算

16、符為“# #”，當(dāng)前運(yùn)算符也為，當(dāng)前運(yùn)算符也為“# #”，則棧頂運(yùn)算符退棧，比較結(jié)束；則棧頂運(yùn)算符退棧，比較結(jié)束；步驟步驟中綴表達(dá)式中綴表達(dá)式STACK輸出輸出1A(BCD)E#2(BCD)E#A3(BCD)E# A4BCD)E# (A5CD)E# (AB6CD)E# +(AB7D)E# (ABC8D)E# (/ABC9)E# (/ABCD10)E# # (ABCD/11)E# # (ABCD/ 12E# # ABCD/ 13E# # ABCD/ 14# # ABCD/ E15# # +ABCD/ E 16# #ABCD/ E 出出口口入口入口迷迷宮宮求求解解 棧的應(yīng)用棧的應(yīng)用 過程的嵌套調(diào)用

17、過程的嵌套調(diào)用r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3例例: : 遞歸過程及其實(shí)現(xiàn)遞歸過程及其實(shí)現(xiàn) 遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸遞歸 實(shí)現(xiàn)：建立遞歸工作棧實(shí)現(xiàn)：建立遞歸工作棧#include int Multiply( int M,int N ) int Result; if ( N = 1 ) Result = M; Else Result = M + Multiply(M,N-1); return Result; int main (void) int NumA = 13; int NumB = 4; int P

18、roduct; Product = multiply(NumA,NumB); Printf(“%d * %d = %d”,NumA,NumB,Product); return 1; 運(yùn)行結(jié)果：運(yùn)行結(jié)果： 13 * 4 = 52程序流程：程序流程：Multiply(13,4)M = 13N = 4N != 1Result =13 + Multiply(13,3)return ResultM = 13N = 3N != 1Result =13 + Multiply(13,2)return ResultM = 13N = 2N != 1Result =13 + Multiply(13,1)retur

19、n ResultM = 13N = 1N = 1Result =13return Result52392613從以上的例子中，我們可以歸納出幾個解遞歸問題的步驟：步驟1：了解題意是否適合用遞歸來解題。步驟2：決定遞歸結(jié)束條件(Stopping Cases)。步驟3：決定遞歸執(zhí)行部分(Recursive Step)。 3.3 3.3 隊(duì)列隊(duì)列 隊(duì)列的定義及特點(diǎn)隊(duì)列的定義及特點(diǎn) 定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表的另一端進(jìn)行刪除的線性表 隊(duì)尾隊(duì)尾(rear)(rear)允許插入的一端允許插入的一端 隊(duì)頭隊(duì)頭(front)

20、(front)允許刪除的一端允許刪除的一端 隊(duì)列特點(diǎn)：先進(jìn)先出隊(duì)列特點(diǎn)：先進(jìn)先出 ( ( FIFO ) )a1 a2 a3.an 入隊(duì)入隊(duì)出隊(duì)出隊(duì)frontrear隊(duì)列隊(duì)列Q=(a1,a2,an) 雙端隊(duì)列雙端隊(duì)列入隊(duì)入隊(duì)出隊(duì)出隊(duì)入隊(duì)入隊(duì)a1 a2 a3.an 端端1 1端端2 2出隊(duì)出隊(duì) 鏈隊(duì)列鏈隊(duì)列 結(jié)點(diǎn)定義結(jié)點(diǎn)定義typedef struct node int data; struct node *link;JD;頭結(jié)點(diǎn)頭結(jié)點(diǎn) .front隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針設(shè)隊(duì)首、隊(duì)尾指針front和和rear,front指向頭結(jié)點(diǎn)，指向頭結(jié)點(diǎn)，rear指向隊(duì)尾指向隊(duì)尾frontr

21、earx入入隊(duì)隊(duì)xfrontreary入入隊(duì)隊(duì)xyfrontrearx出出隊(duì)隊(duì)xyfront rear空隊(duì)空隊(duì)front reary出出隊(duì)隊(duì) 入隊(duì)算法入隊(duì)算法 出隊(duì)算法出隊(duì)算法JD *ldcr ( JD *rear , int x ) JD *p; p = ( JD *) malloc ( sizeof ( JD ); p - data = x; p - link = NULL; rear - link = p; rear = p; return ( p );int ldsc ( JD *front , JD *rear ) JD *s; int x; if ( front = = rear

22、) return ( - 1 ); s = front - link; front - link = s - link; if ( s - link = = NULL) rear = front; x = s - data; free ( s ); return ( x ); 隊(duì)列的順序存儲結(jié)構(gòu)隊(duì)列的順序存儲結(jié)構(gòu) 實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sqMfront=0rear=0123450隊(duì)空隊(duì)空123450frontJ1,J2,J3入隊(duì)入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)入隊(duì)J4J5J6front設(shè)兩個指針設(shè)兩個指針front,rear,約定：約定：rear指示隊(duì)尾元素指示隊(duì)尾元素下一位置下一位置；front指示隊(duì)頭元素指示隊(duì)頭元素；初值初值front=rear=0空隊(duì)列條件：空隊(duì)列條件：front=rear入隊(duì)列：入隊(duì)列：sq+rear=x;出隊(duì)列：出隊(duì)列：x=sq+front;rearrearfrontJ1,J2,J3出隊(duì)出隊(duì)frontfrontrear123450J1J2J3front 存在問題存在問題設(shè)數(shù)組維數(shù)為設(shè)數(shù)組維數(shù)為M，則：則： 當(dāng)當(dāng)front=0,rear=M時，再有元素入隊(duì)發(fā)生溢出時，再有元素入隊(duì)發(fā)生溢出真溢出真溢出 當(dāng)當(dāng)front 0,rear=M時，再有元素入隊(duì)發(fā)生溢出時，再有元素入隊(duì)發(fā)生溢