軟件基礎(chǔ)-3棧

1、第二章 線性結(jié)構(gòu),一、棧的定義和運(yùn)算,二、順序棧,三、鏈棧,四、棧的應(yīng)用,五、小結(jié),第 2 節(jié) 棧,第二章 線性表,2.2 棧,一、棧的概念和運(yùn)算,棧的定義 棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)。 設(shè)棧s=(a1,a2,.,an)，a1稱為棧底元素,an稱為棧頂元素。 棧中元素按a1,a2,.,an次序進(jìn)棧，又按an,.,a2,a1次序退棧。因此棧的操作特點(diǎn)是：后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）； n=0時(shí)稱為空棧。,第二章 線性表,2.2 棧,一、棧的概念和運(yùn)算,2.棧的存儲(chǔ) 棧的順序存儲(chǔ)順序棧,棧的

2、鏈?zhǔn)酱鎯?chǔ)鏈棧 用指針來實(shí)現(xiàn)的棧叫鏈棧。棧的容量事先不能估計(jì)時(shí)采用這種存儲(chǔ)結(jié)構(gòu)。,第二章 線性表,2.2 棧,一、棧的概念和運(yùn)算,3.棧的基本運(yùn)算 棧的初始化 判?？?Empty 入棧 Push 出棧 Pop 讀棧頂元素,棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為0,進(jìn)棧,A,出棧,棧滿,B,C,D,E,F,設(shè)一維數(shù)組長(zhǎng)度為M top=0,?？?，此時(shí)出棧，則下溢（underflow) top=M,棧滿，此時(shí)入棧，則上溢（overflow),?？?2.2 棧,二、順序棧 ( 實(shí)現(xiàn)：一維數(shù)組sM ),2.2 棧,二、順序棧 1.棧結(jié)構(gòu),typedef struct datatype dataMA

3、X; int top; SeqStack;,創(chuàng)建一個(gè)棧： SeqStack *s;,2.2 棧,二、順序棧 2.棧的初始化,SeqStack *StackList() /構(gòu)造一個(gè)空棧 SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack); s-top=0; /約定top始終指向新數(shù)據(jù)元素將存放的位置 return s; ,2.2 棧,二、順序棧 3.判?？?int Empty(SeqStack *s) if( s-top = 0) return 1; / 棧空,返回 else return 0; / 棧非空,返回 ,2.2 棧,二、順序棧 4.入棧

