稀疏矩阵的相加运算-数据结构的教程

【文件属性】：
文件名称：稀疏矩阵的相加运算-数据结构的教程
文件大小：5.3MB
文件格式：PPT
更新时间：2021-04-26 09:15:02
发的 2．稀疏矩阵的相加运算 当稀疏矩阵用三元组表进行相加时，有可能出现非零元素的位置变动，这时候，不宜采用三元组表作存储结构，而应该采用十字链表较方便。 （1）十字链表的建立 下面分两步讨论十字链表的建立算法： 第一步，建立表头的循环链表： 依次输入矩阵的行、列数和非零元素个数：m,n和t。由于行、列链表共享一组表头结点，因此，表头结点的个数应该是矩阵中行、列数中较大的一个。假设用s 表示个数，即s=max（m，n）。依次建立总表头结点（由hm指针指向）和s个行、列表头结点，并使用next域使s+1个头结点组成一个循环链表，总表头结点的行、列域分别为稀疏矩阵的行、列数目，s个表头结点的行列域分别为0。并且开始时，每一个行、列链表均是一个空的循环链表，即s个行、列表头结点中的行、列指针域rptr和cptr均指向头结点本身。 第二步，生成表中结点： 依次输入t个非零元素的三元组（i,j,v），生成一个结点，并将它插入到第i行链表和第j列链表中的正确位置上，使第i个行链表和第j个列链表变成一个非空的循环链表。 在十字链表的建立算法中，建表头结点，时间复杂度为O(s)，插入t个非零元结点到相应的行、列链表的时间复杂度为O（t*s），故算法的总的时间复杂度为O(t*s)。