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