專業(yè)課參考-數(shù)據(jù)結(jié)構(gòu)

第5章數(shù)組與廣義表第2

頁(yè)5.1數(shù)組的概念數(shù)據(jù)類型相同的元素（變量）構(gòu)成的有序元素的集合。數(shù)組名代表即為該集合的代表。如果要訪問其中某個(gè)元素(變量)，可以通過元素的索引值(下標(biāo))訪問。C語(yǔ)言中數(shù)組元素的索引值從0開始。

intA[30][10];e=A[i][j];

intA[c1..d1,c2..d2]

更一般情況：子界第3

頁(yè)5.1數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu) 1.線性結(jié)構(gòu)擴(kuò)展AMN=a00a01…

a0N-1a10a11…

a1N-1aM-10aM-11…aM-1N-1

A=(A0，A1，…，AN-1)其中：Ai=(a0i,a1i,…,Am-1i)(0≤i≤N-1)二維數(shù)組是以數(shù)據(jù)元素作為線性表的線性表第4

頁(yè)5.1數(shù)組的概念數(shù)組的邏輯結(jié)構(gòu)2.二維數(shù)組中的每個(gè)元素都受兩個(gè)線性關(guān)系的約束——行、列AMN=a00a01…

a0N-1a10a11…

a1N-1............aM-10aM-11…aM-1N-1在行關(guān)系中ai,j直接前趨ai,j-1ai,j直接后繼ai,j+1在列關(guān)系中ai,j直接前趨ai-1,jai,j直接后繼ai+1,jN維數(shù)組中的每個(gè)元素受N個(gè)線性關(guān)系的約束第5

頁(yè)5.1數(shù)組的概念數(shù)組的基本操作初始化操作InitArray(&A,n,bound1,…,boundn)銷毀操作DestroyArray(&A)讀元素操作Value(A,&e,index1,…,indexn)寫元素操作Assign(&A,e,index1,…,indexn)在高級(jí)語(yǔ)言中的典型體現(xiàn)：intA[M][N];A[i][j]=x;寫y=A[i][j];讀AMN=a00a01…

a0N-1a10a11…

a1N-1aM-10aM-11…aM-1N-1第6

頁(yè)5.1數(shù)組的概念數(shù)組的基本操作1. 讀：給定一組下標(biāo)，讀出對(duì)應(yīng)的數(shù)組元素；2. 寫：給定一組下標(biāo)，存儲(chǔ)或修改與其相對(duì)應(yīng)的數(shù)組元素。

讀/寫操作本質(zhì)上只對(duì)應(yīng)一種操作—尋址：確定指定元素在內(nèi)存中的物理地址。數(shù)組的存儲(chǔ) 兩種形式：既可以是順序存儲(chǔ)，也可以采用鏈?zhǔn)浇Y(jié)構(gòu)。第7

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——一維數(shù)組 設(shè)有M個(gè)元素的一維數(shù)組，下標(biāo)范圍為閉區(qū)間[0,M-1]，每個(gè)數(shù)組元素占用L

個(gè)存儲(chǔ)單元。La0ai-1ai……aM-1a1……Loc(a0)Loc(ai)

ai

的存儲(chǔ)地址：Loc(ai

)＝Loc(a0)＋i×L

第8

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址——二維數(shù)組常用的兩種映射方法：按行優(yōu)先：先行后列，先存儲(chǔ)行號(hào)較小的元素，行號(hào)相同者先存儲(chǔ)列號(hào)較小的元素。按列優(yōu)先：先列后行，先存儲(chǔ)列號(hào)較小的元素，列號(hào)相同者先存儲(chǔ)行號(hào)較小的元素。

二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)第9

頁(yè)5.1數(shù)組的概念Pascal語(yǔ)言數(shù)組的行優(yōu)先存儲(chǔ)a111a112a113

…a11n

a121a122a123

…a12n

…………

a1m1a1m2a1m3

…a1mn

a211a212a213

…a21n

a221a222a223

…a22n

…………

a2m1a2m2a2m3

…a2mn

┇

ak11ak12ak13

…ak1n

ak21ak22ak23

…ak2n

…………

akm1akm2akm3

…akmn第10

頁(yè)5.1數(shù)組的概念FORTRAN語(yǔ)言數(shù)組的列優(yōu)先存儲(chǔ)a111a211a311

