基于十字链表与三元组表的稀疏矩阵压缩存储实例研究

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 2 3 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。

数据结构之稀疏矩阵稀疏矩阵的存储方式和操作分析稀疏矩阵是指矩阵中大部分元素为零的特殊矩阵。

在实际应用中，稀疏矩阵经常出现，如图像处理、网络分析和科学计算等领域。

对于稀疏矩阵的存储和操作是数据结构中的重要内容。

本文将介绍稀疏矩阵的存储方式和相关操作的分析。

一、稀疏矩阵存储方式稀疏矩阵的存储方式有多种，其中三元组顺序表和二维数组是比较常用的方法。

1. 三元组顺序表三元组顺序表是一种基于行优先存储的方式，可以将稀疏矩阵以非零元素的形式存储起来。

主要包括行号、列号和元素值三个信息。

以一个4x5的稀疏矩阵为例，其中有三个非零元素分别为A[1][2]=3, A[2][3]=4, A[3][4]=5。

可以使用三元组顺序表来存储：```行号列号元素值1 2 32 3 43 4 5```三元组顺序表的优点是可以节省存储空间，同时也方便进行矩阵的操作。

但是在进行元素的查找和修改时，效率较低。

2. 二维数组二维数组是一种常见的矩阵表示方法，可以直接使用二维数组来表示稀疏矩阵。

其中非零元素的位置用实际的值表示，其余位置用零值表示。

以同样的4x5的稀疏矩阵为例，使用二维数组存储如下：```0 0 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5```二维数组的优点是简单直观，并且可以快速进行元素的查找和修改。

但当稀疏矩阵的规模较大时，会造成较高的存储资源浪费。

二、稀疏矩阵的操作分析对于稀疏矩阵的操作，主要包括矩阵的转置、相加、相乘等。

1. 转置操作稀疏矩阵的转置是指将原始矩阵的行与列对调。

对于三元组顺序表来说，转置操作主要涉及到行号和列号的交换。

而对于二维数组来说，可以直接在取值的时候将行号和列号对调即可。

2. 相加操作稀疏矩阵的相加操作是指将两个矩阵对应位置的元素相加。

对于三元组顺序表来说，可以通过遍历两个矩阵的非零元素，并将其对应位置的元素相加。

而对于二维数组来说，可以直接将对应位置的元素相加即可。

3. 相乘操作稀疏矩阵的相乘操作是指将两个矩阵相乘得到一个新的矩阵。

稀疏矩阵应用摘要本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。

程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词程序设计；稀疏矩阵；三元组；十字链表1 引言•课程设计任务本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；求出A的转置矩阵D，输出D；求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

•课程设计性质数据结构课程设计是重要地实践性教学环节。

在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。

本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。

此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。

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

•需求分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。

首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别注意在十字链表下，对变量进行动态的地址分配。

福建工程学院课程设计课程：数据结构题目：稀疏矩阵的快速转置专业：运算机类班级：座号：姓名：2021年6月25日实验题目：稀疏矩阵的快速转置一、要解决的问题利用三元组表存储稀疏矩阵，利用快速转置算法进行转置，并输出转置之前和以后的三元组表和矩阵。

二、算法大体思想描述：由于稀疏矩阵的非零元素较少，零元素较多，因此只需存储其非零元素。

因此能够成立一个三元组表，别离保存稀疏矩阵的非零元素的行号、列号和元素值。

对稀疏矩阵进行快速转置是能够引入两个向量num[n+1],cpot[n+1],别离标记矩阵中第col列的非零元素个数和第一个非零元素在转置后的矩阵的位置；再扫描三元组表，找到非零元素，直接对其在转置后的矩阵所在的位置上进行修改，以节省时刻。

