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