數(shù)據(jù)結(jié)構(gòu)--第三章棧和隊(duì)列-在線瀏覽
2025-03-07 18:51本頁(yè)面
【正文】 2,3 1003H top=1000H 1 top=1001H top=1002H 2 3top=1003H 45 輸出序列： 〖 例 〗在一個(gè) n個(gè)單元的順序棧中，假定以地址高端 (下標(biāo)為 n1的單元 )作為棧底，則向棧中壓入一個(gè)元素時(shí)，棧頂指針 top的變化是 ______ top 不變 top=n top=top1 top=top+1 棧低 棧頂 top=1 n1 n2 … 1 0 〖 例 〗若一個(gè)棧的輸入序列是 1， 2， … ， n， 輸出序列的第一個(gè)元素是 n， 則第 i個(gè)輸出元素是______ ni ni+1 i ni1 top=1 n n1 … 1 2 top=n1 方法一 ： 將棧的容量加到足夠大，但這種方法由于事先難以估計(jì)容量，有可能浪費(fèi)空間。 兩棧的棧底分別設(shè)在給定存儲(chǔ)空間的兩端，然后各自向中間伸延， 當(dāng)兩棧的棧頂相遇時(shí)才可能發(fā)生溢出。 共享?xiàng)５目臻g示意為： top[0]和 top[1]分別為兩個(gè)棧頂指示器 。 int top[2]。 top[1]=M。 switch(i) {case 0: top[0]++。 break。 S[top[1]]=x。 default: return(FALSE) } return(TRUE)。 *x=S[top[0]]。 break。 *x=S[top[1]]。break。 } return(TRUE)。那么該題就變?yōu)?如何安排三次 push操作（ s）和pop操作 (x)的順序 以得到盡量多的不同的輸出 。為便于操作，采用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧。 鏈棧的示意圖為： ∧ a1 … an1 an top top為棧頂指針，始終指向當(dāng)前棧頂元素前面的頭結(jié)點(diǎn)。 注意： 鏈棧在使用完畢時(shí)，應(yīng)該釋放其空間。 struct node *next。 30 鏈棧基本操作的實(shí)現(xiàn) 1)鏈棧的進(jìn)棧操作 int Push(LinkStack top, StackElementType x) /* 將數(shù)據(jù)元素 x壓入棧 top中 */ { LinkStackNode * temp。/*申請(qǐng)空間 */ if(temp==NULL) return(FALSE)。 /* 構(gòu)造結(jié)點(diǎn) */ tempnext=topnext。 /* 修改當(dāng)前棧頂指針 */ return(TRUE)。 temp=topnext。 topnext=tempnext。 free(temp)。 } 32 棧的應(yīng)用舉例 例 括號(hào)匹配的檢驗(yàn) 則 檢驗(yàn)括號(hào)是否匹配 可用棧來(lái)實(shí)現(xiàn)。 33 分析可能出現(xiàn)的 不匹配 的情況 : 1) 到來(lái)的右括弧 并非是所“期待” 的； 2) 到來(lái)的是 “不速之客” ； 3)直到結(jié)束，也沒(méi)有到來(lái) 所“期待” 的括弧。 3）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若 ?？?，則表明表達(dá)式中 匹配正確 ， 否則表明“ 左括弧 ” 有余 。 int i。 InitStack(amp。 For(i=0。\039。(39。[39。{39。S,str[i])。 case 39。: case 39。: case 39。: if(IsEmpty(S)) { printf(\n 右 括 號(hào) 多 余 !)。} else {GetTop (amp。ch)。S,amp。 else { printf(\n對(duì)應(yīng)的左右括號(hào)不同類(lèi) !)。} } }/*switch*/ }/*for*/ if(IsEmpty(S)) printf(\n括號(hào)匹配 !)。 } 36 例 數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d) d + N mod d 計(jì)算順序 輸出順序 例如：（ 1348)10 = (2504)8 ， 其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 37 ? 十進(jìn)制轉(zhuǎn)換為二進(jìn)制（例如： 25） ? 有 余 數(shù) 是 1 沒(méi) 余 數(shù) 是 0 ? 25除 2=12......1 ? 12除 2=6 ...... 0 ? 6 除 2=3 ...... 0 ? 3 除 2=1 ...... 1 ? 1 除 2=0 ...... 1 ? 然后我們將余數(shù)按“從下往上 ”的順序書(shū)寫(xiě)就是： 11001，那么這個(gè) 11001就是十進(jìn)制25的二進(jìn)制形式 top 1 1 1 0 0 top top 出棧： top top top top 數(shù)制轉(zhuǎn)換算法 void Conversion(int N) /*對(duì)任意非負(fù)十進(jìn)制數(shù) N， 打印等值的八進(jìn)制數(shù) */ { Stack S。 /*S為順序?；蜴湕?*/ InitStack(amp。 while
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1