三、详细设计⒈元素类型，结点类型typedef struct {int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;} Tsmatrix;2.对抽象数据类型中的部份大体操作的伪码算法如下：Tsmatrix * creatarray(Tsmatrix *M){ int m,n,p=1;int c;printf("please input the array A:\n");for(m=1;m<=a;m++)for(n=1;n<=b;n++){ scanf("%d",&c);if(c!=0){ M->data[p].e=c;M->data[p].i=m;M->data[p].j=n;p++;}}M->tu=p; M->mu=a; M->nu=b;printf("yuan lai san yuan zu de biao shi wei :\n\n");for(m=1;m<=M->tu;m++)printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);printf("\n");return M;}/*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T){ int p,col,q,t,m;int num[100];int cpot[100];T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;if(T->tu!=0){for(col=1;col<=M->nu;col++) num[col]=0;for(t=1;t<=M->tu;t++) ++num[M->data[t].j];cpot[1]=1;for(col=2;col<=M->nu;col++) cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M->tu;++p){ col=M->data[p].j; q=cpot[col];T->data[q].i=M->data[p].j;T->data[q].j=M->data[p].i;T->data[q].e=M->data[p].e;++cpot[col];}}printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");for(m=1;m<=T->tu;m++)printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);printf("\n");return T;}/*输出三元组函数*/void print(Tsmatrix *T,int x,int y){ int m,n,p=1;int d;for(m=1;m<=x;m++){ printf("\n");for(n=1;n<=y;n++){ if(T->data[p].i==m&&T->data[p].j==n){ d=T->data[p].e;p++;}else d=0;printf("%6d",d);}}}}3.主函数和其他函数的伪码算法void main(){ Tsmatrix *M,*T;M=(Tsmatrix *)malloc(sizeof(Tsmatrix));T=(Tsmatrix *)malloc(sizeof(Tsmatrix));printf("please input array's row and col:\n");scanf("%d%d",&a,&b); /*输入行列数*/ M=creatarray(M); /*创建稀疏矩阵*/printf("you had creat the array:\n");print(M,a,b); /*输出创建好的三元组*/T=fasttrans(M,T); /*将三元组转置*/printf("the trans array is:\n");print(T,b,a);getch();}4、模块结构及功能}四、源程序清单：#include<>#define MAXSIZE 100typedef struct {int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;} Tsmatrix;int a,b; /*概念全局变量数组的行数a和列数b*//*用数组创建三元组*/Tsmatrix * creatarray(Tsmatrix *M){ int m,n,p=1;int c;printf("please input the array A:\n");for(m=1;m<=a;m++)for(n=1;n<=b;n++){ scanf("%d",&c);if(c!=0){ M->data[p].e=c;M->data[p].i=m;M->data[p].j=n;p++;}}M->tu=p; M->mu=a; M->nu=b;printf("yuan lai san yuan zu de biao shi wei :\n\n");for(m=1;m<M->tu;m++)printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);printf("\n");return M;}/*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T){ int p,col,q,t,m;int num[100];int cpot[100];T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;if(T->tu!=0){for(col=1;col<=M->nu;col++) num[col]=0;for(t=1;t<=M->tu;t++) ++num[M->data[t].j];cpot[1]=1;for(col=2;col<=M->nu;col++) cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M->tu;++p){ col=M->data[p].j; q=cpot[col];T->data[q].i=M->data[p].j;T->data[q].j=M->data[p].i;T->data[q].e=M->data[p].e;++cpot[col];}}printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");for(m=1;m<T->tu;m++)printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);printf("\n");return T;}/*输出三元组函数*/void print(Tsmatrix *T,int x,int y){ int m,n,p=1;int d;for(m=1;m<=x;m++){ printf("\n");for(n=1;n<=y;n++){ if(T->data[p].i==m&&T->data[p].j==n){ d=T->data[p].e;p++;}else d=0;printf("%6d",d);}}}void main(){ Tsmatrix *M,*T;M=(Tsmatrix *)malloc(sizeof(Tsmatrix));T=(Tsmatrix *)malloc(sizeof(Tsmatrix));printf("please input array's row and col:\n");scanf("%d%d",&a,&b); /*输入行列数*/M=creatarray(M);printf("you had creat the array:\n");print(M,a,b);T=fasttrans(M,T);printf("the trans array is:\n");print(T,b,a);getch();}五、测试数据及测试结果：（1）我输入的稀疏矩阵为：（2）回车显示的结果是：六、课程设计总结及心得体会：通过本次课程设计，我对有关稀疏矩阵及其三元组表的知识做了温习和巩固。

稀疏矩阵的⼗字链表存储稀疏矩阵的压缩存储有⼏种⽅式，如：三元组顺序表、⾏逻辑链接的顺序表和⼗字链表。

使⽤链表存储的好处是：便于矩阵中元素的插⼊和删除。

例如：“将矩阵B加到矩阵A上”，那么矩阵A存储的元素就会有变动。

⽐如会增加⼀些⾮零元，或者删除⼀些元素（因为b ij+a ij=0）。

