【正文】 while (p!=plink) { /*找第 m個結(jié)點 */ for (i=1。i++) { pre = p。 } /*輸出該結(jié)點 */ printf( out element: %d \n, pinfo)。 prelink = plink。 p = prelink。 *pclist=NULL。 } 2022/1/4 73/114 void main() { LinkList jos_clist。 /*輸入所需各參數(shù)的值 */ do { printf(\n please input the values of n = )。n)。 do { printf( please input the values of s = )。s)。 do { printf( please input the values of m = )。m)。 if (init_clist(amp。jos_clist,s,m)。 } 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動態(tài)存儲管理 2022/1/4 74/114 矩陣作為一種線性表的推廣 在矩陣的邏輯結(jié)構(gòu) (K, R)中，可以定義 K是一個線性表的集合， R是 K上的一個線性關(guān)系。 矩陣 2022/1/4 75/114 1. 行優(yōu)先順序 即元素按行向量順序排列，第 i+1個行向量緊接在第 i個行向量后面 矩陣 Am*n中元素的排列順序是： a0 0, a0 1, …, a 0 n1, a1 0, a1 1, …, a 1 n1, ……, a m1 0, am1 1, …, a m1 n1 其地址計算公式為（假設(shè)每個元素占一個單元）： Loc(aij) = loc(a00) + i*n + j 2. 列優(yōu)先順序 即元素按列向量順序排列，第 j+1個列向量緊接在第 j個列向量后面 矩陣 Am*n中元素的排列順序是： a0 0, a1 0, …, a m1 0, a0 1, a1 1, …, a m1 1, ……, a 0 n1, a1 n1, …, a m1 n1 其地址計算公式為： Loc(aij) = loc(a00) + j*m + i 矩陣的順序表示 2022/1/4 76/114 按行優(yōu)先 順序存儲，其地址計算公式為（以下都假設(shè)每個元素占一個單元）： Loc(aij) = loc(a00) + i*n + j 按列優(yōu)先 順序存儲，其地址計算公式為： Loc(aij) = loc(a00) + j*m + i 矩陣的順序表示的特點： 存儲密度很高，存取的速度很快。 存儲稀疏矩陣的方法是多種多樣的，下面介紹其中幾種： (1) 三元組表示法 (2) 偽地址表示法 (3) 帶輔助行向量的二元組表示法 (4) 行 列表示法 稀疏矩陣的表示方法 2022/1/4 79/114 (1) 三元組表示法 這個方法用一個數(shù)組（順序結(jié)構(gòu)）來表示稀疏矩陣。每個結(jié)點包括 3個字段，分別為該非零元素的行下標(biāo)、列下標(biāo)和值。 設(shè)行下標(biāo)和列下標(biāo)也占一個存儲單元，那么這種方法需要 3k個存儲單元 2022/1/4 80/114 2022/1/4 81/114 對于矩陣 X： 其稀疏矩陣的三元組表示為： 行下標(biāo) 列下標(biāo) 值 0 0 0 15 1 0 3 22 2 0 5 15 3 1 1 11 4 1 2 3 5 2 3 6 6 4 0 91 7 5 2 28 分析 設(shè)行下標(biāo)和列下標(biāo)也占一個存儲單元，那么這種方法需要３ｋ個存儲單元（ｋ為非零元素個數(shù)，在上面的例子中 k=8）。 這種表示的缺點是修改不便。為了保持表示的行優(yōu)先順序，以便進(jìn)行二分法檢索，那么插入時就必須在存儲器里移動所有后面的元素。偽地址法和三元組法相似，只是數(shù)組的每個結(jié)點只包括兩個字段，分別為矩陣非零元素的偽地址和值。 2022/1/4 83/114 2022/1/4 84/114 偽地址 值 0 0 15 1 3 22 2 5 15 3 7 11 4 8 3 5 15 6 6 24 91 7 32 28 稀疏矩陣偽地址表示 (3) 帶輔助行向量的二元組表示法 這個方法是三元組表示法的一個變種。 NRA [i] = NRA[i1] + 矩陣第 i1行中非零元素的個數(shù) 用帶輔助行向量的二元組表示法表示稀疏矩陣，每個非零元素只需要兩個字段表示：分別為非零元素的列下標(biāo)和值。另外還有行的頭指針向量和列的頭指針向量，行的頭指針向量有ｍ個元素，分別指向代表各行的第一個非零元素的結(jié)點。 2022/1/4 87/114 2022/1/4 88/114 討論 時間代價和空間代價始終是數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計的最主要因素，然而它們往往是相互對立的。 順序表和單鏈表是兩種最簡單的數(shù)據(jù)結(jié)構(gòu)，但是它們的應(yīng)用非常廣泛。 稀疏矩陣本身也是許多復(fù)雜結(jié)構(gòu)的抽象。它是表處理語言（例如 LISP）的基礎(chǔ)結(jié)構(gòu)，也可以用于表示動態(tài)存儲空間的整體模型。但是，廣義表中的元素允許以不同形式出現(xiàn) :它可以是一個原子（邏輯上不能再分解的元素），也可以又是一個廣義表。一個廣義表還允許直接或間接地作為它自身的子（廣義）表。 一個廣義表中所包含的元素的個數(shù)，稱為這個廣義表的長度。 一個廣義表的 深度 ，就是指廣義表中所含子表的層數(shù)。例如： Ｅ＝（） Ｌ＝（ａ，ｂ） Ａ＝（ｘ，Ｌ）＝（ｘ，（ａ，ｂ）） Ｂ＝（Ａ，ｙ）＝（（ｘ，（ａ，ｂ）），ｙ） Ｃ＝（Ａ，Ｂ）＝（（ｘ，（ａ，ｂ）），（（ｘ，（ａ，ｂ）），ｙ）） Ｄ＝（ｚ，Ｄ）＝（ｚ，（ｚ，（ｚ … ））） 2022/1/4 93/114 廣義表的分類 如果廣義表中的元素全部都是原子（例如廣義表Ｌ），這種廣義表就是 線性表 ； 如果廣義表中的元素允許有子廣義表，但所有各層子廣義表均無共享（例如廣義表Ａ、Ｂ），這種廣義表，稱為 純表 ； 在各層子廣義表中允許共享的廣義表（例如廣義表Ｃ的子表 B中共享了 A），稱為 再入表 ； 允許（子）廣義表直接（或間接）地把作為自己的子廣義表時，這樣的廣義表（例如廣義表Ｄ），稱為 遞歸表 。 其中 atom是一標(biāo)志位： atom＝ 0表示本結(jié)點為子廣義表，這時字段 info存放子廣義表中第一個元素所對應(yīng)結(jié)點的地址； atom＝ 1表示本結(jié)點為原子，字段 info存放本原子的信息（當(dāng)信息量比較大時，也可以存放本原子信息存放的地址）。 2022/1/4 97/114 2022/1/4 98/114 帶頭結(jié)點的單鏈表示法 上述單鏈表示法的一個主要缺點是：如果要刪除廣義表（或子廣義表）中某一元素（例如刪除 A中的 x）則需要搜索廣義表中所有結(jié)點后才能進(jìn)行。 為區(qū)分是一般結(jié)點或者是表頭結(jié)點，不妨令表頭結(jié)點 atom字段為 1；表頭結(jié)點的 info字段可以用來存放本廣義表（或子廣義表）的有關(guān)信息，表頭結(jié)點的 link字段指向廣義表中第一個元素對應(yīng)的結(jié)點。 習(xí)慣上把這種在使用期間，可自由插入和刪除的數(shù)據(jù)結(jié)構(gòu)稱為 動態(tài)數(shù)據(jù)結(jié)構(gòu) 。 結(jié)點的動態(tài)分配與回收 2022/1/4 101/114 在前面的討論中，當(dāng)單鏈表插入值為 x的元素時，只需調(diào)用函數(shù) malloc，便能得到一個所需結(jié)點的空間，并返回這個結(jié)點的起始地址； 在某指針?biāo)赶虻慕Y(jié)點刪除后，調(diào)用函數(shù) free，就可以將該結(jié)點所占的空間釋放，以利于再分配。 2022/1/4 102/114 等長結(jié)點的分配與回收 可利用空間表 2022/1/4 103/114 不等長結(jié)點的分配與回收 一個處理方法是，在動態(tài)區(qū)中建立多個可利用空間表，每個可利用空間表對應(yīng)一種固定長度的結(jié)點。另外，要管理多個可利用空間表，系統(tǒng)開銷也較大。分配時按申請的長度在可利用空間表中進(jìn)行檢索，找到其長度大于或等于申請長度的結(jié)點，從中截取合適的長度。 2022/1/4 104/114 為了便于管理，在不等長的可利用空間表中，每個結(jié)點除了要有一個 link字段指向表中下一個結(jié)點以外，還應(yīng)有一個存放本結(jié)點大小的字段 size。 2022/1/4 105/114 動態(tài)分配 1. 最佳適配 檢索可利用空間表中的全部結(jié)點，在所有 size≥N的塊中，找出最小的一塊進(jìn)行分配，這種分配策略稱為最佳適配。 3. 最大適配 如果在可利用空間表中，每次都用最大的可利用塊來分配，當(dāng)最大的塊長度小于Ｎ時，則分配失敗。 2022/1/4 106/114 例 1：最佳適配分配過程 2022/1/4 107/114 例 2：首先適配分配 2022/1/4 108/114 例 3：最大適配分配 2022/1/4 109/114 回收過程 必須隨時考查能否和相鄰的塊合并的問題。 為了減少查找的時間，可作如下兩種改進(jìn)： 第一：可以把可利用空間表中結(jié)點，按內(nèi)存單元地址的遞增順序鏈接起來。 2022/1/4 110/114 討論 這樣處理方法的優(yōu)點是可以解決存儲空間的共享問題，缺點是分配和回收的算法復(fù)雜了。 這就產(chǎn)生所謂“ 碎片問題 ”。系統(tǒng)能夠提供給動態(tài)分配的空間，常常不能滿足用戶的需求。這些結(jié)點曾經(jīng)屬于已利用空間，但是在刪除時沒有得到及時回收，所以它們既不在可利用空間的廣義表中，也不在已利用空間的廣義表中。 為了尋找無用結(jié)點，只要系統(tǒng)搜索（或稱周游）整個已利用空間的廣義表，凡是周游經(jīng)過的結(jié)點，都是有用的，可以做上標(biāo)志；凡是沒有周游到的結(jié)點（未做標(biāo)志的結(jié)點），都應(yīng)該回收。 2022/1/4 113/114 存儲壓縮 碎片 與廢料不同，它出現(xiàn)在可利用空間中，但是因為太小，長期無法分配使用。 所謂存儲壓縮，就是把有用的結(jié)點壓縮到動態(tài)區(qū)的一端，把可利用的結(jié)點（包括碎片）壓縮到動態(tài)區(qū)的另一端，使全部可利用的空間連成一片，構(gòu)成一個大的可利用塊。 2022/1/4 114/114 Qa