数据结构第9讲数组与广义表

港控/mmm° 2022-06-07 11:26 275阅读 0赞

**数据结构 第9讲 数组与广义表**

> 数组是由相同类型的数据元素构成的有序集合。
> 
> 一维数组看一看作一个线性表，例如：

![Center][]

图1一维数组

> 二维数组也可以看作一个线性表，例如：

![Center 1][]

图2二维数组（按列序）

> 是不是可以看作一个线性表*X*=(*X*0，*X*1，*X*2，*…*，*Xn*\-1)？只不过每一个数据元素*Xi*也是一个线性表。
> 
> 那么，横看成岭侧成峰：

![Center 2][]

图3二维数组（按行序）

> 也可以看作一个线性表*Y*=(*Y*0，*Y*1，*Y*2，*…*，*Ym*\-1)？只不过每一个数据元素*Yi*也是一个线性表。
> 
> 数组一般采用顺序存储结构，因为存储单元是一维的，而数组可以是多维，如何用一组连续的存储单元来存储多维数组呢？以二维数组为例，可以按行序存储，即先存第一行，再存第二行，…；也可以按列序存储，先存第一列，再存第二列，…；现在比较流行的C语言，Java都是按行序存储的。
> 
> **如果按行序存储，怎么找到*aij*的存储位置呢？**
> 
> 先看看在存储*aij*之前，前面已经存储了多少个元素：

![Center 3][]

图4二维数组（按行序存储）

> 从图4可以看出，在*aij*之前一共有***i*\**n*\+*j***个元素，如果每个元素用*L*个字节，那么需要**(*i*\**n*\+*j***)***\*L***个字节，只需要用基地址加上这些字节就可以得到*aij*的存储位置了。
> 
> 按行序存储，*aij*的存储位置：
> 
> ![Center 4][]
> 
> *LOC*(*a*00)表示第一个元素的存储位置，即基地址，*LOC*(*aij*)表示*aij*的存储位置。
> 
> 授人以鱼不如授人以渔，告诉你记住公式，就像送你一条鱼，不如交给你捕鱼的秘籍！
> 
> **存储位置计算秘籍：***aij*的存储位置等于矩阵第一个元素的存储位置，加上前面的元素个数\*每个元素占的空间数。

![Center 5][]

> **如果按列序存储，怎么找到*aij*的存储位置呢？**
> 
> 先看看在存储*aij*之前，前面已经存储了多少个元素：

![Center 6][]

图5二维数组（按列序存储）

> 从图5可以看出，在*aij*之前一共有***j*\**m*\+*i***个元素，如果每个元素用*L*个字节，那么需要**(*j*\**m*\+*i***)***\*L***个字节，只需要用基地址加上这些字节就可以得到*aij*的存储位置了。
> 
> 按列序存储，*aij*的存储位置：

![Center 7][]

> *LOC*(*a*00)表示第一个元素的存储位置，即基地址，*LOC*(*aij*)表示*aij*的存储位置。
> 
> **需要特别注意：二维数组的下标是从1开始的，那么画风就变了～～～**
> 
> 在很多科学工程计算问题中，经常遇到一些阶数很高的矩阵，而且这些矩阵的很多值是相同的，有的还有很多元素是0，为了节省空间，可以对这类矩阵进行压缩存储。

> **什么是压缩存储？**

> 把多个相同的元素分配一个存储空间，元素为0的不分配空间。
> 
> **什么样的矩阵能够压缩？**

> 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
> 
> **什么叫稀疏矩阵？**
> 
> 矩阵中非零元素的个数较少，怎样才算是较少呢？一般认为非零元素个数小于5%的矩阵为稀疏矩阵。
> 
> 下面介绍几种特殊矩阵的压缩存储方式：
> 
> **1.对角矩阵**
> 
> 对角矩阵是指在*n*´*n*的矩阵中，非零元素集中在主对角线及其两侧共*L*(奇数)条对角线的带状区域内—*L*对角矩阵。如图13所示。

![Center 8][]

图13 5对角矩阵

> 很明显，*L*对角矩阵的带宽为*L*，半带宽*d*=(*L*\-1)/2，例如5对角矩阵，半带宽*d*=2。当|*i*\-*j*|>*d*时，*aij*=0。当|*i*\-*j*|<=*d*时，*aij*≠0，为对角矩阵的带状区域元素。
> 
> 那么*L*对角矩阵一共有多少个非零元素呢？
> 
> 首先将每一行以对角线为中心，补零，让每一行都达到*L*个元素，如图14所示。一共补了多少个零呢？第一行补*d*，第二行补*d*，…，1，左上角补零个数为*d* (*d*\+1)/2，同理，右下角补零个数也为*d* (*d*\+1)/2，总的补零个数为*d* (*d*\+1)，那么每行按*L*个元素计算，再减去补零元素个数即可。即带状区域元素个数为：*L\*n*\-*d* (*d*\+1)，因为*d*=(*L*\-1)/2，即*L*=2*d*\+1，所有带状区域元素个数也可以表达为：(2*d*\+1)*\*n*\-*d* (*d*\+1)。

![Center 9][]

图14 5对角矩阵

> 那么，补零后每行都有*L*个元素，需要*L\*n*个空间。为了节省空间，第一行前面和最后一行后面的*d*个0可以不存储，即"**掐头去尾**"，即需要*L\*n*\-2*d*个空间。如图15所示，阴影部分就是要存储的元素。

