【正文】 2022/1/4 114/114 Qamp。 2022/1/4 113/114 存儲(chǔ)壓縮 碎片 與廢料不同，它出現(xiàn)在可利用空間中，但是因?yàn)樘?，長期無法分配使用。這些結(jié)點(diǎn)曾經(jīng)屬于已利用空間，但是在刪除時(shí)沒有得到及時(shí)回收，所以它們既不在可利用空間的廣義表中，也不在已利用空間的廣義表中。 這就產(chǎn)生所謂“ 碎片問題 ”。 為了減少查找的時(shí)間，可作如下兩種改進(jìn)： 第一：可以把可利用空間表中結(jié)點(diǎn)，按內(nèi)存單元地址的遞增順序鏈接起來。 3. 最大適配 如果在可利用空間表中，每次都用最大的可利用塊來分配，當(dāng)最大的塊長度小于Ｎ時(shí)，則分配失敗。 2022/1/4 104/114 為了便于管理，在不等長的可利用空間表中，每個(gè)結(jié)點(diǎn)除了要有一個(gè) link字段指向表中下一個(gè)結(jié)點(diǎn)以外，還應(yīng)有一個(gè)存放本結(jié)點(diǎn)大小的字段 size。另外，要管理多個(gè)可利用空間表，系統(tǒng)開銷也較大。 結(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)所占的空間釋放，以利于再分配。 為區(qū)分是一般結(jié)點(diǎn)或者是表頭結(jié)點(diǎn)，不妨令表頭結(jié)點(diǎn) atom字段為 1；表頭結(jié)點(diǎn)的 info字段可以用來存放本廣義表（或子廣義表）的有關(guān)信息，表頭結(jié)點(diǎn)的 link字段指向廣義表中第一個(gè)元素對(duì)應(yīng)的結(jié)點(diǎn)。 其中 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í)，也可以存放本原子信息存放的地址）。 一個(gè)廣義表的 深度 ，就是指廣義表中所含子表的層數(shù)。一個(gè)廣義表還允許直接或間接地作為它自身的子（廣義）表。它是表處理語言（例如 LISP）的基礎(chǔ)結(jié)構(gòu)，也可以用于表示動(dòng)態(tài)存儲(chǔ)空間的整體模型。 順序表和單鏈表是兩種最簡單的數(shù)據(jù)結(jié)構(gòu)，但是它們的應(yīng)用非常廣泛。另外還有行的頭指針向量和列的頭指針向量，行的頭指針向量有ｍ個(gè)元素，分別指向代表各行的第一個(gè)非零元素的結(jié)點(diǎn)。 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è)變種。為了保持表示的行優(yōu)先順序，以便進(jìn)行二分法檢索，那么插入時(shí)就必須在存儲(chǔ)器里移動(dòng)所有后面的元素。 設(shè)行下標(biāo)和列下標(biāo)也占一個(gè)存儲(chǔ)單元，那么這種方法需要 3k個(gè)存儲(chǔ)單元 2022/1/4 80/114 2022/1/4 81/114 對(duì)于矩陣 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)也占一個(gè)存儲(chǔ)單元，那么這種方法需要３ｋ個(gè)存儲(chǔ)單元（ｋ為非零元素個(gè)數(shù)，在上面的例子中 k=8）。 存儲(chǔ)稀疏矩陣的方法是多種多樣的，下面介紹其中幾種： (1) 三元組表示法 (2) 偽地址表示法 (3) 帶輔助行向量的二元組表示法 (4) 行 列表示法 稀疏矩陣的表示方法 2022/1/4 79/114 (1) 三元組表示法 這個(gè)方法用一個(gè)數(shù)組（順序結(jié)構(gòu)）來表示稀疏矩陣。 } 基本概 念與 ADT 順序表示 鏈接表示 應(yīng)用舉例 矩陣 廣義表與動(dòng)態(tài)存儲(chǔ)管理 2022/1/4 74/114 矩陣作為一種線性表的推廣 在矩陣的邏輯結(jié)構(gòu) (K, R)中，可以定義 K是一個(gè)線性表的集合， R是 K上的一個(gè)線性關(guān)系。 if (init_clist(amp。 do { printf( please input the values of m = )。 do { printf( please input the values of s = )。 /*輸入所需各參數(shù)的值 */ do { printf(\n please input the values of n = )。 *pclist=NULL。 prelink = plink。i++) { pre = p。i++) { pre =p。 while (p!=*pclist) { pre =p。 int i。 qlink=p。i++) { p=(PNode)malloc(sizeof(struct Node))。 qlink = q。 q = (PNode)malloc(sizeof(struct Node))。 (b) 從 p所指結(jié)點(diǎn)開始計(jì)數(shù)尋找第 m個(gè)結(jié)點(diǎn) 。 josephus_seq(jos_alist,s,m)。 PSeqList jos_alist=createNullList_seq( n )。s)。 scanf(%d,amp。 /*求下標(biāo)為 s1的元素的值 */ printf(Out element %d \n, w)。 for(i = palistn。 Josephus問題： 對(duì)于任意給定的 n, s和 m，求出按出列次序得到的 n個(gè)人員的序列 Josephus問題 2022/1/4 63/114 2022/1/4 64/114 以 n=8， s=1， m=4為例 (a) n4 (b) n4n8 (c) n4n8n5 (d) n4n8n5n2 2022/1/4 65/114 (e) n4n8n5n2n1 (f) n4n8n5n2n1n3 (g) n4n8n5n2n1n3n7 (h) n4n8n5n2n1n3n7n6 求解 Josephus問題的一般步驟： (1) 利用線性表的一些運(yùn)算 構(gòu)造 Josephus表 。 qrlink = prlink。 prlinkllink = pllink。 struct DoubleList { /*雙鏈表類型 */ PDoubleNode head。 /*雙鏈表結(jié)點(diǎn) */ typedef struct DoubleNode * PDoubleNode。 先調(diào) 用 locatePre_link(llist, p )找到 p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 然后實(shí)現(xiàn)結(jié)點(diǎn)刪除。 /*找到值為 x的結(jié)點(diǎn) */ plink = qlink。 plinkinfo != x ) p = plink。 p = llist。 p1link != p ) p1 = p1link。 if (llist==NULL) return(NULL)。 qlink = plink。 注意： (1)、 (2)順序不能反！ 2022/1/4 48/114 int insertPost_link(LinkList llist, PNode p, DataType x) { /*在 llist帶頭結(jié)點(diǎn)的單鏈表中 ,p所指結(jié)點(diǎn)后面插入元素 x */ PNode q = (PNode)malloc(sizeof( struct Node))。 pinfo != x) p = plink。 if (llist==NULL) return(NULL)。 /*創(chuàng)建失敗 */ return (llist)。 }。 }。 單鏈表表示 2022/1/4 39/114 2022/1/4 40/114 結(jié)點(diǎn)類型和單鏈表類型定義： [說明 ] PNode與 LinkList實(shí)為同一類型，既可以是指向某一結(jié)點(diǎn)的指針類型，也可以看成單鏈表的類型 (即頭指針的類型 ) 2022/1/4 41/114 struct Node。 palistMAXNUM *=2。 return 0。=1/(n+1)，則有： 2022/1/4 31/114 因此，刪除和插入算法的時(shí)間復(fù)雜度為： T(n)=O(n) 觀察插入算法： 如何補(bǔ)救？ 重新申請(qǐng)一個(gè)比較大（如原數(shù)組大小 *2）的數(shù)組，以代替原來的數(shù)組 順序表空間的擴(kuò)展 2022/1/4 32/114 int insertPre_seq(PSeqList palist, int p, DataType x) { … … if ( palistn = palist MAXNUM) { /*溢出 */ printf(Overflow! \n)。 palistn = palistn 1。 return 0。 /*插入元素 x*/ palistn = palistn + 1。 } for(q=palistn 1。 if ( palistn = palist MAXNUM) { /*溢出 */ printf(Overflow! \n)。 qpalistn 。 /*存儲(chǔ)分配失敗 */