专业课参考-数据结构

第5章数组与广义表第2

页5.1数组的概念数据类型相同的元素（变量）构成的有序元素的集合。数组名代表即为该集合的代表。如果要访问其中某个元素(变量)，可以通过元素的索引值(下标)访问。C语言中数组元素的索引值从0开始。

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

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

更一般情况：子界第3

页5.1数组的概念数组的逻辑结构 1.线性结构扩展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)二维数组是以数据元素作为线性表的线性表第4

页5.1数组的概念数组的逻辑结构2.二维数组中的每个元素都受两个线性关系的约束——行、列AMN=a00a01…

a0N-1a10a11…

a1N-1............aM-10aM-11…aM-1N-1在行关系中ai,j直接前趋ai,j-1ai,j直接后继ai,j+1在列关系中ai,j直接前趋ai-1,jai,j直接后继ai+1,jN维数组中的每个元素受N个线性关系的约束第5

页5.1数组的概念数组的基本操作初始化操作InitArray(&A,n,bound1,…,boundn)销毁操作DestroyArray(&A)读元素操作Value(A,&e,index1,…,indexn)写元素操作Assign(&A,e,index1,…,indexn)在高级语言中的典型体现：intA[M][N];A[i][j]=x;写y=A[i][j];读AMN=a00a01…

a0N-1a10a11…

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

页5.1数组的概念数组的基本操作1. 读：给定一组下标，读出对应的数组元素；2. 写：给定一组下标，存储或修改与其相对应的数组元素。

读/写操作本质上只对应一种操作—寻址：确定指定元素在内存中的物理地址。数组的存储 两种形式：既可以是顺序存储，也可以采用链式结构。第7

页5.2数组的存储和实现数组的存储结构与寻址——一维数组 设有M个元素的一维数组，下标范围为闭区间[0,M-1]，每个数组元素占用L

个存储单元。La0ai-1ai……aM-1a1……Loc(a0)Loc(ai)

ai

的存储地址：Loc(ai

)＝Loc(a0)＋i×L

第8

页5.2数组的存储和实现数组的存储结构与寻址——二维数组常用的两种映射方法：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。

二维数组内存二维结构一维结构第9

页5.1数组的概念Pascal语言数组的行优先存储a111a112a113

…a11n

a121a122a123

…a12n

…………

a1m1a1m2a1m3

…a1mn

a211a212a213

…a21n

a221a222a223

…a22n

…………

a2m1a2m2a2m3

…a2mn

┇

ak11ak12ak13

…ak1n

ak21ak22ak23

…ak2n

…………

akm1akm2akm3

…akmn第10

页5.1数组的概念FORTRAN语言数组的列优先存储a111a211a311

…ak11a121a221a321

…ak21

…………

a1m1a2m1a3m1

…akm1

a112a212a312

…ak12

a122a222a322

…ak22

…………

a1m2a2m2a3m2

…akm2

┇

a11na21na31n

…ak1n

a12na22na32n

…ak2n

…………

a1mna2mna3mn

…akmn第11

页5.2数组的存储和实现二维数组——按行优先（M×N）0N-1

0M-1aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=i×N＋j本行中aij

之前的元素个数每行元素个数整行数aijLoc(aij)

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

页5.2数组的存储和实现二维数组——按行优先的更一般情况l2h2

