【正文】 組順序表存儲表示 define MAXSIZE 12500 //假設非零元個數的最大值為 12500 typedef struct{ int i,j。 ? 壓縮存儲原則：只存矩陣的 行列維數 和每個 非零元的行列下標及其值 。 0000000000468 5 1 67 8 21 9 32 1 200??????????對角矩陣 ? n階矩陣； ? 所有的 非零元都 集中 在以主對角線為中心的帶狀區(qū)域中 。 7273 1 74 9 8 60 0 0000??????????三角矩陣 ? n階矩陣； ? 下 （ 上 ）三角矩陣：矩陣的 上 （ 下 ）三角（不 包括對角線）中的元均為 常數 c或零。 77762342 1 93 1 84 9 8??????????7273 1 74 9 8 60 0 0000??????????0000000000468 5 1 67 8 21 9 32 1 200??????????0 0 0 00 0 00 0 0 00 0 0 0 00 0 0 048 1 6712??????????Data Structure Page 11 2022/8/22 特殊矩陣 ?特殊矩陣 ? 值相同的元素或者零元素在矩陣中的 分布有一定規(guī)律 。 ? LOC(0,0)表示數據元素 a00的存儲地址， 是數組的起始地址（基地址） 。 ? LOC(0,0)表示數據元素 a00的存儲地址， 是數組的起始地址（基地址） 。 ?有兩種映象方法： ? “ 以行 (序 )為主 (序 )” ：對二維數組進行 按行切分 ，即將數組中的數據元素 按行依次排放 在存儲器中； ? “ 以列 (序 )為主 (序 )”對二維數組進行 按列切分 ，即將數組中的數據元素 按列依次排放 在存儲器中。 操作結果：若下標不超界，則將 e 的值賦給 A中指定下標的元素。 Assign(amp。e, index1, ..., indexn) 初始條件： A 是 n 維數組， e 為元素變量，隨后是 n 個下標值。 操作結果：銷毀數組 A。 DestroyArray(amp。 ????????0 0 0 1 0 2 0 ,n 11 0 1 1 1 2 1 ,n 1m nm 1 ,0 m 1 ,1 m 1 ,2 m 1 ,n 1a a a . . . aa a a . . . aA=. . . . . . . . . . . . . . .a a a . . . a列向量 ????????0 0 0 1 0 2 0 ,n 11 0 1 1 1 2 1 ,n 1m nm 1 ,0 m 1 ,1 m 1 ,2 m 1 ,n 1a a a . . . aa a a . . . aA=. . . . . . . . . . . . . . .a a a . . . a行向量 Data Structure Page 3 2022/8/22 數組的抽象數據類型定義 ADT Array { 數據對象 ： ji=0,..., bi1, i=1,2,..,n D＝ {aj1,j2,...jn|n(0)為數組的維數， bi為數組第 i維的長度， ji為數組元素的第 i維下標， aj1,j2,...jn ∈ElemSet } 數據關系 ： R＝ {R1, R2, ..., Rn} Ri＝ { aj1,… ， ji, … ,jn, aj1,… ， ji+1, … ,jn | 0≤j k≤b k1, 1≤k≤n 且 k?i, 0≤j i≤b i2, aj1,… ， ji, … ,jn, aj1,… ， ji+1, … ,jn ∈D, i=2,...,n } Data Structure Page 4 2022/8/22 基本操作 InitArray(amp。 ?知識點 ? 數組的類型定義、數組的存儲表示、特殊矩陣的壓縮存儲表示方法、隨機稀疏矩陣的壓縮存儲表示方法 。 ? 理解 稀疏矩陣 的兩類存儲壓縮方法的特點及其適用范圍，領會以三元組表示稀疏矩陣時進行矩陣運算所采用的處理方法。Data Structure Page 1 2022/8/22 第五章 數組和廣義表 ?學習目標 ? 理解 多維數組類型 的特點及其在高級編程語言中的 存儲表示和實現方法 ，并掌握數組在 “ 以行為主 ” 的存儲表示中的地址計算方法。 ? 掌握 特殊矩陣的存儲壓縮 表示方法。 ?重點和難點 ? 重點是學習 數組類型 的定義及其 存儲表示 。 Data Structure Page 2 2022/8/22 數組的定義 ?數組是線性表的推廣 ? 數組可以看成是一種 特殊的線性表 ，即線性表中 數據元素本身也是一個線性表 。A, n, bound1, ..., boundn) 操作結果：若維數 n 和各維長度合法，則構造相應的數組 A。A) 初始條件：數組 A 已經存在。 Value(A, amp。 操作結果：若各下標不超界，則 e賦值為所指定的 A的元素值，并返回 OK。A, e, index1, ..., indexn) 初始條件： A 是 n 維數組， e 為元素變量，隨后是 n 個下標值。 } ADT Array Data Structure Page 5 2022/8/22 數組的順序表示和實現 ?用 一組連續(xù)的存儲單元 來表示數組。 ????????0 0 0 1 0 2 0 ,n 11 0 1 1 1 2 1 ,n 1m nm 1 ,0 m 1 ,1 m 1 ,2 m 1 ,n 1a a a . . . aa a a . . . aA=. . . . . . . . . . . . . . .a a a . . . aData Structure Page 6 2022/8/22 按行序為主序存放 am1,n1 …….. am1,1 am1,0 ……… a1,n1 …….. a11 a10 a0,n1 ……. a01 a00 0 1 n1 m*n1 n ????????1 0 1 1 1 2 1 ,n0 0 0 1 0 2 0 ,n mm 1 ,0 m 1 ,1 m 1 ,2 m 1 ,n1 n11......A=. . . . . . . . . . . . . . ....aaa a a aaaa a a aData Structure Page 7 2022/8/22 按列序為主序存放 am1 ,n1 …… .. a1,n1 a0,n1 ……… . am1,1 …… .. a11 a01 am1,1 …… . a10 a00 0 1 m1 m*n1 m ????????0 ,n 11 ,n 0 0212m nm 1111m 1 ,00,21m 1 ,n10m 0 1 11,a . . .a . . .A=. . . . . . . . . . . . . . .a . .aaa .aaaaaaData Structure Page 8 2022/8/22 按行序為主序存放 am1,n1 …….. am1,1 am1,0 ……… a1,n1 …….. a11 a10 a0,n1 ……. a01 a00 0 1 n1 m*n1 n ????????1 0 1 1 1 2 1 ,n0 0 0 1 0 2 0 ,n mm 1 ,0 m 1 ,1 m 1 ,2 m 1 ,n1 n11......A=. . . . . . . . . . . . . . ....aaa a a aaaa a a a? 每個