數(shù)據(jù)結(jié)構(gòu)線性表ppt課件-文庫吧資料
2025-05-05 02:43本頁面
【正文】 先進先出 第一個入隊的元素在隊頭 最后一個入隊的元素在隊尾 第一個出隊的元素為隊頭元素 最后一個出隊的元素為隊尾元素 出隊列 隊列 第 36 頁 二、隊列的基本操作 1）初始化操作 InitQueue(amp。 （ a1, a2, ... , ai 1, ai , ai+1, …, a n ） 插入 刪除 能進行插入的一端稱為隊尾，能進行刪除的一端稱為隊頭。 任何一個遞歸程序都可以通過非遞歸程序?qū)崿F(xiàn)。 } //EvaluateExpression 棧的應(yīng)用舉例 第 33 頁 遞歸是很有用的工具，在數(shù)學(xué)和程序設(shè)計等許多領(lǐng)域中都會用到。 //進行二元運算 a ? b break。 Pop(OPND, a)。 case : //新輸入的算符 c優(yōu)先級低 ， 即棧頂算符優(yōu)先權(quán)高 //出棧并將運算結(jié)果入棧 OPND Pop ( OPTR, theta)。 c=getchar( )。 break。 } //不是運算符則進棧 else 棧的應(yīng)用舉例 第 32 頁 switch ( Precede(GetTop(OPTR), c ) { //判定 OPTR的棧頂運算符 ?1與讀入的運算符 ?2間的優(yōu)先關(guān)系 case : // 新輸入的算符 c優(yōu)先級高 ， c進棧 Push(OPTR, c)。 while ( c!=‘’ || GetTop(OPTR)!=‘’ ) { if (! In (c, OP)) // In(c, OP)判斷 c是否為運算符 { Push(OPND, c)。 InitStack(OPND)。 InitStack(OPTR)。 棧的應(yīng)用舉例 第 30 頁 表達式求值示意： 5 + 6 ? ( 1 + 2 ) 4 top base OPTR棧 OPND棧 top base 5 top top + top 6 top top ( top 1 top + top 2 top top 3top top1823 top4 toptop19toptoptop5 讀入表達式過程： + 6 ( 1 + 2 ) 4 = 19 1+2=3 6 3=18 5+18=23 234=19 棧的應(yīng)用舉例 第 31 頁 算法描述 operandType EvaluateExpression( ) { //算術(shù)表達式求值的算符優(yōu)先算法。 依次讀入表達式中每個字符，若是操作數(shù)，則進 OPND棧；若是運算符，則與 OPTR棧的棧頂運算符比較優(yōu)先級后作相應(yīng)操作。一個是 OPTR棧，用以保存運算符；一個是 OPND棧，用以保存操作數(shù)或運算結(jié)果。 棧的鏈?zhǔn)酱鎯蛯崿F(xiàn) 棧 Data next S an1 a1 an ∧ 第 24 頁 小 結(jié) 棧是限定僅能在表尾一端進行插入、刪除操作的線性表 棧的元素具有后進先出的特點 棧頂元素的位置由一個稱為棧頂指針的變量指示，進棧和出棧操作都要修改棧頂指針 棧 第 25 頁 1）問題的提出 從鍵盤一次性輸入一串算術(shù)表達式，給出計算結(jié)果。 } //Pop 出棧操作算法 棧 第 23 頁 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱鏈棧。 e=*。 // ?？? e = * 。S, ElemType amp。e ) 功能： 棧頂元素退棧，并用 e 返回。 } //Push 棧 第 21 頁 出棧操作前 100 99 n n1 n2 1 0 an an1 a2 a1 6）出 棧操作 Pop ( SqStack amp。 } * ++ = e。 //存儲分配失敗 = + 。S, ElemType e ) { //將元素 e插入棧中，使其成為新的棧頂元素 if ( = ) // 若棧滿則追加存儲空間 { = (ElemType * ) realloc ( , ( +STACKINCREMENT) * sizeof(ElemType))。S, ElemType e ) 功能： 元素 e 進棧。 return OK。e ) { if ( == ) return ERROR。 } //ClearStack 置空操作算法 棧 第 17 頁 e an 100 99 n n1 n2 1 0 an an1 a2 a1 4）取棧頂元素操作 GetTop ( SqStack S, ElemType amp。 // 若棧未建立（尚未分配?？臻g） = 。S) 功能 ： 將棧 S置為空棧 100 99 n n1 n2 1 0 an an1 a2 a1 100 99 n n1 n2 1 0 an an1 a2 a1 棧 第 16 頁 Status ClearStack ( SqStack amp。 return OK。 //回收?？臻g = = NULL。S ) { if ( ! ) return ERROR。 } // InitStack 第 13 頁 99 n n1 n2 1 0 an an1 a2 a1 2） 銷毀棧操作 DestroyStack(SqStack amp。 = ST
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1