數(shù)據(jù)結(jié)構(gòu)線性表ppt課件-在線瀏覽
2025-06-16 02:43本頁(yè)面
【正文】 空 e = *()。 } //GetTop 取棧頂元素操作算法 棧 第 19 頁(yè) 5） 進(jìn)棧操作 Push ( SqStack amp。 100 99 n n1 n2 1 0 an an1 a2 a1 e進(jìn)棧前 e進(jìn)棧后 100 99 n n1 n2 1 0 e an an1 a2 a1 棧 第 20 頁(yè) 進(jìn)棧操作算法 Status Push ( SqStack amp。 if ( ! S. base ) exit(OVERFLOW)。 += STACKINCREMENT。 //元素 e 插入棧頂，后修改棧頂指針 return OK。S, ElemType amp。 棧 e an 出棧操作后 100 99 n n1 n2 1 0 an1 a2 a1 第 22 頁(yè) Status Pop ( SqStack amp。e ) { if ( == ) return ERROR。 // 。 return OK。 棧頂 棧底 在前面學(xué)習(xí)了線性鏈表的插入、刪除操作算法，不難寫出鏈?zhǔn)綏３跏蓟?、進(jìn)棧、出棧等操作的算法 。 2+3*(54)=5 棧的應(yīng)用舉例－表達(dá)式求值 棧的應(yīng)用舉例 第 26 頁(yè) 2）表達(dá)式的構(gòu)成 操作數(shù) +運(yùn)算符 +界符 1 2 3 4 如何確定運(yùn)算符的運(yùn)算順序？ 常數(shù) +、 、 *、 / ( )、 棧的應(yīng)用舉例 3）表達(dá)式的求值： 例： 5+6?(1+2)4 按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為： 5+6?(1+2)4 = 5+6?34 = 5+184 = 234 = 19 第 27 頁(yè) 4）算符優(yōu)先關(guān)系表 表達(dá)式中任何相鄰運(yùn)算符 ? ?2 的優(yōu)先關(guān)系有： ?1 ?2： ?1的優(yōu)先級(jí) 低于 ?2 ?1 = ?2： ?1的優(yōu)先級(jí) 等于 ?2 ?1 ?2： ?1的優(yōu)先級(jí) 高于 ?2 + θ2 θ1 * / ( ) + * / ( ) = = 注： θ θ 2是相鄰算符， θ 1在左， θ 2在右 棧的應(yīng)用舉例 第 28 頁(yè) 5）算符優(yōu)先算法 從左向右掃描表達(dá)式： 遇操作數(shù) —— 保存； 遇運(yùn)算符號(hào) ?j—— 與前面的剛掃描過(guò)的運(yùn)算符 ?i比較： 若 ?i?j 則保存 ?j（ 因此已保存的運(yùn)算符的優(yōu)先關(guān)系為?1?2?3?4… ） 若 ?i?j 則說(shuō)明 ?i是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算 若 ?i=?j 則說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào) 5 + 4 ? (1 + 2) 6 后面也許有優(yōu)先級(jí)更高的算符 + ? + ( 后保存的算符優(yōu)先級(jí)高 用兩個(gè)棧分別保存掃描過(guò)程中 遇到的操作數(shù)和運(yùn)算符 棧的應(yīng)用舉例 第 29 頁(yè) 在算符優(yōu)先算法中，建立了兩個(gè)工作棧。 算法的基本思想是： 首先置操作數(shù)棧為空棧，表達(dá)式起始符“ ” 為運(yùn)算符棧的棧底元素。 直至整個(gè)表達(dá)式求值完畢（即 OPTR棧的棧頂元素和當(dāng)前讀入的字符均為 “ ” ）。設(shè) OPTR和 OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧， OP為運(yùn)算符、界限符集合。 Push (OPTR, )。 c=getchar( )。 c=getchar( )。 c=getchar( )。 case =: // 脫括號(hào)并接收下一字符 Pop(OPTR, x)。 break。 Pop ( OPND, b)。 Push ( OPND, Operate(a, theta, b) )。 } //switch } //while return GetTop(OPND)。 遞歸定義：簡(jiǎn)單說(shuō)，一個(gè)用自己定義自己的概念，稱為遞歸定義。 棧與遞歸 第 34 頁(yè) 隊(duì)列的概念 一、什么是隊(duì)列 隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表。 稱插入操作為入隊(duì)，刪除操作為出隊(duì)。Q) 功能：構(gòu)造一個(gè)空隊(duì)列 Q。Q) 功能：銷毀已存在隊(duì)列 Q。Q) 功能： 將隊(duì)列 Q置為空隊(duì)列。Q,amp。 5） 取隊(duì)頭元素操作 GetHead(Q,amp。 隊(duì)列 第 37 頁(yè) 二、隊(duì)列的基本操作 6） 入隊(duì)操作 EnQueue(amp。 7）判空操作 QueueEmpty(Q) 功能：若隊(duì)列 Q為空，則返回 True， 否則返回False。 //初始化時(shí)分配 存儲(chǔ)空間的基址 int front。 //隊(duì)尾指針，指向隊(duì)尾元素的下一個(gè)位置 }SqQueue。rear指 向 隊(duì)尾元素 的下一個(gè)位置 ； front指 向 隊(duì)頭元素 。 出隊(duì)列： e =[ front++ ]。 rear 1 2 3 4 5 0 J4,J5,J6入隊(duì) J4 J5 J6 front 0 M1 1 f
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1