下图是矩阵M和M的⼗字链表存储：⼗字链表及其结点可⽤如下结构体表⽰：typedef struct OLNode{int i, j; // ⾮零元的⾏列下标ElemType e;struct OLNode *right, *down; // 向右域和向下域} OLNode, *OLink;typedef struct{OLink *rhead, *chead; // ⾏链表和列链表的头指针数组int mu, nu, tu; // 稀疏矩阵的⾏数、列数和⾮零元个数} CrossList;在通过代码创建⼗字链表时，要特别注意right、down和rhead、chead这些指针的赋值。

现在来看“将矩阵B加到矩阵A上”这个问题。

所要做的操作：a ij +b ij，其结果⼀共会有4种情况：1. a ij（b ij = 0）（不做变化）2. b ij（a ij = 0）（在A中插⼊⼀个新结点）3. a ij +b ij ≠ 0 （改变结点a ij的值域）4. a ij +b ij = 0 （删除结点a ij）假设指针pa和pb分别指向矩阵A和B中⾏值相同的两个结点，对于上述4种情况的处理过程为：1. 若“pa == NULL”或“pa->j⼤于pb->j”，则在矩阵A中插⼊⼀个值为b ij的结点。

并且需要修改同⼀⾏前⼀结点的right指针，和同⼀列前⼀结点的down指针。

2. 若“pa->j⼩于pb-j”，则pa指针右移⼀步。

3. 若“pa->j等于pb-j”，并且“pa->e + pb->e != 0”，则修改pa->e即可。

稀疏矩阵的压缩存储方法稀疏矩阵是指矩阵中绝大部分元素为0的矩阵。

在现实生活中，很多矩阵都是稀疏的，比如图像处理中的二值化图像、网络连接矩阵等。

由于稀疏矩阵中大部分元素为0，对其进行存储和计算会消耗大量的存储空间和计算资源。

因此，对稀疏矩阵进行压缩存储是一种有效的方式，可以节省存储空间、提高计算效率。

一般来说，存储稀疏矩阵的方法有三种：顺序存储法、链式存储法和三元组顺序表法。

其中，三元组顺序表法是最常用的一种方法。

三元组顺序表法是将稀疏矩阵的非零元素按照行、列和值三个维度进行存储。

具体来说，可以定义一个结构体来表示一个非零元素，包括行号、列号和值三个属性。

然后，可以使用一个一维数组来存储所有的非零元素，数组的长度为非零元素的个数。

这样，就可以通过遍历数组来获取稀疏矩阵的所有非零元素。

三元组顺序表法的优点是存储简单、操作灵活。

由于只存储非零元素，可以大大减少存储空间的占用。

而且，可以根据需要对非零元素进行插入、删除等操作，非常方便。

除了三元组顺序表法，还有其他的压缩存储方法。

比如，可以使用行逻辑链接法，将矩阵的每一行都看作一个链表的节点，节点中包含列号和值两个属性。

通过将每一行的节点连接起来，就可以得到一个链表，从而实现稀疏矩阵的存储和操作。

这种方法相对简单，但是在获取某个元素时效率较低。

还可以使用十字链表法来存储稀疏矩阵。

十字链表法是在三元组顺序表法的基础上进行改进，将矩阵的行和列分别看作两个链表，链表中的节点包含行号、列号和值三个属性。

通过将行链表和列链表进行交叉连接，就可以得到一个十字链表。

这种方法可以提高获取某个元素的效率，但是相应地增加了存储空间的占用。

稀疏矩阵的压缩存储方法是一种优化矩阵存储和计算的有效方式。

三元组顺序表法是最常用的一种方法，可以通过一个一维数组存储稀疏矩阵的非零元素。

此外，还可以使用行逻辑链接法和十字链表法来存储稀疏矩阵。

不同的方法适用于不同的场景，可以根据实际需求选择合适的压缩存储方法。

稀疏矩阵压缩存储方法嘿，朋友们！今天咱来唠唠这个稀疏矩阵压缩存储方法。

你说啥是稀疏矩阵呀？就好比你有一大筐苹果，大部分都是空的位置，只有那么几个苹果在那，这就很稀疏嘛！那对于这样的矩阵，咱要是傻乎乎地全存起来，多浪费空间呀，就像你非得把那一大筐空位置也当宝贝一样存着。

这时候压缩存储方法就闪亮登场啦！它就像是个聪明的整理大师，能把那些重要的、有实际意义的元素好好地归置起来，而那些没啥用的空位置就不管啦。

比如说有一种方法叫三元组顺序表。

想象一下，这就像是给每个重要的元素都贴上一个小标签，标签上写着它在哪行哪列，还有它的值是多少。

这样不就把关键信息都抓住了嘛，还不占太多地方。

还有一种叫十字链表法呢！这就好比是给矩阵里的元素织了一张特别的网，把它们都串起来，让它们之间的关系变得清清楚楚。

这样找起元素来可方便啦，就跟你在一堆杂物里能快速找到你想要的东西一样。

咱为啥要用这压缩存储方法呀？你想想，要是数据量超级大，那得占多少存储空间呀！这就好比你有一个超级大的房间，要是不懂得合理利用空间，那不是浪费嘛！用了这方法，就像给房间做了个巧妙的收纳，一下子就整洁多了。

而且呀，在处理数据的时候，这压缩存储方法可太有用啦！能让计算速度变快，就像给你的电脑加了个小火箭，跑得飞快。

你说这多好呀！既节省了空间，又提高了效率。

这就像是你出门旅行，只带了最必要的东西，又轻松又方便。

所以呀，可别小瞧了这稀疏矩阵压缩存储方法，它可是数据处理里的一把好手呢！它能让我们更高效地处理那些看似杂乱无章的数据，让它们变得井井有条。

咱可得好好利用起来，让我们的工作和学习变得更轻松、更高效呀！这难道不是很值得我们去研究和掌握的吗？原创不易，请尊重原创，谢谢!。

稀疏矩阵的十字链表存储的思路
稀疏矩阵是一种大多数元素都为0的矩阵，而十字链表是一种常
见的数据结构，用于存储稀疏矩阵。

十字链表提供了一种有效的方法，可以对矩阵进行高效的访问和操作。

十字链表的存储方式是将矩阵分成两个链表：行链表和列链表。

行链表和列链表中的每个节点都存储了一个非零元素和该元素的行编
号和列编号。

同时，每个节点也包含了指向下一个相同行或相同列的
节点的指针。

在十字链表中，每个节点都可以快速找到它所处的行和列以及与
它相邻的元素。

这使得我们可以在矩阵中进行诸如插入、删除、修改
及查找等操作。

在操作过程中，我们可以通过指针操作找到相邻的非
零元素，从而充分利用稀疏矩阵的特殊性质。

对于一个稀疏矩阵，我们需要将每一个非零元素存储到十字链表中。

首先，我们需要创建一个新的节点，并为它分配内存空间。

然后，我们需要将该节点插入到正确的位置，即行链表和列链表中。

插入操作的基本思路是，我们首先遍历行链表，找到该元素所在
的行号。

然后在该行号的节点中，按照列号的大小插入该新节点。

同时，我们需要在列链表中找到该元素所在的列号，并在该列号的节点
中插入新节点。

除了插入操作外，十字链表还支持删除操作、修改操作和查找操作。

这些操作都可以通过指针操作实现。

总的来说，十字链表是一种高效的数据结构，可以有效地存储稀
疏矩阵。

通过使用十字链表，我们可以对矩阵进行各种操作，而不必
费力遍历整个矩阵。

在实现稀疏矩阵算法时，我们常常会使用十字链
表这种数据结构。

稀疏矩阵的存储实现Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT课程设计任务书学生姓名：宋吉松专业班级：软件1202班指导教师：李晓红工作单位：计算机科学与技术学院题目: 稀疏矩阵的存储实现初始条件：理论：学习了《数据结构》课程，掌握了一种计算机高级语言。

实践：计算机技术系实验中心提供计算机及软件开发环境。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）实现稀疏矩阵的三元组和十字链表两种存储结构（2）实现稀疏矩阵的基本运算（3）输出结果2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。

时间安排： 2013年12月16日--25日指导教师签名：李晓红 2013年12月14日系主任（或责任教师）签名：年月日摘要本课程设计在学习数据结构的前提下，运用c语言，对稀疏矩阵进行三元组存储和十字链表存储，并完成稀疏矩阵的转置，相加，相乘等基本运算。

关键词稀疏矩阵三元组十字链表基本运算Abstract This course is designed on the premise of learning datastructures using c language, for sparse matrix triple store to store and cross-linked, and were achieved under the two storage sparse matrix transpose, add, multiply, and other basic operations.Keywords sparse matrix triples Crusaders basic operations目录引言 (1)1 需求分析稀疏矩阵三元组表和十字链表两种存储的实现 (2)稀疏矩阵转置 (2)稀疏矩阵的相加相乘 (2)输出结果 (2)2 数据结构设计三元组的结构体 (2)十字链表的结构体 (3)3算法设计三元组...3 (5)三元组的相加 (5) (8) (10)十字链表 (11)..12主函数 (13)4 设计体会 (16)5 结束语 (16)附1 参考文献 (16)附2 源代码 (17)附3 运行结果 (38)引言什么是稀疏矩阵人们无法给出确切的定义，它只是一个凭人们的直觉来了解的概念。

基于三元组表的存储结构实现稀疏矩阵的应用课程设计，实验报告数据结构课程设计设计题目:基于三元组表的存储结构实现稀疏矩阵的应用学生姓名: 专业班级: 指导教师: 完成时间:信息工程学院信科系课程设计成绩评定表(本科)课题名称基于三元组表的存储结构实现稀疏矩阵的基本操作院系年级专业学号姓名成绩1、课题设计目的:(1)掌握稀疏矩阵三元组表的存储、创建、显示、转置。

(2)利用三元组表实现矩阵的相加、减。

(3)了解稀疏矩阵的相关应用。

2、课题设计意义:本次课题设计可以使我们更熟练的掌握有关三元组表及稀疏课题设计矩阵的相关知识，比一般存储方法节省了存储空间，基于三元组表目的与的存储结构实现了稀疏矩阵的基本操作。

设计意义本次课程设计是本组成员共同努力而完成的，第一次进行课程设计是我们的探索过程，这个过程中，我们克服了一个个困难，在摸索中前行，我们相信通过此次课程设计我们每个人都会对数据结构这门课程有更深一步的了解。

指导教师:年月日目录一、课题设计目的及意义 ............................................11.1、课题设计目的 (1)1.2、课程设计意义 (1)二、需求分析 (1)2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值 (1)2.2 构造函数进行稀疏矩阵的转置并输出结果 (1)2.3 构造函数进行两稀疏矩阵相加、减及相乘并输出最终稀疏矩阵 (1)2.4 退出系统 (2)三、项目设计 (2)3.1结构设计 (2)3.2算法思想 (2)3.3模块图 (2)3.4流程图 (3)四、系统实现 (4)4.1主调函数 (4)4.2三元组表建立 (4)4.3矩阵建立 (4)4.4矩阵相加减及转置 (5)五、系统调试 (8)5.1主菜单输出 (8)5.2矩阵相加 (9)5.3矩阵转置 (9)5.4矩阵相减 (10)六、实验总结 (10)七、附录 (11)一、课题设计目的及意义1.1、课题设计目的(1)掌握稀疏矩阵三元组表的存储，创建，显示，转置等方法。

关于稀疏矩阵和十字链表的参考文献
1. "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 这本书是计算机算法领域的经典教材，其中有关稀疏矩阵和数据结
构的章节可以提供深入的理解和参考。

2. "Sparse Matrix Technology" by I. S. Duff, R. G. Grimes, and J. G. Lewis. 这本书详细介绍了稀疏矩阵的技术和算法，对于深入了解稀疏矩阵的处理和优化有很好的参考价值。

3. "Data Structures and Algorithm Analysis in C++" by Mark Allen Weiss. 这本书介绍了数据结构和算法分析的C++实现，其中包括了对十字链表等数据结构的讲解和实现。

4. "A New Storage Scheme for Lists Using Doubly Linked Recursion" by C. Y. Ho and R. C. H. Connor. 这篇学术文章介
绍了十字链表的存储方案，提供了对该数据结构的深入理解和实现
细节。

以上书籍和学术文章可以作为对稀疏矩阵和十字链表的深入研究和学习的参考文献，希望能够对你有所帮助。

return hm;
}
linknode *InputMatlind(linknode *hm,int s)
{
linknode *cp[100],*p,*q;
int m,n,t;
int i,j,k,maxlin;
i=hm->rows;
j=hm->cols;
if (i>j)
maxlin=i;
else
maxlin=j;
{
p->right=q->right;
q->right=p;
k=0;
}
else if(q->right->cols==n)
{
p->right=q->right->right;
q->right=p;
k=0;
}
else if(q->right->cols<n)
{
q=q->right;
k=1;
}
}
k=1;
2、实验内容
（1）创建空的稀疏矩阵的十字链表存储结构。
（2）稀疏矩阵十字链表的数据输入。
（3）稀疏矩阵十字链表的数据显示。
（4）稀疏矩阵十字链表的数据查找。
3、实验要求
（1）利用C或c++语言完成算法设计和程序设计。
（2）上机调试通过实验程序。
（3）输入右侧矩阵A，检验程序运行结果。
（4）给出具体的算法分析，包括时间复杂度和空间复杂度。
k=1;
}
else
k=0;
}while (k);
hm=InputMatlind(hm,s);
printf("\n显示十字链表");

