數(shù)據(jù)結(jié)構(gòu)之棧對(duì)列串課件-文庫吧
2025-07-28 09:01 本頁面
【正文】 t STACK 2. 堆棧在 表達(dá)式計(jì)算 中的應(yīng)用 ?后綴表示法（逆波蘭表示法） ? ab+， abc*+， ab+c*， …… ? 逆波蘭表達(dá)式的特點(diǎn)：無括號(hào)，形式簡(jiǎn)潔，運(yùn)算符的順序與運(yùn)算順序相同。 ? 由于逆波蘭表示法以上特點(diǎn)，其處理很方便。建立一個(gè)棧，對(duì)逆波蘭表達(dá)式從左到右掃描，遇到運(yùn)算分量則進(jìn)棧，遇到運(yùn)算符號(hào)則取其棧頂元素（二目或一目）運(yùn)算，并把結(jié)果進(jìn)棧。 ?例：求 –B*（ C+D）的值。 ( 其逆波蘭表示： B@CD+* ) ? 把進(jìn)制的數(shù) n轉(zhuǎn)換成八進(jìn)制的數(shù) r。 1. n除以 r, 商為 S, 輸出余數(shù)。 2. 若 s=0，則結(jié)束，輸出序列的逆就是轉(zhuǎn) 換后的結(jié)果。 3. n:=s, 轉(zhuǎn) 1. 例：把進(jìn)制的數(shù) 355轉(zhuǎn)換成八進(jìn)制的數(shù)。 ?基本思想：若遇見左括號(hào)，則進(jìn)棧；若右括號(hào)，則退棧，并比較是否匹配。 ?假設(shè)下列形式都是合法的： （）， [ ]，（ [ ]），（ [ ] [ ]），（ [（） ]）； 而下列是不合法的： （ ]， [），（ [ ] ]， …… 棧與遞歸 ?遞歸：自己調(diào)用自己，分直接遞歸和間接遞歸 ?例：階乘 n!=1 當(dāng) n=0時(shí) n!=n*(n1)! 當(dāng) n0時(shí) 定義遞歸時(shí)要做到： 1. 調(diào)用必須越來越簡(jiǎn)單，并且能在有限步內(nèi)結(jié)束。 2. 調(diào)用到最后一步時(shí)，必須有非遞歸的確切的定 義。 ?求 n!的遞歸算法： Int fact(n) { if(n==0) Return(1)。 Else return(n*fact(n1))。 } 遞歸的執(zhí)行 調(diào)用時(shí)做以下工作： 等； ； 。 返回時(shí)做以下工作： 。 。 。 例：階乘 Int fact(int n) { if (n==0) return(1)。 Else return(n*fact(n1))。 } Fact(n) { Top=1。 m=n。 While(m1) { S[top]=m。 m=m1 top=top+1。 } R=1。 While(top1) { Top=top1。 R= R * s[top]。 } } 斐波那契（ Fibonacci)數(shù)的定義 。 希爾波特（ ,1891)曲線的定義； 塞平斯基（ Sierpinski)曲線的定義； Hanoi塔穩(wěn)問題； 中斷處理問題； …… 隊(duì)列（ Queue） ?隊(duì)列是一種運(yùn)算受限制的線性表，元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行。 ?允許添加元素的一端稱為隊(duì)尾（ Rear）；允許刪除元素的一端稱為隊(duì)頭（ Front）。 ?向隊(duì)列添加元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。 ?新入隊(duì)的元素只能添加在隊(duì)尾，出隊(duì)的元素只能是刪除隊(duì)頭的元素，隊(duì)列的特點(diǎn)是先進(jìn)入隊(duì)列的元素先出隊(duì)，所以隊(duì)列也稱作先進(jìn)先出表或 FIFO（ FirstInFirstOut）表。 隊(duì)列的表示 ?與堆棧類似，隊(duì)列也可以簡(jiǎn)單的用一維數(shù)組表示。 ?設(shè)數(shù)組名為 Queue，其下標(biāo)下界為 1，上界為 n。 ?一般使用一個(gè)變量 r指示隊(duì)尾的下標(biāo)值，叫做隊(duì)尾指針；用另一個(gè)變量 f 指示隊(duì)頭的下標(biāo)值，稱為隊(duì)頭指針。 ?隊(duì)列中元素的數(shù)目等于零稱為空隊(duì)列。 ?對(duì)列的順序存儲(chǔ)結(jié)構(gòu) 假定有 A～ F 6個(gè)元素先后進(jìn)入隊(duì)列，但 A、B,C三個(gè)元素已出隊(duì)了，故隊(duì)尾指針 r=6，而隊(duì)頭指針 f=3。 A B C D E F 1 2 3 4 5 6 …………………… n QU EUE f r 對(duì)列的形式定義 define maxsize 允許數(shù)組元素的最大個(gè)數(shù) Typedef struct { elementtype elements[maxsize]。 Int front。 Int rear。 }quetype。 ?插入操作 若 maxsize1。 /*對(duì)列不滿 */ 則插入： ++: /*插入 */ []=x。 ?刪除操作 若 /*對(duì)列非空 */ 則刪除： ++。 /*刪除 */ return([]) 1. 入隊(duì)（ insert） ?當(dāng)給隊(duì)列插入元素時(shí)，隊(duì)尾指針 r后移而隊(duì)頭指針不動(dòng)，但有一個(gè)情況例外，即當(dāng)向空隊(duì)列插入第一個(gè)元素時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)由 0變?yōu)?1。 ?設(shè)用下標(biāo)從 1到 n的數(shù)組 Q表示隊(duì)列，且已知待添加的元素在變量 x中。 入隊(duì)函數(shù) void insert (Q, int n, front, rear, x) { if ( == n1) printf(“溢出 !\n”)。 /*判斷是否已到數(shù)組末端 */ else { ++。 []=x。 /*插入元素 */ } } 2. 出隊(duì)（ Delete） ?當(dāng)從隊(duì)列刪除元素時(shí)，隊(duì)頭指針 f后移而隊(duì)尾指針 r不動(dòng)，但也有一個(gè)情況例外，即當(dāng)刪除了最后一個(gè)元素，隊(duì)列成為了空隊(duì)列時(shí)，隊(duì)頭指針與隊(duì)尾指針同時(shí)變?yōu)?0。 ?假設(shè)要求將出隊(duì)的元素值賦給變量 x 。 出隊(duì)函數(shù) void Delete (Q, int front, rear, n, x) { if (Qfront==) printf(“下溢出 !\n”)。 /*判斷是否為空隊(duì)列 */ else { ++: x=Q. elements[]。 /*取隊(duì)頭元素給 x賦值 */ if (==) {==0 /*置成空對(duì)列 } } } “假溢出”問題 ?在插入時(shí)，由條件 =maxsize1, 判斷對(duì)列是否滿， 在刪除時(shí)，由條件 =, 判斷對(duì)列是否
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1