![Center 10][]

图15 5对角矩阵（掐头去尾）

> 如果按行序，用一维数组（下标从零开始）存储*L*对角矩阵。
> 
> **怎么找到*aij*的存储位置呢？**
> 
> 首先找到*aii*的存储位置，因为*aii*是对角线上的元素，以对角线为中心，左右两侧都是*d*个元素，如图16所示。因此*aii*之前有*i*\-1行，每行*L*个元素，*aii*所在行左侧有*d*个元素，如图15所示。因此*aii*之前有(*i*\-1)*\*L*\+*d*个元素，因为第一行前面的*d*个0"**掐头去尾**"没有存储，所以*aii*之前有(*i*\-1)*\*L*个元素。*aii*的存储位置为：(*i*\-1)*\*L*。而*aij*和*aii*相差*j*\-*i*个元素，也就是说，*aij*的存储位置为：(*i*\-1)*\*L*\+*j*\-*i*。

![Center 11][]

图16对角矩阵存储（按行序）

> **总结公式：**
> 
> 按行序，用一维数组（下标从零开始）存储*L*对角矩阵，***aij*的存储位置：**
> 
> ![Center 12][]
> 
> 例如：3对角矩阵，*L*=3，得到3对角矩阵中*aij*的存储位置：*k*=3(*i*\-1)+*j*\-*i*=2*i*\+*j*\-3，同样，5对角矩阵中*aij*的存储位置：*k*=5(*i*\-1)+*j*\-*i*=4*i*\+*j*\-5。
> 
> 如果一维数组的下标从1开始，公式后面再\+1即可。
> 
> 对角矩阵还有一种按对角线的顺序存储方式，如图17所示：

![Center 13][]

图17 5对角矩阵

> 即对角线作为0行，左侧分别为1，2，…，*d*行，右侧分别为\-1，\-2，…，\-*d*行，列值不变，相当于转换为*L*×*n*的矩阵，如图18所示：

![Center 14][]

图18 5对角矩阵存储（按对角线）

> 那么图18中(*b*)矩阵，其它位置补零，用一维数组（下标从零开始）按行存储，*aij*之前有*iˊ*\+*d*行，*aij*所在行前面有*j*\-1个元素，因此下标为：

![Center 15][]

> **2. 稀疏矩阵**
> 
> 稀疏矩阵是指非零元素个数较少，且分布没有规律可言，那么少到什么程度才算稀疏呢？一般认为非零元素小于5%时，属于稀疏矩阵，当然也没那么绝对噢。如图19所示。

![Center 16][]

图19 稀疏矩阵

> 稀疏矩阵如何存储呢？
> 
> 为了节省空间，只需要记录每个非零元素的行、列和数值即可。这就是三元组存储法。如图20所示。

![Center 17][]

图20 稀疏矩阵三元组存储

> **广义表：**
> 
> 广义表是线性表的推广，也称为列表。它是*n*(*n*³0)个表元素组成的有限序列，记作*LS*= (*a*0, *a*1, *a*2, …,*an*\-1)，*LS*是表名，*ai*是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。*n*为表的长度。*n*=0的广义表为空表。
> 
> 广义表最常见就是求表头、表尾。
> 
> 表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表。
> 
> 表尾GetTail(L)：非空广义表删除表头元素后余下元素所构成的表。表尾一定是一个表。
> 
> 例如D=(a,(b),(a,(b,c,d)))，表长为，表头为a，表尾为( (b),(a,(b,c,d)))。如图21所示。

![Center 18][]

图21 广义表

[Center]: /images/20220607/1894c9dfdc9b4261a68ae3a1b06c4514.png
[Center 1]: /images/20220607/ecd3aeffe0e44def87d1ffc276da50a3.png
[Center 2]: /images/20220607/1371ac256911465ca43c94a4351c9fed.png
[Center 3]: /images/20220607/949d63d38a744b2fafce5911c857ff07.png
[Center 4]: /images/20220607/9883c192d08645438e87ccf32b3334ab.png
[Center 5]: /images/20220607/4393402e43f94c7c933fc8063072a4e8.png
[Center 6]: /images/20220607/25b830e6341d4ac6a4e441d1f0dbbbca.png
[Center 7]: /images/20220607/40d5a5b21843472c958b7bd8959bc03c.png
[Center 8]: /images/20220607/d5708a610432449f801709d241d39069.png
[Center 9]: /images/20220607/15a5e905a9ba4feebd718b75aa004689.png
[Center 10]: /images/20220607/c6630aa497924711b272caf8e39977c2.png
[Center 11]: /images/20220607/ff1cc16220de48209629281ad90ebc0f.png
[Center 12]: /images/20220607/cbcdb02de6c3468189bd76c1dad8047d.png
[Center 13]: /images/20220607/f9e72bc766574943aab054795d9d125f.png
[Center 14]: /images/20220607/bf2e9b973e0045d78e55749b7c63507d.png
[Center 15]: /images/20220607/43c41b495f1a4fd0801ee203a7b709b6.png
[Center 16]: /images/20220607/97fc3fdb2b6f4d07b673446167d3f13d.png
[Center 17]: /images/20220607/dfae4ea22a4d4de08955b02ff7393511.png
[Center 18]: /images/20220607/68f042d087a44dc289f45807c64dd590.png