⇧
❮
❯
↻
🍀计算机基础🍀 4136字 21分钟

数据结构强化笔记（5）：数组、矩阵、广义表

作者

本文介绍三种扩展线性表结构——数组、矩阵、广义表。

Hyplus目录

1 数组

数组（Array）：线性表的推⼴，结构中的元素本身可以是具有某种结构的数据，但应属于同⼀数据类型。

⼆维数组（2D Array）：元素为⼀维数组的数组，但在内存中依旧连续存储。

数组的正常配置：从下标开始存储元素，即起始下标为\text{0}，如A[0]、A[0][0]

写法：A[n]、A[n][m]分别等价于A[0...n-1]、A[0...n-1][0...m-1]；A[1...n]、A[1...n][1...m]表示指定从下标1开始存储元素的非正常配置

元素存储地址计算：设L为每个数组元素所占的存储单元大小

  1. 一维数组计算式：\text{LOC}(a_i)=\text{LOC}(a_0)+i\times L
  2. 二维数组存储/映射方式若二维数组A的行数为r、列数为c，则存储结构计算式为
    • 行优先存储：\text{LOC}(a_{i,j})=\text{LOC}(a_{0,0})+(i\times c + j)\times L
    • 列优先存储：\text{LOC}(a_{i,j})=\text{LOC}(a_{0,0})+(i+j\times r) \times L

【总结与归纳】巧算二维数组/矩阵元素地址：

  1. “○”优先，则“另一个”乘向“○”的下标
  2. 对于从下标1开始存元素的二维数组（即矩阵），改写成数组的正常配置再套公式，若要算“之前有多少元素”则⽆需修缮直接结果

2 矩阵

矩阵（Matrix）：⼆维数组的代数表示。

矩阵的正常配置：从下标1开始存储元素，即起始坐标为a_{11}

上述的数组元素地址计算式同样适⽤于矩阵（需先改写成数组的正常配置）

2.1 特殊矩阵的压缩存储

将矩阵通过某种⽅式⽤更少的空间存储称为矩阵的压缩存储，通常用⼀维数组B[0...MAXSIZE]或类似结构。思想：相同元素只存储⼀份。

  1. 对称矩阵：n阶方阵A_{n\times n}中，满足a_{ij}=a_{ji}
    • 压缩存储方法：只将下三⻆（含对⻆线）的元素存⼊⼀维数组，所需存储空间为\dfrac{(1+n)n}{2}
    • 下三角部分：设a_{ij}在一维数组B[0...MAXSIZE]中对应的下标为k，则 
      \begin{aligned}
k=\dfrac{i(i-1)}{2}+j-1
\end{aligned}

      【推导】对1,\cdots,i-1求和，加上自身列标；数组从下标0开始存储故减1（若从下标1开始存储则无需减）

    • 上三角部分：因为a_{ji}=a_{ij}，故将上式的i,j直接轮换即可

  1. 上/下三角矩阵：主对角线的一侧全为常数c（可为\text{0}）
    • 压缩存储方法：与对称矩阵类似，将非c三角的元素存⼊⼀维数组，常数c非零时可存于表尾\dfrac{(1+n)n}{2}（零元素则无需存储），故所需存储空间为\dfrac{(1+n)n}{2}+1
    • 下三角矩阵：同对称矩阵下三角部分
    • 上三角矩阵：设a_{ij}在一维数组B[0...MAXSIZE]中对应的下标为k，则 
      \begin{aligned}
k=\dfrac{(i-1)(2n-i+2)}{2}+(j-i)
\end{aligned}

  1. （三）对角矩阵（带状矩阵）：除主对⻆线及其上下两条斜向带状区域内元素外，其余元素全为常数c（可为\text{0}）
    • 压缩存储方法：类似三角矩阵，常数c非零时可存于表尾，计算思路亦基本一致（注意最上、下两⾏元素仅含2个非c元素）

2.2 稀疏矩阵的存储⽅法

稀疏矩阵：⾮零元素远少于零元素的矩阵，可以利用零元素节约大量存储、运算和程序运行时间。