4、,int Push(SeqStack *s,datatype x) if( s-top = Max) return 0; / 棧滿,返回 else s-datas-top=x; /x值入棧 s-top+; /指示器加1 return 1; /成功，返回 ,2.2 棧,二、順序棧 .出棧且讀棧頂元素,int Pop(SeqStack *s,datatype *x) if( Empty(s) return 0; / ?？?返回 else s-top-; /指示器減1 *x=s-datas-top ; /出棧 return 1; /成功，返回 ,2.2 棧,三、鏈棧,top問題？ 若top指向最后一

5、個(gè)元素，則入棧和出棧操作時(shí)top的值都要變化，在C中參數(shù)傳值方式難實(shí)現(xiàn)！ 解決辦法： 用增加頭結(jié)點(diǎn)方式,2.2 棧,三、鏈棧,.結(jié)點(diǎn)定義 typedef struct Node datatype data; struct Node *next; StackNode;,棧空: 若有頭結(jié)點(diǎn)時(shí)top-next=Null為空棧； 若無頭結(jié)點(diǎn)時(shí)top=Null為空棧,建立一個(gè)鏈棧： StackNode *top;,如何判?？?？,2.2 棧,三、鏈棧,2.鏈棧初始化 StackNode *Creat( ) StackNode *top; / 創(chuàng)建頭結(jié)點(diǎn) top= (StackNode *)malloc(s

6、izeof(StackNode); top-next=Null; / 設(shè)置頭結(jié)點(diǎn) return top; /返回頭指針 ,2.2 棧,三、鏈棧,3.入棧頭插法 void Push(StackNode *s, datatype x ) StackNode *p; / 創(chuàng)建一個(gè)新結(jié)點(diǎn)p p= (StackNode *)malloc(sizeof(StackNode); p-data=x; / 設(shè)置p結(jié)點(diǎn) p-next=s-next; / p結(jié)點(diǎn)加入鏈棧中 s-next=p; /頭結(jié)點(diǎn)next指向新的棧頂結(jié)點(diǎn)p ,x,StackNode *p;,p= (StackNode *)malloc(size

7、of(StackNode);,p-data=x;,p-next=s-next;,s-next=p;,2.2 棧,三、鏈棧,.出棧 int Pop(StackNode *s, datatype *x ) StackNode *p; / 創(chuàng)建一個(gè)新結(jié)點(diǎn)p if (s-next=Null ) return 0; /?？?，返回失敗 *x= s-next-data; / 傳回棧頂結(jié)點(diǎn)的數(shù)據(jù) p=s-next; / p結(jié)點(diǎn)指向棧頂結(jié)點(diǎn) s-next=p-next; /頭結(jié)點(diǎn)next域指向p下一個(gè)結(jié)點(diǎn) free(p); / 釋放p結(jié)點(diǎn)刪除棧頂結(jié)點(diǎn) return 1; /返回成功 ,2.2 棧,四、棧的應(yīng)用,

8、 數(shù)制轉(zhuǎn)換 函數(shù)的遞歸調(diào)用 表達(dá)式求值 迷宮求解, 數(shù)制轉(zhuǎn)換,2.2 棧,算法見書第55頁，自學(xué),2.2 棧, 表達(dá)式求值 1. 高級(jí)語言中的表達(dá)式是用人們熟悉的公式形式書寫的， 如：a+b*c-d 中綴表達(dá)式 為解決運(yùn)算順序問題把運(yùn)算符分成若干等級(jí)級(jí)別高的先運(yùn)算。 . 后綴表達(dá)式（也稱逆波蘭表達(dá)式RPN) 如：abc*+d- 運(yùn)算符在運(yùn)算對(duì)象的后面，無需判斷運(yùn)算符優(yōu)先級(jí)，遇到運(yùn)算符就計(jì)算運(yùn)算對(duì)象，簡(jiǎn)單方便。,2. 棧,.中綴表達(dá)式求值 為解決運(yùn)算順序問題把運(yùn)算符分成若干等級(jí)，稱為優(yōu)先數(shù)。 運(yùn)算符： * / * + - （ ） 界限符： ； 優(yōu)先級(jí)： 4 3 3 2 2 1 1 0 輸入：表達(dá)

9、式符號(hào)序列 輸出：表達(dá)式值 y 為進(jìn)行表達(dá)式的翻譯，需設(shè)立兩個(gè)棧，分別存放操作數(shù)(NS)和運(yùn)算符(OS)， 初始化棧 NS、OS：在OS中放入表達(dá)式結(jié)束符“；” 。,1.中綴表達(dá)式求值 A*B + C/D;,自左至右掃描表達(dá)式，對(duì)掃描的每個(gè)符號(hào)w作如下處理： 1) 若w為操作數(shù)，將其壓入NS棧，繼續(xù)掃描 2) 若w為運(yùn)算符，需看當(dāng)前OS的棧頂元素優(yōu)先數(shù)： 若w大于OS棧頂運(yùn)算符，則將w壓入OS棧,繼續(xù)掃描。 若w為“；”，且OS棧頂也為“；”，則表示表達(dá)式處理結(jié)束，此時(shí)NS棧頂?shù)脑丶礊榇吮磉_(dá)式的結(jié)果值。 若w為“)”,且OS棧頂也為“(”,從OS棧中彈出“(”,繼續(xù)掃描. 若w小于或等于OS

10、棧頂運(yùn)算符，則從NS棧中彈出兩個(gè)操作數(shù)，設(shè)為x、y，再從OS棧中彈出一個(gè)運(yùn)算符，設(shè)為，構(gòu)成一條指令：y x T，將結(jié)果T送入NS棧。繼續(xù)與OS棧頂元素比較,2. 棧,例 A*B + C/D;,2. 后綴表達(dá)式求值 只需一個(gè)操作數(shù)棧，步驟： 1) 讀入表達(dá)式一個(gè)字符 2) 若是操作數(shù)，壓入棧，轉(zhuǎn)4 3) 若是運(yùn)算符，從棧中彈出2個(gè)數(shù)，將運(yùn)算結(jié)果再壓入棧 4) 若表達(dá)式輸入完畢，棧頂即表達(dá)式值； 若表達(dá)式未輸入完，轉(zhuǎn)1,例 計(jì)算 4+3*5,轉(zhuǎn)換為后綴表達(dá)式：435*+,后綴表達(dá)式計(jì)算簡(jiǎn)單方便，如何完成由中綴到后綴的轉(zhuǎn)換呢？,中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換：需用一個(gè)運(yùn)算符棧,請(qǐng)把 a+(b*c+d)

