稀疏矩阵和三元组的基础理论
需积分: 16 50 浏览量
2008-12-26
11:53:34
上传
评论
收藏 19KB DOC 举报
第三章稀疏矩阵与广义表
矩阵：（ Matrix ）是一个具有 m 行 × n 列的数表，共有 m × n 个数。
稀疏矩阵：是矩阵中的一种特殊情况，它的非零元素的个数远远小于
零元素的个数。如图 3-1 就是一个 3×5 的稀疏矩阵。
图 3-1
三元组：对于矩阵中的每个非零元素，可用它的行号、列号以及元素值这个三元组（ i,j,a
ij ）来表示。
稀疏矩阵的三元组表示：把每个非零元素的三元组按照行号为主序（即为主关键字）、列
号为辅序（即为次关键字）进行排列，就构成了一个表示稀疏矩阵的三元组线性表。
稀疏矩阵的抽象数据类型：
ADT SparseMatrix is
Data:
// 可采用顺序存储结构或链接存储结构
Operation:
void InitMatrix(SMatrix& M); // 初始化
SMatrix Transpose(SMatrix &M); // 转置
SMatrix Add(SMatrix& M1, SMatrix& M2); // 矩阵相加
SMatrix Multiply(SMatrix& M1, SMatrix& M2); // 矩阵相乘
void InputMatrix(SMatrix& M,int m,int n); // 输入数据
void OutputMatrix(SMatrix& M); // 输出矩阵
end SparseMatrix
稀疏矩阵的的存储结构：
1．顺序存储：就 是对其相应的三元组线形表进行顺序存储。这种存储方式的优点是利用
资源评论
