一、一维数组与多维数组

1. 一维数组

一维数组的每个数组元素是一个序对，由下标(index)和值(value)组成。

数组的连续存储方式

2. 多维数组

二维数组的动态定义和初始化

int **A;
int row = 3, col = 3; int i, j;
A = new int* [row];
for(int i = 0; i < row; i++){
    A[i] = new int [col];
}

存储方式

• 行优先：存好一行再存一行

  $loc(j, k) = a + (j * col + k) * l$

• 列优先：存好一列再存一列

  $loc(j, k) = a + (k * row + j) * l$

三维数组

各维元素个数为$m_1, m_2, m_3$

下标为$i_1, i_2, i_3$的数组元素的存储地址：

$LOC(i_1, i_2, i_3) = a + (i_1 * m_2 * m_3 + i_2 * m_3 + i_3) * l$

二、特殊矩阵

指非零元素或零元素的分布有一定规律的矩阵：对称矩阵、三对角矩阵。

1. 对称矩阵的压缩存储

对于一个$n\times n$的对称阵$A$，可以只存其上三角矩阵或下三角矩阵，存的元素数量为$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$。

• 假设一个数组$B$只存其下三角矩阵，行优先

  • 若$i > j$，则$A[i][j]$则在下三角部分，在$B$中有储存，下标为$\frac{i(i+1)}{2} + j$
  • 若$j > i$，则$A[i][j]$在上三角部分，去找$A[j][i]$，下标为$\frac{j(j + 1)}{2} + i$

• 假设一个数组$B$只存其上三角矩阵，行优先

  • 若$j > i$，则$A[i][j]$在上三角部分，在$B$中有储存，下标为$n + (n - 1) + \cdots (n - i + 1) + j = \frac{i(2n - i + 1)}{2} + j$
  • 若$i < j$，则$A[i][j]$在下三角部分，去找$A[j][i]$，下标为$\frac{j(2n-j+1)}{2} + i$

2. 三对角矩阵的压缩存储

三对角矩阵总共有$3n - 2$个非零元素

在三条对角线上的元素$a_{ij}$满足：$0 \leq i \leq n - 1, \quad i - 1 \leq j \leq i + 1$

• 矩阵$A[i][j]$的在矩阵$b$中的位置为$(3 * i - 1) + (j - i + 1) = 2 * i + j$

• 若已知三对角矩阵中某元素$A[i][j]$在数组$b[]$存放在第$k$个位置，则有

  $$i = \lfloor \frac{(k + 1)}{3} \rfloor \quad j = k - 2 * i$$

•  

三、稀疏矩阵

稀疏因子：对于矩阵$A_{m \times n}$有$s$个非零元素，令稀疏因子$e = \frac{s}{m \times n}$，通常若$e \leq 0.05$，则称矩阵为稀疏矩阵

两种表示方式：三元组表示$(i, j, a_{ij})$确定了矩阵$A$的一个非零元素、正交链表表示

1. 三元组表示

三元组中的排列应该现根据行从小到大排，再根据列从小到大排

快速转置法

建立辅助数组rowSize、rowStart

2. 带行指针数组的二元组

3. 正交链表

优点：适应矩阵操作$(+、-、*)$是矩阵非零元素的动态变化

表头结点：

question：next和right的作用是什么？有什么区别？

非零元素结点

四、字符串

字符串是$n(n \geq 0)$个字符的有限序列。

1. 概念

子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串

子串在主串中的位置：位置从0开始数，首次出现的首字母位置。

2. 模式匹配(KMP 算法)

在主串中寻找子串（第一个字符）在串中的位置

用一个next特征向量来确定：

当模式$P$中第$j$个字符与目标$S$中相应字符失配时，模式$P$中应当由哪个字符（设为第$k+1$个）与目标中刚失配的字符重新继续进行比较

next数组的定义

next[i]表示模式串A[0]至A[i]这个字串，使得前$k$个字符等于后$k$个字符的最大值

五、广义表（General Lists）

1. 概念

广义表是$n(n \geq 0)$个表元素组成的有限序列，记作$LS(a_1, a_2, a_3, \cdots, a_n)$。

$LS$是表名，$a_i$是表元素，可以是表（称为子表），可以是数据元素（称为原子）。

$n$是表的长度，$n = 0$的广义表为空表。

表头：表的第一个表元素

表尾：其他表元素组成的表称为广义表的表尾（tail）

线性表：只包含原子的表

纯表：所有元素在表中仅出现一次

再入表/共享表：存在元素在在表中出现多次

2. 特性

有次序性、有深度、有长度、有共享、可递归（本身为自己的子表）

A()		// A长度为0，深度为1
B(6, 2)		// B长度为2，深度为1
C('a', (5, 3, 'x'))		// C长度为2，深度为2
D(B, C, A)		// D长度为3，深度为3

3. 表头、表尾

A()		// head(A) 和 tail(A) 不存在
B(6, 2)		// head(B) = 6, tail(B) = (2)
C('a', (5, 3, 'x'))		// head(C) = 'a', tail(C) = ((5, 3, 'x'))
D(B, C, A)		// head(D) = B, tail(D) = (C, A)

4. 广义表结点定义

utype | info | tlink

结点类型utype：

• 0， 表头
• 1， 原子数据
• 2， 子表

信息info：

• utype = 0时，存放引用计数
• utype = 1时，存放数据值value
• utype = 2时，存放指向子表表头的指针（hlink）

尾指针tlink：

• utype = 0时，指向该表第一个结点
• utype $\neq$ 0时，指向同一层下一个结点。