C++三元组顺序表怎么实现稀疏矩阵快速转置-C++-PHP中文网

三元组顺序表存稀疏矩阵只存非零元(row,col,value)，按行优先排列；快速转置通过预计算num[j]（第j列非零元数）和cpot[j]（转置后起始位置），实现o(t+n)时间复杂度，关键在边界处理与下标统一。

c++三元组顺序表怎么实现稀疏矩阵快速转置

三元组顺序表怎么存稀疏矩阵

稀疏矩阵用三元组顺序表，本质就是只存非零元：每个元素记作 (row, col, value)，用一个结构体数组按行优先（或列优先）顺序排列。关键不是“怎么存”，而是“存完之后怎么让转置快起来”——直接遍历原三元组、对每个元生成 (col, row, value) 再排序，时间复杂度是 O(t log t)（t 是非零元个数），这不叫快速转置。

快速转置的核心：预计算每列非零元个数

真正快速的转置靠的是“空间换时间”+“定位预处理”。原矩阵第 j 列的非零元，转置后全变成新矩阵第 j 行的元素。所以只要提前算出：

num[j]：原矩阵第 j 列有多少个非零元（j 从 0 或 1 开始，需统一）
cpot[j]：原矩阵第 j 列第一个非零元，在转置后的三元组数组中该存到哪个下标位置（即起始偏移）

cpot[0] = 0，然后 cpot[j] = cpot[j-1] + num[j-1]（若列号从 0 开始）。这样扫一遍原三元组，对每个 (i, j, v)，立刻知道它该填到转置数组的 cpot[j]++ 位置，全程 O(t + n)，n 是列数。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

C++ 实现时容易错的三个地方

写代码时这几个点一错就转出来全是乱序或越界：

列号/行号下标是否从 0 还是 1 起？cpot 和 num 数组大小必须是 matrix_cols + 1（如果列号从 1 开始），否则 cpot[col] 访问越界
原三元组必须严格按行优先排序，否则 num 统计会漏——但快速转置算法本身不检查这个，得你保证输入合法
cpot 是“起始位置”，每次填完一个元素后要自增：transposed[cpot[col]] = {col, row, value}; cpot[col]++;，漏掉 ++ 就所有同列元素全叠在第一个位置

一个极简可跑的 C++ 片段示意

假设用 vector<tuple>></tuple> 存三元组，行列从 0 开始：

vector<tuple>> fastTranspose(const vector<tuple>>& M, int rows, int cols) {
    vector<int> num(cols, 0);           // num[j] = 原矩阵第 j 列非零元个数
    for (auto [r, c, v] : M) num[c]++;
    
    vector<int> cpot(cols, 0);         // cpot[j] = 转置后第 j 行（原第 j 列）首个位置
    for (int j = 1; j > T(M.size());
    for (auto [r, c, v] : M) {
        int pos = cpot[c];               // 原第 c 列 → 转置后第 c 行
        T[pos] = {c, r, v};            // 注意：(col, row, value)
        cpot[c]++;                     // 移动指针
    }
    return T;
}
</int></int></tuple></tuple>

真正难的不是写这几行，而是确认你的输入 M 的列索引范围没超 cols，且 num 和 cpot 长度匹配——这种边界错，调试时往往只看到结果空或错位，很难一眼定位。