实现稀疏矩阵（采用三元组表示）的基本运算实验报告一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求:（1）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；（3）输出a + b 的三元组；（4）输出 a * b 的三元组；三实验内容:稀疏矩阵的抽象数据类型:ADT SparseMatrix {数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n;ai,j∈ElemSet,m和n分别称为矩阵的行数和列数}数据关系: R={ Row , Col }Row ={<ai,j ,ai,j+1> | 1≤i≤m , 1≤j ≤n-1}Col ={<a i,j , a i+1,j >| 1≤i≤m-1,1≤j ≤n}基本操作:CreateSMatrix(&M)操作结果：创建稀疏矩阵 M PrintSMatrix(M)初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M)初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T)初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到TAddSMatrix(M, N, &Q)初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+NSubSMatrix(M, N, &Q)初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T)初始条件：稀疏矩阵M已经存在操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q)初始条件：稀疏矩阵M已经存在操作结果：求矩阵的积Q=M*N}ADT SparseMatrix存储结构的定义#define N 4typedef int ElemType;#define MaxSize 100 =i;[].c=j;[].d=A[i][j];++;}}}void DispMat(TSMatrix t){int i;if <=0)return;printf("\t%d\t%d\t%d\n",,,;printf("\t------------------\n");for (i=0;i<;i++)printf("\t%d\t%d\t%d\n",[i].r,[i].c,[i].d); }解题思路：1.转置矩阵：只要判定原矩阵有值，那么只要遍历一遍原矩阵，把原来矩阵中非0元素行列变换一下赋值到新的矩阵中即可。

