數(shù)據(jù)結(jié)構(gòu)第11講

1、數(shù)組與特殊矩陣壓縮存儲(chǔ)知識(shí)要點(diǎn)： ?數(shù)組的基本概念 ?數(shù)組的基本運(yùn)算和存儲(chǔ)結(jié)構(gòu) ?特殊矩陣壓縮存儲(chǔ),1、 數(shù)組的邏輯結(jié)構(gòu),數(shù)組是我們熟悉的一種數(shù)據(jù)結(jié)構(gòu)，可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)

2、組”的一維數(shù)組，依此類推。,數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來標(biāo)識(shí)，因此，在數(shù)組上只有存取元素和修改元素值的操作。不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級(jí)語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。在數(shù)組中通常做下面兩種操作：(1)取值操作：給定一組下標(biāo)，讀其對(duì)應(yīng)的數(shù)據(jù)元素。 (2)賦值操作：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)據(jù)元素。 我們著重研究二維和

3、三維數(shù)組，因?yàn)樗鼈兊膽?yīng)用是廣泛的，尤其是二維數(shù)組。,N維數(shù)組的數(shù)據(jù)類型定義,n_ARRAY = (D, R),其中：,Ri = {| aj1,j2,…ji…jn , aj1,j2,…ji+1…jn ?D },數(shù)據(jù)關(guān)系：R = { R1 ,R2，…. Rn },D = {aj1,j2…jn| ji為數(shù)組元素的第i 維下標(biāo) ，aj1,j2…jn ?Elemset}數(shù)據(jù)對(duì)象：ji

4、=0,...,bi-1,i=1,2,....,n.n稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長度,數(shù)組的抽象數(shù)據(jù)類型定義，參見教材P90,構(gòu)造數(shù)組、銷毀數(shù)組、讀數(shù)組元素、寫數(shù)組元素,基本操作：,2 、 數(shù)組的內(nèi)存映象,通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲(chǔ)結(jié)構(gòu)，這是因?yàn)閮?nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一個(gè)映象函數(shù)，則可根據(jù)數(shù)組元素的下標(biāo)得到它的存儲(chǔ)地址。 對(duì)于一維數(shù)組按下標(biāo)順序分配即可。 對(duì)多維數(shù)組分

5、配時(shí)，要把它的元素映象存儲(chǔ)在一維存儲(chǔ)器中，一般有兩種存儲(chǔ)方式：一是以行為主序（或先行后列）的順序存放，如BASIC、PASCAL、COBOL、C等程序設(shè)計(jì)語言中用的是以行為主的順序分配，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，如FORTRAN、MATLAB語言中，用的是以列為主序的分配順序，即一列一列地分配。,以行為主序（低下標(biāo)優(yōu)先）的分配規(guī)律是：最右邊的下標(biāo)先變化，即最右下標(biāo)從小到大，循環(huán)一遍后，右邊第

6、二個(gè)下標(biāo)再變，…，從右向左，最后是左下標(biāo)。以列為主序（高下標(biāo)優(yōu)先）分配的規(guī)律恰好相反：最左邊的下標(biāo)先變化，即最左下標(biāo)從小到大，循環(huán)一遍后，左邊第二個(gè)下標(biāo)再變，…，從左向右，最后是右下標(biāo)。,例如一個(gè)2×3二維數(shù)組，邏輯結(jié)構(gòu)可以用左圖表示。以行為主序的內(nèi)存映象如右圖（a）所示。 分配順序?yàn)椋篴11 ，a12 ，a13 ，a21 ，a22 ，a23 ；以列為主序的分配順序?yàn)椋篴11 ，a21 ，a12 ，a22 ，a13 　，a23

7、 ；它的內(nèi)存映象如右圖（b）所示。,設(shè)有m×n二維數(shù)組Amn，下面我們看按元素的下標(biāo)求其地址的計(jì)算： 以“以行為主序”的分配為例：設(shè)數(shù)組的基址為LOC(a11)，每個(gè)數(shù)組元素占據(jù)l個(gè)地址單元，那么aij 的物理地址可用一線性尋址函數(shù)計(jì)算： LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * l 在C語言中，數(shù)組中每一維的下界定義為0，則：