11、/e 轉(zhuǎn)換為后綴表達(dá)式,輸入：中綴表達(dá)式 輸出：后綴表達(dá)式 從左至右掃描中綴表達(dá)式，每個(gè)符號(hào)做如下判斷： 1）若是變量則作為新表達(dá)式的變量； 2）若是“(”就入棧； 3）若是運(yùn)算符則檢查棧，如果?？?，則運(yùn)算符進(jìn)棧， 否則，與棧頂運(yùn)算符比較： (1) 若小于或等于棧頂運(yùn)算符級(jí)別，則棧頂元素出棧，寫入新表達(dá)式，繼續(xù)比較下一個(gè)棧頂運(yùn)算符; (2) 反之，將新運(yùn)算符入棧； 4）若是“)”,則將棧頂運(yùn)算符一一出棧，寫入新表達(dá)式中，直到讀出相應(yīng)的“(”為止，然后刪去“(”。,abc*d+e/+,例中綴表達(dá)式A * B + C / D ; 求等價(jià)的后綴表達(dá)式?,*,2. 棧, 過程嵌套和遞歸調(diào)用 過程嵌套和

12、遞歸調(diào)用是程序設(shè)計(jì)中很重要的應(yīng)用。當(dāng)過程調(diào)用子程序時(shí)，必須把斷點(diǎn)的信息及地址保存起來，當(dāng)子過程執(zhí)行完畢返回時(shí)，取用這些信息，找到返回地址，從斷點(diǎn)處繼續(xù)執(zhí)行。當(dāng)程序中出現(xiàn)多重嵌套調(diào)用時(shí)，必須開辟一個(gè)棧，將各層斷點(diǎn)信息依次入棧，當(dāng)各層子過程返回時(shí)，又以相反的次序從棧頂取出，這樣才能保證程序的正常執(zhí)行。,函數(shù)的遞歸調(diào)用,1. 定義： 在調(diào)用一個(gè)函數(shù)的過程中直接或間接地調(diào)用該函數(shù)本身。 直接調(diào)用 int f(int x) int y,z; . z=f(x); return (2*z); ,f 函數(shù),調(diào)用 f函數(shù),int f1(x) int x; int y,z; . z=f2( y); return

13、(2*z); ,int f2(t) int t; int a,c; . c=f1(a); return (3+c); ,間接調(diào)用,特點(diǎn) 是無終止的遞歸調(diào)用，因此，應(yīng)該給定一個(gè)限制遞歸次數(shù)的條件。,long fac ( int n) long s; if ( n= =1) s=1; else s=n*fac(n-1); return(s); ,例如：寫一函數(shù)求n!,以求4的階乘為例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)=2*fac( 1),fac(1)=1,fac(4)=4*3*2*1,fac(2)=2*1,fac(3)=3*2*1,下 推,回 代,利用棧實(shí)現(xiàn)遞歸調(diào)用,s,long fac ( int n) long s; if ( n= =1) s=1; else s=n*fac(n-1); return(s); ,main() printf(“%d”fac(4); ,回文游戲：順讀與逆讀字符串