数据结构课件-第5章 数组

第5章数组

数组是一种特殊的线性表，表中的数据元素本身也是一个数据结构。5.1数组的类型定义5.3稀疏矩阵的压缩存储5.2数组的顺序表示和实现5.1数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：()()()()()()()()()可以看成是由一个行向量组成的向量，也可以看成是由一个列向量组成的向量。数组的类型定义ADTArray{

数据对象：

D＝{aj1,j2,...,,ji,jn|ji=0,...,bi-1,i=1,2,..,n}

数据关系：

R＝{R1,R2,...,Rn}Ri＝{<aj1,...

ji,...jn

,aj1,...ji+1,...jn

>|0jkbk-1,1kn且ki,0ji

bi-2,i=2,...,n}

}ADTArray/n维数组。Bi：第i维的长度基本操作:二维数组的定义:数据对象:

D={aij|0≤i≤b1-1,0≤j≤b2-1}数据关系:

R={ROW,COL}

ROW={<ai,j,ai+1,j>|0≤i≤b1-2,0≤j≤b2-1}

COL={<ai,j,ai,j+1>|0≤i≤b1-1,0≤j≤b2-2}//b1为行数；b2为列数基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。DestroyArray(&A)

操作结果：销毁数组A。Value(A,&e,index1,...,indexn)初始条件：

A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,...,indexn)

初始条件：

A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。5.2数组的顺序表示和实现1.类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。2.有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。(1)以行序为主序(2)以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序为主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

例如：

称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j

的存储位置：

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

3.计算二维数组元素地址的通式

二维数组列优先存储的通式为：

LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij

…

ad1,c2…ad1,d2

Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数则行优先存储时的地址公式为：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。例1〖软考题〗：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是

个字节。答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288例2：设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为

。∵LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L∴LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2

＝8950

假设m行n列的矩阵含t个非零元素，则称为稀疏因子。5.3稀疏矩阵的压缩存储1.何谓稀疏矩阵？

通常认为

0.05的矩阵为稀疏矩阵。

简单说，设矩阵A中有t个非零元素，若t远远小于矩阵元素的总数（即t<<m×n），则称A为稀疏矩阵。1)特殊矩阵

非零元在矩阵中的分布有一定规则。例如:三角矩阵矩阵的上（下）三角中的元素均为常数或0

对角矩阵所有的非0元素都分布在以对角线为中心的带状区域对称矩阵aij＝aji2)随机稀疏矩阵非零元在矩阵中随机出现2.稀疏矩阵a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

上三角矩阵下三角矩阵

a00a01a10a11a12a21a22a23….…..….an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1

对角矩阵151375080018926302510613

对称矩阵

以常规方法，即以二维数组表示高阶的稀疏或特殊矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。3.稀疏矩阵的压缩存储方法1)三元组顺序表2)行逻辑联接的顺序表3)

十字链表

#defineMAXSIZE12500

typedefstruct{

inti,j;//该非零元的行下标和列下标

ElemTypev;//该非零元的值

}Triple;//三元组类型1)三元组顺序表typedefunion{

Tripledata[MAXSIZE+1];//data[0]未使用

intmu,nu,tu;//当ElemType为int时可放在data[0]}TSMatrix;//稀疏矩阵类型如何表示稀疏矩阵M的第i个非零元素所在的列？2)三元组表示例6

7

8

121213931-3361443245218611564-7ijv01234567M6

7

8

31-3611512125218139432464-73614ijv01234567M三元组表默认行序1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。小结2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。1.假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为

。（无第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．A,B,C均不对

巩固练习2.设矩阵A是一个对称矩阵(第一个元素为a1,1)，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j,在一维数组B中下标k的值为

。

Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j1.假设有60行70列的二维数组a[1…60,1…70]以行序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为

。（无第0行第0列元素）Ａ．16902Ｂ．16904Ｃ．14454Ｄ．A,B,C均不对

强化练习2.设矩阵A是一个对称矩阵(第一个元素为a1,1)，为了节省存储，将其下三角部分按列序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j,在一维数组B中下标k的值为

。

A.(i+(i-j+1))×j/2B.无解

选择：（程序员2005）设数组a[1..10,5..15]的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j](1≤i≤10,5≤j≤15)的地址计算公式为（）A.a-204+2i+jB.a-204+40i+4jC.a-84+i+jD.a-64+44i+4j选择：（程序员2004）对于二维数组A[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素A[3,4]相对于数组空间起始地址的偏移量分别是（）和（）A.12B.14C.16D.18－D－A选择：（北京邮电1998）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A66,65（即元素下标）在B中的位置K为（）A.198 B.195 C.197选择：（武汉理工2002）三对角线矩阵A[1..n][1..n]以行序为主顺序存储，其存储始址是B，每个元素占一个存储单元，则元素A[i][j]的存储起始地址为（）(1≤i,j≤n)A.b+2*j+i-2B.b+2*i+j-2C.b+2*j+i-3D.b+2*i+j-32006年11月试题55对于二维数组a[0…4,1…5]，设每个元素占1个存储单元，且以列为主序存储，则元素a[2,2]，相对于数组空间起始地址的偏移量是_(55)_A.5 B.7 C.10 D.15软件设计师2010.5设有如下所示的下三角矩阵A[0..8,0..8]，将该三角矩阵的非零元素（即行下标不小于列下标的所有元素）按行优先压缩存储在数组M[1..m]中，则元素A