稀疏矩阵压缩存储方法稀疏矩阵是指大部分元素为0的矩阵。

对于稀疏矩阵的存储，传统的二维数组会造成较大的存储空间浪费，因此需要采用稀疏矩阵的压缩存储方法，以节省存储空间和提高运算效率。

一种常见的稀疏矩阵压缩存储方法是三元组表示法，即将稀疏矩阵的非零元素存储为一个三元组的形式，包括非零元素的行、列和值。

这种方法的优点是简单易懂，适用于各种稀疏矩阵。

以一个5x5的稀疏矩阵为例，其矩阵内容如下：1 0 0 0 23 0 0 0 40 0 5 0 00 6 0 0 00 0 0 0 7将该矩阵用三元组表示法进行压缩存储，可以得到如下的表示：(0,0,1) (0,4,2) (1,0,3) (1,4,4) (2,2,5) (3,1,6) (4,4,7)其中每个三元组的第一个元素表示非零元素的行号，第二个元素表示非零元素的列号，第三个元素表示非零元素的值。

这样，我们只需存储非零元素的信息，大大减少了存储空间。

对于稀疏矩阵的运算，三元组表示法也很方便。

例如，对两个稀疏矩阵进行相加操作，只需遍历两个矩阵的三元组，对行列号相同的元素进行相加即可。

