數(shù)據(jù)結(jié)構(gòu)數(shù)組第一頁，共三十八頁，2022年，8月28日●6.1數(shù)組的基本概念數(shù)組可以看成是線性表的一種擴展，表中的元素本身也是一種數(shù)據(jù)結(jié)構(gòu)，但所有的元素都屬于同一類型。第二頁，共三十八頁，2022年，8月28日●6.1.1數(shù)組的定義及邏輯結(jié)構(gòu)例如：二維數(shù)組可以看成“數(shù)組元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看成“數(shù)組元素是二維數(shù)組”的一維數(shù)組，依次類推。一個m行×n列的二維數(shù)組。a11a12…a1na21a22…a2n…………am1am2…amnAm×n＝第三頁，共三十八頁，2022年，8月28日數(shù)組是一個固定格式和數(shù)量的數(shù)據(jù)有序列，每個數(shù)組元素用惟一的一組下標標識。數(shù)組的基本操作:

⑴取值操作：給定一組下標，讀其對應的數(shù)組元素。⑵賦值操作：給定一組下標，存儲或修改與其相對應的數(shù)組元素?！?.1.1數(shù)組的定義及邏輯結(jié)構(gòu)第四頁，共三十八頁，2022年，8月28日●6.1.2數(shù)組的順序存儲結(jié)構(gòu)在內(nèi)存中,數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。對于一維數(shù)組按下標順序分配即可。對于多維數(shù)組的分配，要把它的元素映像在一維存儲器中，一般有兩種存儲方式，即“以行(序)為主(序)”的映象方法和“以列(序)為主(序)”的映象方法?！耙孕袨橹鳌钡拇鎯Y(jié)構(gòu):將數(shù)組中的數(shù)據(jù)元素“按行依次排放”在存儲器中；“以列為主”的存儲結(jié)構(gòu):將數(shù)組中的數(shù)據(jù)元素“按列依次排放”在存儲器中。第五頁，共三十八頁，2022年，8月28日●6.1.2數(shù)組的順序存儲結(jié)構(gòu)LOC(A1(1))=LOC(a11)a11a12…a1nLOC(A2(1))=LOC(a21)a21a22…a2n…LOC(Am(1))=LOC(am1)am1am2…amnLOC(A1-(1))=LOC(a11)a11a21…am1LOC(A2-(1))=LOC(a12)a12a22…am2…LOC(An-(1))=LOC(a1n)a1na2n…amnA1(1)A2(1)Am(1)A1-(1)A2-(1)An-(1)(a)以行為主序(b)以列為主序第六頁，共三十八頁，2022年，8月28日

由下標計算數(shù)組元素的存儲位置:

假設每個數(shù)據(jù)元素占L個存儲單元⒈一維數(shù)組A(n)任意元素ai的存儲位置

LOC(ai)=LOC(a0)+i*L

/*假設數(shù)組下標界從0開始*/第七頁，共三十八頁，2022年，8月28日●6.1.2數(shù)組的順序存儲結(jié)構(gòu)⒉二維數(shù)組A(m×n)一個2×3的二維數(shù)組，其邏輯結(jié)構(gòu)和內(nèi)存映像如下。

a11a12a13a21a22a232×3數(shù)組的邏輯結(jié)構(gòu)a11a12a13a21a22a23a11a21a12a22a13a23以行為主序內(nèi)存映像以列為主序內(nèi)存映像第八頁，共三十八頁，2022年，8月28日假設二維數(shù)組A[m][n]中每個數(shù)據(jù)元素占L個存儲地址，并以LOC(aij)表示下標為(i,j)的數(shù)據(jù)元素的存儲地址，則數(shù)據(jù)元素在“以行為主”的順序映象中的存儲地址為：

LOC(aij)=在C語言中，數(shù)組中每一維下標界定義為0，則

LOC(aij)=

/*假設數(shù)組下標界從0開始*/●6.1.2數(shù)組的順序存儲結(jié)構(gòu)LOC(a11)+((i-1)*n+j-1)*L

/*假設數(shù)組下標界從1開始*/LOC(a00)+(i*n+j)*L第九頁，共三十八頁，2022年，8月28日2023/2/25練習已知二維數(shù)組A[1..3,1..5]的存儲首地址為100，它采用以行為主的順序存儲，且每個元素占用4個字節(jié)

LOC(a2，4)=100+[（2-1）*5+4-1]*4=

132第十頁，共三十八頁，2022年，8月28日2023/2/25練習已知二維數(shù)組A[1..3,1..5]的存儲首地址為100，它采用以列為主的順序存儲，且每個元素占用4個字節(jié)

LOC(a2，4)=100+[（4-1）*3+2-1]*4=

140第十一頁，共三十八頁，2022年，8月28日例

設有二維數(shù)組a(6,8)，每個元素占6個字節(jié)存儲，a0,0起始地址為1000，計算⑴數(shù)組a的存儲量是多少字節(jié)。⑵數(shù)組的最后一個元素a5,7的起始地址。⑶按行優(yōu)先存放時，元素a1,4的起始地址。⑷按列優(yōu)先存放時，元素a4,7的起始地址。練習第十二頁，共三十八頁，2022年，8月28日解⑴數(shù)組a的存儲量=6*8*6=288(字節(jié))⑵最后一個元素按行優(yōu)先和按列優(yōu)先地址都相同。

