数据结构入门--数组与广义表

数组的顺序存储

数组是由相同类型的数据元素构成的有限集合。

数组一般采用顺序存储结构，因为存储单元是一维的，而数组可以是多维的，如何用一组连续的存储单元来存储多维数组呢？

以二维数组为例，可以按行序存储，即先存第一行，再存第二行…也可以按列序存储，先存第一列，再存第二列…

1. 按行序存储

   如果按行序存储，怎么找到 a ij 的存储位置呢？

   先看看存储 a ij 之前，前面已经存储了多少个元素：

   

   在 a ij 之前一共有 i×n+j 个元素，如果每个元素占用 L 字节，那么共需要 (i×n+j)×L 字节，只需要用基地址加上这些字节就可以得到 a ij 的存储地址了。

   按行序存储，a ij 的存储地址为：

   

   LOC(a 00 )表示第一个元素的存储地址，即基地址，LOC(a ij)表示 a ij 的存储地址。

2. 按列序存储

   如果按列序存储，怎么找到 a ij 的存储位置呢？

   先看看存储 a ij 之前，前面已经存储了多少个元素：

   

   在 a ij 之前一共有 j×m+i 个元素，如果每个元素占用 L 字节，那么共需要(j×m+i)×L 字节，只需要用基地址加上这些字节就可以得到 a ij 的存储地址了。

   按列序存储，a ij 的存储地址为：

   

   LOC(a00 )表示第一个元素的存储地址，即基地址，LOC(a ij)表示 a ij 的存储地址。

   注意：如果二维数组的下标是从 1 开始的，那么情形就变了。

   先看看存储 a ij 之前，前面已经存储了多少个元素：

   

   行数和个数都少 1，在 a ij 之前一共有 (i−1)×n+j−1 个元素，如果每个元素占用 L 字节，那么共需要 ((i−1)×n+j−1)×L 字节，只需要用基地址加上这些字节就可以得到 a ij 的存储地址了。

   如果二维数组下标从 1 开始，按行序存储，a ij 的存储地址为：

   

   LOC(a11 )表示第一个元素的存储地址，即基地址，LOC(a ij)表示 a ij 的存储地址。

   如果二维数组下标从 1 开始，按列序存储，a ij 的存储地址为：

   

   也就是说，如果下标是从 1 开始的，相应的公式需要行减 1，列减 1。

存储地址计算秘籍：a ij 的存储地址等于第一个元素的存储地址，加上前面的元素个数乘以每个元素占用的字节数。

LOC(aij) = LOC(第一个元素) +(aij 前面的元素个数) × 每个元素占的字节

特殊矩阵的压缩存储

• **什么是压缩存储？**给多个相同的元素分配一个存储空间，元素为 0 的不分配空间。
• **什么样的矩阵能够压缩？**一些特殊矩阵，如对称矩阵、三角矩阵、对角矩阵、稀疏矩阵等。
• **什么叫稀疏矩阵？**矩阵中非零元素的个数较少，怎样才算是较少呢？一般认为非零元素个数小于 5%的矩阵为稀疏矩阵。

对称矩阵：

对称矩阵比较特殊，其数据元素沿着对角线对称，即：aij = aji

那么，因为上三角和下三角是一样的，因此只存储其中的一个就可以了。如果用一维数组存储下三角，则只需要 n(n+1)/2 个空间，比全部存储需要 n^2 个空间少了很多。

如果按行序存储下三角，那么怎么找到 a ij 的存储位置呢？

先看看存储下三角中的 a ij 之前，前面已经存储了多少个元素:

如果将对称矩阵的下三角（i≥j）存储在一维数组 s[]中，那么下三角中 a ij 的下标就是 i(i−1)/2+j−1

而上三角的元素（i<j），根据对称性，a ij = a ji，可以直接读取下三角中的 a ji，因此按行序存储下三角时，a ij 的下标为：

**存储下标计算秘籍：**如果用一维数组 s[]存储（下标从 0 开始），则 a ij 的存储下标 k 等于a ij 前面的元素个数。

如果一维数组的下标从 1 开始呢？——公式后面再加 1 就行了。

上面的公式是计算一维数组存储的下标，如果给了基地址（a11 的存储地址），那么 aij 的存储地址为：

即 LOC(a ij)=LOC(第一个元素)+(a ij 前面的元素个数)×每个元素占用的字节。

三角矩阵：

三角矩阵比较特殊，分为下三角矩阵和上三角矩阵，下三角矩阵是指矩阵的下三角有数据，而其余的都是常数 c 或者为 0：

在下三角矩阵存储时，只需要存储其下三角中的元素，最后一个空间存储常数 c 即可。如果上面全为 0，则不需要存储；下三角也是如此。

例如下三角矩阵按行存储在一维数组 s[]中：

下三角矩阵如果按行序存储，怎么找到 a ij 的存储位置呢？

先看看存储 a ij 之前，前面已经存储了多少个元素：

如果一维数组的下标从零开始，那么下三角中 a ij 的下标就是 i(i−1)/2+j−1。而上三角的元素因为全是常数 c 或者为 0，最后一个空间（下标为 n(n+1)/2）存储常数 c 即可，如果是 0，则不需要存储。

因此下三角矩阵按行序存储时，a ij 的下标为：

上三角矩阵如果按行序存储，怎么找到 a ij 的存储位置呢？

先看看存储 a ij 之前，前面已经存储了多少个元素（梯形公式）：

