【正文】 個位置； 隊尾指針 rear總是指向隊尾元素的位置。 front front rear D E F G H rear 下一頁 上一頁 停止放映 第 43/89 頁 解決假溢出的方法 如果使當(dāng) rear = MAXSIZE+1 時，即超過隊列末端時，令 rear = 1；從而使隊列的首尾相連接。 下一頁 上一頁 停止放映 第 44/89 頁 循環(huán)隊列 設(shè)定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1 。 else front ＝ front + 1。 step2 隊尾指針后移一個位置 ,將新結(jié)點元素值存入當(dāng)前結(jié)點單元。 queue[rear] = x 。 下一頁 上一頁 停止放映 第 50/89 頁 循環(huán)隊列出隊操作程序 delqueue( ) { int y。 下一頁 上一頁 停止放映 第 54/89 頁 鏈隊列的入隊操作 算法 114描述 : step1 申請建立一個新結(jié)點 T。 下一頁 上一頁 停止放映 第 55/89 頁 鏈隊列的入隊操作 addqueue(int x) { QNODE *t。 } else { rear next = t。 } } 下一頁 上一頁 停止放映 第 56/89 頁 鏈隊列的出隊操作 當(dāng)隊列長度大于 1時 ,只修改隊頭指針即可。若空 ,則顯示 隊列 ‘ 下溢 ’ 。 下一頁 上一頁 停止放映 第 58/89 頁 鏈隊列的出隊操作的程序 delqueue( ) { int x。 } else { t = frontnext。 free(t)。 當(dāng) 2個串的長度相等，且各對應(yīng)位置上的字符都相同時，稱兩個 子串相等 。 REPLACE（ S1， S2， S3） 用串 S3替換串 S1中所有與串 S2相等且不重疊的子串。由此產(chǎn)生緊縮和非緊縮存儲區(qū)別。 下一頁 上一頁 停止放映 第 66/89 頁 串的鏈表存儲結(jié)構(gòu) 與順序存儲結(jié)構(gòu)類似也有緊縮和非緊縮存儲結(jié)構(gòu)的區(qū)別。指針用來指示串在堆中的位置； 例如，設(shè)有 a=?BEI?， b=? JING?， c=??，d=?SHANGHAI?； 串名 串長 起始地址 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 頁 文本編輯 文本編輯操作實質(zhì)上是修改字符數(shù)據(jù)的形式和格式。 文本編輯器中設(shè)有頁指針、行指針和字符指針，分別對應(yīng)當(dāng)前的頁、行和字符。 ? V A R i , j , k : R E A L 。 ? 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 下一頁 上一頁 停止放映 第 72/89 頁 文本編輯（三） 為了進行管理 ,建立頁表和行表的存儲映象表 : 行號 起始地址 長度 100 201 13 110 214 17 120 231 8 130 239 14 140 253 20 150 273 20 160 293 7 下一頁 上一頁 停止放映 第 73/89 頁 建立關(guān)鍵字索引表 – 信息檢索是字符串的又一種應(yīng)用。因為內(nèi)容相似的書籍不會同名，因此，識別很困難。 下一頁 上一頁 停止放映 第 82/89 頁 數(shù)組的順序存儲結(jié)構(gòu) ? 數(shù)組元素是連續(xù)存放的，因此只能采用順序存儲結(jié)構(gòu)。數(shù)組中的每個元素由元素的兩個下標表達式唯一的確定。數(shù)組中的每個元素由元素的兩個下標表達式唯一的確定。 壓縮的含義是： – 相同值的多個元素占用一個存儲單元； – 零元素不分配存儲單元。 2) 假設(shè)一單循環(huán)鏈表的長度大于 1，且表中即無頭結(jié)點也無頭指針。 1章作業(yè)： 1 1 17 3. 作業(yè) (數(shù)字化 )要求： – 按要求提交到指定路徑下 : – /軟件基礎(chǔ) /劉志強 /班級編號 – 用 C（或其它語言）語言描述算法 – 作業(yè)命名方式為： 學(xué)號 .章數(shù) _序號 ( 例如 , ) 下一頁 上一頁 停止放映 第 92/89 頁 結(jié)束語 ? 計算機教學(xué)實驗中心網(wǎng)址： ： \\ctec . ? 作業(yè)提交路徑 : ： \\202 . \moodle ? 數(shù)字化作業(yè)的路徑 : :\\\軟件基礎(chǔ) ? 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點： 計教中心 102房間（ 1300大教室對面） 謝謝，再見！ 。試寫出刪除表中結(jié)點 S 的算法。 下一頁 上一頁 停止放映 第 89/89 頁 對稱矩陣的壓縮存儲 對稱矩陣的元素滿足： aij = aji 1 ? i ， j ? n 因此將 n*n 個元素壓縮存放到 n（ n+1） /2 個單元的一維數(shù)組 S（（ n+1） *n/2）中。 下一頁 上一頁 停止放映 第 86/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， a21， a31），（ a12， a22， a32），（ a13， a23， a33），（ a14， a24， a34）） LOC（ a23） = LOC（ a11） +（ 31） 3 +（ 21） = 8 LOC（ a34） = 1 + （ 41） 3 + （ 31） = 12 LOC（ a14） = 1 + （ 41） 3 + （ 11） = 10 下一頁 上一頁 停止放映 第 87/89 頁 數(shù)組的壓縮存儲 實際工程問題中推導(dǎo)出的數(shù)組常常是高階、含大量零元素的矩陣，或者是些有規(guī)律排列的元素。 下一頁 上一頁 停止放映 第 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ù)組看作若干個列向量。數(shù)組存放通常采用兩種方式： –按行優(yōu)先順序 –按列優(yōu)先順序 下一頁 上一頁 停止放映 第 83/89 頁 按行優(yōu)先順序存儲結(jié)構(gòu) 按行優(yōu)先順序存放是將數(shù)組看作若干個行向量。 下一頁 上一頁 停止放映 第 74/89 頁 建立關(guān)鍵字索引表算法描述 從書目中讀入一個書目表（字符串）； 從書目串中提取所有關(guān)鍵詞插入詞表； 對詞表中的每一個關(guān)鍵詞，建立索引表（有序）； 隨后即可檢索查詢。其中關(guān)鍵