数组的基本概念数组的存储结构特殊矩阵的压缩存储ppt课件.ppt

《数组的基本概念数组的存储结构特殊矩阵的压缩存储ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数组的基本概念数组的存储结构特殊矩阵的压缩存储第五章数组和特殊矩阵数组的基本概念（P65）数组的定义数组是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n≥1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、…、in称为该元素的下标，并称该数组为n维数组。数组的特点元素本身可以具有某种结构，属于同一数据类型；数组是一个具有固定格式和数量的数据集合。a11a12…a1na21a22…a2n…………am1am2…amnA=A=(A1，A

2、2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)数组——线性表的推广二维数组是数据元素为线性表的线性表。数组的基本概念设一维数组的下标的范围为闭区间［l，h］，每个数组元素占用c个存储单元，则其任一元素ai的存储地址可由下式确定：Loc(ai)＝Loc(al)＋(i－l)×ccalai-1ai……ahal+1……Loc(al)Loc(ai)数组的存储结构——一维数组(P66)常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。

3、按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。二维数组内存二维结构一维结构数组的存储结构——二维数组特殊矩阵的压缩存储特殊矩阵：包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等。稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：为多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。36　4　7　8628　4　24　816　97　4　6058　2　9　57A＝对称矩阵特点：aij=aji如何压缩存储？只存储下三角部分的元素。特殊矩阵的压缩存储——对称阵对于下三角中

4、的元素aij（i≥j），在数组SA中的下标k与i、j的关系为：k＝i×(i＋1)/2＋j。上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j＋1)/2＋i。第1行第n-1行第0行a00a10a11a20a21a22aij…an-10an-11…an-1n-1…第2行012345kn(n+1)/2-1特殊矩阵的压缩存储——对称阵3cccc6　2ccc48　1cc7　4　6　0c8　2　9　5　7(a)下三角矩阵34　8　10c2　9　4　6cc１5

5、7ccc0　8cccc7(b)上三角矩阵如何压缩存储？只存储上三角（或下三角）部分的元素。特殊矩阵的压缩存储——三角阵矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i×(i＋1)/2＋j当i≥jn×(n＋1)/2当i＜jk=012345kn(n+1)/2第1行第0行a00a10a11a20a21aij…an-1n-1…第2行ca22存储下三角元素对角线上方的常数——只存一个特殊矩阵的压缩存储——三角阵矩阵中任一元素aij在数组中的下标k与i、j的对应关系：i×(2n－i＋1)/2＋j－

6、i当i≤jn×(n＋1)/2当i＞jk=存储上三角元素对角线上方的常数——只存一个特殊矩阵的压缩存储——三角阵对角矩阵：所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。a00a010　0　0a10a11a120　00a21a22a23000a32a33a340　0　0a43a44A=特殊矩阵的压缩存储——对角矩阵a00a0100　0a10a11a120　00a21a22a23000a32a33a340　0　0a43a44A=将带

7、状区域立起来0a00a01a10a11a12a21a22a23a32a33a34a43a440B=s＝j-i+1t=i映射到二维数组B中，映射关系特殊矩阵的压缩存储——对角矩阵按行存储元素aij在一维数组中的序号=2+3(i－1)+(j－i+2)=2i+j+1∵一维数组下标从0开始∴元素aij在一维数组中的下标=2i+j(b)寻址的计算方法(c)压缩到一维数组中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112(a)三对角矩阵00　00

8、　000000　0　0A=a00a01a10a11a12a21a22a23a32a33a34a43a44特殊矩阵的压缩存储——对角矩阵15000000110000000600000000900000A=如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储——稀疏矩阵（1）三元组顺序表（P69）将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)——三元组（2）十字链表（P72）采用链接存储结构存储三元组表，每个非零元素对应的三元组存储为一个链表结点，结构为：稀