数组的定义和运算
C语言支持一维数组和多维数组。如果一个数组的所有元素都不是数组，那么该数组称为一维数组。
image.png
image.png
在java中数组被看成是一个对象，在定义数组时，有两种定义方法：int[] a 和int a[]；第二种是C/C++对数组定义方式，对于JAVA建议采用第一种定义方式。
image.png
image.png
image.png
image.png
n维数组中的元素，每一个元素都受着n个关系的约束，在每个关系中，数据元素都有一个直接的后继元素，因此在这个 n个关系中的任一关系，就其单个关系而言，仍是线性的关系。
当n=1时；n维数组的定义就锐化为线性表的定义。反之，n维数组也可以看成是线性表的推广。
二维数组可以看成是每个数据元素是一个线性表。
image.png
一个三维数组可以用其数据元素为二维的线性表来定义。
由此可见n维数组是一种较为复杂的数据结构，但它可以由简单数据结构--线性表辗转合成而得。n维数组是一种“同构”的数据结构，即它的每个数据元素的数据类型相同。
数组的两种操作：
（1）给定一组下标，存取相应的数据元素；
（2）给定一组下标，修改相应的数据元素中的某一个或者几个数据项的值；
数组的顺序存储结构
由于数组一般不做插入或者删除的操作，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不在发生变动，因此采用顺序存储结构表示数组是自然的事。
由于存储单元是一维的结构，而数组是一个多维的结构，则用一组连续的存储单元存放数组的数据元素就有次序的约定的问题，例如对于二维数组的存储方式，一种是以列序为主序存储，另一种是以行序为主序存储。
矩阵的压缩存储
矩阵是很多科学与工程计算问题中研究的数学对象，如何存储矩阵的元，使得矩阵的各种运算能够有效的进行。通常的高级语言编制程序时，都是用二维数组来存储矩阵的元，有的语言中还提供了各种矩阵的运算，方便用户使用。
数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素，或者零元素。有时为了节省存储空间，可以对此类的矩阵进行压缩存储。压缩存储是指，为多个值相同的元只分配一个存储空间。
特殊矩阵
假若值相同的元素或者零元素在矩阵中的分布有一定的规律，我们称这种矩阵为特殊矩阵，反之为稀疏矩阵。
对称矩阵
对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可以将n的平方个元压缩存储到n（n+1）/2个元的空间中。
image.png
以下例子引用http://c.biancheng.net/cpp/html/966.html
对称矩阵的特点是：在一个n 阶方阵中，有aij=aji ，其中1≤i , j≤n，如图5.5 所示是一个５阶对称矩阵。对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可，比如，我们只存储下三角中的元素aij，其特点是中j≤i 且1≤i≤n，对于上三角中的元素aij ，它和对应的aji 相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要nn 个存储单元，现在只需要n(n+1)/2 个存储单元了，节约了n(n-1)/2个存储单元，当n 较大时，这是可观的一部分存储资源。
如何只存储下三角部分呢？对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n(n+1)/2 个元素，因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储顺序可用图5.6 示意，这样，原矩阵下三角中的某一个元素aij 则具体对应一个sak，下面的问题是要找到k 与i、j 之间的关系。
image.png
角中的元素aij，其特点是：i≥j 且1≤i≤n，存储到SA 中后，根据存储原则，它前面有i-1行，共有1+2+…+i-1=i(i-1)/2 个元素，而aij 又是它所在的行中的第j 个，所以在上面的排列顺序中，aij 是第i(i-1)/2+j 个元素，因此它在SA 中的下标k 与i、j 的关系为：
k=i(i-1)/2+j-1 (０≤k<n(n+1)/2 )
若i<j，则aij 是上三角中的元素，因为aij=aji ，这样，访问上三角中的元素aij 时则去访问和它对应的下三角中的aji 即可，因此将上式中的行列下标交换就是上三角中的元素在SA 中的对应关系：
k=j(j-1)/2+i-1 (０≤k<n(n+1)/2 )
对角矩阵
所有的非零元都集中在以对角线为中心的带状区域中。
image.png
对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，但在有些情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的。下面从这一角度来考虑这些特殊矩阵的存储方法。
稀疏矩阵
image.png
按照压缩存储的概念，只存储稀疏矩阵的非零元，同时记下她所在的行列的位置。
网友评论