【正文】 為 T。 下一頁 上一頁 停止放映 第 67/89 頁 堆存儲結(jié)構(gòu) 串的順序存儲和鏈表存儲各有利弊，在實(shí)際應(yīng)用中常采用一種動態(tài)存儲結(jié)構(gòu)，稱其為 堆結(jié)構(gòu) 。 下一頁 上一頁 停止放映 第 70/89 頁 文本編輯 (一） 將下列程序看作是一個字符串。其中關(guān)鍵技術(shù)，是設(shè)計一個索引系統(tǒng)。數(shù)組存放通常采用兩種方式： –按行優(yōu)先順序 –按列優(yōu)先順序 下一頁 上一頁 停止放映 第 83/89 頁 按行優(yōu)先順序存儲結(jié)構(gòu) 按行優(yōu)先順序存放是將數(shù)組看作若干個行向量。 下一頁 上一頁 停止放映 第 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ù)組的壓縮存儲 實(shí)際工程問題中推導(dǎo)出的數(shù)組常常是高階、含大量零元素的矩陣，或者是些有規(guī)律排列的元素。試寫出刪除表中結(jié)點(diǎn) S 的算法。 2) 假設(shè)一單循環(huán)鏈表的長度大于 1，且表中即無頭結(jié)點(diǎn)也無頭指針。數(shù)組中的每個元素由元素的兩個下標(biāo)表達(dá)式唯一的確定。 下一頁 上一頁 停止放映 第 82/89 頁 數(shù)組的順序存儲結(jié)構(gòu) ? 數(shù)組元素是連續(xù)存放的，因此只能采用順序存儲結(jié)構(gòu)。 ? 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 下一頁 上一頁 停止放映 第 72/89 頁 文本編輯（三） 為了進(jìn)行管理 ,建立頁表和行表的存儲映象表 : 行號 起始地址 長度 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)用。 文本編輯器中設(shè)有頁指針、行指針和字符指針，分別對應(yīng)當(dāng)前的頁、行和字符。 下一頁 上一頁 停止放映 第 66/89 頁 串的鏈表存儲結(jié)構(gòu) 與順序存儲結(jié)構(gòu)類似也有緊縮和非緊縮存儲結(jié)構(gòu)的區(qū)別。 REPLACE（ S1， S2， S3） 用串 S3替換串 S1中所有與串 S2相等且不重疊的子串。 free(t)。 下一頁 上一頁 停止放映 第 58/89 頁 鏈隊列的出隊操作的程序 delqueue( ) { int x。 } } 下一頁 上一頁 停止放映 第 56/89 頁 鏈隊列的出隊操作 當(dāng)隊列長度大于 1時 ,只修改隊頭指針即可。 下一頁 上一頁 停止放映 第 55/89 頁 鏈隊列的入隊操作 addqueue(int x) { QNODE *t。 下一頁 上一頁 停止放映 第 50/89 頁 循環(huán)隊列出隊操作程序 delqueue( ) { int y。 step2 隊尾指針后移一個位置 ,將新結(jié)點(diǎn)元素值存入當(dāng)前結(jié)點(diǎn)單元。 下一頁 上一頁 停止放映 第 44/89 頁 循環(huán)隊列 設(shè)定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1 。 下一頁 上一頁 停止放映 第 40/89 頁 關(guān)于隊列表示的約定 為解決這個問題，約定如下： 隊頭指針 front總是指向隊頭元素的前一個位置； 隊尾指針 rear總是指向隊尾元素的位置。 隊列具有先進(jìn)先出（ FIFO）的特點(diǎn)。 } fac(1) fac(2) fac(3) fac(4) fac(5) top 1 fac(1)=1 2*fac(1) fac(2)=2*fac(1) 3*fac(2) fac(3)=3*fac(2) 4*fac(3) fac(4)=4*fac(3) 5*fac(4) fac(5)=5*fac(4) 下一頁 上一頁 停止放映 第 30/89 頁 舉例 3（子程序的嵌套調(diào)用） 有一主程序 main（）調(diào)用子程序示意圖如下： main sub1 sub2 sub3 end end end end sub3 sub2 sub1 main top 下一頁 上一頁 停止放映 第 31/89 頁 舉例 4 N階 Hanoi塔問題 假設(shè)有 X、 Y、 Z三座塔。 下一頁 上一頁 停止放映 第 24/89 頁 算法 111 出棧操作程序 pop (SNODE * top) { SNODE *p。 if(t = = NULL ) { printf(“內(nèi)存中已無可用空間 \n”)。 struct snode *link。 } else { x = stack [ top ]； top ； /* 棧頂指針 減 1*/ } return x ； } 示例 下一頁 上一頁 停止放映 第 17/89 頁 多棧共享問題 ? 多棧共享是充分利用棧空間的一種策略。寫出可能的出棧序列 。 棧下溢 若?？?，再要執(zhí)行出棧操作，則會發(fā)生下溢。 字符串和數(shù)組也是一種線性表，它們的處理與一般線性表的處理又有哪些異同？ 下一頁 上一頁 停止放映 第 3/89 頁 教學(xué)目標(biāo) 掌握 棧、隊列、數(shù)組、串結(jié)構(gòu)的有關(guān) 概念、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)及有關(guān)操作。 棧的順序存儲結(jié)構(gòu)稱為順序棧 。 exit （ 1） 。對棧結(jié)構(gòu)也是一樣的。 ? 鏈棧為空的條件： top = NULL ? 鏈棧為滿的條件 : t = NULL t 為申請的結(jié)點(diǎn) ,為 NULL表示失敗 . 下一頁 上一頁 停止放映 第 20/89 頁 鏈棧示意圖 a1 a2 a3 ^ 棧底 top 棧頂 …... ai 下一頁 上一頁 停止放映 第 21/89 頁 算法 110 進(jìn)棧操作 算法 110操作步驟 : step1 申請一個鏈棧結(jié)點(diǎn) ,若 t=NULL,則表示鏈滿 。 t link = top。 } else { p = top； top = top link ； x = p data ； free(p) 。移動圓盤的規(guī)則為： 1）每次只能移動一個圓盤； 2）圓盤可以插在 X、 Y、 Z的任意一個上； 3）任何時刻都不能將較大的圓盤壓在較小的圓盤之上。 Addqueue（ Q） 插入操作 Delqueue（ Q） 刪除操作 Frontqueue（ Q）取隊頭元素 下一頁 上一頁 停止放映 第 38/89 頁 隊列的順序存儲結(jié)構(gòu) C語言中順序存儲結(jié)構(gòu)采用一維數(shù)組結(jié)構(gòu)，描述如下： define MAXSIZE n int queue[MAXSIZ]； int front,rear。顯然，這是邏輯設(shè)計上的問題。 下一頁 上一頁 停止放映 第 45/89 頁 循環(huán)隊列的指針移動 （ 1） 隊頭指針 front = front% MAXSIZE + 1； 等價于： if（ front MAXSIZE ） front = 1 。