这样，不需要遍历整个矩阵，大大提高了运算效率。

除了三元组表示法，还有一种常见的稀疏矩阵压缩存储方法是行逻辑链接表（CSR）表示法。

该方法将稀疏矩阵按行划分，分别存储每行的非零元素和对应的列号。

同时，还需要一个长度为行数的一维数组来记录每行的起始位置和非零元素的个数。

还是以之前的稀疏矩阵为例，将其用CSR表示法进行存储。

首先，确定每行的非零元素个数，可以得到一维数组count=[2,2,1,1,1]，表示第0行有2个非零元素，第1行有2个非零元素，以此类推。

然后，可以得到一维数组rowPtr=[0,2,4,5,6]，表示第0行非零元素在三元组中的起始位置为0，第1行为2，以此类推。

最后，将每行的非零元素以及对应的列号存储在一维数组data 和colInd中，其中data=[1,2,3,4,5,6,7]，colInd=[0,4,0,4,2,1,4]。

c语言稀疏矩阵应用代码实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。

在C语言中，实现稀疏矩阵的加法、转置和乘法涉及复杂的数据结构和算法。

其中，常用的表示稀疏矩阵的两种数据结构是三元组和十字链表。

下面我将为您提供一个简单的示例代码，用C语言实现稀疏矩阵的加法、转置和乘法操作，使用三元组表示法来表示稀疏矩阵。