LOC(a0,0)=1000,n=8,i=5,j=7,L=6LOC(a5,7)=LOC(a0,0)+(n*i+j)*L=1000*(8*5+7)*6=1282⑶按行優(yōu)先存放時，LOC(a0,0)=1000,n=8,i=1,j=4,L=6LOC(a1,4)=LOC(a0,0)+(n*i+j)*L=1000*(8*1+4)*6=1072⑷按列優(yōu)先存放時，LOC(a0,0)=1000,m=6,i=4,j=7,L=6LOC(a4,7)=LOC(a0,0)+(m*j+i)*L=1000*(6*7+4)*6=1276第十三頁，共三十八頁，2022年，8月28日例

試設計算法，在O(n)時間內(nèi)將數(shù)組A[1..n]劃分為左右兩部分，使得左邊的所有元素值均為奇數(shù)，右邊的所有元素值均為偶數(shù)，要求所使用的輔助存儲空間大小為O(1)。算法設計：用一維數(shù)組A[1..n]表示，從左往右掃描數(shù)組A尋找偶數(shù),從右往左掃描數(shù)組A尋找奇數(shù),交換這兩個數(shù)

?！?.1.2數(shù)組的順序存儲結(jié)構(gòu)第十四頁，共三十八頁，2022年，8月28日voidpart(intA[],intn)

{inti=0,j=n-1,k;while(i<j){while((A[i]%2!=0)&&(i<j))i=i+1;while((A[j]%2!=1)&&(i<j))j=j-1;if(i<j){k=A[i];A[i]=A[j];A[j]=k;i++;j--;}}

}第十五頁，共三十八頁，2022年，8月28日例

已知二維數(shù)組Am×n，求當m=n時，對角線上所有數(shù)組元素的和?！?.1.2數(shù)組的順序存儲結(jié)構(gòu)a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34a40a41a42a43a44A＝5×5算法設計：本題中一條對角線是aii，其中(0≤i≤m-1)，另一條對角線是am-i-1,i，其中(0≤i≤m-1)。第十六頁，共三十八頁，2022年，8月28日#defineMAX20void

proc(intA[][MAX],intm,intn){inti,s;if(m!=n)printf(“m≠n”);else{s=0;for(i=0;i<m;i++)s=s+A[i][i];for(i=0;i<n;i++)s=s+A[n-i-1][i];printf(“s=%4d\n”,s);}}main(){intm,n,i,j;intA[MAX][MAX];printf(“m,n=”);scanf(“%d,%d”,&m,&n);for(i=0;i<m;i++)for(j=0;j<n;j++)scanf(“%d”,&A[i][j]);proc(A,m,n);}●6.1.2數(shù)組的順序存儲結(jié)構(gòu)第十七頁，共三十八頁，2022年，8月28日●

6.2矩陣的壓縮存儲對于一些有特性的高階矩陣，即矩陣中有很多值相同的元或零值元，為了節(jié)省存儲空間，需要對它們進行“壓縮存儲”，即不存或少存這些值相同的元或零值元。如果矩陣中值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱之為“特殊矩陣”。第十八頁，共三十八頁，2022年，8月28日●6.2.1對稱矩陣的壓縮存儲⒈對稱矩陣若n階方陣A中的元素滿足特性

aij=aji

0≤i,j≤n-1

則稱為n階對稱矩陣。例如A矩陣是一個5階對稱矩陣。A＝2352936638562732378498341第十九頁，共三十八頁，2022年，8月28日⒉對稱矩陣的存儲為每一對對稱矩陣元素分配一個存儲空間，則可以將n2個元素壓縮到n(n+1)/2個空間，節(jié)約了n(n-1)/2個存儲單元。

以行為主序存儲下三角對稱矩陣（包括對角線）●6.2.1對稱矩陣的壓縮存儲a0,0a1,0a1,1a2,0a2,1a2,2…an-1,0…an-1,n-1012345…n(n+1)/2-1第1行第2行第3行第n行第二十頁，共三十八頁，2022年，8月28日●6.2.1對稱矩陣的壓縮存儲在下三角矩陣中共有n(n+1)/2個元素，假設以一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構(gòu)，則sa[k]和矩陣元素aij之間存在以下一一對應的關(guān)系。

i(i+1)/2+j當i≥j（aij位于下三角）

k=

j(j+1)/2+i當i＜j（aij位于上三角）第二十一頁，共三十八頁，2022年，8月28日●6.2.1對稱矩陣的壓縮存儲A＝a00a01a02a03a04a10a11a12a13a14a20a21a22a23a24a30a31a32a33a34a40a41a42a43a44sa(k)01234567891011121314a00a01a11a02a12a22a03a13a23a33a04a14a24a34a44a10a20a21a30a31a32a40a41a42a43第二十二頁，共三十八頁，2022年，8月28日●6.2.2三角矩陣的壓縮存儲⒈三角矩陣