l1h1aij前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中aij前面的元素个数=(i

-l1)×(h2

-l2＋1)＋(j

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

前面的元素个数每行元素个数整行数第13

页5.2数组的存储和实现三维数组

三维数组：A[m1,m2,m3]：Loc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×L

第14

页5.2数组的存储和实现N维数组

N维数组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数组基址Ci为常数第15

页5.2数组的存储和实现二维数组——静态数组表示法 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

页5.2数组的存储和实现数组的动态表示法 typedefstruct{ ElemType*base;//动态空间基址

intdim;//数组维数

int*bound；//维界基址（各维大小）

int*constants;//数组映像函数常量基址 }Array;A.baseA.dimA.boundsA.constantsb1b2b3c1c2c3a000a0013A[b1][b2][b3]第17

页初始化数组操作

StatusInitArray(Array2&A,intb1,intb2){//数组的初始化

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

页销毁数组操作StatusDestroyArray(Array2&A){/*销毁数组A*/if(A.base){free(A.base);A.base=NULL;A.bound1=0;A.bound2=0;returnOK;}elsereturnERROR;}第19

页

读元素操作StatusValue(Array2A,ElemType&e,intj1,intj2){/*若各下标不超界，则将所指定的A的元素值赋值给e，并返回OK*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;e=*(A.base+A.bound2*j1+j2);returnOK;}第20

页写元素操作StatusAssign(Array2&A,ElemTypee,intj1,intj2){/*若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。*/if((j1<0)||(j1>=A.bound1)||(j2<0)||(j2>=A.bound2))returnERROR;*(A.base+A.bound2*j1+j2)=e;returnOK;}第21

页n维数组元素存储地址的计算

假设数组Ab1b2…bn

每个元素占用L个存储单元，Loc(j1,j2,…,jn)为元素aj1,j2,…,jn

的存储地址。Loc(0,0,…,0)是数组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

页5.3矩阵的压缩存储

为节省存储空间，时常会对某些矩阵进行压缩存储。所谓压缩存储： 1）对多个值相同的元只分配一个存储空间； 2）对零元不分配存储空间。

5.3.1特殊矩阵的压缩存储

5.3.2稀疏矩阵的压缩存储第23

页5.3.1特殊矩阵

特殊矩阵：值相同元素或者非零元素的分布有一定规律的矩阵。对称矩阵/上（下）三角矩阵。a11a12…

a1na21a22…

a2n……am1am2…

amna11a12…

a1n0

a22…

a2n

……00…

amn第24

页5.3.1特殊矩阵对称矩阵/上（下）三角矩阵 用一维数组，按行优先存储下三角元素。a11

a12a13a14…

a1na21a22

a23a24…

a2na31a32a33

a34

…a3n…an1an2an3an4

…

anna11a21a22

a31a32a33

…

an1an2…

ann

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

页5.3.1特殊矩阵对称矩阵/上（下）三角矩阵 矩阵元素aij

在一维数组中的存储位置

k：a11

a12a13a14…

a1na21a22

a23a24…

a2na31a32a33

a34

…a3n…an1an2an3an4

…

anna11a21a22

a31a32a33

…

an1an2…

ann

012345n(n+1)/2-1k=i(i-1)/2+j-1当ijj(j-1)/2+i-1当ij性质：aij=aji1≤i,j≤n对于下标i,j，线性地址第26

页5.3.1特殊矩阵对称矩阵/上（下）三角矩阵aij

在一维数组中的序号=阴影部分的面积=

i×(i+1)/2+j+1∵一维数组下标从0开始∴aij

在一维数组中的下标k=i×(i+1)/2+j0…in-10…j…n-1

aij每行元素个数12…iaij在本行中的序号aij第0行第1行…第i-1行第27

页5.3.2稀疏矩阵稀疏矩阵：含有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵。讨论含有较多零元素的稀疏矩阵的压缩存储。M

=

012900000000000-3000014000240000018000001500-7000M有42（67）个元素，有8个非零元素如何进行稀疏矩阵的压缩存储？？第28

页5.3.2稀疏矩阵三元组顺序表M

=

012900000000000-3000014000240000018000001500-7000采用三元组存储：(行,列,值)(

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

第29

页5.3.2稀疏矩阵三元组顺序表

#defineMAXSIZE12500typedefstruct{inti,j;//非零元的行下标和列下标

ElemTypee;//非零元值

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

//用于存储三元组表,data[0]未用

intmu,nu,tu;//行数、列数和非零元个数

}TSMatrix;第30

页5.3.2稀疏矩阵三元组表的顺序存储M

=

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

9432464-73614678

按行（行内按列）顺序存储非零元素。第31

页5.3.2稀疏矩阵三元组表的顺序存储——转置算法M

=

012900000000000-3000014000240000018000001500-7000

T

=

00-3001512000180900240000000-70000000014000000000

基本算法：交换对应行/列位置上的元素。第32

页5.3.2稀疏矩阵一般矩阵的转置算法

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

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

…算法的时间复杂度为：O(m*n)第33

页5.3.2稀疏矩阵ije12345678M.dataM.muM.nuM.tu31-361151212521813

9432464-7361467821124

6

-713

-33

42416

1531963

142

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

页5.3.2稀疏矩阵转置运算算法TransposeSMatrix(TSMatrixM,TSMatrix&T)基本思想 对M.data从头至尾扫描：

第1次扫描时，将M.data中列号为1的三元组赋值到T.data中； 第2次扫描时，将M.data中列号为2的三元组赋值到T.data中； 依此类推，直至将M.data所有三元组赋值到T.data中。第35

页121213931-3361443245218611564-7ijvijv31-325

1813

-361151615121221

1252

1813

931

9432434

2464

-746

-7361463

14M.dataT.data第一次扫描查找第1列元素第一次扫描结束第二次扫描结束第二次扫描查找第2列元素第三次扫描查找第3列元素第四次扫描查找第4列元素第五次扫描查找第5列元素第六次扫描查找第6列元素5.3.2稀疏矩阵第七次扫描查找第7列元素三元组表的顺序存储——转置算法第36

页5.3.2稀疏矩阵StatusTranMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;

if(T.tu)//非零元素个数!=0{q=1;//q为当前三元组在T.data[]存储位置(下标)

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算法的时间复杂度：O(nu*tu)第37

页5.3.2稀疏矩阵时间复杂度分析转置算法TranMatrix的时间复杂度为O(nutu)当非零元的个数tu和矩阵元素个数munu同数量级时，转置运算算法的时间复杂度为O(numunu)算法一般用于tu<<munu的情况第38

页5.3.2稀疏矩阵提高算法效率num[col]：存储M第col列非零元个数cpos[col]：存储M第col列第一个非零元在T.data中的位置121213931-3361443245218611564-7ijvM.datacpos[col]的计算方法：

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

22811012785319第39

页5.3.2稀疏矩阵第3列第二个非零元在b中的位置121213931-3361443245218611564-7colnum[col]cpot[col]1234567228110135278M.dataT.data12122112第2列第一个非零元在b中的位置139第3列第一个非零元在b中的位置31931-313-33614631443243424521825186115161564-746-74第2列第二个非零元在b中的位置65第4列第二个非零元在b中的位置第1列第一个非零元在b中的位置2793第6列第一个非零元在b中的位置扫描M.data实现M到T的转置809第40

页5.3.2稀疏矩阵StatusFastTransMatrix(TSMatrixM,TSMatrix&T){//采用三元组顺序表存储稀疏矩阵，求M的转置矩阵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中每一列非零元个数

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

//求第col列中第一个非零元在T.data中的序号

cpot[1]=1;

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

页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];

}