常见的稀疏矩阵存储方法如下所示：

  1. 三元组表示法：根据⾏优先或列优先，⽤三元数对(i,j,v)的三元组矩阵存储⾮0元素的特征。在节省大量存储空间的同时，会使得稀疏矩阵失去随机存取的特性
    • 0行特殊存储稀疏矩阵信息：行数、列数、非零元个数
    • 其余每行代表一个非零元素：行标、列标、值

【例】如图为以⾏优先存储将稀疏矩阵M⽤三元组矩阵表示：

  1. 伪地址法：按元素在矩阵中⾏优先或列优先存储的相对位置计算得出其伪地址（同5.1中数组的元素存储地址计算）
  2. 邻接表表示法：⽤存图的⽅式存储（详见“邻接表”）
  3. ⼗字链表表示法：使⽤⼗字链表存储，结构体如下
typedef struct OLNode {
    int row, col;   // ⾏号、列号
    struct OLNode *right, *down;    // 指向右边结点、下⽅结点
    ElemType val;   // 若为元素结点则储存元素值，若为表最左边、最上边的头结点则不存储数据
} OLNode;   // 链表结点

typedef struct OLHead {
    OLNode *rhead, *chead;  // 指向⾏、列头结点数组
    int m, n, k;    // 矩阵⾏数、列数、⾮零结点总数
} CrossList;

3 广义表

⼴义表（Generalized List）：表元素可以是原⼦或者⼴义表的线性表扩展结构。

3.1 广义表的重要概念

⻓度（Length）：表直接包含的元素（原子或子表）的个数，即广义表表达式中最上层元素的个数。长度为0的表称为空表，用()表示。

深度（Depth）：广义表表达式中嵌套括号的最⼤层数。特别地，原子的深度为0，空表的深度为1。

【例1】写出下列⼴义表的⻓度与深度

  • A=(())：元素为空表的表。⻓度为1，深度为2
  • B=(d,e)：元素全为原⼦。⻓度为2，深度为1
  • C=(b,(c,d))：第⼆个元素为另⼀个⼴义表(c,d)。⻓度为2，深度为1
  • D=(B,C)：引⽤了已有⼴义表B,C，展开可得((d,c),(b,(c,d)))，⻓度为2，深度为3
  • E=(a,E)：长度为2；由递归定义，展开可得(a,(a,(a,(a,\cdots))))，深度无限
  • F=((a))：元素为“元素只含原子a的表”的表。⻓度为1，深度为2

表头（Head）：第⼀个元素（既可为原⼦也可为表）

表尾（Tail）：其余所有元素组成的表（只可为表）

常⽤操作：取表头\text{GetHead}(\cdot)、取表尾\text{GetTail}(\cdot)

【例2】对例1中出现的部分表执⾏各种取表头尾操作：
\text{GetHead}(B)=d,\ \text{GetTail}(B)=(e),\ \text{GetHead}(D)=B,\ \text{GetTail}(D)=(C),\ \text{GetHead}(F)=(a),\ \text{GetTail}(F)=()

3.2 广义表的存储结构

头尾链表存储结构：如图所示

  • 基本结点结构：
    • 原子结点：标记域（0）、数据域
    • 广义表结点：标记域（1）、头指针域（指向原子或广义表结点）、尾指针域（非空则指向本层下一个广义表结点）
  • 特点（类似无头单链表）：
    1. 链表主体都是⼴义表结点，原⼦结点只能从⼴义表结点头指针域引出
    2. 广义表结点的头指针域可直接指向现有⼴义表（与其头指针汇合来引⽤），也可指向本表结点表示递归

扩展线性表存储结构（同层结点链存储结构）：如图所示

  • 对比头尾链表存储结构，结点结构变化：原⼦结点追加尾指针域（作⽤同⼴义表结点）
  • 特点（类似带头结点的单链表）：
    1. 以⼴义表头结点开头：其头指针域为空，尾指针指向第⼀个数据结点
    2. 链表主体既可为⼴义表亦可为原⼦（形式与数学式完全⼀致）
      • 注：⼦表⽆⼴义表头结点。故引⽤已有⼴义表时头指针指向被引用表的⼴义表头结点的尾指针所指的第⼀个数据结点

