【正文】 39。 ch = 39。 amp。){ if(ch = 39。 while(ch != 39。 char ch = postfix[i]。 計(jì)算例 a b * c de/ f * + t1 t3 t4 t2 t5 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 后綴表達(dá)式用什么來(lái)存儲(chǔ) ? 字符棧、字符數(shù)組、字符串 其實(shí)這三者本質(zhì)上都是一樣的，都可以實(shí)現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 a b * c d e / f * + T1 = T2 = T3 = T4 = T5 = 操作數(shù)或中間結(jié)果棧 S 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 1. 初始化棧 S； 2. 從左到右依次掃描表達(dá)式的每個(gè)字符，執(zhí)行下述操作； 若當(dāng)前字符是運(yùn)算對(duì)象，則入棧 S，處理下個(gè)字符 若當(dāng)前字符是運(yùn)算符，則從棧 S出棧兩個(gè)運(yùn)算對(duì)象，執(zhí)行運(yùn)算并將結(jié)果入棧 S，處理下一個(gè)字符； 3. 輸出棧 S的棧頂元素，即表達(dá)式的運(yùn)算結(jié)果； 算法描述 —— 偽代碼 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 double calculate(char postfix[]){ SeqStackdouble S。 ? 算術(shù)表達(dá)式有三種表示： ? 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B； ? 前綴 (prefix)表示 操作符 操作數(shù) 操作數(shù) ， 如 +AB； ? 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 ? 中綴表達(dá)式 a * b + ( c – d/e ) *f ? 后綴表達(dá)式 a b * c de/ f *+ ? 前綴表達(dá)式 + *ab *c/def 表達(dá)式事例 結(jié)論： 1）操作數(shù)之間的相對(duì)次序不變； 2）運(yùn)算符的相對(duì)次序不同； 3）后綴表達(dá)式的運(yùn)算規(guī)則為： 運(yùn)算符在式中出現(xiàn)的順序恰為 表達(dá)式的運(yùn)算順序； 每個(gè)運(yùn)算符和在它們之前且 緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最 小的表達(dá)式 4）前綴表達(dá)式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們 之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè) 最小的表達(dá)式 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 （逆波蘭式）求值 ? 從左向右順序地掃描表達(dá)式 ， 并用一個(gè) 棧 暫存掃描到的 操作數(shù) 或 計(jì)算結(jié)果 。 ?鏈隊(duì)列：沒(méi)有隊(duì)列滿的問(wèn)題 ， 只有當(dāng)內(nèi)存沒(méi)有可用空間時(shí)才會(huì)出現(xiàn)隊(duì)列滿 ， 但是每個(gè)元素都需要一個(gè)指針域 ， 從而產(chǎn)生了結(jié)構(gòu)性開銷 。 } 鏈隊(duì)列的實(shí)現(xiàn) ——出隊(duì) 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 循環(huán)隊(duì)列和鏈隊(duì)列的比較 時(shí)間性能 : ?循環(huán)隊(duì)列和鏈隊(duì)列的基本操作都需要常數(shù)時(shí)間 O (1)。 delete p。 frontnext = pnext。 p = frontnext。 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 鏈隊(duì)列的實(shí)現(xiàn) ——出隊(duì) front a1 a2 an ∧ rear p 考慮邊界情況：隊(duì)列中只有一個(gè)元素？ front a1 p ∧ rear ∧ rear 算法描述： if (pnext == NULL) rear = front。 } 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 鏈隊(duì)列的實(shí)現(xiàn) ——出隊(duì) front a1 a2 an ∧ rear p 算法描述： p=frontnext。 rearnext = s。 sdata = x。 rear=s。 如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？ front 算法描述： snext=NULL。 rear=s。 如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？ a1 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 鏈隊(duì)列的實(shí)現(xiàn) ——入隊(duì) 操作接口： void EnQueue(DataType x)。 rearnext=s。 如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？ 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 x s 鏈隊(duì)列的實(shí)現(xiàn) ——入隊(duì) 操作接口： void EnQueue(DataType x)。 rearnext=s。 } 鏈隊(duì)列的實(shí)現(xiàn) ——構(gòu)造函數(shù) front ∧ rear 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 x s 鏈隊(duì)列的實(shí)現(xiàn) ——入隊(duì) 操作接口： void EnQueue(DataType x)。 frontnext = NULL。 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 操作接口： LinkQueue( )。 DataType GetQueue( )； bool Empty( )； private: NodeDataType *front, *rear。 void EnQueue(DataType x)。 } 循環(huán)隊(duì)列的實(shí)現(xiàn) ——讀隊(duì)頭元素 0 1 2 3 4 入隊(duì) a4 a5 a6 出隊(duì) front rear a3 i 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 鏈隊(duì)列： 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu) 隊(duì)頭指針即為鏈表的頭指針 first a1 a2 an ∧ 如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？ rear front 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 非空鏈隊(duì)列 front a1 a2 an ∧ rear 空鏈隊(duì)列 front ∧ rear 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 鏈 隊(duì) 列 類 的 聲 明 template class DataType class LinkQueue { public: LinkQueue( )。 i = (front + 1) % QueueSize。 return data[front]。 } 循環(huán)隊(duì)列的實(shí)現(xiàn) ——入隊(duì) 0 1 2 3 4 入隊(duì) 出隊(duì) a3 a4 rear front a5 rear 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 0 1 2 3 4 入隊(duì) a4 a5 a6 出隊(duì) template class DataType DataType CirQueueDataType ::DeQueue( ) { if (rear == front) throw 下溢 。 rear =(rear+1) % QueueSize。 }。 bool Empty( )； private: DataType data[QueueSize]。 DataType DeQueue( )。 如何確定不同的隊(duì)空、隊(duì)滿的判定條件？ 為什么要將隊(duì)空和隊(duì)滿的判定條件分開？ 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊(duì)滿的條件： (rear+1) mod QueueSize=front 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì) rearfront a3 a4 front a5 rear a6 出隊(duì) 0 1 2 3 4 入隊(duì) rearfront a3 a4 front a5 rear a6 出隊(duì) 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 循 環(huán) 隊(duì) 列 類 的 聲 明 const int QueueSize=100。 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何解決假溢出？ 0 1 2 3 4 入隊(duì) 出隊(duì) a3 a4 front a5 rear rear a6 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 例： a1a2依次出隊(duì) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì) 出隊(duì) a1 a2 a3 a4 rear front front front 出隊(duì)操作時(shí)間性能提高為 O(1) 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 例： a1a2依次出隊(duì) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì) 出隊(duì) a3 a4 rear front 隊(duì)列的移動(dòng)有什么特點(diǎn)？ 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 例： a1a2依次出隊(duì) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì) 出隊(duì) a3 a4 rear front 整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng) 單向移動(dòng)性 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 假溢出： 當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。 （ a1, a2, ?? , an） 隊(duì)尾 隊(duì)頭 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊(duì)列的操作特性： 先進(jìn)先出 a1 a2 a3 入隊(duì) 隊(duì)尾 隊(duì)頭 出隊(duì) 隊(duì)頭 隊(duì)列的邏輯結(jié)構(gòu) 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 隊(duì)列的抽象數(shù)據(jù)類型定義 ADT Queue Data 隊(duì)列中元素具有相同類型及先進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系 Operation InitQueue 前置條件：隊(duì)列不存在 輸入：無(wú) 功能：初始化隊(duì)列 輸出：無(wú) 后置條件：創(chuàng)建一個(gè)空隊(duì)列 隊(duì)列 數(shù)據(jù)結(jié)構(gòu)（ C++版）第 2版 清華大學(xué)出版社 DestroyQueue 前置條件：隊(duì)列已存在 輸入：無(wú) 功能：銷毀隊(duì)列 輸出：無(wú) 后置條件：釋放隊(duì)列所占用的存儲(chǔ)空間 EnQueue 前置條件：隊(duì)列已存在 輸入：元素值 x 功能：在隊(duì)尾插入一個(gè)元素 輸出：如果插入不成功，