數(shù)組與廣義表

1、本章主要內(nèi)容：本章主要內(nèi)容：數(shù)組及其運(yùn)算數(shù)組及其運(yùn)算數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的順序存儲結(jié)構(gòu)矩陣的壓縮存儲矩陣的壓縮存儲q特殊矩陣特殊矩陣三角矩陣三角矩陣對稱矩陣對稱矩陣q稀疏矩陣稀疏矩陣三元組順序表三元組順序表十字鏈表十字鏈表廣義表廣義表1. 1. 數(shù)組及其運(yùn)算數(shù)組及其運(yùn)算Amxn= a00 a01 a0n-1a10 a11 a1n-1 . . . .am-10 am-12 am-1n-1Amxn= a00 a01 a0n-1a10 a11 a1n-1 . . . .am-10 am-12 am-1n-1a00 a01 a0n-1a10 a11 a1n-1 . . . .am-10 am-12

2、am-1n-1Amxn= a00 a01 a0n-1a10 a11 a1n-1 . . . .am-10 am-12 am-1n-1這樣二維數(shù)組轉(zhuǎn)換為線性表結(jié)構(gòu)，每個元素本身又是一個線性表。兩種不同的構(gòu)造得出數(shù)組的兩種不同的存儲結(jié)構(gòu)。多維問題：三維可以看成多個二維構(gòu)成的線性表；n維可以看成有多個n-1維構(gòu)成的線性表。數(shù)組運(yùn)算：只有存取、修改運(yùn)算。2. 2. 數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的順序存儲結(jié)構(gòu) 由于數(shù)組的運(yùn)算只有存取和修改操作，因此數(shù)組一般采用順序存儲結(jié)構(gòu)，即：一片地址連續(xù)的存儲空間存儲數(shù)組中的元素。但是，由于數(shù)組是多維結(jié)構(gòu)，而存儲單元是一維結(jié)構(gòu)，這樣必須按照某種次序?qū)?shù)組元素排成一個線性序列

3、。 例如：二維數(shù)組既可以看作是由每一行的所有元素作為一個元素構(gòu)成的一維數(shù)組，也可以看作是由每一列的所有元素作為一個元素構(gòu)成的一維數(shù)組。從而導(dǎo)致兩種不同的存儲方式：行優(yōu)先和列優(yōu)先的存儲方式。行優(yōu)先行優(yōu)先：C, PASCALC, PASCAL等，先存儲完一行中的所有元素，再存儲下一行。等，先存儲完一行中的所有元素，再存儲下一行。列優(yōu)先列優(yōu)先：FORTRANFORTRAN等，先存儲完一列中的所有元素，再存儲下一列。等，先存儲完一列中的所有元素，再存儲下一列。a00a01a02am-1 n-1a0 n-1a10a00a10a20am-1 n-1a m-1 0a01LOC(aij )=LOC(a00)+

4、(i*n+j)*cLOC(aij)=LOC(a00)+(j*m+i)*cm行n列,每個元素占c個存儲單元三維數(shù)組定位： 行優(yōu)先： LOC(akij) = LOC(a000)+(k*m*n+i*n+j)*c 列優(yōu)先： LOC(akij) = LOC(a000)+(k*m*n+j*m+i)*c3. 3. 矩陣的壓縮存儲矩陣的壓縮存儲二維數(shù)組存儲矩陣。特殊矩陣：矩陣中具有相同值的元素的排列具有規(guī)律。稀疏矩陣：矩陣中具有相同值的元素的排列沒有規(guī)律。（1）特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲 (a) 三角矩陣：用n(n+1)/2+1個單元存儲構(gòu)成的線性表存儲。 給定行列，如何確定在線性表中的位置？ 給定

5、線性表中的一個位置，如何確定行列？ 上三角？ 下三角？ (b) 對稱矩陣：aij = aji 存儲：有n(n+1)/2個單元構(gòu)成的線性表； 定位：給定行列，如何確定在線性表中的位置？ 給定線性表中的一個位置，如何確定行列？（2）稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 定義：矩陣中非空元素個數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素個數(shù)， 并且空元素排列無規(guī)律。 存儲：存儲非空元素的同時，存儲位置輔助信息：(i, j, aij) (i, j, aij)稱為一個三元組，唯一表達(dá)一個非空元素。 存儲方式：這些三元組如何組織，方便矩陣的運(yùn)算？ (a) 三元組順序表：三元組構(gòu)成的順序表作為稀疏矩陣的壓縮存儲 方式，便于矩陣的轉(zhuǎn)置

6、、相乘等操作。 #define maxsize struct node int i, j; datatype v; ;Struct matrix int mu, nu, tu; struct node datamaxsize; (b) 十字鏈表：三元組構(gòu)成的鏈表作為稀疏矩陣的壓縮存儲方式， 便于矩陣的加減等非空元素數(shù)目變化大的運(yùn)算。ijvdownright結(jié)點結(jié)構(gòu)(i,j,v)三元組表達(dá)一個非空元素。Down指針連接同列的下一個非空元素；Right指針連接同行的下一個非空元素。每一行增加一個行表頭結(jié)點，每一列增加一個列表頭結(jié)點：00nextdownright23000000000001122030004. 4. 廣義表廣義表L=(a1, a2, , ai, , an)，其中ai可以是不可分割的原子元素，也可以是一個廣義表。A=()L=(a,b)C=(a,(b,c,d)E=(a,E) = (a, (a, (a,()存儲結(jié)構(gòu)：只能采用動態(tài)鏈