第2章-6数组.ppt

《第2章-6数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4数组7/22/20211数组数组的定义数组是n(n>=0)个相同数据类型数据元素构成的有限序列。在顺序存储方式下，一个一维数组，一旦第一个元素ai的存储地址Loc(ai)确定，而每个元素所占用的存储空间大小k为则第i个元素的地址可以由以下公式计算：Loc(ai)=Loc(a1)+(i-1)*L7/22/20212一维数组连续存储的线性聚集除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。一维数组是一个线性表。7/22/20213二维数组二维数组的任何一行都是一个线性表

2、二维数组可以看成由m个行向量组成的线性表，这种情况称为数组的行主序。二维数组也可以看成由n个行列向量组成的线性表，这种情况称为数组的列主序。7/22/20214二维数组的顺序存储结构两种情况：行优先顺序存储列优先顺序存储行优先顺序存储的地址关系Loc(aij)=Loc(a11)+((i-1)*n+(j-1))*L列优先顺序存储的地址关系Loc(aij)=Loc(a11)+((j-1)*m+(i-1))*L其中L是数组中每个元素占有的字节数7/22/20215数组顺序存储的优点随机存取三维数组顺序存储Amnp行优先的地址关系Loc(aij

3、k)=Loc(a111)+((i-1)*n*p+(j-1)*p+(k-1))*L列优先的地址关系Loc(aijk)=Loc(a111)+((k-1)*m*n+(j-1)*n+(i-1))*L7/22/20216矩阵的压缩存储矩阵是很多科学与工程计算问题中研究的数学对象。在此我们感兴趣的是如何存储矩阵的元素,从而使矩阵的各种运算等能够有效地进行。压缩存储：在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素或零元素，称为稀疏矩阵。为了节省空间，可以为多个值相同的元素只分配一个空间，对零元素不分配空间。特殊矩阵：值相同的元

4、素或零元素在矩阵中的分布有一定的规律。7/22/20217特殊矩阵对称矩阵：满足aij=aji1<=i,j<=n我们只存储矩阵的下三角及对角线。那么只需要n(n+1)/2个元素的空间。设以一维数组s[０...n(n+1)/2－１]来存储。则矩阵中的元素aij与其在数组中的位置有如下的关系：i>=j(下三角阵)：Loc(aij)=Loc(a11)+(i*(i-1)/2+(j-1))*Li<=j(上三角阵)：Loc(aij)=Loc(a11)+(j*(j-1)/2+(i-1))*L7/22/20218特殊矩阵三角矩阵：主对角线以上（或以下）

5、均为同一个常数，则称为下三角矩阵（或上三角矩阵）。设以一维数组s[0...n(n+1)/2]来存储，最后一个单元存储常数项。则矩阵中的元素aij与其在数组中的位置有如下的关系：i>=j(下三角阵)：Loc(aij)=Loc(a11)+(i*(i-1)/2+(j-1))*Li<=j(上三角阵)：Loc(aij)=Loc(a11)+((i-1)*(2n-i+2)/2+(j-i))*L7/22/20219带状（三对角）矩阵数据元素存放在主对角线及其临近的上下方。地址关系Loc(aij)=Loc(a11)+((i-1)*2+(j-1))*L=L

6、oc(a11)+(2i+j-3)*L7/22/202110稀疏矩阵我们在存储的时候，只记录t个非零元素的信息。除了存储非零元素的值之外，还存储它所在的行号和列号。由此构成一个三元组(i,j,aij)，该三元组唯一确定了该矩阵元素。除此而外，还记录矩阵的信息：行列m，n和非零元素的个数t。7/22/202111稀疏矩阵非零元素个数数组维数元素值元素下标7/22/202112TheEnd7/22/202113