首先，我们需要定义表示稀疏矩阵的三元组结构体：```c#include<stdio.h>#define MAX_SIZE100typedef struct{int row;int col;int value;}Element;typedef struct{int rows;int cols;int num_elements;Element data[MAX_SIZE];}SparseMatrix;```接下来，我们实现稀疏矩阵的加法、转置和乘法函数：```c#include<stdbool.h>//加法函数SparseMatrix addSparseMatrix(SparseMatrix matrix1,SparseMatrix matrix2){ SparseMatrix result;result.rows=matrix1.rows;result.cols=matrix1.cols;result.num_elements=0;int i=0,j=0;while(i<matrix1.num_elements&&j<matrix2.num_elements){if(matrix1.data[i].row<matrix2.data[j].row||(matrix1.data[i].row==matrix2.data[j].row&&matrix1.data[i].col<matrix2.data[j].col)){ result.data[result.num_elements++]=matrix1.data[i++];}else if(matrix1.data[i].row>matrix2.data[j].row||(matrix1.data[i].row==matrix2.data[j].row&&matrix1.data[i].col>matrix2.data[j].col)){ result.data[result.num_elements++]=matrix2.data[j++];}else{Element element;element.row=matrix1.data[i].row;element.col=matrix1.data[i].col;element.value=matrix1.data[i].value+matrix2.data[j].value;if(element.value!=0){result.data[result.num_elements++]=element;}i++;j++;}}while(i<matrix1.num_elements){result.data[result.num_elements++]=matrix1.data[i++];}while(j<matrix2.num_elements){result.data[result.num_elements++]=matrix2.data[j++];}return result;}//转置函数SparseMatrix transposeSparseMatrix(SparseMatrix matrix){ SparseMatrix result;result.rows=matrix.cols;result.cols=matrix.rows;result.num_elements=matrix.num_elements;int count[matrix.cols];int index[matrix.cols];for(int i=0;i<matrix.cols;i++){count[i]=0;}for(int i=0;i<matrix.num_elements;i++){count[matrix.data[i].col]++;}index[0]=0;for(int i=1;i<matrix.cols;i++){index[i]=index[i-1]+count[i-1];}for(int i=0;i<matrix.num_elements;i++){int j=index[matrix.data[i].col];result.data[j].row=matrix.data[i].col;result.data[j].col=matrix.data[i].row;result.data[j].value=matrix.data[i].value;index[matrix.data[i].col]++;}return result;}//乘法函数SparseMatrix multiplySparseMatrix(SparseMatrix matrix1,SparseMatrix matrix2){ SparseMatrix result;if(matrix1.cols!=matrix2.rows){result.rows=0;result.cols=0;result.num_elements=0;return result;}result.rows=matrix1.rows;result.cols=matrix2.cols;result.num_elements=0;bool visited[matrix2.cols];for(int i=0;i<matrix2.cols;i++){visited[i]=false;}for(int i=0;i<matrix1.num_elements;i++){for(int j=0;j<matrix2.num_elements;j++){if(matrix1.data[i].col==matrix2.data[j].row){Element element;element.row=matrix1.data[i].row;element.col=matrix2.data[j].col;element.value=matrix1.data[i].value*matrix2.data[j].value; result.data[result.num_elements++]=element;visited[matrix2.data[j].col]=true;}}}for(int i=0;i<matrix2.cols;i++){if(!visited[i]){for(int j=0;j<matrix1.rows;j++){Element element;element.row=j;element.col=i;element.value=0;result.data[result.num_elements++]=element;}}}return result;}```请注意，上述代码只是一个简单示例，实际应用中可能需要根据具体需求进行优化和扩展。

采⽤⼗字链表存储的稀疏矩阵Description当矩阵的⾮零元个数和位置在操作过程中变化较⼤时，就不宜采⽤顺序存储的结构来表⽰三元组的线性表了。

