稀疏矩阵的运算

1 / 35

稀疏矩阵应用

摘 要 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词 程序设计；稀疏矩阵；三元组；十字链表

1 引言

• 课程设计任务

本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C； 求出A的转置矩阵D，输出D； 求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

• 课程设计性质

数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。

2 / 35 1.3课程设计目的

其目的是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

• 需求分析

2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值

稀疏矩阵——三元组顺序表⽬录

稀疏矩阵

假设m*n的矩阵中，有t的⾮零元，令s=t/m * n,当，s<=0.05时，称此矩阵为稀疏矩阵，简单理解就是⾮零元特别少的矩阵

//⼀般矩阵a

1 2 3

a= 4 5 6

7 8 9

//稀疏矩阵s

0 0 0 0 0

0 2 0 0 5

s= 0 0 3 0 0

0 0 0 0 4

矩阵的转置

⼀个m * n的矩阵转置后变为 n * m的矩阵

//3*2的矩阵-转置前

1 2

4 5

7 8

//转置后变为2*3

1 4 7

2 5 8

转置后的矩阵每个元素的下表与原来的下表刚好相反，例如上⾯4转置前的下标为（2，1），转置后变为（1，2）；

矩阵压缩存储-三元组顺序表

之所以引⼊三元组顺序表，是因为，对于稀疏矩阵⽽⾔，⽤传统的存储⽅法会造成存储空间的浪费

0 12 9 0 0 0 0

0 0 0 0 0 0 0

-3 0 0 0 0 14 0

M= 0 0 24 0 0 0 0

0 18 0 0 0 0 0

15 0 0 -7 0 0 0

//上⾯矩阵⽤三元组表⽰

i j v

1 2 12

1 3 9

3 1 -3

3 6 14

4 3 24

5 2 18

6 1 15

6 4 -7

typedef struct

{

int i,j; //⾏坐标、列坐标

ElemType e; //元素

}Triple;

typedef struct

{

Triple date[MAXSIZE+1]; //0不存储元素

int mu,nu,tu; //⾏数、列数、⾮零元个数

}TSMatrix;

稀疏矩阵的转置传统⽅法的转置算法时遍历矩阵的每⼀项，交换其下标值即可

for(col=1;col<=nu;col++)

{

for(row=1;row<=mu;row++)

{

T[col][row]=M[row][col]

}

}

//时间复杂度 : O(nu*mu)

利⽤三元组顺序表进⾏存储的稀疏矩阵要想实现转置显然不能⽤上⾯的算法，下⾯介绍两种⽅法：

稀疏矩阵乘法是一种针对稀疏矩阵的乘法运算，由于稀疏矩阵中非零元素较少，因此可以利用这一特性进行优化计算，提高计算效率。以下是两个稀疏矩阵乘法的详细介绍：

稀疏矩阵的定义：稀疏矩阵是一个矩阵，其中大多数元素都是零。在存储和计算时，为了节省空间和时间，我们可以只存储非零元素，并采用特殊的数据结构来表示这种矩阵。

稀疏矩阵乘法的原理：稀疏矩阵乘法的原理与普通矩阵乘法相似，只是由于稀疏矩阵中非零元素较少，所以在计算时可以只考虑这些非零元素，而忽略零元素。具体来说，对于两个稀疏矩阵A和B的乘积C，我们可以按照元素的位置关系，逐个计算A中的非零元素与B中的非零元素的乘积，并将结果加到C中相应位置上。

稀疏矩阵乘法的算法步骤：

读入两个稀疏矩阵A和B。

初始化结果矩阵C为零矩阵。

遍历A中的每一个非零元素（i，j），如果A(i，j)非零，则按照元素的位置关系，计算A(i，j)与B中相应位置的元素的乘积，并将结果加到C中相应位置上。

返回结果矩阵C。

稀疏矩阵乘法的优化：由于稀疏矩阵中非零元素较少，因此在计算时可以采用一些优化策略来提高计算效率。例如，可以采用压缩存储技术来减少存储空间的使用；可以采用并行计算技术来提高计算速度；还可以采用一些迭代算法来加速计算过程。

总之，稀疏矩阵乘法是一种针对稀疏矩阵的特殊运算方法，由于其具有较高的计算效率和较低的空间复杂度，因此在科学计算、工程领域和数据处理等方面得到了广泛应用。

稀疏矩阵乘法的时间复杂度

稀疏矩阵乘法的时间复杂度，这话一说出来，可能有些朋友会皱眉头，觉得这又是个高深的数学问题。但实际上，咱们今天就来聊聊这个看似复杂的事情，轻松点、幽默点，让大家都能明白。咱们得搞清楚什么是稀疏矩阵。简单来说，就是矩阵里有很多的零。想象一下，你在看一张桌子，上面摆着很多碗，只有几个碗里有东西，其他的都是空的。这样的矩阵就叫稀疏矩阵。其实在很多实际应用中，稀疏矩阵的出现是非常常见的，特别是在图像处理、机器学习和数据科学中，真是频繁得让人惊叹。

咱们就要说说稀疏矩阵乘法。说白了，就是把两个稀疏矩阵相乘。这个过程其实可以看作是把两个“空碗”组合成一个新碗，看看能不能得到一些“有料”的东西。由于很多位置上都是零，所以在计算的时候，咱们可以聪明点，干脆不去计算那些零的位置，省得浪费时间和精力，简直就是把“事半功倍”发挥到了极致。这一招可不是什么秘笈，很多程序员和数学家都用得特别溜。

不过，时间复杂度是个什么鬼呢？简单来说，它就是描述算法运行时间的一个指标。想象一下，咱们去市场买菜，时间复杂度就像是你去菜市场的路程，如果你走的路特别绕，那肯定花的时间就长；如果你选了一条最近的路，当然就能更快到达。对于稀疏矩阵乘法来说，时间复杂度跟矩阵的稀疏程度和大小有很大关系。一般来说，如果你有一个稀疏矩阵A和B，那么它们相乘的复杂度大致是O(NzA + NzB)，Nz代表非零元素的数量。别被这些符号吓到，通俗点说，就是看你非零元素有多少，越多计算的时间就越长。

再说个形象的例子。想象你在一个派对上，跟一群朋友聊得火热，结果你发现只有几个人是你特别想交流的。如果你一个一个去找他们，肯定费时费力。但是如果你能知

道他们在哪，直接冲过去，效率简直翻倍。稀疏矩阵乘法就像这样，只找非零的元素，省去那些冗余的时间，简直太聪明了。

再来聊聊实际应用。稀疏矩阵在机器学习中可是大显身手。比如在推荐系统里，用户和物品的评分矩阵常常都是稀疏的，绝大多数用户根本没给某些物品打过分。这种情况下，使用稀疏矩阵乘法，就能快速计算出用户对未评分物品的潜在评分，推荐个性化的产品，真是太酷了。想想看，假如你一直在寻找那件心仪的衣服，结果推荐系统帮你找到了几件超合适的，简直就是有求必应的“神算子”。