8、 LOC(aij) = LOC(a00) + ( i*n + j ) * l 推廣到一般的二維數(shù)組：A[c1..d1] [c2..d2]，則aij的物理地址計(jì)算函數(shù)為： LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )*l,同理對(duì)于三維數(shù)組Amnp，即m×n×p數(shù)組，對(duì)于數(shù)組元素aijk其物理地址為： LOC

9、(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1)*l 推廣到一般的三維數(shù)組：A[c1..d1] [c2..d2] [c3..d3]，則aijk的物理地址為： LOC(i,j,k)=LOC(a c1 c2 c3)+( (i- c1) *( d2 - c2 + 1)* (d3- c3 + 1)+ (j- c2) *( d3- c3 + 1)+(k- c3))*l,三維數(shù)組的邏

10、輯結(jié)構(gòu)和以行為主序的分配示意圖如圖所示。,例1：如何求出a(3,2)的存儲(chǔ)地址？,,要事先確定：1）是行優(yōu)先方式還是列優(yōu)先方式？2）數(shù)組的首地址是多少？3）每個(gè)元素的長度？,例2：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是 0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編 址。那么，這個(gè)數(shù)組的體積是 個(gè)字節(jié)。,答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=2

11、88,例3：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 請(qǐng)問按列存儲(chǔ)的 公式相同嗎？,答：盡管是方陣，但公式仍不同。應(yīng)為： Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K,例4：設(shè)數(shù)組a[1…60, 1…70]的基地址為2048，每個(gè)元素占2 個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58] 的存儲(chǔ)地址為

12、 。,答：根據(jù)列優(yōu)先公式 Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950,,例6 若矩陣Am×n 中存在某個(gè)元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個(gè)鞍點(diǎn)。試編寫一個(gè)算法，找出A中的所有鞍點(diǎn)。 基本思想：在矩陣A中求

13、出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，接著處理下一行。矩陣A用一個(gè)二維數(shù)組表示。,void saddle (int A[ ][ ],int m, int n) /*m,n是矩陣A的行和列*/{ int i,j,min; for (i=0;i=m) printf (＂%d,%d,%d\n＂, i ,k,min); } } } 算法的時(shí)間

14、性能為O(m*(n+m*n))。,Loc(j1,j2,…jn)=LOC(0,0,…0)＋,若是N維數(shù)組，其中任一元素的地址該如何計(jì)算？,其中Cn=L, Ci-1=bi×Ci， 1<i≤n,一個(gè)元素長度,數(shù)組基址,前面若干元素占用的地址字節(jié)總數(shù),第i維長度,與所存元素個(gè)數(shù)有關(guān)的系數(shù)，可用遞推法求出,,教材已給出低維優(yōu)先的地址計(jì)算公式，見P93（5-2）式該式稱為n維數(shù)組的映像函數(shù)：,數(shù)組順序存儲(chǔ)的表示和實(shí)現(xiàn),Ini

15、tArray(Array &A, int dim, ...);// 若維數(shù)dim和隨后的維數(shù)合法,構(gòu)造相應(yīng)的數(shù)組,并返回OKDestroyArray (Array &A);//銷毀數(shù)組AValue(Array A, ElemType &e, ...);若各下標(biāo)不超界,則e賦值為所指定的A的元素值,并返回OK Assign(Array &A, ElemType e, ...)若各下標(biāo)不超界,則將

16、e的值賦給所指定的A的元素,并返回OK,,0 1 ... dim-1,#incluse #define MAX_ARRAY_DIM 8typedef struct { ElemType *base;//數(shù)組元素基址 int dim;//數(shù)組維數(shù) int *bounds; //數(shù)組各維長度信息保存區(qū)基址 int *c

17、onstants; //數(shù)組映像函數(shù)常量的基址}Array;,即Ci信息保存區(qū),,,,,,,base,dim (4),bounds,constants,,,,,,,elemtatol-1,,,,,7,0 1 2 3,,,,,8,6,5,336,1,Array A[5][6][7][8];,8,56,0,,5x6x7x8,Status InitArray(Array &A, int dim,

