【正文】 環(huán)隊(duì)列隊(duì)空、隊(duì)滿條件 隊(duì)空條件 front = rear ； 隊(duì)滿條件 front = rear % MAXSIZE +1 rear front 1 2 3 MAXSIZE ... 1 2 3 4 ... i rear i+1 front MAXSIZE a1 a2 a3 ai1 示例 … 下一頁 上一頁 停止放映 第 47/89 頁 循環(huán)隊(duì)列入隊(duì)操作 算法 112描述 : step1 判別隊(duì)列是否已滿 。 這就是循環(huán)隊(duì)列的處理思想。 判別隊(duì)列為空的條件也將復(fù)雜化。 隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。 else return ( n * fac(n1))。 step3 釋放被刪除結(jié)點(diǎn)的存儲(chǔ)空間。 t=(SNODE * )malloc(sizeof(SNODE))。 下一頁 上一頁 停止放映 第 19/89 頁 鏈棧存儲(chǔ)結(jié)構(gòu) ? 鏈棧存儲(chǔ)結(jié)構(gòu)的 C語言描述： struct snode { int data。 exit(1)。 下一頁 上一頁 停止放映 第 11/89 頁 棧操作舉例 a1 a2 …… a n 棧底 棧頂 MAXSIZE TOP 1. top=0 A B C 2. (空棧 ) top=3 (A、 B、 C進(jìn)棧 ） A B 3. top=2 (C出棧） 4. A B C D E F top=MAXSIZE (棧滿） 下一頁 上一頁 停止放映 第 12/89 頁 例 110 有三個(gè)元素的進(jìn)棧序列是 1， 2， 3。 下一頁 上一頁 停止放映 第 8/89 頁 棧有關(guān)概念 棧上溢 ?？臻g是有限的，若棧已滿，在進(jìn)行入棧操作時(shí)，就要產(chǎn)生上溢。 下一頁 上一頁 停止放映 第 4/89 頁 教學(xué)主要內(nèi)容 ? 棧、隊(duì)列、數(shù)組、串的 : – 有關(guān) 概念 – 邏輯結(jié)構(gòu)及特點(diǎn) – 存儲(chǔ)結(jié)構(gòu) – 有關(guān) 操作 下一頁 上一頁 停止放映 第 5/89 頁 本章涉及內(nèi)容 第 1章的 棧和隊(duì)列 (P32~P46) 串和數(shù)組 (P47~P55) 下一頁 上一頁 停止放映 第 6/89 頁 一、棧結(jié)構(gòu) 棧的定義 棧的基本運(yùn)算 棧的順序存儲(chǔ)結(jié)構(gòu) 多棧共享問題 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 棧的應(yīng)用 下一頁 上一頁 停止放映 第 7/89 頁 棧的定義 堆棧 (Stack) – 棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。 棧的操作只能在一端進(jìn)行；即棧頂位置隨進(jìn)棧和出棧而變化 。 } else { top + +； /* 棧指針加 1 */ stack [ top ] = x ； /* 元素 x進(jìn)棧 */ } } 示例 下一頁 上一頁 停止放映 第 15/89 頁 算法 19 出棧算法 ? 算法步驟 : – step1 判別棧是否為空；若空，則輸出 棧下溢信息，并停止執(zhí)行；否則， 執(zhí)行 step2； – step2 彈出（刪除）棧頂元素； – step3 棧頂指針 top下移 (減 1)。 順序棧最多可用于 2個(gè)棧的共享，對(duì)于更多的棧就難于表達(dá)了。否則 ,執(zhí)行 step2 。 top= t。 } } 下一頁 上一頁 停止放映 第 25/89 頁 棧的應(yīng)用 表達(dá)式計(jì)算 子程序的嵌套調(diào)用 參數(shù)傳遞 鍵盤緩沖區(qū) 遞歸過程的實(shí)現(xiàn) 下一頁 上一頁 停止放映 第 26/89 頁 舉例 1 表達(dá)式計(jì)算 計(jì)算表達(dá)式，首先要正確地定義運(yùn)算規(guī)則： – 先乘除、后加減 – 從左到右 – 先括號(hào)內(nèi)，再括號(hào)外 為了讓計(jì)算機(jī)能識(shí)別表達(dá)式，規(guī)定： – 表達(dá)式由操作數(shù)（ Operand）和操作符（ Operator）和定界符（ Delimiter）組成。 注： 這是一個(gè)遞歸問題， n階問題可以分解為 n圓盤和 n1階問題。 front為隊(duì)頭指針 ,指示隊(duì)頭元素的位置 。 front front rear D E F G H rear 下一頁 上一頁 停止放映 第 43/89 頁 解決假溢出的方法 如果使當(dāng) rear = MAXSIZE+1 時(shí)，即超過隊(duì)列末端時(shí)，令 rear = 1；從而使隊(duì)列的首尾相連接。 else front ＝ front + 1。 queue[rear] = x 。 下一頁 上一頁 停止放映 第 54/89 頁 鏈隊(duì)列的入隊(duì)操作 算法 114描述 : step1 申請(qǐng)建立一個(gè)新結(jié)點(diǎn) T。 } else { rear next = t。若空 ,則顯示 隊(duì)列 ‘ 下溢 ’ 。 } else { t = frontnext。 當(dāng) 2個(gè)串的長(zhǎng)度相等，且各對(duì)應(yīng)位置上的字符都相同時(shí)，稱兩個(gè) 子串相等 。由此產(chǎn)生緊縮和非緊縮存儲(chǔ)區(qū)別。指針用來指示串在堆中的位置； 例如，設(shè)有 a=?BEI?， b=? JING?， c=??，d=?SHANGHAI?； 串名 串長(zhǎng) 起始地址 a 3 1 b 5 4 c 0 9 d 8 9 B E I J I N G S H A N G H A I 下一頁 上一頁 停止放映 第 68/89 頁 串的應(yīng)用 文本編輯 建立關(guān)鍵字索引表 下一頁 上一頁 停止放映 第 69/89 頁 文本編輯 文本編輯操作實(shí)質(zhì)上是修改字符數(shù)據(jù)的形式和格式。 ? V A R i , j , k : R E A L 。因?yàn)閮?nèi)容相似的書籍不會(huì)同名，因此，識(shí)別很困難。數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一的確定。 壓縮的含義是： – 相同值的多個(gè)元素占用一個(gè)存儲(chǔ)單元； – 零元素不分配存儲(chǔ)單元。 1章作業(yè)： 1 1 17 3. 作業(yè) (數(shù)字化 )要求： – 按要求提交到指定路徑下 : – /軟件基礎(chǔ) /劉志強(qiáng) /班級(jí)編號(hào) – 用 C（或其它語言）語言描述算法 – 作業(yè)命名方式為： 學(xué)號(hào) .章數(shù) _序號(hào) ( 例如 , ) 下一頁 上一頁 停止放映 第 92/89 頁 結(jié)束語 ? 計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心網(wǎng)址： ： \\ctec . ? 作業(yè)提交路徑 : ： \\202 . \moodle ? 數(shù)字化作業(yè)的路徑 : :\\\軟件基礎(chǔ) ? 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點(diǎn)： 計(jì)教中心 102房間（ 1300大教室對(duì)面） 謝謝，再見！ 。 下一頁 上一頁 停止放映 第 89/89 頁 對(duì)稱矩陣的壓縮存儲(chǔ) 對(duì)稱矩陣的元素滿足： aij = aji 1 ? i ， j ? n 因此將 n*n 個(gè)元素壓縮存放到 n（ n+1） /2 個(gè)單元的一維數(shù)組 S（（ n+1） *n/2）中。 下一頁 上一頁 停止放映 第 84/89 頁 二維數(shù)組按行優(yōu)先存儲(chǔ)舉例 有二維數(shù)組如下： a11 a12 a13 a14 A3x4 = a21 a22 a23 a24 = a31 a32 a33 a34 1 2 3 4 5 6 7 8 9 10 11 12 (（ a11， a12， a13， a14），（ a21， a22， a23， a24），（ a31， a32， a33， a34）） LOC（ a23） = LOC（ a11） +（ 21） x4+（ 31） = 7 LOC（ a34） = 1 + （ 31） x 4 + （ 41） = 12 LOC（ a14） = 1 + （ 11） x 4 + （ 41） = 4 下一頁 上一頁 停止放映 第 85/89 頁