|
带行表的三元组表 为了方便某些矩阵运算在按行优先存储的三元组表中加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位 置这就是带行表的三元组表 ()类型描述 #define MaxRow l //在三元组表定义前加入此最大行定义 typedef struct { TriTupleNode data[MaxSize]; int RowTab[MaxRow];//行表应保证m≤MaxRow int mnt; }RTriTupleTable; ()带行表的三元组表的操作 ① 对于任给行号i(≤i≤m)能迅速地确定该行的第一个非零元在三元组表中的存储位置为RowTab[i] ② RowTab[i](≤i≤m)表示第i行之前的所有行的非零元数 ③ 第i行上的非零元数目为RowTab[i+]RowTab[i](≤i≤m) ④ 最后一行(即第ml行)的非零元数目为tRowTab[m](t为矩阵的非零元总数) 注意 若在行表中令RowTab[m]=t(要求MaxRow>m)会更方便 些且t可省略 带行表的三元组表可改进矩阵的转置算法具体【参阅其它参考书】 稀疏矩阵压缩存储方式分析 () 三元组表和带行表的三元组表的特点 相应的算法描述较为简单但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合 【例】执行将矩阵B相加到矩阵A上的运算时某位置上的结果可能会由非零元变为零元但也可能由零元变为非零元这就会 引起在A的三元组表中进行删除和插人操作从而导致大量结点的移动对此类运算采用链式存储结构为宜 ()稀疏矩阵的链式结构 稀疏矩阵的链式结构有十字链表等方法适用于非零元变化大的场合 比较复杂可【参阅其它参考书】 |
