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