1、数组的定义
数组是由类型相同的数据元素构成的有序集合,每个元素称为数组元素，每个元素受 n(n>=1) 个线性关系的约束，每个元素在 n 个线性关系中的序号i1, i2, …，in 称为该元素的下标，可以通过下标访问该数据元素。
数组分为一维数组和多维数组。
数组一旦被定义， 它的维数和维界就不再改变。 因此， 除了结构的初始化和销毁之外， 数组只有存取元素和修改元素值的操作。
1.1、一维数组
一维数组是指下标的个数只有一个的数组， 有时称为向量， 是最基本的数据类型， 在Java 中需要事先声明，程序才能够在编译过程中预留内存空间。
声明的格式一般为：
<数据类型><变量名称>[]= new<数据类型>[<数组大小>];
例如：
float numbera=new int[5];
声明一个长度为 5 的浮点数据类型的一维数组，数组名为numbera。
1.2、多维数组
多维数组是指下标的个数有两个或两个以上， 我们比较常用的是二维数组。
二维数组的声明同一维数组。 格式为：
<数据类型> <数组名称>[][]=new 〈数据类型>[sizel][size2];
例如：
int data[][]=newim [5][4];
表示声明了名称为data的整形二维数组。
2、数组存储
2.1、一维数组的存储
一维数组A[n] = {a0, a1…,an-1}的数据存储按照顺序存储， 逻辑地址和物理地址都是连续的。
一维数组任意数据元素ai的存储单元地址：Loc(ai) = Loc(a0) + i * k (0 ≤ i < n)，其中k为单个元素所占空间。
2.2、多维数组的存储
由于内存是一维的，而数组是多维结构，可以认为二维数组是一个每个数据元素是一维数组的一维数组；三维数组是每个数据元素是二维数组的一维数组；四维数组是个每个数据元素是三维数组的一维数组，以此类推。
以二维数组的顺序存储为例说明， 对于一个m×n的二维数组，可以看成一个矩阵：
也可以看成一个行向量的一维数组：
二维数组在顺序存储时一般有两种。
- 行优先顺序： 存储时先按行从小到大的顺序存储， 在每一行中按列号从小到大存储。
- 列优先顺序： 存储时先按列从小到大的顺序存储， 在每一列中按行号从小到大存储。
以上的两种存储顺序中， 第一个被存放的元素总是第一行第一列的数据元素， 所以该元素的地址是我们的己知条件。
行优先顺序存储二维数组的任一数据元素 a[i,j] 的存储单元地址：Loc(a[i，j]) = Loc(a[0, 0]) + (i * n + j) *k （0 ≤ i < m，0 ≤ j < n），其中k为单个元素所占空间。
列优先存储的二维数组a[i,j]的存储单元地址：Loc(a[i,j]) = Loc(a[0,0]) + (j * m + i)*k（0 ≤ i < m，0 ≤ j < n），其中k为单个元素所占空间。
二、矩阵的存储
1、矩阵的压缩存储
所谓矩阵的压缩存储， 也就是在存储数组时， 尽量减少存储空间， 所以在矩阵存储中， 如果有规律可寻， 只要存储其中一部分， 而另一部分的存储地址可以通过相应的算法将它计算出来， 从而占有比较少的存储空间达到存储整个矩阵的目的。
矩阵的压缩存储仅是针对特殊矩阵的， 而对于没有规律可循的二维数组则不能够使用矩阵压缩存储。
二维数组(矩阵)的压缩存储一般有 3 种， 它们分别是对称矩阵、 稀疏矩阵和三角矩阵。
1.1、对称矩阵
若n阶矩阵A中的元素满足以下条件:
aij=aji（i>=1;j>=1）
则成为对称矩阵。如下例：
结合数据结构压缩存储的思想，我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。
对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：
存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：
最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。
例如，在数组 skr[6] 中存储上文中的对称矩阵，则矩阵的压缩存储状态如图 所示（存储上三角和下三角的结果相同）：
注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。例如，如果想从上图中的数组提取矩阵中位于 (3,1) 处的元素，由于该元素位于下三角，需用下三角公式获取元素在数组中的位置，即：
1.2、稀疏矩阵
稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。
稀疏矩阵压缩存储主要采用三元表示法来实现。其存储规则是每一个非零元素占有一行， 每行中包含非零元素所在的行号、 列号、 非零元素的数值。
(row col value)
例如稀疏矩阵：
采用三元表示法：
1.3、三角矩阵
以对角线划分，三角矩阵有上三角和下三角两种。
主对角线下的数据元素全部相同的矩阵为上三角矩阵，主对角线上元素全部相同的矩阵为下三角矩阵。
对于这类特殊的矩阵，压缩存储的方式是：重复元素C可共用一个存储空间，其余的元素可以采用对称矩阵的压缩存储方式存储。
这么一来，对称矩阵可以看做一种特殊的三角矩阵。
三、广义表
1、广义表的定义
广义表是线性表的推广， 具体定义为n(n>=0)个元素的有限序列。
一般记作：LS=(a1,a2,a3, … ai, …, an)
广义表的数据元素可以分为两种，一种不可再分（原子），一种可再分（子表）。
以下是一些常见的广义表定义：
- A = ()：A 表示一个广义表，只不过表是空的。
- B = (e)：广义表 B 中只有一个原子 e。
- C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
- D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
- E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。
从上面的例子可以归纳出一些结论：
- 广义表的元素可以是子表， 而子表的元素还可以是子子表……由此， 广义表是一个多层次的结构。
- 广义表可为其他广义表共享。
- 广义表可以是一个递归表，即广义表也可以是其本身的一个子表。
当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。
2、广义表的存储
由于广义表中的数据元素具有不同的结构，通常是一种递归的数据结构，很难为每个广义表分配固定大小的存储空间，一般用链式存储结构表示，有头尾表示法和孩子兄弟表示法两种存储方式。
2.1、头尾表示法
任意非空的广义表，可分解为表头和表尾，反之，一对确定的表头和表尾可唯一确定一个广义表。
在头尾表示法中需要有两种结构的结点：一种是表结点，可以表示字表；一种是原子结点，用来表示原子。
在表结点中有三个域组成：标志域、指向表头的指针域和指向表尾的指针域；
而原子结点需要两个域：标志域和值域。标志域是用来区分这两种结点的。
2.3、孩子兄弟表示法
在孩子兄弟表示法中，原子结点和表结点用相似的两种结点来表示。
其中表结点有孩子结点，cp和bp分别指向第一个孩子换一个兄弟的指针域；
原子结点是无孩子结点，data和bp分别是指域和指向兄弟的指针域。
tag是标志域，用来区分这两类结点，如tag为1，则表示该结点为表结点即有孩子的结点；tag为0，则表示该节点为原子结点即无孩子结点。