18、...){ va_list ap; if(dim MAX_ARRAY_DIM) return ERROR; A.dim = dim; A.bounds = (int * ) malloc(dim*sizeof(int)); if(!A.bounds) exit(OVERFLOW); elemtotal = 1; va_start(ap, dim);//ap為va_list類型，是

19、存放變長參數(shù)表信息的類型 for(i =0 ; i=0; --i) A.constants[i] = A.bounds[i+1] * A.constants[i+1]; return OK;},,Status DestroyArray(Array &A){ if (!A.base) return ERROR; free(A.base); A.base =

20、 NULL; if (!A.bounds) return ERROR; free(A.bounds); A.bounds = NULL; if (!A.constants) return ERROR; free(A.constants); A.constants = NULL; return OK;},銷毀數(shù)組A,數(shù)組基址指針,各維長度保

21、存區(qū)指針,映像函數(shù)Ci保存區(qū)指針,若ap所指的各下標(biāo)值合法, 則求出該元素在A中的位置,Status Locate(Array A, va_list ap, int &off){ //若ap指示的各下標(biāo)值合法，則求出該元素在A中，相對(duì)地址offoff = 0; for(i=0; i= a.bounds[i]) return OVERFLOW; off += A.constants

22、[i] * ind; } return OK;},,i,off,A是n維數(shù)組, e為元素變量, 隨后是n個(gè)下標(biāo)值;若各下標(biāo)不超界, 則e賦值為所指定的A的元素值,并返回OK,Status Value(Array A, ElemType &e, ...){ va_list ap; va_start(ap,e); if(result = Locate(A, ap, off)) <= 0)

23、 return result; e = *(A.base + off); return OK;},,i,off,e,,,,A是n維數(shù)組, e為元素變量, 隨后是n個(gè)下標(biāo)值;若各下標(biāo)不超界,則將e的值賦給所指定的A的元素,并返回OK,Status Assign(Array &A, ElemType e, ...){ va_start(ap,e); if(resu

24、lt = Locate(A, ap, off)) <= 0) return result; *(A.base + off) = e; return OK;},,i,off,,5.3 矩陣的壓縮存儲(chǔ),討論：1. 什么是壓縮存儲(chǔ)？若多個(gè)數(shù)據(jù)元素的值都相同，則只分配一個(gè)元素值的存儲(chǔ)空間，且零元素不占存儲(chǔ)空間。2. 所有二維數(shù)組（矩陣）都能壓縮嗎？未必，要看矩陣是否具備以上壓縮條件。3. 什

25、么樣的矩陣具備以上壓縮條件？ 一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。4. 什么叫稀疏矩陣？矩陣中非零元素的個(gè)數(shù)較少（一般小于5%）,重點(diǎn)介紹稀疏矩陣的壓縮和相應(yīng)的操作。,,特殊矩陣的壓縮存儲(chǔ),對(duì)稱矩陣 三角矩陣 帶狀矩陣,1、 對(duì)稱矩陣,對(duì)稱矩陣的特點(diǎn)是：在一個(gè)n階方陣中，有aij=aji ，其中1≤i , j≤n，如圖所示是一個(gè)５階對(duì)稱矩陣。,對(duì)稱矩陣關(guān)于主對(duì)角線對(duì)稱，因此只需存