如果一维数组的下标从 0 开始，那么上三角中 aij 的下标就是(i−1)(2n−i+2)/2+j−i。而下三角的元素全是常数 c 或者为 0，最后一个空间（下标为 n(n+1)/2）存储常数 c 即可。

因此上三角矩阵按行序存储时，a ij 的下标为：

对角矩阵：

对角矩阵又称为带状矩阵，是指在 n×n 的矩阵中非零元素集中在主对角线及其两侧，共 L（奇数）条对角线的带状区域内，称为 L 对角矩阵：

1. L 对角矩阵非零元素个数

   首先将每一行以对角线为中心进行补零，让每一行都达到带宽 L 个元素。一共补了多少个零呢？第一行补 d 个 0，第二行补 d−1 个 0 左上角补零个数为 d (d+1)/2。同理，右下角补零个数也为 d(d+1)/2，总的补零个数为 d(d+1)。那么每行按 L 个元素计算，再减去补零元素个数即可，即带状区域元素个数为 L×n−d(d+1)。因为 d=(L−1)/2，即 L=2d+1，所以带状区域元素个数也可以表达为(2d+1)×n−d(d+1)。

   

2. 按行序存储

   补零后每行都有 L 个元素，需要 L×n 个空间。为了节省空间，第一行前面和最后一行后面的 d 个 0 可以不存储，“掐头去尾”，需要 L×n−2d 个空间。

   

   怎么找到 a ij 的存储位置呢？

   首先找到 aii 的存储位置，因为 aii 是对角线上的元素，以对角线为中心，左右两侧都是d 个元素。a ii 之前有 i−1 行，每行 L 个元素，a ii 所在行左侧有 d 个元素，因此 a ii 之前有(i−1)×L+d 个元素。

   因为第一行前面的 d 个 0“掐头去尾”没有存储，所以 a ii 之前有(i−1)×L 个元素。aii 的存储位置为：(i−1)×L。而 aij 和 aii 相差 j−i 个元素，也就是说，aij的存储位置为：(i−1)×L+j−i：

   

   如果 a ij 在 a ii 的左侧（i>j）呢？它们之间相差 i−j 个元素。只需要计算出 a ii 的存储位置，减去它们之间的差值就可以了。
   即 aij 的存储位置为(i−1)×L−(i−j)=(i−1)×L+j−i。

   公式总结：

   按行序，用一维数组（下标从 0 开始）存储 L 对角矩阵，a ij 的存储位置为：

   

   例如3对角矩阵中 a ij 的存储位置为 k=3(i−1)+j−i=2i+j−3，如果一维数组的下标从 1 开始，公式后面再加 1 即可。

3. 按对角线存储

   对角矩阵还有一种按对角线的顺序存储方式：

   

   即对角线作为 0 行，左侧分别为 1, 2, …, d行，右侧分别为−1, −2, …, −d 行。相当于行转换为 i′=i−j，列值 j 不变，把 n×n 的 L 对角矩阵转换为 L×n 的矩阵：

   

   将其他位置补零：

   

   用一维数组 s[]（下标从 0 开始）按行序存储，仍然采用“掐头去尾”，第一行前面和最后一行后面的 d 个 0 不存储：

   

   怎么找到 a ij 的存储位置呢？

   a i′j 之前有 i′+d行，每行有 n 个元素，a i′j 所在行左侧有 j−1 个元素，因此 ai′j 之前有(i′+d)×n+j−1 个元素。

   因为第一行前面的 d 个 0“掐头去尾”没有存储，所以 a i′j 之前有(i′+d)×n+j−1−d 个元素。a i′j的存储位置为：(i′+d)×n+j−1−d。

   

   如果用一维数组（下标从 0 开始）按行序存储，a i′j 的下标为：

   

   又因为 i′=i−j，因此对角矩阵中的 a ij 下标为：

   

   公式总结：

   按对角线存储，对角矩阵中的 a ij 下标为：

   

稀疏矩阵：

稀疏矩阵是指非零元素个数较少，且分布没有规律可言，那么少到什么程度才算稀疏呢？一般认为非零元素小于 5%时，属于稀疏矩阵。

当然也没那么绝对，只要非零元素个数远远小于矩阵元素个数，就可以认为是稀疏矩阵。

为了节省空间，只需要记录每个非零元素的行、列和数值即可，这就是三元组存储法

广义表

广义表是线性表的推广，也称为列表。

它是 n(n≥0)个表元素组成的有限序列，记作 LS= (a0 , a1, a2 , …, a n−1 )。LS 是表名，a i 是表元素，它可以是表（称为子表），也可以是数据元素(称为原子)。

n 为表的长度，n=0 的广义表为空表。

广义表最常见的操作就是求表头和表尾。

• 表头 GetHead(L)：

  非空广义表的第一个元素，可以是一个单元素，也可以是一个子表。

  

• 表尾 GetTail(L)：

  删除表头元素后余下的元素所构成的表。表尾一定是一个表。

  

数组与广义表学习技巧

**存储地址计算秘籍：**a ij 的存储地址等于第一个元素的存储地址，加上前面的元素个数乘以每个元素占用的字节数。计算公式为：

LOC(第一个元素)表示第一个元素的存储地址，即基地址，LOC(a ij)表示 aij 的存储地址。

**存储下标计算秘籍：**如果用一维数组 s[]存储（下标从 0 开始），则 aij 的存储下标 k 等于a ij 前面的元素个数。计算公式为：

如果一维数组的下标从 1 开始，公式后面再加 1 就行了。