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