軟件基礎-3棧

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

2、鏈式存儲鏈棧 用指針來實現的棧叫鏈棧。棧的容量事先不能估計時采用這種存儲結構。,第二章 線性表,2.2 棧,一、棧的概念和運算,3.棧的基本運算 棧的初始化 判?？?Empty 入棧 Push 出棧 Pop 讀棧頂元素,棧頂指針top,指向實際棧頂后的空位置，初值為0,進棧,A,出棧,棧滿,B,C,D,E,F,設一維數組長度為M top=0,?？?，此時出棧，則下溢（underflow) top=M,棧滿，此時入棧，則上溢（overflow),棧空,2.2 棧,二、順序棧 ( 實現：一維數組sM ),2.2 棧,二、順序棧 1.棧結構,typedef struct datatype dataMA

3、X; int top; SeqStack;,創(chuàng)建一個棧： SeqStack *s;,2.2 棧,二、順序棧 2.棧的初始化,SeqStack *StackList() /構造一個空棧 SeqStack *s; s=(SeqStack*)malloc(sizeof(SeqStack); s-top=0; /約定top始終指向新數據元素將存放的位置 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、個元素，則入棧和出棧操作時top的值都要變化，在C中參數傳值方式難實現！ 解決辦法： 用增加頭結點方式,2.2 棧,三、鏈棧,.結點定義 typedef struct Node datatype data; struct Node *next; StackNode;,?？? 若有頭結點時top-next=Null為空棧； 若無頭結點時top=Null為空棧,建立一個鏈棧： StackNode *top;,如何判?？眨?2.2 棧,三、鏈棧,2.鏈棧初始化 StackNode *Creat( ) StackNode *top; / 創(chuàng)建頭結點 top= (StackNode *)malloc(s

6、izeof(StackNode); top-next=Null; / 設置頭結點 return top; /返回頭指針 ,2.2 棧,三、鏈棧,3.入棧頭插法 void Push(StackNode *s, datatype x ) StackNode *p; / 創(chuàng)建一個新結點p p= (StackNode *)malloc(sizeof(StackNode); p-data=x; / 設置p結點 p-next=s-next; / p結點加入鏈棧中 s-next=p; /頭結點next指向新的棧頂結點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)建一個新結點p if (s-next=Null ) return 0; /棧空，返回失敗 *x= s-next-data; / 傳回棧頂結點的數據 p=s-next; / p結點指向棧頂結點 s-next=p-next; /頭結點next域指向p下一個結點 free(p); / 釋放p結點刪除棧頂結點 return 1; /返回成功 ,2.2 棧,四、棧的應用,

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

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

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

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

12、遞歸調用是程序設計中很重要的應用。當過程調用子程序時，必須把斷點的信息及地址保存起來，當子過程執(zhí)行完畢返回時，取用這些信息，找到返回地址，從斷點處繼續(xù)執(zhí)行。當程序中出現多重嵌套調用時，必須開辟一個棧，將各層斷點信息依次入棧，當各層子過程返回時，又以相反的次序從棧頂取出，這樣才能保證程序的正常執(zhí)行。,函數的遞歸調用,1. 定義： 在調用一個函數的過程中直接或間接地調用該函數本身。 直接調用 int f(int x) int y,z; . z=f(x); return (2*z); ,f 函數,調用 f函數,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); ,間接調用,特點 是無終止的遞歸調用，因此，應該給定一個限制遞歸次數的條件。,long fac ( int n) long s; if ( n= =1) s=1; else s=n*fac(n-1); return(s); ,例如：寫一函數求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,下 推,回 代,利用棧實現遞歸調用,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); ,回文游戲：順讀與逆讀字符串