【正文】 地址法和三元組法相似，只是數(shù)組的每個(gè)結(jié)點(diǎn)只包括兩個(gè)字段，分別為矩陣非零元素的偽地址和值。 這種方法需用 2k個(gè)存儲(chǔ)單元，比三元組法要節(jié)省，它付出的代價(jià)是計(jì)算偽地址，而偽地址是很好算的，元素 aij的偽地址為 i*n+j。 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) 帶輔助行向量的二元組表示法 這個(gè)方法是三元組表示法的一個(gè)變種。在三元組表示法中，去掉行下標(biāo)字段，而加上一個(gè)有ｍ＋１個(gè)元素的輔助行向量 NRA ，它的值定義如下： NRA[0] = 0。 NRA [i] = NRA[i1] + 矩陣第 i1行中非零元素的個(gè)數(shù) 用帶輔助行向量的二元組表示法表示稀疏矩陣，每個(gè)非零元素只需要兩個(gè)字段表示：分別為非零元素的列下標(biāo)和值。 2022/1/4 85/114 2022/1/4 86/114 (4) 行 列表示法 矩陣的一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，每個(gè)結(jié)點(diǎn)包括五個(gè)字段，分別為元素的行下標(biāo)、列下標(biāo)、值，以及指向本行下一個(gè)非零元素的指針和指向本列下一個(gè)非零元素的指針。另外還有行的頭指針向量和列的頭指針向量，行的頭指針向量有ｍ個(gè)元素，分別指向代表各行的第一個(gè)非零元素的結(jié)點(diǎn)。列的頭指針向量有ｎ個(gè)元素，分別指向代表各列的第一個(gè)非零元素的結(jié)點(diǎn)。 2022/1/4 87/114 2022/1/4 88/114 討論 時(shí)間代價(jià)和空間代價(jià)始終是數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的最主要因素，然而它們往往是相互對(duì)立的。 一個(gè)好的設(shè)計(jì)總是在時(shí)間代價(jià)和空間代價(jià)之間作出了一個(gè)好的權(quán)衡，而這種權(quán)衡的標(biāo)準(zhǔn)需要根據(jù)實(shí)際計(jì)算機(jī)的資源情況和求解問(wèn)題的特點(diǎn)來(lái)確定。 順序表和單鏈表是兩種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，但是它們的應(yīng)用非常廣泛。本節(jié)中對(duì)于稀疏矩陣的所有表示都是這兩種結(jié)構(gòu)的擴(kuò)充和組合。 稀疏矩陣本身也是許多復(fù)雜結(jié)構(gòu)的抽象。 2022/1/4 89/114 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動(dòng)態(tài)存儲(chǔ)管理 2022/1/4 90/114 廣義表是線性表的推廣，具有廣泛的應(yīng)用價(jià)值。它是表處理語(yǔ)言（例如 LISP）的基礎(chǔ)結(jié)構(gòu)，也可以用于表示動(dòng)態(tài)存儲(chǔ)空間的整體模型。 2022/1/4 91/114 從邏輯上看， 廣義表 也是零個(gè)或多個(gè)元素組成的序列。但是，廣義表中的元素允許以不同形式出現(xiàn) :它可以是一個(gè)原子（邏輯上不能再分解的元素），也可以又是一個(gè)廣義表。 作為廣義表元素的廣義表稱作廣義表的子（廣義）表。一個(gè)廣義表還允許直接或間接地作為它自身的子（廣義）表。 為了區(qū)分廣義表和原子，可以用圓括號(hào)把一個(gè)廣義表括起來(lái)，再用逗號(hào)來(lái)分隔廣義表中的元素。 一個(gè)廣義表中所包含的元素的個(gè)數(shù)，稱為這個(gè)廣義表的長(zhǎng)度。長(zhǎng)度為零的廣義表稱為空（廣義）表。 一個(gè)廣義表的 深度 ，就是指廣義表中所含子表的層數(shù)。 廣義表 2022/1/4 92/114 書寫中約定：用大寫字母表示廣義表，用小寫字母表示原子。例如： Ｅ＝（） Ｌ＝（ａ，ｂ） Ａ＝（ｘ，Ｌ）＝（ｘ，（ａ，ｂ）） Ｂ＝（Ａ，ｙ）＝（（ｘ，（ａ，ｂ）），ｙ） Ｃ＝（Ａ，Ｂ）＝（（ｘ，（ａ，ｂ）），（（ｘ，（ａ，ｂ）），ｙ）） Ｄ＝（ｚ，Ｄ）＝（ｚ，（ｚ，（ｚ … ））） 2022/1/4 93/114 廣義表的分類 如果廣義表中的元素全部都是原子（例如廣義表Ｌ），這種廣義表就是 線性表 ； 如果廣義表中的元素允許有子廣義表，但所有各層子廣義表均無(wú)共享（例如廣義表Ａ、Ｂ），這種廣義表，稱為 純表 ； 在各層子廣義表中允許共享的廣義表（例如廣義表Ｃ的子表 B中共享了 A），稱為 再入表 ； 允許（子）廣義表直接（或間接）地把作為自己的子廣義表時(shí)，這樣的廣義表（例如廣義表Ｄ），稱為 遞歸表 。 2022/1/4 94/114 廣義表的操作 建立一個(gè)廣義表； 取廣義表的頭一個(gè)元素； 在廣義表中插入一個(gè)元素， 刪除一個(gè)元素； 取刪除頭一個(gè)元素后的廣義表； 把一個(gè)廣義表拆成兩個(gè)部分； 把兩個(gè)廣義表合并成一個(gè)新廣義表； 周游一個(gè)廣義表； 拷貝一個(gè)廣義表； 判別某元素是否原子； 判別兩個(gè)廣義表是否相等； 判別某廣義表是否空廣義表 …… 2022/1/4 95/114 廣義表的表示方法主要有： 單鏈表示法 帶頭結(jié)點(diǎn)的單鏈表示法 2022/1/4 96/114 單鏈表示法 每個(gè)結(jié)點(diǎn)由三個(gè)字段組成： atom， info， link。 其中 atom是一標(biāo)志位： atom＝ 0表示本結(jié)點(diǎn)為子廣義表，這時(shí)字段 info存放子廣義表中第一個(gè)元素所對(duì)應(yīng)結(jié)點(diǎn)的地址； atom＝ 1表示本結(jié)點(diǎn)為原子，字段 info存放本原子的信息（當(dāng)信息量比較大時(shí)，也可以存放本原子信息存放的地址）。 字段 link存放與本元素同層的下一個(gè)元素所對(duì)應(yīng)結(jié)點(diǎn)的地址，當(dāng)本元素是所在層的最后一個(gè)元素時(shí)， link＝ NULL。 2022/1/4 97/114 2022/1/4 98/114 帶頭結(jié)點(diǎn)的單鏈表示法 上述單鏈表示法的一個(gè)主要缺點(diǎn)是：如果要?jiǎng)h除廣義表（或子廣義表）中某一元素（例如刪除 A中的 x）則需要搜索廣義表中所有結(jié)點(diǎn)后才能進(jìn)行。 解決辦法：對(duì)每個(gè)子廣義表，增設(shè)一個(gè)廣義表頭結(jié)點(diǎn)。 為區(qū)分是一般結(jié)點(diǎn)或者是表頭結(jié)點(diǎn)，不妨令表頭結(jié)點(diǎn) atom字段為 1；表頭結(jié)點(diǎn)的 info字段可以用來(lái)存放本廣義表（或子廣義表）的有關(guān)信息，表頭結(jié)點(diǎn)的 link字段指向廣義表中第一個(gè)元素對(duì)應(yīng)的結(jié)點(diǎn)。 2022/1/4 99/114 2022/1/4 100/114 單鏈表中的元素的個(gè)數(shù)是任意的，允許自由變化。 習(xí)慣上把這種在使用期間，可自由插入和刪除的數(shù)據(jù)結(jié)構(gòu)稱為 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) 。 在程序運(yùn)行過(guò)程中，對(duì)于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)的分配和回收需要采用 動(dòng)態(tài)存儲(chǔ)管理 的方法。 結(jié)點(diǎn)的動(dòng)態(tài)分配與回收 2022/1/4 101/114 在前面的討論中，當(dāng)單鏈表插入值為 x的元素時(shí)，只需調(diào)用函數(shù) malloc，便能得到一個(gè)所需結(jié)點(diǎn)的空間，并返回這個(gè)結(jié)點(diǎn)的起始地址； 在某指針?biāo)赶虻慕Y(jié)點(diǎn)刪除后，調(diào)用函數(shù) free，就可以將該結(jié)點(diǎn)所占的空間釋放，以利于再分配。 函數(shù) malloc和 free就是實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)管理的兩個(gè)最基本的函數(shù)。 2022/1/4 102/114 等長(zhǎng)結(jié)點(diǎn)的分配與回收 可利用空間表 2022/1/4 103/114 不等長(zhǎng)結(jié)點(diǎn)的分配與回收 一個(gè)處理方法是，在動(dòng)態(tài)區(qū)中建立多個(gè)可利用空間表，每個(gè)可利用空間表對(duì)應(yīng)一種固定長(zhǎng)度的結(jié)點(diǎn)。缺點(diǎn)是，難以真正解決多個(gè)可利用空間表的共享問(wèn)題。另外，要管理多個(gè)可利用空間表，系統(tǒng)開(kāi)銷也較大。（不詳細(xì)討論） 另一種辦法是：組織一個(gè)可以管理各種大小結(jié)點(diǎn)的可利用空間表。分配時(shí)按申請(qǐng)的長(zhǎng)度在可利用空間表中進(jìn)行檢索，找到其長(zhǎng)度大于或等于申請(qǐng)長(zhǎng)度的結(jié)點(diǎn)，從中截取合適的長(zhǎng)度?；厥諘r(shí)考慮剛剛被刪除的結(jié)點(diǎn)空間能否與可利用空間表中的某些結(jié)點(diǎn)合并，組成較大的結(jié)點(diǎn)。 2022/1/4 104/114 為了便于管理，在不等長(zhǎng)的可利用空間表中，每個(gè)結(jié)點(diǎn)除了要有一個(gè) link字段指向表中下一個(gè)結(jié)點(diǎn)以外，還應(yīng)有一個(gè)存放本結(jié)點(diǎn)大小的字段 size。系統(tǒng)運(yùn)行初期，整個(gè)動(dòng)態(tài)區(qū)就可以看成一個(gè)大的結(jié)點(diǎn)（稱為 可利用塊 ）。 2022/1/4 105/114 動(dòng)態(tài)分配 1. 最佳適配 檢索可利用空間表中的全部結(jié)點(diǎn)，在所有 size≥N的塊中，找出最小的一塊進(jìn)行分配，這種分配策略稱為最佳適配。 2. 首先適配 如果在可利用空間表中，找到第一個(gè) size≥N的可利用塊就進(jìn)行分配，則稱為首先適配。 3. 最大適配 如果在可利用空間表中，每次都用最大的可利用塊來(lái)分配，當(dāng)最大的塊長(zhǎng)度小于Ｎ時(shí)，則分配失敗。這種方法稱為最大適配。 2022/1/4 106/114 例 1：最佳適配分配過(guò)程 2022/1/4 107/114 例 2：首先適配分配 2022/1/4 108/114 例 3：最大適配分配 2022/1/4 109/114 回收過(guò)程 必須隨時(shí)考查能否和相鄰的塊合并的問(wèn)題。如果在可利用空間表中有與被釋放的結(jié)點(diǎn)相鄰的可利用塊，應(yīng)把它合關(guān)成較大的可利用塊。 為了減少查找的時(shí)間，可作如下兩種改進(jìn)： 第一：可以把可利用空間表中結(jié)點(diǎn)，按內(nèi)存單元地址的遞增順序鏈接起來(lái)。 第二：可以在每個(gè)結(jié)點(diǎn)（包括已分配結(jié)點(diǎn)和可利用塊）的兩端各加上一個(gè)標(biāo)志位 tag，已分配的 tag = 1，可利用的 tag = 0；在可利用塊的兩端都標(biāo)明 size字段，并將可利用塊之間的鏈接方式，改換成雙鏈循環(huán)表結(jié)構(gòu)，分別指向本可利用塊在可利用空間表中的前驅(qū)和后繼。 2022/1/4 110/114 討論 這樣處理方法的優(yōu)點(diǎn)是可以解決存儲(chǔ)空間的共享問(wèn)題，缺點(diǎn)是分配和回收的算法復(fù)雜了。 另外，在系統(tǒng)長(zhǎng)期動(dòng)態(tài)運(yùn)行的過(guò)程中，這種方法有可能使整個(gè)空間被分割成許多大小不等的碎塊，而某些碎塊由于太小而長(zhǎng)期得不到使用。 這就產(chǎn)生所謂“ 碎片問(wèn)題 ”。 2022/1/4 111/114 內(nèi)存的資源是有限的，加上存儲(chǔ)管理功能的限制和使用的不當(dāng)，隨著系統(tǒng)的長(zhǎng)期運(yùn)行，動(dòng)態(tài)區(qū)可能出現(xiàn)嚴(yán)重的浪費(fèi)。系統(tǒng)能夠提供給動(dòng)態(tài)分配的空間，常常不能滿足用戶的需求。下面介紹的廢料收集和存儲(chǔ)壓縮技術(shù)，就是在動(dòng)態(tài)區(qū)快要溢出時(shí)的補(bǔ)救方法 廢料收集與存儲(chǔ)壓縮 2022/1/4 112/114 廢料收集 在動(dòng)態(tài)區(qū)中還可能存在一些被無(wú)用結(jié)點(diǎn)占用的空間，簡(jiǎn)稱為 無(wú)用結(jié)點(diǎn) （也稱為 廢料 ）。這些結(jié)點(diǎn)曾經(jīng)屬于已利用空間，但是在刪除時(shí)沒(méi)有得到及時(shí)回收，所以它們既不在可利用空間的廣義表中，也不在已利用空間的廣義表中。 廢料收集 需要解決的問(wèn)題是：從整個(gè)動(dòng)態(tài)區(qū)的已利用空間中，找出哪些結(jié)點(diǎn)是無(wú)用結(jié)點(diǎn)，并且把它們送入可利用空間表中。 為了尋找無(wú)用結(jié)點(diǎn)，只要系統(tǒng)搜索（或稱周游）整個(gè)已利用空間的廣義表，凡是周游經(jīng)過(guò)的結(jié)點(diǎn)，都是有用的，可以做上標(biāo)志；凡是沒(méi)有周游到的結(jié)點(diǎn)（未做標(biāo)志的結(jié)點(diǎn)），都應(yīng)該回收。 在執(zhí)行周游和標(biāo)志的算法以后，只要掃描一遍動(dòng)態(tài)區(qū)，將所有未做標(biāo)志的結(jié)點(diǎn)（包括原來(lái)就在可利用空間表中的結(jié)點(diǎn)和廢料）全部送入可利用空間表中，即完成了廢料的回收。 2022/1/4 113/114 存儲(chǔ)壓縮 碎片 與廢料不同，它出現(xiàn)在可利用空間中，但是因?yàn)樘?，長(zhǎng)期無(wú)法分配使用。 為了從根本上解決碎片問(wèn)題，可以采用 存儲(chǔ)壓縮 的方法。 所謂存儲(chǔ)壓縮，就是把有用的結(jié)點(diǎn)壓縮到動(dòng)態(tài)區(qū)的一端，把可利用的結(jié)點(diǎn)（包括碎片）壓縮到動(dòng)態(tài)區(qū)的另一端，使全部可利用的空間連成一片，構(gòu)成一個(gè)大的可利用塊。 在實(shí)際系統(tǒng)中，常常把廢料的收集和存儲(chǔ)壓縮一起進(jìn)行。 2022/1/4 114/114 Qamp。A 2022/1/4 115/114