第五章 数组(Array).ppt

《第五章 数组(Array).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组（Array）数组的定义及其基本操作数组的存储结构矩阵的压缩存储数据结构（DataStructure）定义及其操作定义：是n(n≥1)个相同类型数据元素a0,a1…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。在一维数组中，任一数据元素ai的存储地址Loc(ai)可以通过a0的地址Loc(a0)以及每个数据元素存储单元k由下式确定：数组满足随机存储特性可以证明：数组具有以下性质：（1）数组中的数据元素数目固定。（2）数组中的数据元素具有相同的数据类型。（3）数组中的每个数据元素都和一组唯一的下标值对应。（4）

2、数组是一种随机存储结构。.数组的基本操作:一般地，不对数组进行插入和删除操作1.随机存。2.随机取。（基本操作）3.数组列表。4.矩阵运算。（部分高级语言支持）存储结构一维数组：存储结构关系式为：二维及多维数组：通常有两种排序方式：1、行优先序列：将多维数组元素按行排列在PASCAL、C语言中，数组就是按行优先顺序存储的。2、列优先序列：将多维数组元素按列排列在FORTRAN语言中，数组就是按列优先顺序存储的。数组的静态存储分配和动态存储分配（p102）例，二维数组Am×n按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。则元素ai

3、j的存储地址为：LOC(aij)=LOC(a00)+[i*n+j]*d如果按“列优先顺序”，则为：LOC(aij)=LOC(a00)+[j*m+i]*d同样，三维数组Am×n×p按“行优先顺序”存储，则Aijk地址计算函数为：LOC(aijk)=LOC(a000)+[i*n*p+j*p+k]*d矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元

4、素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。压缩原理：对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。5.3矩阵的压缩存储不失一般

5、性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1对称矩阵a00a10a11a20…an-10…an-1,n-1sa：1、当i≧j，则aij在下三角形中，其在顺序存储表中元素sak的关系按下式计算：k=i*(i+1)/2+j0≦k

6、)/2令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：k=I*(I+1)/2+J0≦k

7、需要在算法中按公式作一映射即可实现矩阵元素的随机存储。p104稀疏矩阵简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵。准确说，在矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非

8、零元的三元组及其行列数唯一确定。0129000000-30015000000012000180-3000014090024000024000000000–70180