三元组和十字链表表示法1
需积分: 0 63 浏览量
2022-08-03
16:07:12
上传
评论
收藏 346KB PDF 举报
稀
疏
矩
阵
的
三
元
组
表
示
法
和
十
字
链
表
法
稀
疏
矩
阵
一个矩阵中有大量的零元素。对于稀疏矩阵，如果单纯的用一般矩阵来表示的话很浪费空间，因为非零元素仅有少
量几个，我们可以用其他方式来表示少数非零元素在矩阵的位置就可以保存稀疏矩阵的全部信息了。
三
元
组
矩阵中每一个元素都是有行序号、列序号以及该元素的值唯一表示。因此，我们可以用三项内容唯一表示稀疏矩阵
的每一个非零元素，即形式为：（i, j, value)，那么剩下位置都为零元素。
三元组表示法类型定义需要两个结构体来定义，一个用来保存每一非零元素的位置和值的信息，另一用来定义整个
矩阵的信息，包括矩阵的行数和列数，非零元素的个数以及整个三元组表。
三元组结点定义：
三元组顺序表定义：
稀
疏
矩
阵
的
转
置
——
三
元
组
表
示
基
本
思
想
是
1、将矩阵的行、列下标值交换。即将三元组中的行、列位置i、j相互交换。
2、重排三元组表中的元素的顺序。即交换后仍然是按行优先顺序的。
时间复杂度为O(nmt)其中t为非零个数。可见，但非零个数比较大时不适合用三元组表示法。
稀
疏
矩
阵
的
快
速
转
置
——
三
元
组
表
示
#defineMAX_SIZE101
typedefintelemtype;
typedefstruct
{introw;/*行下标*/
intcol;/*列下标*/
elemtypevalue;/*元素值*/
}Triple;
三元组顺序表定义
typedefstruct
{intrn;/*行数*/
intcn;/*列数*/
inttn;/*非0元素个数*/
Tripledata[MAX_SIZE];
}TMatrix;
评论0