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

╰+攻爆jí腚メ 2022-05-17 13:39 238阅读 0赞

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

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

一维数组看一看作一个线性表，例如：

![这里写图片描述][70]

图1一维数组

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

![这里写图片描述][70 1]

图2二维数组（按列序）

是不是可以看作一个线性表X=(X0，X1，X2，…，Xn-1)？只不过每一个数据元素Xi也是一个线性表。

那么，横看成岭侧成峰：

![这里写图片描述][70 2]

图3二维数组（按行序）

也可以看作一个线性表Y=(Y0，Y1，Y2，…，Ym-1)？只不过每一个数据元素Yi也是一个线性表。

数组一般采用顺序存储结构，因为存储单元是一维的，而数组可以是多维，如何用一组连续的存储单元来存储多维数组呢？以二维数组为例，可以按行序存储，即先存第一行，再存第二行，…；也可以按列序存储，先存第一列，再存第二列，…；现在比较流行的C语言，Java都是按行序存储的。

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

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

![这里写图片描述][70 3]

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

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

按行序存储，aij的存储位置：  
![这里写图片描述][70 4]

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

授人以鱼不如授人以渔，告诉你记住公式，就像送你一条鱼，不如交给你捕鱼的秘籍！

存储位置计算秘籍：aij的存储位置等于矩阵第一个元素的存储位置，加上前面的元素个数\*每个元素占的空间数。

![这里写图片描述][70 5]

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

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

![这里写图片描述][70 6]

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

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

按列序存储，aij的存储位置：

![这里写图片描述][70 7]

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

需要特别注意：二维数组的下标是从1开始的，那么画风就变了～～～

在很多科学工程计算问题中，经常遇到一些阶数很高的矩阵，而且这些矩阵的很多值是相同的，有的还有很多元素是0，为了节省空间，可以对这类矩阵进行压缩存储。

什么是压缩存储？  
把多个相同的元素分配一个存储空间，元素为0的不分配空间。

什么样的矩阵能够压缩？  
一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

什么叫稀疏矩阵？  
矩阵中非零元素的个数较少，怎样才算是较少呢？一般认为非零元素个数小于5%的矩阵为稀疏矩阵。

下面介绍几种特殊矩阵的压缩存储方式：

1.对角矩阵

对角矩阵是指在n´n的矩阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内—L对角矩阵。如图13所示。

![这里写图片描述][70 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=2d+1，所有带状区域元素个数也可以表达为：(2d+1)\*n-d (d+1)。

![这里写图片描述][70 9]

图14 5对角矩阵

那么，补零后每行都有L个元素，需要L\*n个空间。为了节省空间，第一行前面和最后一行后面的d个0可以不存储，即”掐头去尾”，即需要L\*n-2d个空间。如图15所示，阴影部分就是要存储的元素。  
![这里写图片描述][70 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。

![这里写图片描述][70 11]

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

总结公式：

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

![这里写图片描述][70 12]

例如：3对角矩阵，L=3，得到3对角矩阵中aij的存储位置：k=3(i-1)+j-i=2i+j-3，同样，5对角矩阵中aij的存储位置：k=5(i-1)+j-i=4i+j-5。

如果一维数组的下标从1开始，公式后面再+1即可。

对角矩阵还有一种按对角线的顺序存储方式，如图17所示：

![这里写图片描述][70 13]

图17 5对角矩阵

即对角线作为0行，左侧分别为1，2，…，d行，右侧分别为-1，-2，…，-d行，列值不变，相当于转换为L×n的矩阵，如图18所示：  
![这里写图片描述][70 14]

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

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

![这里写图片描述][70 15]

1.  稀疏矩阵

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

![这里写图片描述][70 16]

图19 稀疏矩阵

稀疏矩阵如何存储呢？

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

![这里写图片描述][70 17]

图20 稀疏矩阵三元组存储

广义表：

广义表是线性表的推广，也称为列表。它是n(n³0)个表元素组成的有限序列，记作LS= (a0, a1, a2, …,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所示。

![这里写图片描述][70 18]

[70]: /images/20220517/c8d793ce7c054438b6ee3687295b14d9.png
[70 1]: /images/20220517/d51aa582420c48f2a578c07ac2333e0d.png
[70 2]: /images/20220517/eba7f8752c2047ccbf5d53d4bdfd76f7.png
[70 3]: /images/20220517/d770b03de90d4855b81441ec5b9f346d.png
[70 4]: /images/20220517/7199dd3239dd41229dafac59abd2df57.png
[70 5]: /images/20220517/c2bab541663643f39e75827578ef3050.png
[70 6]: /images/20220517/410bfca05a714e2081432ac4fab2278a.png
[70 7]: /images/20220517/96e36c87dd6a4b47ac9c29a5e3c2b771.png
[70 8]: /images/20220517/3f661306074141d28ca45ba38a5ea668.png
[70 9]: /images/20220517/4677ed68bfe049e0aa34994376893567.png
[70 10]: /images/20220517/dc8d0ead85394f6d96f003d2b3f339f0.png
[70 11]: /images/20220517/8881d70e3c724117a8628d76b0d872b7.png
[70 12]: /images/20220517/891f49cd2d684a79baf7dfb96d224366.png
[70 13]: /images/20220517/e4b34707732a4c67bb695199d6d5b472.png
[70 14]: /images/20220517/376b157fcf0146dda0f98d2e8a23474f.png
[70 15]: /images/20220517/c9eee0fe584a46baa4c45c0a83f5b8aa.png
[70 16]: /images/20220517/80ae20ca51814fe98afacfda72e12f4b.png
[70 17]: /images/20220517/d167bffa75ca4bc4a212e7777225ff90.png
[70 18]: /images/20220517/e8be8bb11f3d4c97a0959cd24051fc6e.png