【正文】 n(n+1)/21]中。如下頁圖便是一個 5階對稱矩陣。 }// Assign 第五章 數(shù)組和廣義表 矩陣的壓縮存儲 特殊矩陣 所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。 *(+off)=e。A, ElemType e ,…){ va_start(ap,e)。 return OK。 // va_start(ap,A) if(result=Locate(A,ap,off)=0) return result。 //A和 e換順序 //若各下標(biāo)不超界，則 e賦值為所指定的 A 的元素值，并返回 OK。 }// Locate cj iiiof f ???d i m1第五章 數(shù)組和廣義表 Status Value(Array A, ElemType amp。 off+=[i]*ind。i++) { ind=va_arg(ap,int)。//最終 off帶回在存儲該元素時已經(jīng)存儲的元素個數(shù) For(i=0。 }// DestroyArray 第五章 數(shù)組和廣義表 Status Locate(Array A, va_list ap, int amp。A. constants =NULL。 if(!) return ERROR。 free()。=NULL。A){ //銷毀數(shù)組 A if(!) return ERROR。 return OK。i=0。//求映象函數(shù)的值 [dim1]=1。 A. constants=(int*)malloc(dim*sizeof(int))。 = (ElemType *)malloc(elemtotal*sizeof(ElemType))。 elemtotal*= [i]。i++) { [i]=va_arg(ap,int)。//ap為 va_list類型 ,存放變長參數(shù)表信息的數(shù)組 for(i=0。 //若各維長度合法 ,則存入 ,并求出元素總數(shù) elemtotal elemtotal=1。 =(int*)malloc(dim*sizeof(int))。A, int dim,…){ //若維數(shù) dim 和各維長度合法，構(gòu)造相應(yīng)的數(shù)組 A，并返回 OK if(dim1||dim MAX_ARRAY_DIM ) return ERROR。 //存放映象函數(shù)常量基址 ,由 InitArray分配 } Array。 //數(shù)組的維數(shù) int *bounds。 第五章 數(shù)組和廣義表 下面是數(shù)組順序存儲表示和實現(xiàn) //數(shù)組順序存儲表示 include // 標(biāo)準(zhǔn)頭文件 ,提供一個類型 va_list ,三個宏 va_start // va_arg 和 va_end 的定義 define MAX_ARRAY_DIM 8 //假設(shè)數(shù)組的最大維數(shù) typedef struct{ ElemType *base。由于計算各個元素存儲位置的時間相等，所以存取數(shù)組中任一元素的時間也相等。 (c1, c2, c3, ..., 1, )稱為 n 維數(shù)組的映象函數(shù) (常量 )。//我們所選擇的 2)以列序為主序 (高下標(biāo)優(yōu)先 )。 2) 數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。 操作結(jié)果： 若下標(biāo)不超界，則將 e的值賦給所指定的A的元素，并返回 OK。 第五章 數(shù)組和廣義表 Assign(amp。e, index1, ..., indexn) 初始條件： A是 n維數(shù)組， e為元素變量，隨后是 n 個下標(biāo)值。A) 操作結(jié)果：銷毀數(shù)組 A。A, n, bound1, ..., boundn) 操作結(jié)果：若維數(shù) n 和各維長度合法，構(gòu)造相應(yīng)的數(shù)組 A，并返回 OK。 typedef array1 array2[m]。例如，二維數(shù)組： 0 0 0 1 0 , 11 0 1 1 1 , 11 , 0 1 , 1 1 , 1.. . .. ... . .. ... . .. . .. . .. . .. ... . .. .nnmnm m m na a aa a aAa a a???? ? ? ??????????(a) a01 a11 am1,1 a0,n1 a1 ,n1 am1 ,n1 a00 a10 am1,0 Am n= (b) Am n=（（ a00,a01,…,a 0,n1),(a10,a11,…,a 1,n1),…(a m1,0 , am1,1,…,a m1,n1)) (c) 第五章 數(shù)組和廣義表 typedef Elemtype array2[m][n]。第五章 數(shù)組和廣義表 數(shù)組的類型定義 稀疏矩陣的壓縮存儲 數(shù)組的順序表示和實現(xiàn) 廣義表的類型定義 廣義表的表示方法 廣義表操作的遞歸函數(shù) 本章小結(jié) 習(xí) 題 第五章 數(shù)組和廣義表 數(shù)組的類型定義 由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是向量的推廣。 等價于： typedef Elemtype array1[n]。 一般地：多維數(shù)組的定義如下頁所示： 第五章 數(shù)組和廣義表 ADT Array { 數(shù)據(jù)對象： D＝ {aj1,j2, ...,ji,jn| ji =0,...,bi 1, i=1,2,..,n } 數(shù)據(jù)關(guān)系： R＝ {R1, R2, ..., Rn} Ri＝ {aj1,... ji,... jn , aj1, ...ji +1, ...jn | 0 ? jk ? bk 1, 1 ? k ? n 且 k ? i, 0 ? ji ? bi 2, i=2,...,n } 基本操作 : } ADT Array 第五章 數(shù)組和廣義表 InitArray(amp。 DestroyArray(amp。 Value(A, amp。 操作結(jié)果： 若各下標(biāo)不超界，則 e賦值為所指定的 A 的元素值，并返回 OK。A, e, index1, ..., indexn) 初始條件： A是 n維數(shù)組， e為元素變量，隨后是 n 個下標(biāo)值。 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。 第五章 數(shù)組和廣義表 二維數(shù)組的抽象定義 : 數(shù)據(jù)對象 : D = {aij | 0≤i≤b11, 0 ≤j≤b21} 數(shù)據(jù)關(guān)系 : R = { ROW, COL } ROW = {aij,ai+1j| 0≤i≤b12, 0≤j≤b21} COL = {aij,aij+1| 0≤i≤b11, 0≤ j≤b22} 第五章 數(shù)組和廣義表 數(shù)組的順序表示和實現(xiàn) 類型特點 : 1) 只有引用型操作，沒有加工型操作 。 有兩種順序映象的方式 : 1)以行序為主序 (低下標(biāo)優(yōu)先 )。 以“行序為主序”的存儲映象 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 L 第五章 數(shù)組和廣義表 按行序為主序存放 0 1 n1 m*n1 n am1n1 …….. am11 am10 ………. a1n1 …….. a11 a10 a0n1 ……. a01 a00 a00 a01 …….. a0n1 a10 a11 …….. a1n1 am10 am11 …… am1n1 …………………. Loc(i,j)=Loc(0,0)+[n*i+ j]*L 第五章 數(shù)組和廣義表 二維數(shù)組 A中任一元素 aij 的存儲位置 LOC(i,j) = LOC(0,0) + (b2 i＋ j) L 稱為基地址或基址 每個元素占 L個存儲單元 已經(jīng)存儲的元素數(shù) LOC(j1,j2) = LOC(0,0) + (b2 j1＋ j2) L LOC(j1,j2,j2)=LOC(0,0,0)+(b2 b3 j1＋ b3 j2＋ j3 ) L LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + (b2 b3 … bn j1+ b3 b4 …b n j2+ … +b n jn1+jn) L 第五章 數(shù)組和廣義表 推廣到一般情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系： ? ?nn 1i k ni = 1 k = i + 1( j b + j ) * L ? LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + (b2 b3 … bn j1+ b3 …b n j2+ b4 …b n j3+ …+b n1 bn jn2+bn jn1+jn) L = LOC(0,0,...,0) + = LOC(0,0,...,0) + ?niii = 1cj其中 = L， ci1 = bi ci , 1 i ? n。數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù) 第五章 數(shù)組和廣義表 = L， 1 = bn L= bn 2 = bn1 bn L= bn1 1 3 = bn2 bn1 bn L= bn2 2 … c3 = b4 b5 … bn L= b4 c4 c2= b3 b4 b5 … bn L= b3 c3 c1= b2 b3 b4 b5 … bn L= b2 c2 ci1 = bi ci Lnikki bC ?? ??? 1設(shè) 第五章 數(shù)組和廣義表 容易看出，數(shù)組元素的存儲位置是其下標(biāo)的線性函數(shù)，一旦確定了數(shù)組的各維的長度， ci 就是常數(shù)。我們稱具有這一特點的存儲結(jié)構(gòu)為隨機存儲結(jié)構(gòu)。//存儲數(shù)組元素的首地址 (基址 ),由 InitArray分配 int dim。 //存放數(shù)組維界的基地址 ,由 InitArray分配 int *constants。 第五章 數(shù)組和廣義表 Status InitArray(Array amp。 =dim。 if(! ) exi