數(shù)據(jù)結(jié)構(gòu)--第三章棧和隊(duì)列-文庫(kù)吧資料
2025-01-24 18:51本頁(yè)面
【正文】 r ch。 [ ( [ ] [ ] ) ] [ ( [ ] ) [ ] ] [ ( [ [ 35 括號(hào)匹配算法 : void BracketMatch(char *str) {Stack S。 不正確的格式：［（ ］）或（［］）） 或（［（ ）］ 34 算法的設(shè)計(jì)思想 : 1）凡出現(xiàn) 左括弧 ，則 進(jìn)棧 ； 2）凡出現(xiàn) 右括弧 ，首先檢查棧是否空 若 ?？?，則表明該“ 右括弧 ” 多余 ， 否則和棧頂元素 比較 ， 若相 匹配 ，則“ 左括弧出棧 ” ， 否則表明 不匹配 。 假設(shè)在表達(dá)式中 （［］（））或［（［ ］［ ］）］ 等為正確的格式， ［（ ］）或（［（ ））或 （（）］ ) 均為不正確的格式。 /* 釋放存儲(chǔ)空間 */ return(TRUE)。 *x=tempdata。 if(temp==NULL) /*棧為空 */ return(FALSE)。 } 31 2)鏈棧的出棧操作 int Pop(LinkStack top, StackElementType *x) { /* 將棧 top的棧頂元素彈出 ， 放到 x所指的存儲(chǔ)空間中 */ LinkStackNode * temp。 topnext=temp。 /* 失敗 */ tempdata=x。 temp=(LinkStackNode * ) malloc(sizeof(LinkStackNode))。 }LinkStackNode, *LinkStack。 28 鏈棧的基本操作特點(diǎn) 1）棧底位置固定在鏈表的末尾 pnext=NULL表示 棧底元素 2）入棧： 用入棧元素建立新結(jié)點(diǎn)，并將其插入到鏈表的第一個(gè)結(jié)點(diǎn)之前； (頭插法 ) 3）出棧： 取出鏈表首元素結(jié)點(diǎn)的值，并將其第一個(gè)結(jié)點(diǎn)從鏈表中刪除 ； 4）空棧： topnext=NULL ； 29 鏈棧的存儲(chǔ)結(jié)構(gòu)定義 typedef struct node { StackElementType data。若 topnext=NULL，則代表空棧 。因?yàn)闂５牟迦牒蛣h除操作僅限制在表頭位置進(jìn)行 ，所以鏈表的表 頭指針就作為棧頂指針 。 sssxxx: 321 ssxsxx: 231 ssxxsx:213 sxsxsx: 123 sxssxx:132 26 補(bǔ)充： 如果進(jìn)棧的序列為 123456，能否得到 435612和 135426的出棧序列，并說(shuō)明為什么不能得到或 者如何得到（寫出以‘ S?表示進(jìn)棧 , ?x?表示出棧 的棧操作序列） 二、 鏈棧 鏈棧是采用鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧。 } 25 〖例〗設(shè)有一個(gè)輸入序列 123， 元素經(jīng)過(guò)一個(gè)棧到達(dá)輸出序列，并且元素一旦離開(kāi)輸入序列就不能再回到輸入序列，試問(wèn)經(jīng)過(guò)這個(gè)棧后可以得到多少種輸出序列？ 分析：每一元素只能做一次入棧、一次出棧，可以入棧后停留一段時(shí)間，然后到達(dá)輸出序列。 default: return(FALSE)。 top[1]++。 case 1: if(top[1]==M) return(FALSE)。 top[0]。 } 24 3） 兩棧共享的出棧操作算法 int Pop(int *S, int *x, int i) {switch(i) {case 0: if(top[0]==1) return(FALSE)。 break。 case 1: top[1]。 S[top[0]]=x。 } 23 2） 兩棧共享的進(jìn)棧操作算法 int Push(int *S, int x, int i) { if(top[0]+1==top[1]) /*棧已滿 */ return(FALSE)。 /*全局變量 */ /*top[0]和 top[1]分別為兩個(gè)棧頂指示器 */ 22 兩棧共享基本操作的實(shí)現(xiàn) 1） 兩棧共享的初始化操作算法 void InitStack(int *S) { top[0]=1。 top[0] top[1] Stack： 0 M1 21 兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義 define M 100 StackElementType S [M]。 20 利用棧 “ 棧底位置不變，而棧頂位置動(dòng)態(tài)變化 ” 的特性，為兩個(gè)棧申請(qǐng)一個(gè)共享的一維數(shù)組空間 S[M]，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是 0， M1。 當(dāng)程序中同時(shí)使用幾個(gè)棧時(shí)，如何防止棧的上溢？ 5. 順序棧上溢的解決方法 方法二 ： 使用兩個(gè)（或多個(gè)）棧共享存儲(chǔ)空間辦法 。 return(TRUE)。 } } 15 6） 取棧頂元素 int GetTop（ int *S, int *x） { /* 將棧 S的棧頂元素取出 ， 放入 x所指的單元 ， 但棧頂指針保持不變 */ if(top==1) /*棧為空 */ return(FALSE)。 top。 } 14 5）出棧 int Pop(int * S, int *x) {
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1