重学数据结构（四、数组和广义表）

一、数组

1、数组的定义

数组是由类型相同的数据元素构成的有序集合,每个元素称为数组元素，每个元素受 n(n>=1) 个线性关系的约束，每个元素在 n 个线性关系中的序号i1, i2, …，in 称为该元素的下标，可以通过下标访问该数据元素。

数组分为一维数组和多维数组。

数组一旦被定义， 它的维数和维界就不再改变。 因此， 除了结构的初始化和销毁之外， 数组只有存取元素和修改元素值的操作。

1.1、一维数组

一维数组是指下标的个数只有一个的数组， 有时称为向量， 是最基本的数据类型， 在Java 中需要事先声明，程序才能够在编译过程中预留内存空间。

声明的格式一般为：

<数据类型><变量名称>[]= new<数据类型>[<数组大小>];

1

例如：

float numbera=new int[5];

1

声明一个长度为 5 的浮点数据类型的一维数组，数组名为numbera。

1.2、多维数组

多维数组是指下标的个数有两个或两个以上， 我们比较常用的是二维数组。

二维数组的声明同一维数组。 格式为：

<数据类型> <数组名称>[][]=new 〈数据类型>[sizel][size2];

1

例如：

int data[][]=newim [5][4];

1

表示声明了名称为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中的元素满足以下条件:

则成为对称矩阵。如下例：

结合数据结构压缩存储的思想，我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。

对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式：

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。

例如，在数组 skr[6] 中存储上文中的对称矩阵，则矩阵的压缩存储状态如图 所示（存储上三角和下三角的结果相同）：

注意，以上两个公式既是用来存储矩阵中元素的，也用来从数组中提取矩阵相应位置的元素。例如，如果想从上图中的数组提取矩阵中位于 (3,1) 处的元素，由于该元素位于下三角，需用下三角公式获取元素在数组中的位置，即：

1.2、稀疏矩阵

稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。

稀疏矩阵压缩存储主要采用三元表示法来实现。其存储规则是每一个非零元素占有一行， 每行中包含非零元素所在的行号、 列号、 非零元素的数值。

例如稀疏矩阵：

采用三元表示法：

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，则表示该节点为原子结点即无孩子结点。

上一篇：重学数据结构（三、队列）

下一篇：重学数据结构（五、串）

参考：

【1】：邓俊辉 编著. 《数据结构与算法》

【2】：王世民 等编著 . 《数据结构与算法分析》

【3】： Michael T. Goodrich 等编著.《Data-Structures-and-Algorithms-in-Java-6th-Edition》

【4】：严蔚敏、吴伟民 编著 . 《数据结构》

【5】：程杰 编著 . 《大话数据结构》

【6】：Java数据结构–数组、矩阵、广义表

【7】：矩阵（稀疏矩阵）压缩存储（3种方式）

【8】：什么是广义表、广义表及定义详解

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。