【正文】 下一頁 上一頁 停止放映 第 88/89 頁 能夠采用壓縮存儲的矩陣 對稱矩陣 存儲主對角線以上（下）的元素； 上（下）三角矩陣 只存儲三角陣元素； 帶狀矩陣 只存儲帶狀元素； 稀疏矩陣 只存儲非零元素； 大量相同元素矩陣 存儲某元素和重復(fù)個(gè)數(shù)。 – 建立書目檢索的關(guān)鍵詞索引表，就能很容易地從關(guān)鍵詞索引表中查到相關(guān)的書目列表。 例如，利用換頁符和換行符把文本劃分為若干頁，每頁若干行。 下一頁 上一頁 停止放映 第 62/89 頁 串的基本操作 LENGTH（ S） 求串 S的長度。 step2 非空 ,則判別隊(duì)長度是否為 1。 step2 判別 T是否為空 。 （ 2）隊(duì)尾指針 rear = rear % MAXSIZE +1 ； 等價(jià)于： if （ rear MAXSIZE ） rear = 1。 rear 為隊(duì)尾指針 ,指示隊(duì)尾元素的位置。 例如， 3*（ 72） ； – 實(shí)際處理表達(dá)式是用兩個(gè)棧結(jié)構(gòu) OPTR（算符）和 OPND（操作數(shù)）加運(yùn)算規(guī)則組成； 四則運(yùn)算 下一頁 上一頁 停止放映 第 27/89 頁 計(jì)算表達(dá)式算法步驟 Step1 初始化，清空 OPTR和 OPND，將左定界符壓 OPTR棧； Step2 循環(huán)輸入表達(dá)式中的每個(gè)字符 – 若輸入操作數(shù)，則進(jìn) OPND棧 – 若是算符，則和 OPTR棧頂元素進(jìn)行比較，按規(guī)則進(jìn)行相應(yīng)操作 – 操作服從優(yōu)先關(guān)系表（ Q1是棧中算符， Q2是當(dāng)前算符） ? Q1Q2 Q2入 OPTR棧，再讀入下一個(gè)元素 ? Q1=Q2 Q1出 OPTR棧，脫括號，再讀一個(gè)元素 ? Q1Q2 Q1出 OPTR棧，從 OPND中取兩個(gè)數(shù)運(yùn)算 Step3 直到出現(xiàn)右定界符為止。 step2 在 top所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn) ,并將 top指向新申請的結(jié)點(diǎn) t。 下一頁 上一頁 停止放映 第 16/89 頁 算法 19 出棧算法程序 pop（ ） { int x。 – 允許進(jìn)行插入和刪除操作的一端稱為 棧頂 (top)，另一端為 棧底(bottom)；棧底固定，而棧頂浮動； – 棧中元素個(gè)數(shù)為零時(shí)稱為空棧。 int top = 1。這時(shí)，就需要采用鏈棧。 step2 刪除 top所指結(jié)點(diǎn)，并使 top 指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)。 進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。 else rear = rear + 1 。若空 ,則顯示隊(duì)列 ‘ 下溢 ’ 。 t data = x。 frontnext = tnext。 非緊縮存儲 一個(gè)字的存儲單元中只存放 1個(gè)字符。 ? I F i j T H E N k : = j 。 下一頁 上一頁 停止放映 第 84/89 頁 二維數(shù)組按行優(yōu)先存儲舉例 有二維數(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 頁 按列優(yōu)先順序存儲結(jié)構(gòu) 按列優(yōu)先順序存放是將數(shù)組看作若干個(gè)列向量。 1章作業(yè)： 1 1 17 3. 作業(yè) (數(shù)字化 )要求： – 按要求提交到指定路徑下 : – /軟件基礎(chǔ) /劉志強(qiáng) /班級編號 – 用 C（或其它語言）語言描述算法 – 作業(yè)命名方式為： 學(xué)號 .章數(shù) _序號 ( 例如 , ) 下一頁 上一頁 停止放映 第 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大教室對面） 謝謝，再見！ 。數(shù)組中的每個(gè)元素由元素的兩個(gè)下標(biāo)表達(dá)式唯一的確定。 ? V A R i , j , k : R E A L 。由此產(chǎn)生緊縮和非緊縮存儲區(qū)別。 } else { t = frontnext。 } else { rear next = t。 queue[rear] = x 。 front front rear D E F G H rear 下一頁 上一頁 停止放映 第 43/89 頁 解決假溢出的方法 如果使當(dāng) rear = MAXSIZE+1 時(shí)，即超過隊(duì)列末端時(shí)，令 rear = 1；從而使隊(duì)列的首尾相連接。 注： 這是一個(gè)遞歸問題， n階問題可以分解為 n圓盤和 n1階問題。 top= t。 順序棧最多可用于 2個(gè)棧的共享，對于更多的棧就難于表達(dá)了。 棧的操作只能在一端進(jìn)行；即棧頂位置隨進(jìn)棧和出棧而變化 。 下一頁 上一頁 停止放映 第 8/89 頁 棧有關(guān)概念 棧上溢 ?？臻g是有限的，若棧已滿，在進(jìn)行入棧操作時(shí)，就要產(chǎn)生上溢。 exit(1)。 t=(SNODE * )malloc(sizeof(SNODE))。 else return ( n * fac(n1))。 判別隊(duì)列為空的條件也將復(fù)雜化。 循環(huán)隊(duì)列在指針移動處理時(shí)與一般隊(duì)列不同： 下一頁 上一頁 停止放映 第 46/89 頁 循環(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ì)列是否已滿 。 step3 非空 ,將 T插入鏈中 ,修改 rear指針。 為 1,則修改頭、尾指針； step3 釋放 T。 DATE=?20?+SUBSTR（ ’ 03/07/00?， 7， 2） +?年 ‘ CONCAT（ S1， S2）聯(lián)接 S1和 S2，組成一個(gè)新串 S=CONCAT（ ’ Str?， ’ ing?） INDEX（ S1， S2） 確定 S2在 S1中的位置。 建立頁表、行表的存儲映象表。 下一頁 上一頁 停止放映 第 75/89 頁 建立關(guān)鍵字索引表 （ a） 書目如下 （ b）關(guān)鍵詞索引表 書號 書名 關(guān)鍵詞 書號索引 005 計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu) 分析 03 050、 067 010 數(shù)據(jù)結(jié)構(gòu)導(dǎo)論 基礎(chǔ) 023 023 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 結(jié)構(gòu) 00 0 023 034 計(jì)算機(jī)算法設(shè)計(jì)及分析 計(jì)算機(jī) 00 034 050 數(shù)值分析簡介 設(shè)計(jì) 034 067 數(shù)值分析 數(shù)據(jù) 00 0 023 算法 034 數(shù)值 050、 067 下一頁 上一頁 停止放映 第 76/89 頁 四、數(shù)組（ Array） 數(shù)組的定義 數(shù)組的存儲結(jié)構(gòu) 特殊矩陣的存儲及管理 數(shù)組的操作 下一頁 上一頁 停止放映 第 77/89 頁 數(shù)組的定義 數(shù)組是相同類型數(shù)據(jù)元素的有限集合； 數(shù)組中的各個(gè)分量稱為數(shù)組元素； 每個(gè)數(shù)組元素值可以用數(shù)組名和一個(gè)下標(biāo)值唯一的確定； 下一頁 上一頁 停止放映 第 78/89 頁 數(shù)組的邏輯