26、儲(chǔ)上三角或下三角部分即可。比如，只存儲(chǔ)下三角中的元素aij，其特點(diǎn)是中j≤i且1≤i≤n，對(duì)于上三角中的元素aij ，它和對(duì)應(yīng)的aji相等，因此當(dāng)訪問的元素在上三角時(shí)，直接去訪問和它對(duì)應(yīng)的下三角元素即可，這樣，原來需要n*n個(gè)存儲(chǔ)單元，現(xiàn)在只需要n(n+1)/2個(gè)存儲(chǔ)單元了，節(jié)約了n(n-1)/2個(gè)存儲(chǔ)單元，當(dāng)n較大時(shí)，這是可觀的一部分存儲(chǔ)資源。,如何只存儲(chǔ)下三角部分？對(duì)下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n*(n

27、+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SA[n(n+1)/2]中，存儲(chǔ)順序可用下圖示意，這樣，原矩陣下三角中的某一個(gè)元素aij則具體對(duì)應(yīng)一個(gè)sak，下面的問題是要找到k與i、j之間的關(guān)系。,對(duì)于下三角中的元素aij，其特點(diǎn)是：i≥j且1≤i≤n，存儲(chǔ)到SA中后，根據(jù)存儲(chǔ)原則，它前面有i-1行，共有1+2+…+i-1=i*(i-1)/2個(gè)元素，而aij又是它所在的行中的第j個(gè)，所以在上面的排列順序中，aij是第i*(i-1)/2

28、+j個(gè)元素，因此它在SA中的下標(biāo)k與i、j的關(guān)系為： k=i*(i-1)/2+j-1 (０≤k<n*(n+1)/2 ) 若i<j，則aij是上三角中的元素，因?yàn)閍ij=aji ，這樣，訪問上三角中的元素aij時(shí)則去訪問和它對(duì)應(yīng)的下三角中的aji即可，因此將上式中的行列下標(biāo)交換就是上三角中的元素在SA中的對(duì)應(yīng)關(guān)系： k=j*(j-1)/2+i-1 (０≤k&

29、lt;n*(n+1)/2 ) 綜上所述，對(duì)于對(duì)稱矩陣中的任意元素aij，若令I(lǐng)=max(i,j)，J=min(i,j)，則將上面兩個(gè)式子綜合起來得到： k=I*(I-1)/2+J-1。,2 、 三角矩陣,形如下圖的矩陣稱為三角矩陣，其中c為某個(gè)常數(shù)。其中(a)為下三角矩陣：主對(duì)角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對(duì)角線以下均為同一個(gè)常數(shù)；下面討論它們的壓縮存儲(chǔ)方法。,

30、1） 下三角矩陣 與對(duì)稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲(chǔ)對(duì)角線上方的常量，因?yàn)槭峭粋€(gè)常數(shù)，所以存一個(gè)即可，這樣一共存儲(chǔ)了n*(n+1)/2+1個(gè)元素，設(shè)存入向量：SA[n*(n+1)/2+1]中，這種的存儲(chǔ)方式可節(jié)約n*(n-1)/2-1個(gè)存儲(chǔ)單元，sak 與aji 的對(duì)應(yīng)關(guān)系為：,2）上三角矩陣 對(duì)于上三角矩陣，存儲(chǔ)思想與下三角類似，以行為主序順序存儲(chǔ)上三角部分，最后存儲(chǔ)對(duì)角線下方的常量。對(duì)于

31、第1行，存儲(chǔ)n個(gè)元素，第2行存儲(chǔ)n-1個(gè)元素，…，第p行存儲(chǔ)(n-p+1)個(gè)元素，aij的前面有i-1行，共存儲(chǔ)：個(gè)元素，aij 是它所在的行中要存儲(chǔ)的第（j-i+1）個(gè)也就是上三角存儲(chǔ)順序中的第 (i-1)*(2n-i+2)/2+(j-i+1)個(gè)，因此它在SA中的下標(biāo)為：k=(i-1)*(2n-i+2)/2+j-i。 綜上， sak 與aji 的對(duì)應(yīng)關(guān)系為：,3 、 帶狀矩陣,n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m

32、 ，滿足當(dāng)∣i-j∣≥m 時(shí)，aij =0，這時(shí)稱w=2m-1為矩陣A的帶寬。下圖是一個(gè)w=3(m=2)的帶狀矩陣。帶狀矩陣也稱為對(duì)角矩陣。由下圖可看出，在這種矩陣中，所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零(或同一個(gè)常數(shù)c)。,一種壓縮方法是將A壓縮到一個(gè)n行w列的二維數(shù)組B中，如下圖所示，當(dāng)某行非零元素的個(gè)數(shù)小于帶寬w時(shí)，先存放非零元素后補(bǔ)零。