下载文档原格式
稀疏矩阵方程算法稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。
在实际问题中，很多矩阵都是稀疏的，例如图像处理、自然语言处理等领域。
由于稀疏矩阵的特殊性，传统的矩阵运算方法效率较低，因此需要设计高效的算法来解决稀疏矩阵方程。
稀疏矩阵方程是指形如Ax=b的线性方程，其中A是一个稀疏矩阵，b是一个向量。
解决稀疏矩阵方程的一种常用方法是使用迭代算法，例如共轭梯度法（Conjugate Gradient，CG）和广义最小残差法（Generalized Minimal Residual，GMRES）等。
共轭梯度法是一种迭代法，它可以用来解决对称正定稀疏矩阵方程。
该方法的基本思想是通过最小化残差的二次范数来逼近方程的解。
具体而言，共轭梯度法通过迭代计算一个与残差正交的搜索方向，并在该方向上进行搜索，直到找到方程的解。
广义最小残差法是一种迭代法，它可以用来解决非对称稀疏矩阵方程。
该方法的基本思想是通过最小化残差的二范数来逼近方程的解。
与共轭梯度法不同的是，广义最小残差法使用Krylov子空间来进行搜索，并在该子空间上进行最小化残差的计算。
除了迭代算法外，还可以使用直接求解方法来解决稀疏矩阵方程。
其中一种常用的方法是LU分解。
LU分解是将稀疏矩阵A分解为一个下三角矩阵L和一个上三角矩阵U的乘积，即A=LU。
通过LU分解，可以将原始方程Ax=b转化为Ly=b和Ux=y两个方程，进而求解出x的值。
稀疏矩阵方程的求解算法还有很多，例如Jacobi迭代法、高斯-赛德尔迭代法等。
这些算法在不同的问题和应用中具有不同的优势和适用性。
在实际应用中，稀疏矩阵方程的求解是一个复杂且关键的问题。
通过选择合适的算法和优化技术，可以提高求解的效率和精度。
同时，还可以利用稀疏矩阵的特殊性质，例如压缩存储和并行计算等，进一步提高算法的性能。
稀疏矩阵方程是一类特殊的线性方程，传统的矩阵运算方法在处理稀疏矩阵时效率较低。
针对稀疏矩阵方程，可以采用迭代算法和直接求解方法来求解。
数据结构实验报告稀疏矩阵运算实验目的：1.学习并理解稀疏矩阵的概念、特点以及存储方式。
2.掌握稀疏矩阵加法、乘法运算的基本思想和算法。
3.实现稀疏矩阵加法、乘法的算法，并进行性能测试和分析。
实验原理：稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。
在实际问题中，有许多矩阵具有稀疏性，例如文本矩阵、图像矩阵等。
由于存储稀疏矩阵时，对于大量的零元素进行存储是一种浪费空间的行为，因此需要采用一种特殊的存储方式。
常见的稀疏矩阵的存储方式有三元组顺序表、十字链表、行逻辑链接表等。
其中，三元组顺序表是最简单直观的一种方式，它是将非零元素按行优先的顺序存储起来，每个元素由三个参数组成：行号、列号和元素值。
此外，还需要记录稀疏矩阵的行数、列数和非零元素个数。
稀疏矩阵加法的原理是将两个稀疏矩阵按照相同的行、列顺序进行遍历，对于相同位置的元素进行相加，得到结果矩阵。
稀疏矩阵乘法的原理是将两个稀疏矩阵按照乘法的定义进行计算，即行乘以列的和。
实验步骤：1.实现稀疏矩阵的三元组顺序表存储方式，并完成稀疏矩阵的初始化、转置、打印等基本操作。
2.实现稀疏矩阵的加法运算，并进行性能测试和分析。
3.实现稀疏矩阵的乘法运算，并进行性能测试和分析。
4.编写实验报告。
实验结果：经过实验测试，稀疏矩阵的加法和乘法算法都能正确运行，并且在处理稀疏矩阵时能够有效节省存储空间。
性能测试结果表明，稀疏矩阵加法、乘法的运行时间与非零元素个数有关，当非零元素个数较少时，运算速度较快；当非零元素个数较多时，运算速度较慢。
实验分析：稀疏矩阵的运算相对于普通矩阵的运算有明显的优势，可以节省存储空间和运算时间。
在实际应用中，稀疏矩阵的存储方式和运算算法都可以进行优化。
例如，可以采用行逻辑链接表的方式存储稀疏矩阵，进一步减少存储空间的占用；可以采用并行计算的策略加快稀疏矩阵的运算速度。
总结：通过本次实验，我深入学习了稀疏矩阵的概念、特点和存储方式，掌握了稀疏矩阵加法、乘法的基本思想和算法，并通过实验实现了稀疏矩阵的加法、乘法运算。
稀疏矩阵乘法是一种针对稀疏矩阵的乘法运算，由于稀疏矩阵中非零元素较少，因此可以利用这一特性进行优化计算，提高计算效率。
以下是两个稀疏矩阵乘法的详细介绍：稀疏矩阵的定义：稀疏矩阵是一个矩阵，其中大多数元素都是零。
在存储和计算时，为了节省空间和时间，我们可以只存储非零元素，并采用特殊的数据结构来表示这种矩阵。
稀疏矩阵乘法的原理：稀疏矩阵乘法的原理与普通矩阵乘法相似，只是由于稀疏矩阵中非零元素较少，所以在计算时可以只考虑这些非零元素，而忽略零元素。
具体来说，对于两个稀疏矩阵A和B的乘积C，我们可以按照元素的位置关系，逐个计算A中的非零元素与B中的非零元素的乘积，并将结果加到C中相应位置上。
稀疏矩阵乘法的算法步骤：
读入两个稀疏矩阵A和B。
初始化结果矩阵C为零矩阵。
遍历A中的每一个非零元素（i，j），如果A(i，j)非零，则按照元素的位置关系，计算A(i，j)与B中相应位置的元素的乘积，并将结果加到C中相应位置上。
返回结果矩阵C。
稀疏矩阵乘法的优化：由于稀疏矩阵中非零元素较少，因此在计算时可以采用一些优化策略来提高计算效率。
例如，可以采用压缩存储技术来减少存储空间的使用；可以采用并
行计算技术来提高计算速度；还可以采用一些迭代算法来加速计算过程。
总之，稀疏矩阵乘法是一种针对稀疏矩阵的特殊运算方法，由于其具有较高的计算效率和较低的空间复杂度，因此在科学计算、工程领域和数据处理等方面得到了广泛应用。
稀疏矩阵一、问题描述假若在n m ⨯阶中，有t 个元素不为零，令nm t ⨯=δ称为矩阵的稀疏因子。
通常认为≤δ0.05时称为稀疏矩阵。
稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。
通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。
二、基本要求1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出;2、编写算法，完成稀疏矩阵的转置操作；3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作；4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。
三、测试数据1、转置操作的测试数据：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛00200013000010020100 2、相加操作的测试数据： ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛00200013000010020100 ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛00200010000210030300 3、相乘操作的测试数据： ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛0000000300400021 ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛001002000021 四、算法思想1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。
稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。
2、稀疏矩阵转置的算法思想将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。
为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。
3、稀疏矩阵相加的算法思想比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。
稀疏矩阵的运算稀疏矩阵的运算稀疏矩阵，顾名思义，就是矩阵中空值（0）的比例很大，而实际值（非0）的比例很小的矩阵。
它最大的特点就是，当矩阵的规模增大时，仍然可以保持较低的计算量。
在运算时，因为稀疏矩阵中的0值没有意义，所以对其做运算也没有意义。
所以，在运算中需要把稀疏矩阵转换成一维数组，即只保留其有意义的值。
下面介绍几种常用的稀疏矩阵运算技术。
1.索引表（Indextable）这是一种最简单的稀疏矩阵运算技术，在使用索引表时，需要用一个额外的一维数组来保存有意义的值的位置，而把矩阵本身变成一维数组，进行运算。
例如矩阵A：1 0 0 0 00 0 0 4 00 0 0 0 00 3 0 0 00 0 7 0 0这样的矩阵，可以使用一个一维数组来保存其有意义的值及其位置，例如：[1,(0,0); 4,(1,3); 3,(3,1); 7,(2,2)]这样，我们就可以用简单的一维数组代替复杂的二维矩阵，从而加快稀疏矩阵的运算。
2.矩阵向量乘法（Matrix-Vector Multiplication）这是一种最常用的稀疏矩阵运算技术，把一个大的稀疏矩阵A和一个向量（一维数组）V作乘法，得到一个新的向量C，即：C = A * V对于上面的实例，可以用以下方式求出C：C[0] = 1 * V[0] + 0 * V[1] + 0 * V[2] + 0 * V[3] + 0 * V[4] C[1] = 0 * V[0] + 0 * V[1] + 0 * V[2] + 4 * V[3] + 0 * V[4] C[2] = 0 * V[0] + 0 * V[1] + 0 * V[2] + 0 * V[3] + 7 * V[4] C[3] = 0 * V[0] + 3 * V[1] + 0 * V[2] + 0 * V[3] + 0 * V[4] 3.矩阵乘法（Matrix Multiplication）矩阵乘法也是一种常用的稀疏矩阵运算技术，把两个大的稀疏矩阵A和B相乘，得到一个新的稀疏矩阵C，即：C = A * B以上就是稀疏矩阵运算的一些常用技术，稀疏矩阵也可以用于解决很多复杂的运算问题，例如机器学习和深度学习等。
稀疏矩阵的基本原理稀疏矩阵是指矩阵中绝大多数的元素都是零的矩阵。
由于稀疏矩阵的元素数量很少，所以进行矩阵运算时，需要采用特殊的算法，以提高计算速度和效率。
本文将简单介绍稀疏矩阵的基本原理。
一、稀疏矩阵的表示方法在计算机中，稀疏矩阵的存储方式有三种：1. COO格式：也称为三元组格式，该格式将矩阵的每一个元素都用一个三元组表示，分别为其行、列和数值，如{(0, 0, 2), (0, 3,1), (1, 1, 3)}。
2. CSR格式：也称为压缩行格式，该格式将矩阵的非零元素按行存储，并通过两个数组（值向量和列指针）表示，如{2, 1, 3, 4, 5}和{0, 2, 4}。
3. CSC格式：也称为压缩列格式，该格式将矩阵的非零元素按列存储，并通过两个数组（值向量和行指针）表示，如{2, 3, 1, 4, 5}和{0, 1, 3, 3, 4}。
二、稀疏矩阵的基本运算稀疏矩阵的基本运算包括加、减、乘和转置等，下面分别介绍：1. 矩阵加法：对于两个矩阵A和B，若其行列相等，则可以进行加法运算。
对于稀疏矩阵的加法，首先需要找到两个矩阵中非零元素的位置，在这些位置上进行加法运算即可。
2. 矩阵减法：与矩阵加法类似，稀疏矩阵的减法也需要找到两个矩阵中非零元素的位置，在这些位置上进行减法运算即可。
3. 矩阵乘法：对于两个矩阵A和B，若A的列数等于B的行数，则可以进行乘法运算，结果为一个新的矩阵C。
稀疏矩阵的乘法运算比较复杂，需要对数组进行操作，具体实现方法可以参考CSR或CSC格式。
4. 转置：对于一个矩阵A，其转置矩阵为AT，即A的列变为AT 的行，AT的列变为A的行。
转置操作可以直接在CSR或CSC格式中进行操作。
三、稀疏矩阵的应用稀疏矩阵广泛应用于科学计算和工程计算等领域，如图像处理、搜索引擎、网络分析等。
由于稀疏矩阵的存储方式和运算均比较特殊，因此对于稀疏矩阵的计算需要采用特殊的算法，如迭代法、预处理法等。
高效的稀疏矩阵计算算法稀疏矩阵是一种具有大量零元素的矩阵，其特点是在矩阵中零元素的数量远远超过非零元素的数量。
在实际应用中，稀疏矩阵经常出现在各种领域，如图像处理、网络分析等。
由于其特殊的结构，传统的矩阵计算算法在稀疏矩阵上的计算效率较低。
因此，针对稀疏矩阵的特点，研究和设计高效的稀疏矩阵计算算法成为了一个重要的课题。
一、稀疏矩阵的表示方法稀疏矩阵的表示方法分为两种，一种是按照行压缩的方式表示，另一种是按照列压缩的方式表示。
按照行压缩的方式表示，是指将矩阵的每一行转化为一条记录，记录中包含了非零元素的列索引以及对应的值。
按照列压缩的方式表示，是指将矩阵的每一列转化为一条记录，记录中包含了非零元素的行索引以及对应的值。
这两种表示方法各有优劣，具体的选择可根据实际问题的需求来确定。
二、稀疏矩阵的加法运算稀疏矩阵的加法运算是指对两个稀疏矩阵进行相应位置的元素相加。
传统的矩阵加法运算算法需要对整个矩阵进行遍历，导致了计算效率低下。
而对于稀疏矩阵来说，由于其大部分元素为零，只需对非零元素进行相加，能够大大提高计算效率。
三、稀疏矩阵的乘法运算稀疏矩阵的乘法运算是指将两个稀疏矩阵相乘得到一个新的稀疏矩阵。
传统的矩阵乘法运算算法的时间复杂度为O(n^3)，对于大规模的稀疏矩阵计算来说，计算时间将会非常长。
而对于稀疏矩阵来说，可以通过优化算法减少计算量，提高计算效率。
其中一种常用的优化算法是CSR压缩存储格式。
四、稀疏矩阵的逆运算稀疏矩阵的逆运算是指找到一个矩阵，使其与原矩阵相乘得到单位矩阵。
传统的矩阵逆运算算法的时间复杂度为O(n^3)，对于稀疏矩阵来说，计算效率较低。
因此，需要设计一种高效的稀疏矩阵逆运算算法，以提高计算效率。
五、实例分析以图像处理领域为例，图像通常可以表示为一个大规模的稀疏矩阵。
对于图像的处理算法，如图像旋转、图像缩放等，都需要对稀疏矩阵进行计算。
如果使用传统的矩阵计算算法，将会消耗大量的时间和计算资源。
稀疏矩阵十字链表算法稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。
在实际应用中，很多矩阵都具有稀疏性，即元素中大部分为0，而只有少数非零元素。
对于这种类型的矩阵，为了节省内存空间并提高计算效率，可以采用稀疏矩阵的存储方式。
稀疏矩阵的一种常用存储方式是十字链表。
十字链表是一种将稀疏矩阵以链表形式存储的数据结构，它能够有效地表示稀疏矩阵的非零元素，并且能够方便地进行插入、删除和查找操作。
稀疏矩阵十字链表的基本思想是将矩阵中的每个非零元素存储为一个结点，并将这些结点以行列坐标的方式进行链接。
具体来说，稀疏矩阵十字链表由两个链表组成：行链表和列链表。
行链表是一个以行为主的链表，每个结点表示矩阵中的一行。
每个结点包含三个字段：行号、列号和值。
行链表中的结点按照行号从小到大的顺序进行排列，同一行中的结点按照列号从小到大的顺序进行排列。
列链表是一个以列为主的链表，每个结点表示矩阵中的一列。
每个结点也包含三个字段：行号、列号和值。
列链表中的结点按照列号从小到大的顺序进行排列，同一列中的结点按照行号从小到大的顺序进行排列。
通过行链表和列链表，可以方便地进行插入、删除和查找操作。
插入操作可以通过在行链表和列链表中找到对应的位置，将新结点插入到相应的位置上。
删除操作可以通过在行链表和列链表中找到对应的位置，将对应的结点删除。
查找操作可以通过在行链表和列链表中找到对应的位置，获取对应的结点。
稀疏矩阵十字链表算法的优点是能够有效地存储稀疏矩阵，并且可以方便地进行插入、删除和查找操作。
相比于其他存储方式，稀疏矩阵十字链表可以节省更多的内存空间，并且具有更高的计算效率。
总结来说，稀疏矩阵十字链表算法是一种有效地存储稀疏矩阵的方法。
通过行链表和列链表的链接，可以方便地进行插入、删除和查找操作。
稀疏矩阵十字链表算法在实际应用中具有广泛的应用，能够节省内存空间并提高计算效率。
#include <stdio.h>#include <malloc.h>#include<stdlib.h>typedef int ElemType;// 稀疏矩阵的十字链表存储表示typedef struct OLNode{int i,j; // 该非零元的行和列下标ElemType e; // 非零元素值struct OLNode *right,*down; // 该非零元所在行表和列表的后继链域}OLNode, *OLink;typedef struct// 行和列链表头指针向量基址,由CreatSMatrix_OL()分配{OLink *rhead, *chead;int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元个数}CrossList;// 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) int InitSMatrix(CrossList *M){(*M).rhead=(*M).chead=NULL;(*M).mu=(*M).nu=(*M).tu=0;return 1;}// 销毁稀疏矩阵Mint DestroySMatrix(CrossList *M){int i;OLNode *p,*q;for(i=1;i<=(*M).mu;i++) // 按行释放结点{p=*((*M).rhead+i);while(p){q=p;p=p->right;free(q);}}free((*M).rhead);free((*M).chead);(*M).rhead=(*M).chead=NULL;(*M).mu=(*M).nu=(*M).tu=0;return 1;}// 创建稀疏矩阵M,采用十字链表存储表示。
int CreateSMatrix(CrossList *M){int i,j,k,m,n,t;ElemType e;OLNode *p,*q;if((*M).rhead)DestroySMatrix(M);printf("请输入稀疏矩阵的行数列数非零元个数:(space) ");scanf("%d%d%d",&m,&n,&t);(*M).mu=m;(*M).nu=n;(*M).tu=t;//初始化行链表头(*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));if(!(*M).rhead)exit(0);//初始化列链表头(*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));if(!(*M).chead)exit(0);for(k=1;k<=m;k++) // 初始化行头指针向量;各行链表为空链表(*M).rhead[k]=NULL;for(k=1;k<=n;k++) // 初始化列头指针向量;各列链表为空链表(*M).chead[k]=NULL;printf("请按任意次序输入%d个非零元的行列元素值:（空格）\n",(*M).tu);for(k=0;k<t;k++){scanf("%d%d%d",&i,&j,&e);p=(OLNode*)malloc(sizeof(OLNode));if(!p)exit(0);p->i=i; // 生成结点p->j=j;p->e=e;if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j){// p插在该行的第一个结点处p->right=(*M).rhead[i];(*M).rhead[i]=p;}else // 寻查在行表中的插入位置{//从该行的行链表头开始，直到找到for(q=(*M).rhead[i]; q->right && q->right->j < j;q = q->right);p->right=q->right; // 完成行插入q->right=p;}if((*M).chead[j] == NULL || (*M).chead[j]->i > i){// p插在该列的第一个结点处p->down = (*M).chead[j];(*M).chead[j] = p;}else // 寻查在列表中的插入位置{for(q = (*M).chead[j];q->down && q->down->i < i;q = q->down);p->down=q->down; // 完成列插入q->down=p;}}return 1;}// 按行或按列输出稀疏矩阵Mint PrintSMatrix(CrossList M){int i,j;OLink p;printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);printf("请输入选择(1.按行输出2.按列输出): ");scanf("%d",&i);switch(i){case 1:for(j=1;j<=M.mu;j++){p=M.rhead[j];while(p){printf("%d行%d列值为%d\n",p->i,p->j,p->e);p=p->right;}}break;case 2:for(j=1;j<=M.nu;j++){p=M.chead[j];while(p){printf("%d行%d列值为%d\n",p->i,p->j,p->e);p=p->down;}}}return 1;}// 由稀疏矩阵M复制得到Tint CopySMatrix(CrossList M,CrossList *T){int i;OLink p,q,q1,q2;if((*T).rhead)DestroySMatrix(T);(*T).mu=M.mu;(*T).nu=M.nu;(*T).tu=M.tu;(*T).rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink));if(!(*T).rhead)exit(0);(*T).chead=(OLink*)malloc((M.nu+1)*sizeof(OLink));if(!(*T).chead)exit(0);for(i=1;i<=M.mu;i++) // 初始化矩阵T的行头指针向量;各行链表为空链表(*T).rhead[i]=NULL;for(i=1;i<=M.nu;i++) // 初始化矩阵T的列头指针向量;各列链表为空链表(*T).chead[i]=NULL;for(i=1;i<=M.mu;i++) // 按行复制{p=M.rhead[i];while(p) // 没到行尾{q=(OLNode*)malloc(sizeof(OLNode)); // 生成结点if(!q)exit(0);q->i=p->i; // 给结点赋值q->j=p->j;q->e=p->e;if(!(*T).rhead[i]) // 插在行表头(*T).rhead[i]=q1=q;else // 插在行表尾q1=q1->right=q;if(!(*T).chead[q->j]) // 插在列表头{(*T).chead[q->j]=q;q->down=NULL;}else // 插在列表尾{q2=(*T).chead[q->j];while(q2->down)q2=q2->down;q2->down=q;q->down=NULL;}p=p->right;}q->right=NULL;}return 1;}// 求稀疏矩阵的和Q=M+Nint AddSMatrix(CrossList M,CrossList N,CrossList *Q){int i,k;OLink p,pq,pm,pn;OLink *col;if(M.mu!=N.mu||M.nu!=N.nu){printf("两个矩阵不是同类型的,不能相加\n");exit(0);}(*Q).mu=M.mu; // 初始化Q矩阵(*Q).nu=M.nu;(*Q).tu=0; // 元素个数的初值(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));if(!(*Q).rhead)exit(0);(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!(*Q).chead)exit(0);for(k=1;k<=(*Q).mu;k++) // 初始化Q的行头指针向量;各行链表为空链表(*Q).rhead[k]=NULL;for(k=1;k<=(*Q).nu;k++) // 初始化Q的列头指针向量;各列链表为空链表(*Q).chead[k]=NULL;// 生成指向列的最后结点的数组col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!col)exit(0);for(k=1;k<=(*Q).nu;k++) // 赋初值col[k]=NULL;for(i=1;i<=M.mu;i++) // 按行的顺序相加{pm=M.rhead[i]; // pm指向矩阵M的第i行的第1个结点pn=N.rhead[i]; // pn指向矩阵N的第i行的第1个结点while(pm&&pn) // pm和pn均不空{if(pm->j<pn->j) // 矩阵M当前结点的列小于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移}else if(pm->j>pn->j)// 矩阵M当前结点的列大于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pn->e;p->right=NULL;pn=pn->right; // pn指针向右移}// 矩阵M、N当前结点的列相等且两元素之和不为0else if(pm->e+pn->e){p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pm->e+pn->e;p->right=NULL;pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移}else // 矩阵M、N当前结点的列相等且两元素之和为0{pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移continue;}if((*Q).rhead[i]==NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}while(pm) // 将矩阵M该行的剩余元素插入矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移if((*Q).rhead[i] == NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i] = pq = p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j] == NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j] = col[p->j] = p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}while(pn) // 将矩阵N该行的剩余元素插入矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pn->e;p->right=NULL;pn=pn->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}}for(k=1;k<=(*Q).nu;k++)if(col[k]) // k列有结点col[k]->down=NULL; // 令该列最后一个结点的down指针为空free(col);return 1;}// 求稀疏矩阵的差Q=M-Nint SubtSMatrix(CrossList M,CrossList N,CrossList *Q){int i,k;OLink p,pq,pm,pn;OLink *col;if(M.mu!=N.mu||M.nu!=N.nu){printf("两个矩阵不是同类型的,不能相加\n");exit(0);}(*Q).mu=M.mu; // 初始化Q矩阵(*Q).nu=M.nu;(*Q).tu=0; // 元素个数的初值(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));if(!(*Q).rhead)exit(0);(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!(*Q).chead)exit(0);for(k=1;k<=(*Q).mu;k++) // 初始化Q的行头指针向量;各行链表为空链表(*Q).rhead[k]=NULL;for(k=1;k<=(*Q).nu;k++) // 初始化Q的列头指针向量;各列链表为空链表(*Q).chead[k]=NULL;// 生成指向列的最后结点的数组col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!col)exit(0);for(k=1;k<=(*Q).nu;k++) // 赋初值col[k]=NULL;for(i=1;i<=M.mu;i++) // 按行的顺序相加{pm=M.rhead[i]; // pm指向矩阵M的第i行的第1个结点pn=N.rhead[i]; // pn指向矩阵N的第i行的第1个结点while(pm&&pn) // pm和pn均不空{if(pm->j<pn->j) // 矩阵M当前结点的列小于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移}// 矩阵M当前结点的列大于矩阵N当前结点的列else if(pm->j>pn->j){p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=-pn->e;p->right=NULL;pn=pn->right; // pn指针向右移}else if(pm->e-pn->e){// 矩阵M、N当前结点的列相等且两元素之差不为0p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pm->e-pn->e;p->right=NULL;pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移}else // 矩阵M、N当前结点的列相等且两元素之差为0{pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移continue;}if((*Q).rhead[i]==NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}while(pm) // 将矩阵M该行的剩余元素插入矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}while(pn) // 将矩阵N该行的剩余元素插入矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // 生成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // 非零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=-pn->e;p->right=NULL;pn=pn->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该行的第1个结点// p插在该行的表头且pq指向p(该行的最后一个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成行插入pq=pq->right; // pq指向该行的最后一个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插入// col[p->j]指向该列的最后一个结点col[p->j]=col[p->j]->down;}}}for(k=1;k<=(*Q).nu;k++)if(col[k]) // k列有结点col[k]->down=NULL; // 令该列最后一个结点的down指针为空free(col);return 1;}// 求稀疏矩阵乘积Q=M*Nint MultSMatrix(CrossList M,CrossList N,CrossList *Q){int i,j,e;OLink q,p0,q0,q1,q2;InitSMatrix(Q);(*Q).mu=M.mu;(*Q).nu=N.nu;(*Q).tu=0;(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));if(!(*Q).rhead)exit(0);(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!(*Q).chead)exit(0);for(i=1;i<=(*Q).mu;i++) // 初始化矩阵Q的行头指针向量;各行链表为空链表(*Q).rhead[i]=NULL;for(i=1;i<=(*Q).nu;i++) // 初始化矩阵Q的列头指针向量;各列链表为空链表(*Q).chead[i]=NULL;for(i=1;i<=(*Q).mu;i++)for(j=1;j<=(*Q).nu;j++){p0=M.rhead[i];q0=N.chead[j];e=0;while(p0&&q0){if(q0->i<p0->j)q0=q0->down; // 列指针后移else if(q0->i>p0->j)p0=p0->right; // 行指针后移else // q0->i==p0->j{e+=p0->e*q0->e; // 乘积累加q0=q0->down; // 行列指针均后移p0=p0->right;}}if(e) // 值不为0{(*Q).tu++; // 非零元素数加1q=(OLink)malloc(sizeof(OLNode)); // 生成结点if(!q) // 生成结点失败exit(0);q->i=i; // 给结点赋值q->j=j;q->e=e;q->right=NULL;q->down=NULL;if(!(*Q).rhead[i]) // 行表空时插在行表头(*Q).rhead[i]=q1=q;else // 否则插在行表尾q1=q1->right=q;if(!(*Q).chead[j]) // 列表空时插在列表头(*Q).chead[j]=q;else // 否则插在列表尾{q2=(*Q).chead[j]; // q2指向j行第1个结点while(q2->down)q2=q2->down; // q2指向j行最后1个结点q2->down=q;}}}return 1;}// 求稀疏矩阵M的转置矩阵Tint TransposeSMatrix(CrossList M,CrossList *T){int u,i;OLink *head,p,q,r;if((*T).rhead)DestroySMatrix(T);CopySMatrix(M,T); // T=Mu=(*T).mu; // 交换(*T).mu和(*T).nu(*T).mu=(*T).nu;(*T).nu=u;head=(*T).rhead; // 交换(*T).rhead和(*T).chead(*T).rhead=(*T).chead;(*T).chead=head;for(u=1;u<=(*T).mu;u++) // 对T的每一行{p=(*T).rhead[u]; // p为行表头while(p) // 没到表尾,对T的每一结点{q=p->down; // q指向下一个结点i=p->i; // 交换.i和.jp->i=p->j;p->j=i;r=p->down; // 交换.down.和rightp->down=p->right;p->right=r;p=q; // p指向下一个结点}}return 1;}int main(){CrossList A,B,C;InitSMatrix(&A); // CrossList类型的变量在初次使用之前必须初始化InitSMatrix(&B);printf("创建矩阵A: ");CreateSMatrix(&A);PrintSMatrix(A);printf("由矩阵A复制矩阵B: ");CopySMatrix(A,&B);PrintSMatrix(B);DestroySMatrix(&B); // CrossList类型的变量在再次使用之前必须先销毁printf("销毁矩阵B后:\n");PrintSMatrix(B);printf("创建矩阵B2:(与矩阵A的行、列数相同，行、列分别为%d,%d)\n",A.mu,A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf("矩阵C1(A+B): ");AddSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩阵C2(A-B): ");SubtSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩阵C3(A的转置): ");TransposeSMatrix(A,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);printf("创建矩阵A2: ");CreateSMatrix(&A);PrintSMatrix(A);printf("创建矩阵B3:(行数应与矩阵A2的列数相同=%d)\n",A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf("矩阵C5(A*B): ");MultSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);system("pause");return 0;}。
