1. 数组
1. 数组的定义
- 数组:数组 是一组偶对(下标值,数据元素值)的集合。在数组中,对于一组有意义的下标,都存在一个与其对应的值。一维数组对应着一个下标值,二维数组对应着两个下标值
- 数组的特点
- 是由\(n(n>1)\)个具有相同数据类型的数据元素
a1
,a2
,...,an
组成的有序序列,且该序列必须存储在一块地址连续的存储单元中 - 数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素
- 数组中的数据元素个数是 固定 的
- 是由\(n(n>1)\)个具有相同数据类型的数据元素
- 直观的 \(n\) 维数组:以二维数组为例,将二维数组看成是一个定长的线性表,其每个元素又是一个定长的线性表
2. 数组的存储形式
- 存储形式:由于计算机的内存结构是一维的,因此用一维内存来表示多维数组,就必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放在存储器中。由于对数组一般不做插入和删除操作,也就是说,数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组
- 存储方式
- 行优先顺序:将数组元素按行排列,第i+1个行向量紧接在第i个行向量后面。以二维数组为例,按行优先顺序存储的线性序列为:\(a_{11},a_{12},\dots,a_{1n},a_{21},a_{22},\dots,a_{2n},\dots,a_{m1},a_{m2},\dots,a_{mn}\)
- 列优先顺序:将数组元素按列向量排列,第j+1个列向量紧接在第j个列向量之后,A的m × n个元素按列优先顺序存储的线性序列为:\(a_{11},a_{21},\dots,a_{m1},a_{12},a_{22},\dots,a_{m2},\dots,a_{1n},a_{2n},\dots,a_{nm}\)
2. 矩阵的压缩存储
1. 对称矩阵
-
特点:\(a_{ij}=a_{ji}\),因此只需要对 \(\frac{n(n+1)}{2}\) 个元素进行存储
-
对称矩阵元素\(a_{ij}\)保存在原数组中时的下标值k与(i,j)之间的对应关系
- \(k = \frac{i\times (i - 1)}{2}+j-1,i \ge j\)
- \(k = \frac{j\times (j - 1)}{2}+i - 1, i < j\)
2. 三角矩阵
-
特点:三角部分有数字,其余为0
-
下三角:
-
上三角:
-
-
对应关系
- 下三角:\(k = \frac{i\times (i - 1)}{2}+j-1,i \le j\)
- 上三角:\(k = \frac{i\times (i - 1)}{2}+j-1,i \ge j\)
3. 稀疏矩阵 的压缩
-
特点若一个m×n的矩阵含有t个非零元素,且 t 远远小于m×n,则我们将这个矩阵称为稀疏矩阵
-
压缩形式:三元组表示法
(i, j, val)
,其中i
,j
分别表示行号列号,val
表示数值,且以行优先存放 -
稀疏矩阵 快速转置 算法
- 本质:记录要存放的位置
- 算法
// the matrix is m * n size; // origin is Original tripletable // ans is the transposed matrix's tripletable /* stuct Triple{ int i, j, val; Triple(int i, int j, int val):i(i),j(j),val(val){} }; */ void FastTransposeMatrix(vector<Triple> origin, vector<Triple> ans){ vector<int> nums(n, 0); //统计矩阵每列非零元素的个数 vector<int> pos(n, 0); //统计矩阵每列第一个非零元素的位置 for(int col = 0; col < n; ++col) ++num[origin[col].j]; pos[0] = 1; for(int col = 1; col < n; ++col) pos[col] = pos[col - 1] + num[col - 1]; for(int idx = 0; idx < n; ++idx){ int col = origin[idx].j; int nowPos = pos[col]; ans[nowPos].i = origin[idx].j; ans[nowPos].j = origin[idx].i; ans[nowPos].val = origin[idx].val; ++pos[col]; //更新每列第一个元素的位置 } }
3. 广义表
- 定义:广义表(\(List\),又称为列表):是由\(n(n\ge 0)\)个元素组成的有穷序列:
Lst = (a1, a2, ..., an)
其中ai
或者是原子项,或者是一个广义表,\(n\)为它的长度。若ai
是广义表,则称为 子表。 - 与线性表的区别:线性表的数据元素都是 相同 的数据类型,但是广义表的数据元素可以还是广义表
- 性质
- 层次性:广义表可以是一个多层次的结构
- 共享性:一个广义表可以被其他广义表所共享
- 递归性:广义表可以是本身的子表
- 概念
- 广义表的长度:广义表中元素的数目
- 表头:非空广义表的 第一个元素
- 表尾:除表头元素之外,其余元素构成的 广义表
- 深度:广义表中括号的重数
List
长度 表头 表尾 深度 A = ()
0 无定义 无定义 1 B = (e)
1 e
()
2 C = (a, (b, c, d))
2 a
((b, c, d))
2 D = ((), e, (a, (b, c, d)))
3 ()
(e, (a, (b, c, d)))
3 E=(a, E)
2 a
(E)
\(\infty\)