数据结构第4章 数组和广义表

名人说：莫道桑榆晚，为霞尚满天。——刘禹锡（刘梦得，诗豪）
本篇笔记整理：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊）

目录

• • 0、思维导图
  • 1、数组与特殊矩阵
  • • 1）基础知识
    • 2）顺序存储
    • 3）特殊矩阵的压缩存储
    • 4）稀疏矩阵的压缩存储及运算
  • 2、广义表
  • • 1）基本概念
    • 2）存储结构
    • 3）基本运算
    • 4）广义表与线性表的联系

0、思维导图

1、数组与特殊矩阵

1）基础知识

在数据结构中，数组和特殊矩阵是基础且重要的概念，它们在存储和处理数据方面扮演着核心角色。以下是这两个概念的基础知识：

1️⃣数组（Array）

数组是一种线性数据结构，用于存储具有相同数据类型的元素的集合。数组中的每个元素都可以通过索引（或位置）直接访问。在内存中，数组的元素是连续存储的。

• 访问元素：可以通过索引直接访问数组中的元素。如果数组的首索引为0，则第 $n$ 个元素的索引为 $n-1$。访问时间复杂度为 $O(1)$。

• 插入和删除：在数组中插入或删除元素通常需要移动元素，以保持元素的连续性。因此，这些操作的时间复杂度为 $O(n)$，其中 $n$ 是数组中的元素数量。

• 优点：直接索引访问；内存利用率高。

• 缺点：大小固定；插入和删除操作效率低。

2️⃣特殊矩阵

特殊矩阵是指具有特定规律或属性的矩阵，这使得它们可以用更优化的方式存储和处理。例如：

1. 对角矩阵：除了主对角线外，其他元素都是0。可以用一个一维数组存储非零元素。

2. 三角矩阵：

   • 上三角矩阵：所有在主对角线以下的元素都是0。

   • 下三角矩阵：所有在主对角线以上的元素都是0。

   • 上三角和下三角矩阵可以通过压缩存储来优化空间，只存储非零元素。

3. 稀疏矩阵：大部分元素为0的矩阵。可以用多种方式（如三元组表或链表）高效存储非零元素和它们的位置信息，从而节省空间。

4. 对称矩阵：$a[i][j]=a[j][i]$ 对所有 $i$ 和 $j$。只需存储上三角或下三角的元素。

3️⃣存储特殊矩阵

对于特殊矩阵，可以采取优化的存储方法，以减少存储空间和提高处理效率。例如，稀疏矩阵的压缩存储可以通过记录非零元素的值及其索引来实现。这种方法在处理大规模稀疏矩阵时特别有效。

了解好基础知识后，来看一下其存储方式：

2）顺序存储

1️⃣行优先存储

数组每一行元素在内存中是连续的，即先存储第一行，再存储第二行，依次类推。

计算公式：LOC(i,j) = LOC(0,0) + [i * n + j] *L;

2️⃣列优先存储

数组的每一列元素在内存中是连续的，即先存储第一列，再存储第二列，依次类推。

计算公式LOC(i,j) = LOC(0,0) + [j * m + i] *L;

3️⃣公式说明

• 设数组为A[m][n]，求A[i][j]元素的存储地址

• 存储单元大小L

• 数组下标从0开始，如若从1开始，要注意区分，可能需要-1

4️⃣为什么有行列优先之分？

主要取决于程序对数组的访问模式和计算需求。

• 如果程序主要是按照行进行遍历或操作的话，那么使用行优先存储会更加高效，因为这样可以减少内存地址的跳转次数，提高缓存命中率。
• 如果程序主要是按照列进行遍历或操作的话，那么使用列优先存储会更加高效，原理同上。

另外，不同的数组存储方式也会影响到矩阵运算的结果，因为矩阵乘法涉及到行和列的交换，所以需要注意矩阵的转置和顺序问题。

3）特殊矩阵的压缩存储

1️⃣对称矩阵

• 元素关于主对角线对称位置的元素值相等

• 例如：$\left(\begin{array}{cc}1& 3\\ 3& 2\end{array}\right),\left(\begin{array}{ccc}2& 5& 6\\ 5& 0& 7\\ 6& 7& 3\end{array}\right)$

2️⃣三角矩阵

• 主对角以上或以下元素全为0的矩阵

  • 以上全为0称为：下三角矩阵

  • 以下全为0称为：上三角矩阵

• 例如：$\left(\begin{array}{cc}1& 0\\ 4& 2\end{array}\right),\left(\begin{array}{ccc}2& 0& 0\\ 0& 0& 0\\ 4& 6& 3\end{array}\right)$

3️⃣三对角矩阵

• 当|i-j|>1（行列下标求差，结果大于1）时，$a_{ij}$=0的矩阵

• 只有主对角线及其两侧的元素不为零