A 高精度运算*

C++常使用变长数组std::vector<int>或字符串std::string存储大整数及其属性，低位存于低位。

Java可直接使用内置大数类BigInteger，若要复现C++算法则可使用ArrayList或数组。

除了存储大整数外，高精度运算算法还可推广至任意进制数的表示与运算，只需将10改为其他进制即可。以下适用于任意进制的高精度运算代码实现：

int base = 10;

/* 高精度加法：C = A + B, A >= 0, B >= 0 */
vector<int> add(vector<int> &A, vector<int> &B) {
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;  // 进位
    for (int i = 0; i < A.size(); i++) {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % base);
        t /= base;
    }

    if (t) C.push_back(t);  // 存入最后的进位
    return C;
}

/* 比较两个高精度整数的大小，返回A - B的符号 */
int cmp(vector<int> &A, vector<int> &B) {
    if (A.size() > B.size()) return 1;  // 优先比较长度
    if (A.size() < B.size()) return -1;

    for (int i = A.size() - 1; i >= 0; i--) {   // 从高位起逐位比较
        if (A[i] > B[i]) return 1;
        if (A[i] < B[i]) return -1;
    }
    return 0;
}

/* 高精度减法：C = A - B, A >= B, A >= 0, B >= 0 */
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    int t = 0;  // 借位
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;   // t成为本轮的被减数
        if (i < B.size()) t -= B[i];
        C.push_back((t + base) % base);     // 若t<0，则存的是借位后的差；否则正常存差

        if (t < 0) t = 1;   // t<0则说明需借位
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();   // 去除前导0（结果为0则保留1位）
    }
    return C;
}

/* 高精度乘低精度：C = A * b, A >= 0, b >= 0 */
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;  // 进位
    for (int i = 0; i < A.size() || t; i++) {   // 自动处理最后剩余进位（i>=size但t>0的情形）
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % base);
        t /= base;
    }

    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();   // b为0时，需去除前导0
    }
    return C;
}

/* 高精度除以低精度：A / b = C ... r, A >= 0, b > 0 */
vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;  // 余数
    for (int i = A.size() - 1; i >= 0; i--) {   // 从最高位开始除
        r = r * base + A[i];
        C.push_back(r / b); // 暂时将高位存于低位
        r %= b;
    }

    reverse(C.begin(), C.end());    // 逆转后即为正常存储形式
    while (C.size() > 1 && C.back() == 0) {
        C.pop_back();
    }
    return C;
}

B 前缀和与差分算法*

以下前缀和与差分数组必须从下标1开始存储

B.1 一维前缀和/拆分*

一维前缀和：对于数列a[1], a[2], ... , a[n]，规定a[i]的前缀和为前i个数的和：s[i] = a[1] + a[2] + ... + a[i] (i >= 1)

  • 求法：s[0] = 0, s[i] = s[i - 1] + a[i] (i >= 1)
  • 应用：求下标区间[l,\ r]上的片段和s[r] - s[l - 1]

一维前缀和

int n;
int a[N], s[N];     // [1 ... n]

/* 初始化前缀和数组 */
void init() {
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
}

/* 求下标区间[l, r]上的片段和 */
int get(int l, int r) {
    return int sum = s[r] - s[l - 1];   // sum = a[l] + ... + a[r]
}

一维差分：由数组a[1], a[2], ... ,a[n]构造差分数组b[1], b[2], ... , b[n]，使得a[i] = b[1] + b[2] + ... + b[i]，b[i] = a[i] - a[i - 1]

  • 应用：给区间[l,\ r]上所有数加上C，时间复杂度O(1)。方法如下
    1. 给b[l]加上C，使得a[l], a[l + 1], ... , a[n]均加上了C
    2. 给b[r + 1]减去C，使得a[r + 1], a[r + 2], ... , a[n]均减去了本不应加的C

对于原差分数组的初始化亦可采用上述操作，赋值a[i]即相当于给区间[i, i]加上a[i]