…ak11a121a221a321

…ak21

…………

a1m1a2m1a3m1

…akm1

a112a212a312

…ak12

a122a222a322

…ak22

…………

a1m2a2m2a3m2

…akm2

┇

a11na21na31n

…ak1n

a12na22na32n

…ak2n

…………

a1mna2mna3mn

…akmn第11

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)二維數(shù)組——按行優(yōu)先（M×N）0N-1

0M-1aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=i×N＋j本行中aij

之前的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)aijLoc(aij)

=Loc(a00)＋(N×i＋j)×L第12

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)二維數(shù)組——按行優(yōu)先的更一般情況l2h2

l1h1aij前面的元素個(gè)數(shù)=陰影部分的面積=整行數(shù)×每行元素個(gè)數(shù)+本行中aij前面的元素個(gè)數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)aijLoc(aij)＝Loc(al1l2)+((i-l1)×(h2-l2+1)+(j-l2))×L本行中aij

前面的元素個(gè)數(shù)每行元素個(gè)數(shù)整行數(shù)第13

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)三維數(shù)組

三維數(shù)組：A[m1,m2,m3]：Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×L

第14

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)N維數(shù)組

N維數(shù)組A[b1,b2,…,bn]中某元素地址

Loc(j1,j2,…,jn) =Loc(0,0,…,0)+(b2×b3×...×bn×j1

+b3×...×bn×j2+...+bn×jn-1+jn)L =Loc(0,0,…,0)+∑ciji 其中：cn=L，ci-1=bi×ci，1<i≤n。ni=1數(shù)組基址Ci為常數(shù)第15

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)二維數(shù)組——靜態(tài)數(shù)組表示法 typedefElemTypeArray[m*n]; ArrayA;

Amn=a00a01…

a0n-1a10a11…

a1n-1

……am-10am-11…am-1n-1a00….a0n-1a10….a1n-1….am-10….am-1n-1第16