• 

• 例如：$\left(\begin{array}{cccc}{a}_{11}& a_{12}& & \\ a_{21}& a_{22}& a_{23}& \\ & a_{32}& a_{33}& a_{34}\\ & & a_{43}& a_{44}\end{array}\right)$

4）稀疏矩阵的压缩存储及运算

1️⃣稀疏矩阵

非零元素的个数 <<（远小于） 零元素的个数，并且非零元素分布无规律的矩阵。

2️⃣压缩存储

为了节约空间和提高效率，稀疏矩阵通常采用压缩存储的方式，即只存储非零元素及其位置信息。

a.三元组顺序表

b.顺序表

3️⃣基本运算

转置、加法、乘法等基本运算。

2、广义表

1）基本概念

1️⃣广义表

一种线性存储结构，它可以存储不可再分的原子或者其他广义表，形式上类似于一个有限序列。例如：$L_S=(a_1,a_2,...,a_n)$

2️⃣广义表深度

括号层数

最外层到最里层有几层括号，广义表的深度就是几。

3️⃣广义表长度

它所包含的元素个数。

广义表中有多少元素，长度就为多少。

2）存储结构

广义表是一种特殊的线性表，它允许元素既可以是单个元素，也可以是另一个广义表。因此，广义表的存储结构需要能够表示这种嵌套关系。

广义表的存储结构主要有两种：

头尾链表和扩展线性链表存储结构。

1️⃣头尾链表存储

头尾链表存储结构使用两个指针来表示一个广义表：

• 表头指针：指向广义表第一个元素的指针
• 表尾指针：指向广义表最后一个元素的指针

广义表中的每个元素都用一个结点来表示，结点包含以下两个域：

• 数据域：存储元素的值
• 下一结点指针：指向下一个元素的指针

对于原子元素，其下一结点指针为NULL。对于子表元素，其下一结点指针指向子表的表头结点。

a.优点：

• 存储结构简单，易于理解和实现
• 插入和删除操作比较方便

b.缺点：

• 查找操作比较困难，需要遍历整个广义表
• 空间利用率不高，因为每个结点都需要存储一个下一结点指针

2️⃣扩展线性链表存储

扩展线性链表存储结构使用一个数组来表示一个广义表。数组中的每个元素可以是原子元素，也可以是子表的地址。

对于原子元素，其地址直接存储在数组中。对于子表元素，其地址指向子表在数组中的起始位置。

a.优点：

• 查找操作比较方便，可以直接通过地址访问数组中的元素
• 空间利用率比较高

b.缺点：

• 插入和删除操作比较困难，需要移动数组中的元素

两种存储结构的比较如下表:

选择哪种存储结构取决于具体的应用需求。

• 如果需要频繁地进行查找操作，则可以使用扩展线性链表存储结构;
• 如果需要频繁地进行插入和删除操作，则可以使用头尾链表存储结构。

3）基本运算

广义表（Generalized List）是线性表的一种推广。在广义表中，元素既可以是单个元素，也可以是另一个广义表。广义表的两个基本运算是 GetHead 和 GetTail：

• GetHead：获取广义表的第一个元素。如果这个元素是另一个广义表，那么返回的就是这个子表。
• GetTail：获取除了第一个元素外，广义表中剩余的所有元素构成的广义表。

总结来看如下：

1️⃣求表头GetHead（L）

• 非空广义表的第一个元素

• 可以是一个元素 / 子表

2️⃣求表尾GetTail(L)

• 非空广义表除表头元素以外其它元素构成的表

• 一定是一个表

3️⃣举例

假设我们有以下广义表 $L$：

$$L=(a,(b,c),d)$$

在这个例子中，$L$ 包含三个元素：$a$，子表 $(b,c)$，和 $d$。

a.GetHead 运算

对广义表 $L$ 执行 GetHead 运算将返回广义表的第一个元素：

$$\text{GetHead}(L)=a$$

b.GetTail 运算

对广义表 $L$ 执行 GetTail 运算将返回除了第一个元素之外的所有元素构成的广义表：

$$\text{GetTail}(L)=((b,c),d)$$

在执行 GetTail 运算后，我们得到一个新的广义表，它包含了原广义表的第二个和第三个元素。这里需要注意，GetTail 运算的结果是一个广义表，而非元素，即使只有一个元素，其仍为表。

4）广义表与线性表的联系

• 广义表 <-------> 线性表的推广

• 线性表 <-------> 广义表的特例

上述内容笔记部分图片来源网络，侵删。
参考内容：

1. 王道论坛.数据结构.中国工信出版社
2. 严蔚敏, 吴伟民. 数据结构 (第二版). 清华大学出版社.

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
点赞加关注，收藏不迷路！本篇文章对你有帮助的话，还请多多点赞支持！