【正文】 一個 行后繼 a23，在列上有一個 列前驅(qū) a12和和一個 列后繼 a32。那么，這個數(shù)組的體積是 個字節(jié)。 ６ .什么叫特殊矩陣？ 若值 相同的元素 或者 零元素 在矩陣中的分布 有一定規(guī)律 ，則該類矩陣稱為特殊矩陣。 row：存儲非零元素的行號 col：存儲非零元素的列號 item：存儲非零元素的值 right：指針域，指向同一行中的下一個三元組 down：指針域，指向同一列中的下一個三元組 right down item col row 十字鏈表的特點： ① 每行非零元素鏈接 成帶表頭結(jié)點的鏈表 (或循環(huán)鏈表 ) ； ② 每列非零元素也鏈接 成帶表頭結(jié)點的鏈表 (或循環(huán)鏈表 )。 4. GetTail【 GetHead【 ((a,b),(c,d))】】 ＝ 。 (()):長度為 1,深度為 2。 0 12 9 0 0 0 0 0 0 0 0 0 3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 7 0 0 二、稀疏矩陣 １、稀疏矩陣的壓縮存儲 問題： 如果只存儲 稀疏矩陣中的非零元素，那這些元素的 位置信息 該如何表示？ 解決思路： 對每個非零元素 增開 若干存儲單元，例如存放其所在的 行號 和 列號 ，便可 準確 反映該元素所在 位置 。如何 節(jié)省空間 。 0 n1 0 m1 (a) 二維數(shù)組 本行中 aij前面的元素個數(shù) 每行元素個數(shù) 整行數(shù) aij 按 行 優(yōu)先存儲的尋址 aij前面的元素個數(shù) =陰影部分的面積 =整行數(shù) 每行元素個數(shù) +本行中 aij前面的元素個數(shù) =(i 0) (n1 0＋ 1)＋ (j 0) LOC(aij)=LOC(a00)+[i*n+j]*L c2 b2 c1 b1 (a) 二維數(shù)組 aij前面的元素個數(shù) =陰影部分的面積 =整行數(shù) 每行元素個數(shù) +本行中aij前面的元素個數(shù) =(i c1) (b2 c2＋ 1)＋ (j c2) 本行中 aij前面的元素個數(shù) 每行元素個數(shù) 整行數(shù) aij 通用按 行 優(yōu)先存儲的尋址公式： 數(shù)組大小 ： （ b1c1+1） *（ b2c2+1） 。 ④ 數(shù)組有 順序存儲 和 鏈式存儲 兩種方式。表頭、表尾 串 —— 零個或多個字符組成的有限序列 。 a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn A= A=(A1， A2， …… ， An) 其中： Ai=(a1i， a2i， …… ， ami) (1≤i≤n) 二維數(shù)組是數(shù)據(jù)元素為一維數(shù)組（線性表）的線性表。 288 例 設(shè)數(shù)組 a[1…60, 1…70] 的基地址為 2048，每個元素占 2個存儲單元，若以 列 序為主序順序存儲，則元素 a[32,58]的存儲地址為 。 ７ .什么叫稀疏矩陣？（重點） 若值 相同的元素 或者 零元素 在矩陣中的分布 不具有規(guī)律 ，且矩陣中 非零元素 的 個數(shù)較少 （一般 小于 5%）時。 則每個非零元素既是行鏈表中的一個結(jié)點；又是列鏈表中的一個結(jié)點，即 呈十字鏈狀 。 實訓(xùn) 3： 求下列廣義表操作的結(jié)果 (k, p, h) （ b） (a,b) 5. GetTail【 （ e） 】 ＝ 。 廣義表 ( )和廣義表 (( ))不同？ ():長度為 0，深度為 1。 特殊矩陣的壓縮存儲 —— 三角矩陣 3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7 (a) 下三角矩陣 3 4 8 1 0 c 2 9 4 6 c c １ 5 7 c c c 0 8 c