一维差分

int n;
int a[N], b[N]; // [1 ... n]

/* 给区间[l, r]上所有数加上c */
void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

/* 初始化差分数组 */
void init() {
    for (int i = 1; i <= n; i++) {
        insert(i, i, a[i]);
    }
}

/* 将操作过的差分数组变为原数组（前缀和与差分互为逆运算） */
void revert() {
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
    }
}

B.2 二维前缀和/拆分*

二维前缀和：对于n * m的矩阵a[n][m]，规定a[i][j]的二维前缀和s[i][j]为元素a[i][j]左上角所有元素的和。

  • 求法：s[0][j] = s[i][0] = s[0][0] = 0, s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] (i, j >= 1)
  • 应用：求下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和，只需将整块左上矩形面积减去红、绿区域（不含待求区域边界）面积再补上多减去的重叠区域面积，即为S = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]

二维前缀和

int n, m;
int a[N][N], s[N][N];   // [1 ... n][1 ... m]

/* 初始化前缀和数组 */
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
}

/* 求以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和 */
int get(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

二维差分：参考一维差分与二维前缀和，差分矩阵中每个数都蕴含于其右下矩阵中的每个数。

操作：给下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩形（含边界）加上C，只需给整个右下角加C，给红、绿区域各减C，最后再给重叠区域加上多减的C即可

对于原差分矩阵初始化操作亦可采用上述操作，参考一维差分

二维差分

int n, m;
int a[N][N], b[N][N];       // [1 ... n][1 ... m]

/* 给以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）加上c */
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

/* 初始化差分矩阵 */
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            insert(i, j, i, j, a[i][j]);
        }
    }
}

/* 将操作过的差分矩阵变为原矩阵：求差分矩阵的前缀和 */
void revert() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
}

C 离散化*

本节实为散列表的一种优化算法，可在完成相关基础内容学习后再次巩固阅读。

离散化（Discretization）：高度分散的整数 → 0, 1, 2, ..., n-1或1, 2, ..., n

vector<int> alls;   // 存储所有待离散化的值

/* 离散化操作（保序） */
void init() {
    sort(alls.begin(), all.end());  // 将所有值排序
    alls.erase(unique(alls.begin(), alls.end()), all.end());    // 去重
}

/* 根据离散化的值k获取原来的值x */
int get(k) {
    return alls[k];
}

/* 二分求出x对应的离散化的值 */
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) { // 找到第1个大于等于x的位置（唯一）
        int mid = l + r >> 1;
        if (alls[mid] >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return r + 1;   // 这里+1是为了映射到1, 2, ..., alls.size()
}

D 区间合并*

规定用形如pair{a, b}的二元整数对（Pair of Integer and Integer）表示一段闭区间[a,b]，对元素为区间的数组进行区间合并操作，一般步骤如下：

  1. 先将所有区间按左端点大小排序
  2. 当前维护区间与下一区间之间分三种情况：包含、有交集（含端点）、无交集
    • 包含：无需操作（实为有交集的特殊情况）
    • 有交集：更新当前区间右端点为较大的即可，继续维护
    • 无交集：结束维护当前区间并保存，更新为下一区间
  3. 迭代结束后保存当前维护区间

区间合并

typedef pair<int, int> PII; // <st, ed>

/* 合并区间 */
vector<PII> merge(vector<PII> &segs) {
    vector<PII> res;

    sort(seg.begin(), seg.end());   // 默认优先按first（左端点大小）排序

    int st = -INF, ed = -INF;   // 当前维护区间（初始化为负无穷）
    for (auto &seg : segs) {
        if (ed < seg.first) {   // 若与当前维护区间无交集
            if (st != -INF) {
                res.push_back({st, ed});    // 当前区间结束维护并保存
            }
            st = seg.first; // 转移至此区间
            ed = seg.second;
        } else {
            ed = max(ed, seg.second);   // 有交集则比较右端点即可，继续维护
        }
    }

    if (st != -INF) {
        res.push_back({st, ed});    // 保存最后一个区间
    }
    return res;
}

发表评论