三元组顺序表存稀疏矩阵只存非零元(row,col,value)，按行优先排列；快速转置通过预计算num[j]（第j列非零元数）和cpot[j]（转置后起始位置），实现O(t+n)时间复杂度，关键在边界处理与下标统一。
三元组顺序表怎么存稀疏矩阵
稀疏矩阵用三元组顺序表，本质就是只存非零元：每个元素记作 (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++ 实现时容易错的三个地方
写代码时这几个点一错就转出来全是乱序或越界：
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<int,int,int>> 存三元组，行列从 0 开始：
vector<tuple<int,int,int>> fastTranspose(const vector<tuple<int,int,int>>& 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 < cols; j++) cpot[j] = cpot[j-1] + num[j-1];
vector<tuple<int,int,int>> 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;
}
真正难的不是写这几行，而是确认你的输入 M 的列索引范围没超 cols，且 num 和 cpot 长度匹配——这种边界错，调试时往往只看到结果空或错位，很难一眼定位。
