0、思维导图
1、数组与特殊矩阵
1）基础知识
在数据结构中，数组和特殊矩阵是基础且重要的概念，它们在存储和处理数据方面扮演着核心角色。以下是这两个概念的基础知识：
1️⃣数组（Array）
数组是一种线性数据结构，用于存储具有相同数据类型的元素的集合。数组中的每个元素都可以通过索引（或位置）直接访问。在内存中，数组的元素是的。
-
访问元素：可以通过索引直接访问数组中的元素。如果数组的首索引为0，则第 n n n 个元素的索引为 n − 1 n-1 n−1。访问时间复杂度为 O ( 1 ) O(1) O(1)。
-
插入和删除：在数组中插入或删除元素通常需要移动元素，以保持元素的连续性。因此，这些操作的时间复杂度为 O ( n ) O(n) O(n)，其中 n n n 是数组中的元素数量。
-
优点：直接索引访问；内存利用率高。
-
缺点：大小固定；插入和删除操作效率低。
2️⃣特殊矩阵
特殊矩阵是指具有特定规律或属性的，这使得它们可以用更优化的方式存储和处理。例如：
-
对角矩阵：除了主对角线外，其他元素都是0。可以用一个一维数组存储非零元素。
-
三角矩阵：
-
上三角矩阵：所有在主对角线以下的元素都是0。
-
下三角矩阵：所有在主对角线以上的元素都是0。
-
上三角和下三角矩阵可以通过压缩存储来优化空间，只存储非零元素。
-
-
稀疏矩阵：大部分元素为0的矩阵。可以用多种方式（如三元组表或链表）高效存储非零元素和它们的位置信息，从而节省空间。
-
对称矩阵： a [ i ] [ j ] = a [ j ] [ i ] a[i][j] = a[j][i] a[i][j]=a[j][i] 对所有 i i i 和 j j 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️⃣对称矩阵
- 元素关于主对角线对称位置的元素值相等
- 例如： ( 1 3 3 2 ) , ( 2 5 6 5 0 7 6 7 3 ) \begin{pmatrix} 1 & 3 \\ 3 & 2 \\ \end{pmatrix} , \quad \begin{pmatrix} 2 & 5 & 6 \\ 5 & 0 & 7 \\ 6 & 7 &3 \end{pmatrix} (1332), 256507673
2️⃣三角矩阵
-
以上或以下元素全为0的矩阵
-
以上全为0称为：下三角矩阵
-
以下全为0称为：上三角矩阵
-
- 例如： ( 1 0 4 2 ) , ( 2 0 0 0 0 0 4 6 3 ) \begin{pmatrix} 1 & 0 \\ 4 & 2 \\ \end{pmatrix} , \quad \begin{pmatrix} 2 & 0 & 0 \\ 0 & 0 & 0 \\ 4 & 6 &3 \end{pmatrix} (1402), 204006003
3️⃣三对角矩阵
-
当|i-j|>1（行列下标求差，结果大于1）时， a i j a_{ij} aij=0的矩阵
-
只有主对角线及其两侧的元素不为零
-
-
例如： ( a 11 a 12 a 21 a 22 a 23 a 32 a 33 a 34 a 43 a 44 ) \begin{pmatrix} a_{11} & a_{12} & & \\ a_{21} & a_{22} & a_{23} & \\ & a_{32} & a_{33} & a_{34} \\ & & a_{43} & a_{44} \end{pmatrix} a11a21a12a22a32a23a33a43a34a44
4）稀疏矩阵的压缩存储及运算
1️⃣稀疏矩阵
非零元素的个数 <<（远小于） 零元素的个数，并且非零元素分布无规律的矩阵。
2️⃣压缩存储
为了节约空间和提高效率，稀疏矩阵通常采用的方式，即只存储非零元素及其位置信息。
a.三元组顺序表
b.顺序表
3️⃣基本运算
转置、加法、乘法等基本运算。
2、广义表
1）基本概念
1️⃣广义表
一种线性存储结构，它可以存储不可再分的原子或者其他广义表，形式上类似于一个有限序列。例如： L S = ( a 1 , a 2 , . . . , a n ) L_S = (a_1,a_2,...,a_n) LS=(a1,a2,...,an)
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 L：
L = ( a , ( b , c ) , d ) L = (a, (b, c), d) L=(a,(b,c),d)
在这个例子中， L L L 包含三个元素： a a a，子表 ( b , c ) (b, c) (b,c)，和 d d d。
a.GetHead 运算
对广义表 L L L 执行 GetHead 运算将返回广义表的第一个元素：
GetHead ( L ) = a \text{GetHead}(L) = a GetHead(L)=a
b.GetTail 运算
对广义表 L L L 执行 GetTail 运算将返回除了第一个元素之外的所有元素构成的广义表：
GetTail ( L ) = ( ( b , c ) , d ) \text{GetTail}(L) = ((b, c), d) GetTail(L)=((b,c),d)
在执行 GetTail 运算后，我们得到一个新的广义表，它包含了原广义表的第二个和第三个元素。这里需要注意，GetTail 运算的结果是一个广义表，而非元素，即使只有一个元素，其仍为表。
4）广义表与线性表的联系
-
广义表 <-------> 线性表的推广
-
线性表 <-------> 广义表的特例