数据结构第5章数组和稀疏矩阵.ppt

《数据结构第5章数组和稀疏矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组特殊矩阵的压缩存储稀疏矩阵第5章数组和稀疏矩阵数组数组是n(n>1)个相同类型数据元素a1,a2,…,an构成的有限序列。数组的性质：（1）数组中的数据元素数目固定。（定长）（2）数组中的数据元素具有相同的数据类型。（3）数组中的每个数据元素都和一组唯一的下标值对应。（4）数组是一种随机存储结构。可以随机存取数组中的任意数据元素。a33a322数组一维数组：a5m多维数组：m=8ADTList{数据对象:D={aj1,j2,j3,…,jd

2、ji=1,2,…,bi,i=1,2,…,d}数据关系:R={r1,r2,…,rn}ri,=

3、j2,,,ji,…,jn,aj1,j2j,,,ji+1,…,jn>

4、1jkbk,1kb且ki,1jibi-1,I=2,3,…d基本运算:Value(A,index1,index2,…,indexd);Assign(A,e,index1,index2,…,indexd);Adisp(A,b1,b2,…bd)}抽象数据类型数组的定义逻辑结构一维数组：aiai-1ai+1线性结构二维数组：aijaij-1aij+1ai-1jai+1j三维数组：aijkaij-1kaij+1kaijk+1aijk-1ai-1jkai+1jk线性结构推广

5、数组的存储结构由于数组主要随机访问，没有插入和删除，所以采用顺序方式存储。一维数组的存储：按次序依次存储在一组连续的存储空间中。LOC(ai)=LOC(a1)+(i-1)*k多维数组的存储：问题：计算机内存是一维，如何存储多维数组。要求：将多维数组中每个元素按某种次序列排列成为一维结构。两种方法：以行为主序顺序和以列为主序顺序。二维数组行优先顺序存储结构a11a1nai1aijainam1amnAmn=Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*d每个元素占存储空间大小为dLoc(aij)=首地址+前面所

6、有元素所占存储空间的总数a11a1n第1行ai1ain第i行am1amn第m行前i-1行：有(i-1)*n个元素第i行：有j-1元素aij前共有(i-1)*n+j-1个元素？问题：若第一个元素为a00（即下标为00）则Loc(aij)=?行aij前共有i行元素本行前有是j个元素Loc(aij)=Loc(a00)+(i*n+j)*dLoc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*da11am1第1列a1jamj第j列a1namn第n列前j-1列：有(j-1)*m个元素第j列：有i-1元素aij前共有(

7、j-1)*m+i-1个元素每个元素占存储空间大小为dLoc(aij)=首地址+前面所有元素所占存储空间的总数？问题：若第一个元素为a00（即下标为00）则Loc(aij)=?列aij前共有j列元素本列前有是i个元素Loc(aij)=Loc(a00)+(j*m+i)*da11a1nai1aijainam1amnAmn=二维数组列优先顺序存储结构三维数组AmnpLoc(aijk)=Loc(a111)+[(i-1)*n*p+(j-1)*p+k-1)]*d行优先顺序：Loc(aijk)=Loc(a111)+[(i-1)+(j-1

8、)*m+(k-1)*m*n]*d列优先顺序：a111…a11pa121…a12p…a1n1…a1npa211…a21p…amn1…amnpa111…am11a121…am21…a1n1…amn1a112…am12…a1np…amnp特殊矩阵的压缩存储a11a1nai1aijainam1amnAmn=通常可以采用二维数组存储矩阵空间复杂度：S(m,n)=O(m*n)问题：（1）矩阵中有大量相同的非零元素这样仍造成空间极大浪费多个相同的非零元素只分配一个存储空间矩阵压缩存储原则特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。

9、对称矩阵、三角矩阵、对角矩阵对称矩阵特点：aij=aji只需存储上三角或下三角中的元素SAa11a21a22a31a32a33a41a42a43……ann0123456789n(n+1)/2-1a32和a23存储在SA[5]矩阵中n*n个元素只需要n(n+1)/2个存储单元SA[k]=aijK=i(i-1)2+j-1ijijK=n(n+1)2datatypeSA[]n(n+1)2+1i(i-1)2+j-1

10、iji

11、