若n階方陣中下(上)三角(不包括對角線)中的元均為常量c或0，則稱為上(下)三角矩陣

例如，B矩陣是上三角矩陣；C矩陣是下三角矩陣。Ｂ＝82345a5671aa897aaa10aaaa8Ｃ＝8000025000368004791051708第二十三頁，共三十八頁，2022年，8月28日⒉三角矩陣的存儲除了和對稱矩陣一樣，只存儲矩陣的下（上）三角中元素之外，再加上一個常數(shù)c的存儲空間即可?！?.2.2三角矩陣的壓縮存儲a00000a10a1100a20a21a220a30a31a32a33a00a01a02a030a11a12a1200a22a23000a334×4下三角矩陣4×4上三角矩陣第二十四頁，共三十八頁，2022年，8月28日●6.2.2三角矩陣的壓縮存儲⑴下三角矩陣

以行為主序，將n×n的下三角矩陣中的元素aij存儲到一維數(shù)組D中。a0,0a1,0a1,1a2,0a2,1a2,2…an-1,0…an-1,n-1

aij=D(k)，k=例設有一個4×4的下三角矩陣，以行為主序，對應到一維數(shù)組D，求其元素a32所對應D(k)的k值。i(i+1)/2+j解a32=D(k)k=3(3+1)/2+2=8第二十五頁，共三十八頁，2022年，8月28日2023/2/25練習

已知下三角矩陣A[1..5,1..5]壓縮存儲于B[1..]中。

B的存儲首地址為100，且每個元素占用4個字節(jié)

ADR(a4，2)=100+[4*(4-1)/2+2-1]*4=

12815第二十六頁，共三十八頁，2022年，8月28日⑵上三角矩陣

以行為主序，將n×n的上三角矩陣中的元素aij存儲到一維數(shù)組D中。a0,0a0,1a0,2…a1,1a1,2…an-1,0…an-1,n-1

aij=D(k)，k=例設有一個4×4的上三角矩陣，以行為主序，對應到一維數(shù)組D，求其元素a23所對應D(k)的k值?！?.2.2三角矩陣的壓縮存儲解a23=D(k)k=4*2+3-2(2+1)/2=8n*i-i(i+1)/2+j第二十七頁，共三十八頁，2022年，8月28日●

6.3稀疏矩陣

如果矩陣中只有少量的非零值元，并且這些非零值元在矩陣中的分布沒有一定規(guī)律，則稱為隨機稀疏矩陣，簡稱為稀疏矩陣。30000000000-4005200000006010007A6×5=第二十八頁，共三十八頁，2022年，8月28日●6.3.1稀疏矩陣的概念順序存儲方式：三元組表鏈式存儲方式：十字鏈表第二十九頁，共三十八頁，2022年，8月28日壓縮存儲

（1）存儲矩陣總體信息:(rows,cols,terms)

rows:總行數(shù)cols:總列數(shù)terms:非零元個數(shù)（2）存儲非零元:(i,j,v)

i行標j列標v元素值一般采用以行為主的順序存儲方式共t個共1個三元組表第三十頁，共三十八頁，2022年，8月28日30000000000-4005200000006010007A6×5=稀疏矩陣AA的三元表組11332-4355412546611657(6,5,7)行標列標值1234567總行數(shù)總列數(shù)非零元個數(shù)放棄下標為0的單元12345612345注意:下標從1開始第三十一頁，共三十八頁，2022年，8月28日#defineMAX1024;

/*最大非零元素個數(shù)*/typedefstruct

{inti,j;

/*非零元素的行號和列號*/

elemtypev;

/*非零元素的值*/

}pnode;

/*存儲非零元素的三元組結(jié)構(gòu)體類型*/

typedefstruct

{introws,cols,terms;

/*矩陣的行、列及非零元的實際個數(shù)*/pnodedata[MAX+1];

/*三元組表，data[0]未用*/

}PMatrix;

/*稀疏矩陣的三元組表存儲類型*/PMatrixA;/*定義了稀疏矩陣A*/稀疏矩陣的三元組類型定義第三十二頁，共三十八頁，2022年，8月28日●6.3.2稀疏矩陣的轉(zhuǎn)置設矩陣A表示一個m×n的稀疏矩陣，那么其轉(zhuǎn)置矩陣B則是一個n×m的稀疏矩陣，且A(i,j)=A(j,i)，其中1≤i≤m，1≤j≤n。B5×6=30020100-4000000000000060005007A的轉(zhuǎn)置B30000000000-4005200000006010007A6×5=稀疏矩陣A第三十三頁，共三十八頁，2022年，8月28日B5×6=30020100-4000000000000060005007A的轉(zhuǎn)置矩陣BB的三元表組例將前稀疏矩陣A轉(zhuǎn)置為如下圖所示的稀疏矩陣B。第三十四頁，共三十八頁，2022年，8月28日B的三元表組A的三元表組11332-4355412546611657(6,5,7)行標列標值123456711314216123-4456535567(5,6,7)行標列標值1234567第三十五頁，共三十八頁，2022年，8月28日