數(shù)據(jù)結(jié)構(gòu)--第三章棧和隊列(編輯修改稿)
2025-02-14 18:51 本頁面
【文章內(nèi)容簡介】 結(jié)點從鏈表中刪除 ； 4）空棧： topnext=NULL ； 29 鏈棧的存儲結(jié)構(gòu)定義 typedef struct node { StackElementType data。 struct node *next。 }LinkStackNode, *LinkStack。 30 鏈棧基本操作的實現(xiàn) 1)鏈棧的進棧操作 int Push(LinkStack top, StackElementType x) /* 將數(shù)據(jù)元素 x壓入棧 top中 */ { LinkStackNode * temp。 temp=(LinkStackNode * ) malloc(sizeof(LinkStackNode))。/*申請空間 */ if(temp==NULL) return(FALSE)。 /* 失敗 */ tempdata=x。 /* 構(gòu)造結(jié)點 */ tempnext=topnext。 topnext=temp。 /* 修改當(dāng)前棧頂指針 */ return(TRUE)。 } 31 2)鏈棧的出棧操作 int Pop(LinkStack top, StackElementType *x) { /* 將棧 top的棧頂元素彈出 ， 放到 x所指的存儲空間中 */ LinkStackNode * temp。 temp=topnext。 if(temp==NULL) /*棧為空 */ return(FALSE)。 topnext=tempnext。 *x=tempdata。 free(temp)。 /* 釋放存儲空間 */ return(TRUE)。 } 32 棧的應(yīng)用舉例 例 括號匹配的檢驗 則 檢驗括號是否匹配 可用棧來實現(xiàn)。 假設(shè)在表達式中 （［］（））或［（［ ］［ ］）］ 等為正確的格式， ［（ ］）或（［（ ））或 （（）］ ) 均為不正確的格式。 33 分析可能出現(xiàn)的 不匹配 的情況 : 1) 到來的右括弧 并非是所“期待” 的； 2) 到來的是 “不速之客” ； 3)直到結(jié)束，也沒有到來 所“期待” 的括弧。 不正確的格式：［（ ］）或（［］）） 或（［（ ）］ 34 算法的設(shè)計思想 : 1）凡出現(xiàn) 左括弧 ，則 進棧 ； 2）凡出現(xiàn) 右括弧 ，首先檢查棧是否空 若 ?？?，則表明該“ 右括弧 ” 多余 ， 否則和棧頂元素 比較 ， 若相 匹配 ，則“ 左括弧出棧 ” ， 否則表明 不匹配 。 3）表達式檢驗結(jié)束時， 若 棧空 ，則表明表達式中 匹配正確 ， 否則表明“ 左括弧 ” 有余 。 [ ( [ ] [ ] ) ] [ ( [ ] ) [ ] ] [ ( [ [ 35 括號匹配算法 : void BracketMatch(char *str) {Stack S。 int i。 char ch。 InitStack(amp。S)。 For(i=0。 str[i]!=39。\039。 i++) {switch(str[i]) {case 39。(39。: case 39。[39。: case 39。{39。: Push(amp。S,str[i])。 break。 case 39。)39。: case 39。]39。: case 39。}39。: if(IsEmpty(S)) { printf(\n 右 括 號 多 余 !)。 return。} else {GetTop (amp。S,amp。ch)。 if(Match(ch,str[i])) Pop(amp。S,amp。ch)。 else { printf(\n對應(yīng)的左右括號不同類 !)。 return。} } }/*switch*/ }/*for*/ if(IsEmpty(S)) printf(\n括號匹配 !)。 else printf(\n左括號多余 !)。 } 36 例 數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d) d + N mod d 計算順序 輸出順序 例如：（ 1348)10 = (2504)8 ， 其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 37 ? 十進制轉(zhuǎn)換為二進制（例如： 25） ? 有 余 數(shù) 是 1 沒 余 數(shù) 是 0 ? 25除 2=12......1 ? 12除 2=6 ...... 0 ? 6 除 2=3 ...... 0 ? 3 除 2=1 ...... 1 ? 1 除 2=0 ...... 1 ? 然后我們將余數(shù)按“從下往上 ”的順序書寫就是： 11001，那么這個
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1