因此，在这种情况下，采⽤链式存储结构表⽰三元组更为恰当。

⼗字链表就是能够实现这样功能的⼀种数据结构。

在⼗字链表中，每个⾮零元可以⽤⼀个包含5个域的结点表⽰。

其中i、j和e这3个域分别表⽰该⾮零元所在的⾏、列和⾮零元的值，向右域right⽤来链接同⼀⾏中下⼀个⾮零元，⽽向下域down⽤来链接同⼀列中下⼀个⾮零元。

同⼀⾏的⾮零元通过right域链接成⼀个线性链表，同⼀列的⾮零元通过down域链接成⼀个线性链表。

每个⾮零元既是某个⾏链表中的⼀个结点，⼜是某个列链表中的⼀个结点，整个矩阵通过这样的结构形成了⼀个⼗字交叉的链表。

稀疏矩阵的⼗字链表类型可以描述如下：下⾯是建⽴稀疏矩阵⼗字链表的算法描述：给出⼀个稀疏矩阵，请将其存储到⼀个⼗字链表中，并将存储完毕的矩阵输出。

Input输⼊的第⼀⾏是两个整数r和c（r<200, c<200, r*c <= 12500），分别表⽰⼀个包含很多0的稀疏矩阵的⾏数和列数。

接下来有r⾏，每⾏有c个整数，⽤空格隔开，表⽰稀疏矩阵的各个元素。

Output输出读⼊的矩阵。

输出共有r⾏，每⾏有c个整数，每个整数后输出⼀个空格。

请注意⾏尾输出换⾏。

Sample Input5 60 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35Sample Output0 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35HINT提⽰：对于m⾏n列且有t个⾮零元的稀疏矩阵，算法5.4的执⾏时间为O(t×s)，其中s=max(m,n)。

这是由于每建⽴⼀个⾮零元结点时，都需要通过遍历查询它所在的⾏表和列表中的插⼊位置。

三元组结构实现稀疏矩阵转置算法的分析文章简要叙述了稀疏矩阵压缩存储的三元组表示法及其基于此种结构的矩阵的转置运算。

探讨了基于三元组结构的矩阵转置算法的具体实现方法及其时空复杂度的问题。

【关键词】稀疏矩阵压缩存储三元组转置算法在一些特殊矩阵中，如对称矩阵和上下三角矩阵，非零元素一般都有明显的规律，从而都可以压缩到一维数组里面，然而，实际应用中经常会遇到这样一些矩阵，它们非零元素少，且分布不均匀，且没有明显的规律，称之为稀疏矩阵。

按照压缩存储的思想，只需存储矩阵中的非零元素。

为了便于存取和检索，一般在存储的时候必须带有合适的辅助信息，即同时记录下它所在的行列的位置等等。

在实际应用中，一般我们采取的是用三元组和十字链表两种表示方法来实现稀疏矩阵的存储及其运算。

稀疏矩阵在数值计算、电力系统的潮流计算、天气预报、工程分析计算等方面都有着大量的应用，不少实际问题都可以转化为对稀疏矩阵的计算问题。

了解稀疏矩阵的各种操作变得尤为重要。

1 基本概念设矩阵中有t个非零元素，若t远远小于矩阵元素的总数，则称该矩阵为稀疏矩阵。

通常，在m×n 的矩阵中，存在t个非零元素。

设δ= t/（m*n），则称δ为矩阵的稀疏因子，一般认为当δ≤0.05时为稀疏矩阵。

在存储稀疏矩阵时，为了节约存储单元，很自然的压缩方法就是只存储非零元素，但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储相应的辅助信息，才能准确迅速确定一个非零元素是矩阵中的哪一个元素。

最简单的办法就是将非零元素的值和它所在的行列号作为一个结点存放到一起，于是矩阵中的每一个非零元素就由一个三元组（i，j，aij）唯一确定。

显然，稀疏矩阵的压缩存储方法会让其失去随机存取功能。

2 三元组表示稀疏矩阵转置算法的实现用三元组来表示非零元素时稀疏矩阵的压缩存储方法的具体数据类型说明如下：三元组表示的稀疏矩阵，如何实现转置算法呢？矩阵的转置是基本的矩阵运算，对于一个m×n 的矩阵M，它的转置N是一个n×m 的矩阵，且有N（i，j）=M（j，i）。