数组和矩阵的压缩存储.ppt

《数组和矩阵的压缩存储.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章串、数组和广义表——数组与矩阵的存储方式8/26/20215:06PM数组可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。4.5数组8/26/20215:06PM数数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面

2、两种操作：(1)取值操作：给定一组下标，读其对应的数据元素(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素4.5数组8/26/20215:06PM一维数组一维数组的示例8/26/20215:06PM一维数组的特点连续存储的线性聚集（别名向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。8/26/20215:06PM二维数组的定义a11a12……..a1na21a22……..a2nam1am2……..amn………………….数组中的每一个元素由一个值和一组下标来描述二维数组8/26/20215:06PMa1

3、a11a12……..a1na2a21a22……..a2namam1am2……..amn………………….ai=(ai1,ai2,……..,ain)(1<=i<=m)——行向量数组是线性表的推广二维数组的表示方法8/26/20215:06PMßi=(ß1i,ß2i,……..,ßmi)(1<=i<=n)——列向量注意：数组的运算主要是存取元素、修改相应的元素。ß1a11a21……am1ß2a12a22……am2ßna1na2n……amn…………………………二维数组的表示方法8/26/20215:06PM二维数组三维数组行向量下标i页向量下标i列向量下标j行向量下标j列向量下标k8/26/2

4、0215:06PM（1）   按行优先顺序存放（2）   按列优先顺序存放数组的顺序存储结构8/26/20215:06PMamn……..am2am1……….a2n……..a22a21a1n…….a12a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(i-1)×n+(j-1)]×SS为每个元素的存储大小按行优先顺序存放8/26/20215:06PMamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……

5、..amn………………….loc(aij)=loc(a11)+[(j-1)×m+(i-1)]×SS为每个元素的大小按列优先顺序存放8/26/20215:06PM1、给定整型数组M[3][5],M按行优先次序存储，起始地址M[0][0]的存储地址为1000，则元素M[2][2]的地址为。A）1022B）1000C）1024D）1124CM[0][0]M[0][1]M[0][2]M[0][3]M[0][4]M[1][0]M[1][1]M[1][2]M[1][3]M[1][4]M[2][0]M[2][1]M[2][2]M[2][3]M[2][4]8/26/20215:06PM所谓特殊矩阵是

6、指非零元素或零元素的分布有一定规律的矩阵。例如对称矩阵，三角矩阵，对角线矩阵等特殊矩阵的压缩存储8/26/20215:06PM1、特殊矩阵（1）  对称矩阵（2）  三角矩阵（3）  对角线矩阵2、稀疏矩阵（1）   顺序存储结构——三元组表示法（2）   顺序存储结构稀疏矩阵的转置运算矩阵的压缩存储8/26/20215:06PM在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺

7、序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：对称矩阵8/26/20215:06PM15137a0050800a10a1118926a20a21a2230251………………..70613an-10an-11an-12…an-1n-1对称矩阵第i行恰有i+1个元素，元素总数为：n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。8/26/20215:06PM为了便于访问对称矩阵A中的