十字链表节点结构应为：struct OLNode { int row, col; double value; OLNode right; OLNode down; }，其中right指向同行下一个非零元，down指向同列下一个非零元，配合行/列头指针数组实现双向链式访问。
十字链表的节点结构怎么设计才对
稀疏矩阵用十字链表存，核心是让每个非零元同时挂到「行链表」和「列链表」上，不能只做单向链接。常见错误是把 row 和 col 当成普通二维索引存进节点，结果遍历时无法跳转——必须用指针串联。
标准做法是定义两个指针：一个指向同行下一个非零元（right），一个指向同列下一个非零元（down）。再加一个头结点数组管理每行/每列的起始位置。
典型结构体如下：
struct OLNode {
int row, col;
double value;
OLNode *right; // 同一行中下一个非零元
OLNode *down; // 同一列中下一个非零元
};注意：right 和 down 都是 OLNode* 类型，不是 int 索引；否则没法 O(1) 跳转，也破坏了链表本质。
立即学习“C++免费学习笔记（深入）”；
初始化十字链表时最容易漏掉什么
很多人只分配了非零元节点，却忘了初始化行头结点和列头结点数组。结果插入时访问 rowHead[i] 或 colHead[j] 就崩溃。
正确步骤是：
- 用
new OLNode*[m]分配m行头指针数组，全部初始化为nullptr - 用
new OLNode*[n]分配n列头指针数组，同样全置空 - 头结点本身不存数据，只作入口；插入新节点时要按行列分别插入到对应头结点的
right/down链中 - 插入顺序影响链表结构：推荐按行优先输入，每次插入先连
right，再找列位置连down，避免反复遍历
插入非零元时为什么老出现指针错乱
插入逻辑稍有偏差，right 和 down 就会互相覆盖或断链。关键在于「插入到行链表」和「插入到列链表」是两个独立过程，不能共用同一套遍历逻辑。
常见错误包括：
- 在找行插入位置时修改了
down指针 - 没判断目标位置是否已存在相同
(row, col)的节点，导致重复插入 - 插入列链表时从
colHead[j]开始遍历，但比较的是row值，却忘了列链表是按row升序排的——这点容易被忽略 - 没处理头结点的特殊性：比如
rowHead[i]->right = newNode是首节点，但后续节点要插在中间，得维护前驱指针
稳妥做法是对每条链都写独立的查找+插入函数，例如 insertIntoRowList(OLNode* head, OLNode* node) 和 insertIntoColList(OLNode* head, OLNode* node)，内部各自维护前驱。
遍历十字链表求某行或某列和为什么比三元组慢不了多少
有人以为十字链表遍历一定比压缩存储（如 CSR）快，其实不然。它优势在「局部更新」和「随机行列访问」，不是单纯求和。
比如求第 i 行所有元素之和，只需从 rowHead[i] 出发沿 right 遍历，时间复杂度是该行非零元个数 O(nnz_i)，和 CSR 的行偏移查表+循环一样快。
但要注意：
- 如果频繁求整矩阵行列统计，建议额外维护
rowSum[m]和colSum[n]数组，插入/删除时同步更新，避免每次遍历 - 十字链表没有全局顺序，不能像 COO 那样直接排序后二分查找某个位置，定位
(i,j)仍需分别走行链和列链，最坏 O(nnz) - 内存开销明显更大：每个非零元存两个指针（16 字节）+ 坐标值（8 字节），而 CSR 只存列号+值（12 字节），还不算行偏移数组
真要用十字链表，通常是因为业务需要频繁插入、删除非零元，或者动态构建过程中行列访问模式不固定——静态只读场景基本没必要上。
