【正文】 4 棧的順序表示和實(shí)現(xiàn) 順序（堆）棧 順序存儲(chǔ)結(jié)構(gòu)的堆棧。用 C語(yǔ)言定義： typedef struct { DataType stack[MaxStackSize]。 }SeqStack。 棧為空 的條件 ： base=top。 a0 a1 …… an1 順序棧 S ai …… 低地址 高地址 an 棧底 base 棧頂 top 入棧 口訣：堆棧指針 top “先壓后加” : S[top++]=an 出棧 口訣：堆棧指針 top “先減后彈” : e=S[top] 順序棧的操作實(shí)現(xiàn) (1)初始化棧 void StackInitiate(SeqStack *S) /*初始化順序堆棧 S*/ { Stop = 0。 else return 1。 return 0。 Stop ++。 } } (4)出棧 int StackPop(SeqStack *S, DataType *d) /*彈出順序堆棧 S的棧頂數(shù)據(jù)元素值到參數(shù) d ，出棧成功則返回 1，否則返回 0*/ { if(Stop = 0) { printf(堆棧已空無(wú)數(shù)據(jù)元素出棧 ! \n)。 } else { Stop 。 return 1。 return 0。 return 1。 Stop ++。 *d = Sstack[Stop]。 改進(jìn)的順序棧結(jié)構(gòu) define STACK_INIT_SIZE 100 define STACKINCREMENT 10 Typedef struct{ datatype *base, *top。 } SqStack。 struct snode * next。 棧底 h a 0 a 1 a n 頭結(jié)點(diǎn) next data 棧頂 棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 鏈?zhǔn)蕉褩５牟僮鲗?shí)現(xiàn) (1) 入棧 int StackPush(LSNode *head, DataType x) { LSNode *p。 return 0。 pnext = headnext。 /*新結(jié)點(diǎn)成為新的棧頂 */ return 1。 if(p == NULL) { printf(堆棧已空出錯(cuò)！ )。 } headnext = pnext。 /*原棧頂結(jié)點(diǎn)元素賦予 d*/ free(p)。 } 注： 由此可以看出：一個(gè)鏈棧由其 棧頂指針唯一指定 設(shè) head指向棧頂元素，則 head=NULL 表示?？? 1) 在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大，棧頂（表頭）操作頻繁， 可不設(shè)頭結(jié)點(diǎn) 鏈棧。 3) 鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成 。 幾點(diǎn)說(shuō)明 : 由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。 十進(jìn)制 N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題 ,其解決方法很多 ,其中一個(gè)簡(jiǎn)單算法基于下列原理 : N=(N div d)*d+N mod d (其中 :div為整除運(yùn)算 ,mod為求余運(yùn)算） 棧的應(yīng)用舉例 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計(jì)算順序 從低到高 輸出順序 從高到低 例如：（ 1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下： 十進(jìn)制數(shù) N和 d進(jìn)制數(shù)之間轉(zhuǎn)換的算法原理： N=( N / d ) * d + N % d 即 an1 a1 a0 … top N % d N / d ? N 1122110 ?? ???????? nn dadadaaN ?void conversion( ) { initstack(S)。 while(n){ push(S,n%8)。 } while(! Stackempty(S)){ pop(S,e)。 } } 2 5 0 4 棧 s N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 假設(shè)在表達(dá)式中 （［］（））或［（［ ］［ ］）］ 等為 正確 的格式， ［（ ］）或（［（ ））或 （（）］） 均為 不正確 的格式。在檢驗(yàn)過(guò)程中，若遇到以下幾種情況之一，就可以得出括號(hào)不匹配的結(jié)論。 例如：考慮下列括號(hào)序列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 [ ( [ ?回文游戲：順讀與逆讀字符串一樣（不含空格） d a d top （原串） 若不等，非回文 若直到棧空都相等，回文 字符串：“ madam im adam” 如何實(shí)現(xiàn)行編輯程序？ “每接受一個(gè)字符即存入存儲(chǔ)器 ” ? 并不恰當(dāng)！ 合理的作法是：設(shè)立一個(gè) 輸入緩沖區(qū) ，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū) ，并假設(shè)“ ”為退格符，“ ”為退行符。 假設(shè)從終端接受了這樣兩行字符： whliilre（ s*s) outchaputchar(*s=++)。 行編輯程序算法如下 : void LineEdit( ){ initstack(s)。 while(ch!=eof){ while(ch!=eof amp。 ch!=?\n?){//EOF為全文結(jié)束符 switch(ch){ case ?? : pop(s,c)。 // 重置 S為空棧 default : push(s,ch)。 // 從終端接收下一個(gè)字符 } //將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)； clearstack(s)。 } destroystack(s)。 ｝ while (棧不空）； 否則 { Typedef struct{ Int ord。//通道塊在迷宮的“坐標(biāo)位置” Int di。//棧的元素類型 Status MazePath(MazeType maze,PosType start,PosType end){ InitStack(S)。//設(shè)置“當(dāng)前位置”為“入口位置” Curstep=1。//留下足跡 e=(curstep,curpos,1)。//加入路徑 If(curpos==end) return (TRUE)。//下一位置是當(dāng)前位置的東鄰 Curstep++。 While(==4 amp。 !StackEmpty(S)){ MarkPrint()。//留下不能通過(guò)的標(biāo)記，并退回一步 } If(4){ ++。//換下一個(gè)方向搜索 curpos=NextPos( )。 Return(FALSE)。直到滿足要求。 解決思路： 順序棧 S用來(lái)存放放入背包內(nèi)的物品序號(hào)（最多有 n個(gè)元素）； 參數(shù) T動(dòng)態(tài)計(jì)算背包還可裝入的重量； 依次裝入試驗(yàn)，不滿足時(shí)從后往前回溯。 ? 算術(shù)表達(dá)式有三種表示： ? 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B； ? 前綴 (prefix)表示 操作符 操作數(shù) 操作數(shù) ， 如 +AB； ? 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 表達(dá)式的中綴表示 a + b * ( c d ) e ^ f / g ? 表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋? ? 優(yōu)先級(jí)高的先計(jì)算 ； ? 優(yōu)先級(jí)相同的自左向右計(jì)算 ； ? 當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算 。 ? 在后綴表達(dá)式的計(jì)算順序中已 隱含了加括號(hào)的優(yōu)先次序 ， 括號(hào)在后綴表達(dá)式中不出現(xiàn) 。 ? 當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。 ? 為了實(shí)現(xiàn)這種轉(zhuǎn)換 ， 需要考慮各操作符的優(yōu)先級(jí) 。 ? 操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在 括號(hào)配對(duì) 或 棧底的 “ ?！碧?hào)配對(duì) 時(shí) 。 ( ^ * , / , % + , )i s p ( 棧內(nèi) ) 0 1 7 5 3 8i c p ( 棧外 ) 0 8 6 4 2 1中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法 ? 操作符棧初始化 ， 將結(jié)束符 ‘ 。然后讀入中綴表達(dá)式字符流的首字符 ch。?， 同時(shí)棧頂?shù)牟僮鞣彩?‘ 。 ? 若 ch是 操作數(shù) 直接輸出 ， 讀入下一個(gè)字符 ch。 ? 若 icp (ch) isp (op)， 退棧并輸出 。 ? 算法結(jié)束，輸出序列即為所需的后綴表達(dá)式?！?(2) 從頭掃描中綴表達(dá)式 ， 取一字符送入 ch。” 時(shí) , 執(zhí)行以下工作 , 否則結(jié)束算法 。 ① 若 ch是 操作數(shù) ， 進(jìn) OPND棧 ， 從中綴表達(dá)式取下一字符送入 ch； ② 若 ch是 操作符 ， 比較 icp(ch)的優(yōu)先級(jí)和 isp(OPTR)的優(yōu)先級(jí)： ? 若 icp(ch) isp(OPTR)， 則 ch進(jìn) OPTR棧 ， 從中綴表達(dá)式取下一字符送入 ch； ? 若 icp(ch) isp(OPTR)， 則從 OPND棧退出 a2和 a1， 從 OPTR棧 退出 θ, 形成運(yùn)算指令 (a1)θ(a2)， 結(jié)果進(jìn) OPND棧 ； ? 若 icp(ch) == isp(OPTR) 且 ch == “)”，則從 OPTR棧 退出棧頂?shù)?“ (”， 對(duì)消括號(hào) ， 然后從中綴表達(dá)式取下一字符送入ch； 以表達(dá)式 ＃ A*B + C/D＃ 為例說(shuō)明利用棧的求值過(guò)程。Push(OPTR,??)。 c=getchar()。c=getchar()。c=getchar()。 Case ?=?: //脫括號(hào)接收下一字符 Pop(OPTR,x)。break。 Pop(OPND,b)。 Push(OPND,Operate(a,theta,b))。 } } return GetTop(OPND)。 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)： 棧與函數(shù)調(diào)用機(jī)制 ? 保存 被調(diào)函數(shù)的 計(jì)算結(jié)果 ； ? 釋放 被調(diào)函數(shù)的 數(shù)據(jù)區(qū) ； ? 依照被調(diào)函數(shù)保存的返回地址將 控制轉(zhuǎn)移 到 調(diào)用函數(shù) 。 … }//main Main的數(shù)據(jù)區(qū) 函數(shù) a的數(shù)據(jù)區(qū) 函數(shù) b的數(shù)據(jù)區(qū) void a( ){ … b( )。 ?遞歸算法： 描述遞歸定義的函數(shù)或求解遞歸問(wèn)題的過(guò)程稱為遞歸算法。 棧結(jié)構(gòu)與遞歸函數(shù) 遞歸算法優(yōu)缺點(diǎn)： ?優(yōu)點(diǎn)：結(jié)構(gòu)清晰，易讀，在高級(jí)語(yǔ)言中，由系統(tǒng)管理堆棧，用戶編程調(diào)試方便。 遞歸工作棧： 整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。 當(dāng)前環(huán)境指針： 活動(dòng)記錄的棧頂指針。包括 實(shí)在參數(shù) 、所有 局部變量 以及上一層的 返回地址 。 遞歸函數(shù) int f(x) int x。 ….. z=f(x)。 } f函數(shù) 調(diào)用 f函數(shù) ?直接調(diào)用 int f1(x) int x。 ….. z=f2( y)。