數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列(編輯修改稿)
2024-11-30 22:17 本頁面
【文章內(nèi)容簡介】 i=0。 !Stack_Empty(S)。 i++) oct[i]=Stack_Pop(S)。 /* 先出棧者是高位，最后是個(gè)位 */ } (2)表達(dá)式求值的算法 在表達(dá)式中存在多個(gè)算符優(yōu)先級(jí)和括號(hào)優(yōu)先級(jí)，所以，在運(yùn)算中要解決優(yōu)先級(jí)后才能進(jìn)行運(yùn)算。優(yōu)先級(jí)的順序是： (1)括號(hào)的優(yōu)先級(jí)最高，對(duì)括號(hào)內(nèi)的各種運(yùn)算符有：先乘除，再加減，同級(jí)運(yùn)算從左至右。 (2)先括號(hào)內(nèi)，后括號(hào)外，多層括號(hào)，由內(nèi)向外。 在每一個(gè)運(yùn)算步，相鄰的算符 c1和 c2之間的關(guān)系是下面三種情況之一 (c1出現(xiàn)在 c2之前 )。 c1c2 c1的優(yōu)先級(jí)低于 c2 c1=c2 c1的優(yōu)先級(jí)等于 c2 c1c2 c1的優(yōu)先級(jí)大于 c2 運(yùn)算符有算術(shù)運(yùn)算符、左右括號(hào)、算式結(jié)束符。 表 定義了算符之間的優(yōu)先關(guān)系。 注意：“ ”為優(yōu)先級(jí)最低的算符，是表達(dá)式結(jié)束符，為算法簡潔，在表達(dá)式最左邊也虛設(shè)一個(gè)“ ”構(gòu)成整個(gè)表達(dá)式的一對(duì)括號(hào)，當(dāng)“ ”=“”表示整個(gè)表達(dá)式求值完畢 。 算法的基本思想 是： (a)定義一個(gè)存放算符棧 OPTR和存放數(shù)據(jù)棧 OPND。 (b) 首先置數(shù)據(jù)棧為空棧，表達(dá)式起始符“ ”為算符棧的棧底元素。 (c) 自左向右掃描表達(dá)式，讀到操作數(shù)進(jìn) OPND棧，讀到運(yùn)算符，則和 OPTR棧頂元素比較 (棧頂元素為 c1，讀到的算符為 c2)；若 c1c2，則 c2進(jìn)棧繼續(xù)掃描后面表達(dá)式；若是 c1 =c2，則“（” =“）”，即括號(hào)內(nèi)運(yùn)算已經(jīng)結(jié)束，將“ c1 ”出棧，并且“ c2”放棄，繼續(xù)掃描。若 c1 c2，則將 c1 出棧，并在操作數(shù)棧取出兩個(gè)元素 a和 b按 c1做運(yùn)算，運(yùn)算結(jié)果進(jìn) OPND。重復(fù)直到表達(dá)式求值完畢 (OPTR棧為空棧 )。 按上面的說明，可將隊(duì)列中插入元素的操作描述為： if (qrear == MAXSIZE 1) printf(″queue full″)。 else { qrear ++。 qdata［ qrear］ = x 。 } 隊(duì)列中刪除元素的操作描述為： if (qfront == q rear) printf (″queue empty″)。 else qfront++。 上面的順序隊(duì)列在操作中存在著如下問題：例如當(dāng) qfront = qrear = 4時(shí)，隊(duì)列為空，但插入新元素只能從當(dāng)前 rear指針指向的位置開始插入，前面 的單元無法利用。更有甚者，當(dāng) qrear = MAXSIZE 1時(shí)，隊(duì)滿條件出現(xiàn)，不能再插入新元素，但當(dāng)前隊(duì)列可能并不滿，而是假滿現(xiàn)象。又如當(dāng) qfront = qrear = MAXSIZE 1 時(shí)，雖為隊(duì)空，但不能再插入新元素，要做一次隊(duì)列置空操作后才能工作。產(chǎn)生這些現(xiàn)象的原因是被刪除元素的空間在該元素刪除以后就永遠(yuǎn)使用不到了。解決這一問題的常用方法是：將向量 qdata從邏輯上構(gòu)筑成一個(gè)頭尾相接的圓環(huán)，即 qdata［ 0］接在 qdata［ MAXSIZE 1］之后，并將這種邏輯含義下的向量稱為循環(huán)向量，此隊(duì)列稱為循環(huán)隊(duì)列，如圖 。循環(huán)隊(duì)列仍然是順序隊(duì)列結(jié)構(gòu)，只是邏輯上和前面的順序隊(duì)列有所不同。 算符 棧內(nèi)優(yōu)先級(jí) 棧外優(yōu)先級(jí) “ *”“ /” 4 3 “ +”“ ” 2 1 “ (” 0 5 “ )” 5 0 “ ” 1 1 為使兩個(gè)算符比較方便，給算符設(shè)置優(yōu)先級(jí)如表 。其中 c1 為棧內(nèi)元素， c2為棧外元素。算符比較算法如下 ： 表 算符優(yōu)先級(jí)設(shè)置 算法 算符比較算法。 char Precede(char c1,char c2) { char c_temp1, c_temp2。 switch (c1) {case ’*’ : case ’/’ :c_temp1=4。 break。 case ’+’ : case ’’ :c_temp1=2。 break。 case ’(’ :c_temp1=0。 break。 case ’)’ :c_temp1=5。 break。 case ’’ :c_temp1=1。 } switch (c2) { case ’*’ : case ’/’ :c_temp2=3。 break。 case ’+’ : case ’’ :c_temp2=1。 break。 case ’(’ :c_temp2=5。 break。 case ’)’ :c_temp2=0。 break。 case ’’ :c_temp2=1。 } if (c_temp1c_temp2) return(’’)。 if (c_temp1=c_temp2) return(’+’)。 if (c_temp1c_temp2) return(’’)。 } ? 算法 表達(dá)式求值算法。 int express( ) { Stack_Init(OPTR)； Stack_Push(OPTR, ’’)’。 /* 運(yùn)算符棧 */ Stack_Init(OPND)； /* 運(yùn)算數(shù)棧 */ w=getchar()。 while(w!= ’’|| Stack_GetTop(OPTR)!= ’’) /* ’’是表達(dá)式結(jié)束的標(biāo)記，也是運(yùn)算符棧為空的標(biāo)記 */ { if(!In(w,OP)) { Stack_Push(OPND,w)。w=getchar()。} /* 不是運(yùn)算符的情況 else /* 判斷運(yùn)算符棧頂元素和新輸入運(yùn)算符的優(yōu)先權(quán) */ switch(Precede(Stack_GetTop(OPTR),w)) { case ’’ : /* 棧頂元素優(yōu)先權(quán)低 */ Stack_Push(OPTR,w)。 w=getchar()。 break。 case ’=’ : /* 左右括號(hào)的優(yōu)先權(quán)相同，去掉括號(hào)并接收下一個(gè)字符 */ x=Stack_Pop(OPTR)。 w=getchar()。 break。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1