頁(yè)5.2數(shù)組的存儲(chǔ)和實(shí)現(xiàn)數(shù)組的動(dòng)態(tài)表示法 typedefstruct{ ElemType*base;//動(dòng)態(tài)空間基址

intdim;//數(shù)組維數(shù)

int*bound；//維界基址（各維大?。?/p>

int*constants;//數(shù)組映像函數(shù)常量基址 }Array;A.baseA.dimA.boundsA.constantsb1b2b3c1c2c3a000a0013A[b1][b2][b3]第17

頁(yè)初始化數(shù)組操作

StatusInitArray(Array2&A,intb1,intb2){//數(shù)組的初始化

if(b1<=0||b2<=0) returnERROR;else{A.bound1=b1;A.bound2=b2;

if(!(A.base=(ElemType*)malloc(b1*b2*sizeof(ElemType)

)

)

)exit(OVERFLOW);returnOK;}}第18

頁(yè)銷毀數(shù)組操作StatusDestroyArray(Array2&A){/*銷毀數(shù)組A*/if(A.base){free(A.base);A.base=NULL;A.bound1=0;A.bound2=0;returnOK;}elsereturnERROR;}第19

頁(yè)

讀元素操作StatusValue(Array2A,ElemType&e,intj1,intj2){/*若各下標(biāo)不超界，則將所指定的A的元素值賦值給e，并返回OK*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;e=*(A.base+A.bound2*j1+j2);returnOK;}第20

頁(yè)寫元素操作StatusAssign(Array2&A,ElemTypee,intj1,intj2){/*若下標(biāo)不超界，則將e的值賦給所指定的A的元素，并返回OK。*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;*(A.base+A.bound2*j1+j2)=e;returnOK;}第21

頁(yè)n維數(shù)組元素存儲(chǔ)地址的計(jì)算

假設(shè)數(shù)組Ab1b2…bn

每個(gè)元素占用L個(gè)存儲(chǔ)單元，Loc(j1,j2,…,jn)為元素aj1,j2,…,jn

的存儲(chǔ)地址。Loc(0,0,…,0)是數(shù)組A的基址。 Loc(j1,j2,…,jn)= Loc(0,0,…,0)+(b2…bnj1

+

b3…bnj2

+…+bnjn-1

+jn)L =Loc(0,…,0)+(c1j1+c2j2+…+cn-1jn-1+cnjn)intB[4][3][5]a000a001

a00b1-1a010a011a01b1-1a020a021a02b1-1第22

頁(yè)5.3矩陣的壓縮存儲(chǔ)

為節(jié)省存儲(chǔ)空間，時(shí)常會(huì)對(duì)某些矩陣進(jìn)行壓縮存儲(chǔ)。所謂壓縮存儲(chǔ)： 1）對(duì)多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間； 2）對(duì)零元不分配存儲(chǔ)空間。

5.3.1特殊矩陣的壓縮存儲(chǔ)

5.3.2稀疏矩陣的壓縮存儲(chǔ)第23

頁(yè)5.3.1特殊矩陣

特殊矩陣：值相同元素或者非零元素的分布有一定規(guī)律的矩陣。對(duì)稱矩陣/上（下）三角矩陣。a11a12…

a1na21a22…

a2n……am1am2…

amna11a12…

a1n0

a22…

a2n

……00…

amn第24

頁(yè)5.3.1特殊矩陣對(duì)稱矩陣/上（下）三角矩陣 用一維數(shù)組，按行優(yōu)先存儲(chǔ)下三角元素。a11

a12a13a14…

a1na21a22

a23a24…

a2na31a32a33

a34

…a3n…an1an2an3an4

…

anna11a21a22

a31a32a33

…

an1an2…

ann

012345n(n+1)/2-1性質(zhì)：aij=aji1≤i,j≤n第25

頁(yè)5.3.1特殊矩陣對(duì)稱矩陣/上（下）三角矩陣 矩陣元素aij

在一維數(shù)組中的存儲(chǔ)位置

k：a11

a12a13a14…

a1na21a22

a23a24…

a2na31a32a33

a34

…a3n…an1an2an3an4

…

anna11a21a22

a31a32a33

…

an1an2…

ann

012345n(n+1)/2-1k=i(i-1)/2+j-1當(dāng)ijj(j-1)/2+i-1當(dāng)ij性質(zhì)：aij=aji1≤i,j≤n對(duì)于下標(biāo)i,j，線性地址第26

頁(yè)5.3.1特殊矩陣對(duì)稱矩陣/上（下）三角矩陣aij

在一維數(shù)組中的序號(hào)=陰影部分的面積=

i×(i+1)/2+j+1∵一維數(shù)組下標(biāo)從0開始∴aij

在一維數(shù)組中的下標(biāo)k=i×(i+1)/2+j0…in-10…j…n-1

aij每行元素個(gè)數(shù)12…iaij在本行中的序號(hào)aij第0行第1行…第i-1行第27

頁(yè)5.3.2稀疏矩陣稀疏矩陣：含有較多值相同元素或較多零元素，且值相同元素或者零元素分布沒有一定規(guī)律的矩陣。討論含有較多零元素的稀疏矩陣的壓縮存儲(chǔ)。M

=

012900000000000-3000014000240000018000001500-7000M有42（67）個(gè)元素，有8個(gè)非零元素如何進(jìn)行稀疏矩陣的壓縮存儲(chǔ)？？第28

頁(yè)5.3.2稀疏矩陣三元組順序表M

=

012900000000000-3000014000240000018000001500-7000采用三元組存儲(chǔ)：(行,列,值)(

(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上矩陣的行數(shù)和列數(shù)：6,7

第29

頁(yè)5.3.2稀疏矩陣三元組順序表

#defineMAXSIZE12500typedefstruct{inti,j;//非零元的行下標(biāo)和列下標(biāo)

ElemTypee;//非零元值

}Triple;typedefstruct{Tripledata[MAXSIZE+1];

//用于存儲(chǔ)三元組表,data[0]未用

intmu,nu,tu;//行數(shù)、列數(shù)和非零元個(gè)數(shù)

}TSMatrix;第30

頁(yè)5.3.2稀疏矩陣三元組表的順序存儲(chǔ)M

=

012900000000000-3000014000240000018000001500-7000ije12345678M.dataM.muM.nuM.tu31-361151212521813

9432464-73614678

按行（行內(nèi)按列）順序存儲(chǔ)非零元素。第31

頁(yè)5.3.2稀疏矩陣三元組表的順序存儲(chǔ)——轉(zhuǎn)置算法M

=

012900000000000-3000014000240000018000001500-7000

T

=

00-3001512000180900240000000-70000000014000000000

基本算法：交換對(duì)應(yīng)行/列位置上的元素。第32

頁(yè)5.3.2稀疏矩陣一般矩陣的轉(zhuǎn)置算法

…inta[m][n],b[m][n];for(i=0;i<m;++i)

for(j=0;j<n;++j)b[j][i]=a[i][j];

…算法的時(shí)間復(fù)雜度為：O(m*n)第33

頁(yè)5.3.2稀疏矩陣ije12345678M.dataM.muM.nuM.tu31-361151212521813

9432464-7361467821124

6

-713

-33

42416

1531963

142

518ije12345678M.dataM.muM.nuM.tu678第34

頁(yè)5.3.2稀疏矩陣轉(zhuǎn)置運(yùn)算算法TransposeSMatrix(TSMatrixM,TSMatrix&T)基本思想 對(duì)M.data從頭至尾掃描：

第1次掃描時(shí)，將M.data中列號(hào)為1的三元組賦值到T.data中； 第2次掃描時(shí)，將M.data中列號(hào)為2的三元組賦值到T.data中； 依此類推，直至將M.data所有三元組賦值到T.data中。第35

頁(yè)121213931-3361443245218611564-7ijvijv31-325

1813

-361151615121221

1252

1813

931

9432434

2464

-746

-7361463

14M.dataT.data第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素5.3.2稀疏矩陣第七次掃描查找第7列元素三元組表的順序存儲(chǔ)——轉(zhuǎn)置算法第36

頁(yè)5.3.2稀疏矩陣StatusTranMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)//非零元素個(gè)數(shù)!=0{q=1;//q為當(dāng)前三元組在T.data[]存儲(chǔ)位置(下標(biāo))

for(col=1;col<=M.nu;++col)

for(p=1;p<=M.tu;++p)//p為掃描M.data指示器

if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}

}//if

returnOK;}//TranMtrix算法的時(shí)間復(fù)雜度：O(nu*tu)第37

頁(yè)5.3.2稀疏矩陣時(shí)間復(fù)雜度分析轉(zhuǎn)置算法TranMatrix的時(shí)間復(fù)雜度為O(nutu)當(dāng)非零元的個(gè)數(shù)tu和矩陣元素個(gè)數(shù)munu同數(shù)量級(jí)時(shí)，轉(zhuǎn)置運(yùn)算算法的時(shí)間復(fù)雜度為O(numunu)算法一般用于tu<<munu的情況第38

頁(yè)5.3.2稀疏矩陣提高算法效率num[col]：存儲(chǔ)M第col列非零元個(gè)數(shù)cpos[col]：存儲(chǔ)M第col列第一個(gè)非零元在T.data中的位置121213931-3361443245218611564-7ijvM.datacpos[col]的計(jì)算方法：

cpos[1]=1cpos[col]=cpos[col-1]+num[col-1]2colncolnum[col]cpot[col]1234567

22811012785319第39

頁(yè)5.3.2稀疏矩陣第3列第二個(gè)非零元在b中的位置121213931-3361443245218611564-7colnum[col]cpot[col]1234567228110135278M.dataT.data12122112第2列第一個(gè)非零元在b中的位置139第3列第一個(gè)非零元在b中的位置31931-313-33614631443243424521825186115161564-746-74第2列第二個(gè)非零元在b中的位置65第4列第二個(gè)非零元在b中的位置第1列第一個(gè)非零元在b中的位置2793第6列第一個(gè)非零元在b中的位置掃描M.data實(shí)現(xiàn)M到T的轉(zhuǎn)置809第40

頁(yè)5.3.2稀疏矩陣StatusFastTransMatrix(TSMatrixM,TSMatrix&T){//采用三元組順序表存儲(chǔ)稀疏矩陣，求M的轉(zhuǎn)置矩陣T

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;//求M中每一列非零元個(gè)數(shù)

for(t=1;t<=M.tu;++t)++num[M.data[t].j];

//求第col列中第一個(gè)非零元在T.data中的序號(hào)

cpot[1]=1;

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];第41

頁(yè)5.3.2稀疏矩陣

for(p=1;p<M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];

}