数据结构实验五矩阵的压缩存储与运算

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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。

矩阵压缩存储矩阵是在计算机科学和数学中常见的数据结构，用于表示具有行和列的二维数据。

在很多应用中，矩阵的大小可能非常大，占用大量的存储空间。

为了节省存储空间并提高计算效率，在某些情况下可以使用矩阵压缩存储技术。

什么是矩阵压缩存储？矩阵压缩存储是一种将稀疏矩阵（其中大部分元素为零）以更紧凑形式表示的技术。

通过只存储非零元素及其位置，可以显著减少所需的存储空间。

稀疏矩阵稀疏矩阵是指其中大部分元素为零的矩阵。

在实际应用中，很多情况下只有少数元素非零，例如图像处理、网络分析、自然语言处理等领域。

对于这些稀疏矩阵，传统的二维数组表示方法会浪费大量的存储空间。

稀疏矩阵压缩存储方法COO格式COO（Coordinate）格式是最简单直观的稀疏矩阵压缩存储方法。

它使用三个数组分别存储非零元素的值、行索引和列索引。

例如，对于矩阵：1 0 00 2 03 0 4COO格式可以表示为：values = [1, 2, 3, 4]rows = [0, 1, 2, 2]cols = [0, 1, 0, 2]CSR格式CSR（Compressed Sparse Row）格式是一种常用的稀疏矩阵压缩存储方法。

它使用三个数组分别存储非零元素的值、每行第一个非零元素在值数组中的位置和列索引。

例如，对于矩阵：1 0 00 2 03 0 4CSR格式可以表示为：values = [1, 2, 3, 4]row_ptrs = [0, -1, -1, -1] # 第一个非零元素在values中的位置cols = [0, -1, -1, -1] # 列索引CSC格式CSC（Compressed Sparse Column）格式与CSR格式类似，只是将行和列交换。

它使用三个数组分别存储非零元素的值、每列第一个非零元素在值数组中的位置和行索引。

其他压缩存储方法除了COO、CSR和CSC格式，还有其他一些矩阵压缩存储方法，如LIL（List of Lists）格式、DOK（Dictionary of Keys）格式等。

一、实验目的1. 理解并掌握矩阵压缩存储的基本原理和方法。

2. 学习针对不同类型矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储技术。

3. 通过编程实现矩阵压缩存储，并验证其正确性和效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 实验数据：随机生成的矩阵数据三、实验内容本次实验主要针对以下三种特殊矩阵的压缩存储进行实验：1. 对称矩阵2. 三角矩阵（上三角矩阵和下三角矩阵）3. 稀疏矩阵四、实验步骤1. 对称矩阵压缩存储- 设计一个对称矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。

- 实现一个函数，将输入的对称矩阵压缩存储到一维数组中。

- 实现一个函数，根据一维数组中的元素索引还原对称矩阵。

2. 三角矩阵压缩存储- 设计一个三角矩阵的结构体，包含矩阵的行数、列数以及压缩后的数组。

- 实现两个函数，分别用于将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中。

- 实现两个函数，分别用于根据一维数组中的元素索引还原上三角矩阵和下三角矩阵。

3. 稀疏矩阵压缩存储- 设计一个稀疏矩阵的结构体，包含矩阵的行数、列数、非零元素个数以及压缩后的数组。

- 实现一个函数，将输入的稀疏矩阵压缩存储到一维数组中。

- 实现一个函数，根据一维数组中的元素索引还原稀疏矩阵。

五、实验结果与分析1. 对称矩阵压缩存储- 实验结果：成功将输入的对称矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：对称矩阵压缩存储可以节省约50%的存储空间。

2. 三角矩阵压缩存储- 实验结果：成功将输入的上三角矩阵和下三角矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：三角矩阵压缩存储可以节省约75%的存储空间。

3. 稀疏矩阵压缩存储- 实验结果：成功将输入的稀疏矩阵压缩存储到一维数组中，并可以正确还原。

- 分析：稀疏矩阵压缩存储可以大大节省存储空间，提高矩阵运算的效率。

精品资料数据结构实验五矩阵的压缩存储与运算........................................第五章矩阵的压缩存储与运算【实验目的】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 23 …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= 。

矩阵的存储及转置算法矩阵是数学中一个重要的概念，它由一个数的方阵组成，可以用于表示线性变换、线性方程组的系数矩阵等。

在实际应用中，矩阵的存储和转置算法是非常关键的。

矩阵的存储可以有多种方式，常用的有行优先和列优先两种方式，它们分别对应于矩阵的行主序和列主序存储。

在行优先存储方式下，矩阵的元素按照行的顺序进行存储，而在列优先存储方式下，矩阵的元素按照列的顺序进行存储。

行主序存储方式可以有效地利用缓存，可以提高矩阵运算的效率，但是在进行矩阵转置操作时，会导致缓存未命中，降低算法的效率。

而列主序存储方式在进行矩阵转置操作时可以利用缓存，提高算法的效率。

因此，在实际应用中，选择合适的存储方式对于提高算法效率非常重要。

矩阵的转置是指将矩阵的行变为列，列变为行。

矩阵的转置操作可以写成下面的公式：A^T[i][j]=A[j][i]其中A表示原始矩阵，A^T表示转置矩阵，[i][j]表示第i行第j列元素。

对于存储方式为行优先的矩阵，转置算法可以按照下面的步骤进行：1.创建一个新的矩阵B，行数等于原始矩阵A的列数，列数等于原始矩阵A的行数。

2.遍历原始矩阵A的所有元素，将该元素放入新矩阵B对应的位置，即A[i][j]变为B[j][i]。

3.返回新矩阵B作为转置矩阵。

对于存储方式为列优先的矩阵，转置算法可以按照下面的步骤进行：1.遍历原始矩阵A的所有元素，从第一列开始，依次将每列的元素放入新矩阵B对应的位置，即A[i][j]变为B[j][i]。

2.返回新矩阵B作为转置矩阵。

需要注意的是，在使用列优先存储方式时，可以直接将原始矩阵的元素复制到新矩阵的对应位置，而无需额外的空间。

综上所述，矩阵的存储和转置算法是非常重要的。

在实际应用中，选择合适的存储方式可以提高算法的效率，而转置操作可以改变矩阵的存储方式，从而改变算法的效率。

因此，了解矩阵的存储和转置算法对于优化矩阵运算非常重要。

矩阵压缩存储矩阵压缩存储是一种将矩阵中的数据进行压缩存储的方法，可以大大减小矩阵所占用的存储空间，提高数据存储和传输的效率。

矩阵压缩存储的实现方式有很多种，其中比较常见的有行压缩存储和列压缩存储。

行压缩存储是将矩阵中的每一行数据进行压缩存储，对于每一行数据，只存储其中非零元素的值和它们在该行中的位置。

这种方式适用于矩阵中非零元素比较稀疏的情况，可以大大减小存储空间。

例如，对于一个5*5的矩阵：1 0 0 0 00 2 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5使用行压缩存储方式，可以将其压缩为：1 12 23 34 4 51 2 2 3 4 5其中第一行表示非零元素的值，第二行表示它们在该行中的位置。

列压缩存储是将矩阵中的每一列数据进行压缩存储，对于每一列数据，只存储其中非零元素的值和它们在该列中的位置。

这种方式适用于矩阵中非零元素比较密集的情况，可以大大减小存储空间。

例如，对于同样的5*5的矩阵：1 0 0 0 00 2 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5使用列压缩存储方式，可以将其压缩为：1 2 3 4 51 2 3 4 51 2 3 4 51 2 4 51 5其中第一行表示非零元素的值，第二行表示它们在该列中的位置。

矩阵压缩存储的优点在于可以大大减小存储空间，提高数据存储和传输的效率。

但是，它也存在一些缺点。

首先，对于非零元素比较密集的矩阵，行压缩存储的效果不如列压缩存储，反之亦然。

其次，矩阵压缩存储需要进行解压缩操作才能得到原始数据，这会增加一定的计算量和时间成本。

最后，矩阵压缩存储的实现需要考虑到数据的稀疏性和分布情况，否则可能会导致存储空间的浪费或者解压缩效率的降低。

总之，矩阵压缩存储是一种非常实用的数据存储和传输方式，可以大大提高数据处理的效率和速度。

在实际应用中，需要根据具体情况选择合适的压缩方式，并进行适当的优化和调整，以达到最佳的效果。

§5 矩阵的压缩存储§5.1 特殊矩阵§5.1.1 三角矩阵与对称矩阵设有矩阵A : array [1..n , 1..n] of Atype ； 三角矩阵：若A 的对角线以上（或以下）的元素均为零。

对称矩阵：若A 中的元素满足： a ij = a ji （1≤i ，j ≤n ）， 则称为n 阶对称矩阵。

为了节省存储空间，三角矩阵和对称矩阵都不需存储对角线以上（或以下）的元素，一般采用一维数组的结构。

此时需要 个元素的存储空间。

若将上三角矩阵中的元素按行顺序存储到V 中，则V[k]与A[i, j]的对应关系是： k = ①若将下三角矩阵中的元素按行顺序存储到V 中，则V[k]与A[i, j]的对应关系是： k= ②§5.1.2 带状矩阵在n ×n 的矩阵中，若所有非零元素均集中在以对角线为中的带状区中，该带状区包括主对角线上面和下面各k 条对角线以及主对角线上的元素，这种矩阵称带状矩阵。

a 11 0 00 0 a 21 a 22 0 0 0 a 31 a 32 a 33 0 0 a 41 a 42 a 43 a 44 0 a 51 a 52 a 53 a 54 a 55 上三角矩阵 a 11 a 12 a 13 a 14 a 15 a 21 a 22 a 23 a 24 a 25 a 31 a 32 a 33 a 34 a 35 a 41 a 42 a 43 a 44 a 45 a 51 a 52 a 53 a 54 a 55 对称矩阵V a 11 a 12 a 13 a 14 a 15 0 a 22 a 23 a 24 a 25 0 0 a 33 a 34 a 35 0 0 0 a 44 a 450 0 00 a 55下三角矩阵11 2 3 0 0 0 4 2 10 13 0 05 12 76 8 0 0 20 17 9 11 15 0 0 6 1 14 21 0 0 0 2 18 3 k=2的带状矩阵 主对角线k 条对角线k 条对角线在带状矩阵A 中，i – j > k 或 ③ 时，A[ i , j ] = 0 。

软件学院上机实验报告课程名称：数据结构实验项目：矩阵实验室：耘慧420姓名：学号专业班级：实验时间： 2016.11.24实验成绩评阅教师一、实验目的及要求1．掌握稀疏矩阵压缩存储方法( 三元组顺序表存储 ) 。

2．完成压缩存储下矩阵计算( 矩阵转置 ) 。

二、性质验证性三、实验学时2学时四、实验环境C与 C++程序设计学习与实验系统五、实验内容及步骤实验内容：1.实现矩阵压缩存储。

( 静态数组压缩存储或直接输入矩阵非 0 元均可 )2.实现矩阵转置算法。

3.实现矩阵快速转置。

实验步骤：1.实现矩阵压缩存储。

( 静态数组压缩存储或直接输入矩阵非 0 元均可 )2. 实现矩阵转置算法TransposeSMatrix(TSMatrix M,TSMatrix &T)。

3. 实现矩阵快速转置FastTransposeSMatrix(TSMatrix M,TSMatrix &T)。

4.主函数中创建矩阵 M ，将 M 调用转置算法转置成矩阵 N，调用快速转置算法转化成矩阵 T。

六、实验数据及结果分析七、总结了解了矩阵的一些知识，懂得了矩阵的一些算法。

并且在实际上机中，学会了矩阵的程序的编写方法。

附录源程序清单插入;#include<stdio.h>#include"malloc.h"#include<conio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define MAXSIZE 12500#define MAXRC 1000typedef int ElemType;typedef int Status;typedef struct {int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];int rpos[MAXRC+1];int mu,tu,nu;}RLSMatrix;Status TransposeSMatrix(RLSMatrix M, RLSMatrix &T){ int q=1,col=0,p=0;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==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;++q;}}return 0;}Status FastTransposeSMtrix(RLSMatrix M,RLSMatrix&T){ int col=0,t=0,p=0,q=0;ElemType num[100],cpot[100];T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){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];}}return OK;}Status CreateSMatrix(RLSMatrix *M){int k,m,n,i;ElemType e;printf(" 请输入行列非零个数");scanf_s("%d",&(*M).mu);scanf_s("%d",&(*M).nu);scanf_s("%d",&(*M).tu);(*M).data[0].i=0;for(i=1;i<=(*M).tu;i++){do{printf(" 请输入元素行列元素值");scanf_s("%d",&m);scanf_s("%d",&n);scanf_s("%d",&e);k=0;if(m<1||m>(*M).mu||n<1||n>(*M).nu)k=1;if(m<=(*M).data[i-1].i&&n<=(*M).data[i-1].j)k=1;}while(k);(*M).data[i].i=m;(*M).data[i].j=n;(*M).data[i].e=e;}return OK;}void printfSMatrix(RLSMatrix &M){int i;printf_s("%4d%4d%8d\n",M.mu,M.nu,M.tu);for(i=1;i<=M.tu;i++)printf_s("%4d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);}int main(void){RLSMatrix M,N,T,Q; CreateSMatrix(&M); FastTransposeSMtrix( M,T); printfSMatrix(T); CreateSMatrix(&N); TransposeSMatrix(M,Q); printfSMatrix(Q);_getch();return 0;}。

矩阵的压缩存储前⾔ ⼀⼊编程深似海，从此砖头是爱⼈，⽇⽇搬，夜夜搬，搬到天荒地⽼，精尽⼈亡，直教⼈失去了⾃我，忘记了时间，忽然之间发现九⽉份快没了，赶紧写篇博客打个卡，证明⼀下我还活着。

数组与矩阵 数组是由⼀组相同类型的数据元素构成的有限序列，访问数据元素的⽅式是使⽤元素各⾃的序号进⾏访问，也就是下标。

数组它本⾝是线性表的推⼴，⼀维数组就是⼀个向量形式的线性表，⼆维数组就是由⼀维数组组成的线性表。

在许多科学计算和⼯程应⽤中，经常要⽤到矩阵的概念，我们⽤的最多的其实就是Mysql的表，表数据都是⾏列存储，这就是矩阵。

由于矩阵具有元素数⽬固定以及元素按下标关系有序排列等特点，所以在使⽤⾼级语⾔编程时，⼀般都是⽤⼆维数组来存储矩阵。

数组的顺序存储为什么是顺序存储？ 我想问这个问题就太低级了。

因为它是数组，数据的存储⽅式分为顺序存储和链式存储两种，数组⼀旦被定义，他的维数和维界就已固定，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作，不存在插⼊和删除操作，所以数组适合⽤顺序存储。

数组存放在内存中的映射关系 数组可以是多维的，但是内存空间却是⼀维的，所以我们就要把多维数组通过⼀定的映射顺序把它变成⼀维的，然后存储到内存空间之中。

在⼤多数⾼级编程语⾔中，多维数组在内存中通常有两种不同的顺序存储⽅式，按⾏优先顺序存储和按列优先顺序存储。

举个例⼦，以下3⾏4列的⼀个⼆维数组矩阵：a1,a2,a3,a4b1,b2,b3,b4c1,c2,c3,c4 按⾏优先顺序存储： 按列优先顺序存储：地址计算 地址计算的意思就是给定数组下标，求在⼀维内存空间的地址，从⽽取出数据。

我们先来看⼀维数组的地址计算 ⼀维数组内的元素只有⼀个下标，存储⽅法和普通的线性表⼀样。

如⼀维数组 A = [a1,a2,a3,......ai,.........,an]，每个元素占⽤size个存储单元（就是内存⼤⼩），那么元素ai的存储地址为 A[0]的位置 + (i-1)*size再来看⼆维数组的地址计算 以⼆维数组Amn为例，⾸元素为A[0][0]，数组中任意元素A[i][j]的地址为：A[0][0]的位置 + （n * (i-1) + (j-1)）* size；⽐如：⼀个5⾏4列的⼆维数组A，按⾏存储，其中每个元素占2个存储单元，⾸元素地址是1000，求第3⾏第2列的元素在内存中的地址。

矩阵压缩存储矩阵压缩存储是一种用于减少数据存储空间的技术，它通过将稀疏矩阵转换为紧凑的格式来实现。

稀疏矩阵是指其中大部分元素为零的矩阵。

在实际应用中，许多矩阵都具有稀疏性，即只有少数非零元素。

因此，使用矩阵压缩存储可以显著减少存储空间的占用。

一种常用的矩阵压缩存储方法是压缩行存储（Compressed Row Storage，CRS）。

在CRS中，只保存非零元素的值以及它们所在的列索引，而行索引则通过其他方式获得。

具体来说，CRS将矩阵分为三个数组，分别用来存储非零元素的值、非零元素所在的列索引以及行指针。

通过使用矩阵压缩存储，可以有效地减少存储空间的占用。

以一个1000x1000的稀疏矩阵为例，假设其中只有100个非零元素，如果使用普通的二维数组来存储该矩阵，需要占用1000x1000=1000000个存储单元。

而如果使用矩阵压缩存储，只需要存储100个非零元素的值和列索引，以及101个行指针。

显然，矩阵压缩存储可以大幅减少存储空间的使用。

矩阵压缩存储不仅可以减少存储空间的占用，还可以提高计算效率。

在处理稀疏矩阵的运算时，如果使用矩阵压缩存储，可以避免对大量零元素的计算，从而提高运算速度。

此外，由于稀疏矩阵的非零元素较少，矩阵压缩存储还可以减少内存访问的次数，进一步提高运算效率。

除了CRS，还有其他的矩阵压缩存储方法，如压缩列存储（Compressed Column Storage，CCS）和块压缩存储（Block Compressed Storage，BCS）。

这些方法在存储结构上有所不同，但都旨在减少存储空间的占用并提高计算效率。

矩阵压缩存储在许多领域都有广泛的应用。

在图像处理中，图像可以看作是一个二维矩阵，而图像处理算法通常只需要对少数非零元素进行操作。

因此，使用矩阵压缩存储可以大幅减少图像数据的存储空间，并提高图像处理的效率。

在科学计算中，矩阵压缩存储也被广泛应用于线性代数运算、有限元分析等领域。

实验：矩阵的压缩存储及相关操作一、实验目的1 理解稀疏矩阵的三元组顺序表类型定义，2 掌握稀疏矩阵的输入( 即根据输入数据创建矩阵的三元组顺序表)3 掌握稀疏矩阵输出(即根据矩阵的三元组顺序表在屏幕上输出完整的矩阵)4 掌握稀疏矩阵的转置算法。

二、实验内容1．编写程序任意输入一个稀疏矩阵M，用三元组顺序表压缩存储该稀疏矩阵M，然后求其转置矩阵T，并输出转置矩阵T。

运行效果图:注意:矩阵要求用三元组顺序表存储三、思考与提高如何计算两个三元组表表示的稀疏矩阵的乘积？【方案一】程序代码：#include <iostream>#include <malloc.h>#include <cmath>#include <iomanip>using namespace std;#define MAXSIZE 12500#define OK 1#define ERROR 0typedef int Status;typedef int ElemType;//#define Triple Mtypedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;}TSMatrix;CreateSMatrix(TSMatrix &M){int i,m,n;ElemType e;Status k;cout<<"输入矩阵的行、列数、非零元素个数：\n";//Mcin>>M.mu>>M.nu>>M.tu;M.data[0].i=0; // 为以下比较顺序做准备for(i=1;i<=M.tu;i++){do{//printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,M.mu,M.nu);cout<<"第"<<i<<"个数所在的行列号元素值\n";//scanf("%d,%d,%d",&m,&n,&e);cin>>m>>n>>e;k=0;if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围k=1;if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错k=1;}while(k); //对于非法操作不予存储，直到输入正确位置M.data[i].i=m;M.data[i].j=n;M.data[i].e=e;}return OK;}Status TransposeSMatrix(TSMatrix M,TSMatrix &T){ // 求稀疏矩阵M的转置矩阵T。

一、实验目的1. 了解矩阵压缩存储的基本原理和方法。

2. 掌握稀疏矩阵的压缩存储方法，包括三元组顺序表存储和压缩存储下三角矩阵。

3. 熟悉矩阵压缩存储在数据结构中的应用，提高数据存储效率。

4. 通过实验验证矩阵压缩存储方法的有效性和优越性。

二、实验原理矩阵压缩存储是一种针对稀疏矩阵的存储方法，通过压缩存储非零元素，减少存储空间，提高数据存储效率。

稀疏矩阵是指矩阵中大部分元素为0的矩阵，其特点是存储空间利用率低，计算效率低。

矩阵压缩存储主要有以下几种方法：1. 三元组顺序表存储：将稀疏矩阵中的非零元素及其对应的行、列索引存储在一个三元组中，形成顺序表。

2. 压缩存储下三角矩阵：对于下三角矩阵，只存储主对角线以下的非零元素及其对应的行、列索引。

3. 压缩存储上三角矩阵：对于上三角矩阵，只存储主对角线以上的非零元素及其对应的行、列索引。

三、实验内容1. 实现稀疏矩阵的三元组顺序表存储。

2. 实现压缩存储下三角矩阵和上三角矩阵。

3. 实现矩阵转置算法，包括压缩存储下三角矩阵的转置和压缩存储上三角矩阵的转置。

4. 比较不同存储方法的存储空间和计算效率。

四、实验步骤1. 创建一个稀疏矩阵，随机生成非零元素及其对应的行、列索引。

2. 实现稀疏矩阵的三元组顺序表存储，将非零元素及其对应的行、列索引存储在一个顺序表中。

3. 实现压缩存储下三角矩阵，只存储主对角线以下的非零元素及其对应的行、列索引。

4. 实现压缩存储上三角矩阵，只存储主对角线以上的非零元素及其对应的行、列索引。

5. 实现矩阵转置算法，包括压缩存储下三角矩阵的转置和压缩存储上三角矩阵的转置。

6. 比较不同存储方法的存储空间和计算效率。

五、实验结果与分析1. 三元组顺序表存储存储空间：n（非零元素个数） 3计算效率：O(n)2. 压缩存储下三角矩阵存储空间：n（非零元素个数） 3计算效率：O(n)3. 压缩存储上三角矩阵存储空间：n（非零元素个数） 3计算效率：O(n)4. 矩阵转置算法计算效率：O(n)通过实验结果可以看出，压缩存储下三角矩阵和上三角矩阵的存储空间和计算效率与三元组顺序表存储相当，且对于稀疏矩阵，压缩存储方法可以显著减少存储空间，提高数据存储效率。

数据结构——矩阵压缩与压缩矩阵的转置与乘法计算 为什么要对矩阵进⾏压缩存储呢？对于⼀个n*m的矩阵，我们⼀般会想到开⼀个n*m的⼆维数组来存储，这样计算操作都很⽅便模拟，但当⼀个矩阵很⼤时，这样对于空间的开销与浪费是很可怕的，尤其是当矩阵变成多维时。

但我们往往不会在矩阵每⼀个位置都存有数据，很多矩阵元素其实是0，我们需要记录的只是那些⾮零元素，于是我们可以记录⾮零元素的位置与值，这样便可以⼤⼤减少空间上的浪费。

矩阵压缩存储代码（注意要按⾏顺序遍历存储矩阵⾮零元素）：1 typedef struct {2int i, j; //⾮零元⾏下标与列下标3 ElemType e;4 }Triple;56 typedef struct {7 Triple data[MAXSIZE + 1];8int mu, nu, tu; //⾏数，列数，⾮零元个数9 }TSMatrix; 矩阵转置是矩阵运算中极为重要的操作，但矩阵压缩后我们不能再按原来的⽅式⽤n*m的遍历⽅式进⾏转置操作，那我们应该怎么进⾏转置呢，⾸先想到的是以列为参考值对元素进⾏遍历转置，这样访问元素的顺序正好是转制后存储的顺序，代码如下：1 Status TransposeSMatrix(TSMatrix M, TSMatrix & T) {2 T.mu = M.nu;3 T.nu = M.mu;4 T.tu = M.tu;5if(T.tu) {6int q = 1;7for(int col = 1; col <= M.nu; ++col)8for(int p = 1; p <= M.tu; ++p)9if(M.data[p].j == col) {10 T.data[q].i = M.data[p].j;11 T.data[q].j = M.data[p].i;12 T.data[q].e = M.data[p].e;13 ++q;14 }15 }16return OK;17 } 我们注意到当矩阵不那么稀疏时，⽐如如果这是⼀个稠密矩阵甚⾄n*m的空间⾥每⼀个位置都是⼀个⾮零元素，这时这个代码的复杂度达到了O(mu*nu*nu)，⽐直接⽤数组存储的O(mu*nu)还要⼤⼀个数量级，这样节省⼀点空间浪费⼤量时间的做法显然是不合适的，我们考虑改进算法，我们注意到如果我们预先知道矩阵M每⼀列的第⼀个⾮零元素在T中应有的位置，那么转置中我们就可以直接把他放在那个位置，这时，我们考虑开辅助数组记录每⼀列第⼀个⾮零元素的位置，以及每⼀列⾮零元素的数量，但其实，每⼀列的第⼀个⾮零元素的位置就是前⼀列第⼀个⾮零元素位置加上前⼀列⾮零元素数量，我们每次维护剩余元素在剩余矩阵中每⼀列第⼀个⾮零元素的位置数组，就得到了下⾯的O(nu + tu)代码:1 Status FastTransposeSMtrix(TSMatrix M, TSMatrix &T) {2 T.mu = M.nu;3 T.nu = M.mu;4 T.tu = M.tu;5if(T.tu) {6int *num = new int[M.nu + 1], *cpot = new int[M.tu + 1];7for(int col = 1; col <= M.nu; ++ col)8 num[col] = 0;9for(int t = 1; t <= M.tu; ++t) ++num[M.data[t].j];10 cpot[1] = 1;11for(int col = 2; col <= M.nu; ++ col)12 cpot[col] = cpot[col - 1] + num[col - 1];13for(int p = 1; p <= M.tu; ++p) {14int col = M.data[p].j, q = cpot[col];15 T.data[q].i = M.data[p].j;16 T.data[q].j = M.data[p].i;17 T.data[q].e = M.data[p].e;18 ++cpot[col];19 }20delete num;21delete cpot;22 }23return OK;24 }矩阵转置到此就结束了，写进⼀个cpp效果就像下⾯这样，感兴趣的可以⾃⼰测试下效果：1 #include <iostream>2 #include <cstdio>3 #include <cstdlib>4 #include <cmath>5 #include <algorithm>6 #include <cstring>7 #include <vector>8 #include <string>9 #include <queue>10 #include <map>11 #include <set>1213#define FRER() freopen("in.txt", "r", stdin);14#define INF 0x3f3f3f3f1516using namespace std;1718//函数状态码定义19#define TRUE 120#define FALSE 021#define OK 122#define ERROR 023#define INFEASIBLE -124//#define OVERFLOW -22526 typedef int Status;27 typedef int ElemType;2829#define MAXSIZE 125003031 typedef struct {32int i, j; //⾮零元⾏下标与列下标33 ElemType e;34 }Triple;3536 typedef struct {37 Triple data[MAXSIZE + 1];38int mu, nu, tu; //⾏数，列数，⾮零元个数39 }TSMatrix;4041 Status TransposeSMatrix(TSMatrix M, TSMatrix & T) {42 T.mu = M.nu;43 T.nu = M.mu;44 T.tu = M.tu;45if(T.tu) {46int q = 1;47for(int col = 1; col <= M.nu; ++col)48for(int p = 1; p <= M.tu; ++p)49if(M.data[p].j == col) {50 T.data[q].i = M.data[p].j;51 T.data[q].j = M.data[p].i;52 T.data[q].e = M.data[p].e;53 ++q;54 }55 }56return OK;57 }5859 Status FastTransposeSMtrix(TSMatrix M, TSMatrix &T) {60 T.mu = M.nu;61 T.nu = M.mu;62 T.tu = M.tu;63if(T.tu) {64int *num = new int[M.nu + 1], *cpot = new int[M.tu + 1]; 65for(int col = 1; col <= M.nu; ++ col)66 num[col] = 0;67for(int t = 1; t <= M.tu; ++t) ++num[M.data[t].j];68 cpot[1] = 1;69for(int col = 2; col <= M.nu; ++ col)70 cpot[col] = cpot[col - 1] + num[col - 1];71for(int p = 1; p <= M.tu; ++p) {72int col = M.data[p].j, q = cpot[col];73 T.data[q].i = M.data[p].j;74 T.data[q].j = M.data[p].i;75 T.data[q].e = M.data[p].e;76 ++cpot[col];77 }78delete num;79delete cpot;80 }81return OK;82 }8384int main()85 {86//FRER()8788 TSMatrix MatrixA, MatrixB;89 cin >> MatrixA.mu >> MatrixA.nu >> MatrixA.tu;90for(int i = 1; i <= MatrixA.tu; ++i)91 cin >> MatrixA.data[i].i >> MatrixA.data[i].j >> MatrixA.data[i].e;92//TransposeSMatrix(MatrixA, MatrixB);93 FastTransposeSMtrix(MatrixA, MatrixB);94for(int i = 1; i <= MatrixB.tu; ++i)95 cout << MatrixB.data[i].i << '' << MatrixB.data[i].j << '' << MatrixB.data[i].e << endl;9697return0;98 }99100/*测试数据1016 7 81021 2 121031 3 91043 1 -31053 6 141064 3 241075 2 181086 1 151096 4 -7110*/ 接下来是压缩矩阵的乘法，类似转置，我们直接在矩阵结构体⾥开⼀个数组⽤来存矩阵每⼀⾏第⼀个⾮零元素的在M中位置，就像这样：1 typedef struct {2 Triple data[MAXSIZE + 1]; //⾮零元三元组表3int rops[MAXSIZE + 1]; //各⾏第⼀个⾮零元位置4int mu, nu, tu; //⾏数，列数，⾮零元个数5 }RLSMatrix; 由于稀疏矩阵相乘不⼀定还是稀疏矩阵，所以我们要根据结果判断元素是否是⾮零元，模拟乘法运算如下：1 Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix & Q) {2if(M.nu != N.mu) return ERROR;3 Q.mu = M.mu;4 Q.nu = N.nu;5 Q.tu = 0;6int *ctemp = new int[Q.nu + 1];78if(M.mu * N.nu != 0) {9for(int arow = 1; arow <= M.mu; ++arow) {10int tp;11 memset(ctemp, 0, (Q.nu + 1) * sizeof(int));12 Q.rops[arow] = Q.tu + 1;13if(arow < M.mu)14 tp = M.rops[arow + 1];15else16 tp = M.tu + 1;17for(int p = M.rops[arow]; p < tp; ++p) { //对当前⾏的每⼀个⾮零元进⾏计算18int brow = M.data[p].j; //找到对应元在N中的标号19int t;20if(brow < N.mu) t = N.rops[brow + 1];21else t = N.tu + 1;22for(int q = N.rops[brow]; q < t; ++q) {23int ccol = N.data[q].j;24 ctemp[ccol] += M.data[p].e * N.data[q].e;25 }26 }27for(int ccol = 1; ccol <= Q.nu; ++ccol) //压缩存储该⾏⾮零元28if(ctemp[ccol]) {29if(++Q.tu > MAXSIZE) return ERROR;30 Q.data[Q.tu].i = arow;31 Q.data[Q.tu].j = ccol;32 Q.data[Q.tu].e = ctemp[ccol];33 }34 }35 }36return OK;37 }。

实验5 矩阵的压缩存储实现1. 实验要求(1) 实现矩阵（对称阵和稀疏阵）的压缩存储结构设计；(2) 实现矩阵的操作（稀疏矩阵快速转置和乘法）算法设计；2. 主要实验方法(1) 设计算法思想；(2) 编写算法代码；(3) 运行算法代码，并分析算法的效率；3. 实验内容实验5.1 对称矩阵顺序表存储表示（一）具体要求：（1）初始化一个对称矩阵（2）显示对称矩阵（3）任意取对称矩阵第i行第j列的值（二）测试: 输入如下对称矩阵，测试存储和访问情况对称矩阵为：1 1 0 51 2 0 70 0 1 55 7 5 7实验5.2 稀疏矩阵的三元组顺序表存储表示，及稀疏矩阵快速转置（一）具体要求：（1）初始化一个稀疏矩阵（2）显示初始化后的稀疏矩阵（3）转置（4）显示转置后的稀疏矩阵（二）测试: 输入如下稀疏矩阵，测试用三元组顺序表存储的稀疏矩阵的转置结果稀疏矩阵为：0 0 0 11 0 0 10 0 1 0实验5.3 稀疏矩阵的行逻辑链接顺序表存储表示，及稀疏矩阵乘法（一）具体要求：（1）初始化两个个稀疏矩阵a,b（2）获取这两个矩阵的各行第一个非零元的位置表rpos（2）显示初始化后的稀疏矩阵a,b（3）矩阵a和b相乘，结果存入矩阵c，即c=a*b（4）显示矩阵c（二）测试: 输入如下稀疏矩阵，测试用行逻辑链接顺序表存储的稀疏矩阵的乘积结果稀疏矩阵a为：3 0 0 50 -1 0 02 0 0 0稀疏矩阵b为：0 21 0-2 40 0乘积结果矩阵c为0 6-1 00 44. 实验重点和难点(1) 重点：特殊矩阵的压缩存储结构设计。

(2) 难点：稀疏矩阵的压缩存储结构的设计及操作算法设计。

5. 实验结果与分析（必须写这部分）应用文字、表格、图形等将数据表示出来6. 实验总结与体会必须写这部分7. 部分代码指导实验5.1实验5.2实验5.3。

稀疏矩阵的压缩存储及运算一、实验内容实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算二、实验母的掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。

矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。

三、问题描述1）用行逻辑链接顺序表和十字链表分别实现稀疏矩阵的压缩存储2）编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构）四、问题的实现稀疏矩阵的抽象数据类型定义：ADT SpareseMatrix{数据对象：;,,2,1;,,2,1|{n j m i D a ij ===},,列数分别称为矩阵的行数和和n m ElemSet a j i ∈数据关系： ：}1,11|,{}11,1|,{},{,1,1,,n j m i Col n j m i Row Col Row R a a a a j i j i j i j i ≤≤-≤≤><=-≤≤≤≤><==++基本操作：CreateSMatrix(&M)；操作结果：创建稀疏矩阵M 。

PrintSMatrix(M)；初始条件：稀疏矩阵M 存在。

操作结果：输出稀疏矩阵M 。

AddSMatrix(M ，N ，&Q)；初始条件：稀疏矩阵M 和N 的行数和列数对应相等。

操作结果：求稀疏矩阵的和Q=M+N 。

MultSMatrix(M ，N ，&Q)；初始条件：稀疏矩阵M 的列数等于N 的行数。

操作结果：求稀疏矩阵乘积Q=M*N 。

TransposeSMatrix(M,&T)；初始条件：稀疏矩阵M 存在。

操作结果：求稀疏矩阵M 的转置矩阵T 。

}ADT SpareseMatrix五、主要源程序代码#include <iostream>using namespace std;#define MAXSIZE 100;typedef struct OLNode{int i,j;int e;struct OLNode *right,*down;}OLNode,*OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;}CrossList; //十字链表结构体定义int CreatSMatrix_OL(CrossList &M){int i,j,e;OLink q;OLink p;cout<<"请输入稀疏矩阵的行数，列数，非零元素的个数：";cin>>M.mu;cin>>M.nu;cin>>M.tu;M.rhead=(OLink *)malloc((M.mu+1)*sizeof(OLNode));M.chead=(OLink *)malloc((M.nu+1)*sizeof(OLNode));for(i=1;i<=M.mu;i++) M.rhead[i]=NULL;for(i=1;i<=M.nu;i++) M.chead[i]=NULL;cout<<"请输入稀疏矩阵，若为空，则退出"<<endl;cin>>i;cin>>j;cin>>e;while (i!=0){p=(OLink)malloc(sizeof(OLNode));p->i=i;p->j=j;p->e=e;if (M.rhead[i]==NULL || M.rhead[i]->j>j) {p->right=M.rhead[i];M.rhead[i]=p;}else{q=M.rhead[i];while (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->down=M.chead[j];M.chead[j]=p;}else{q=M.chead[j];while (q->down && q->down->i<i)q=q->down;p->down=q->down;q->down=p;}cin>>i;cin>>j;cin>>e;}} //创建十字链表void TurnSMatrix_OL(CrossList &M){int a,b;OLink p,q;for(a<1;a<=M.mu;a++){q=p=M.rhead[a];while(q){b=p->i;p->i=p->j;p->j=b;q=p->right;p->right=p->down;p->down=q;}}} //十字链表实现稀疏矩阵转置int AddSMatrix_OL(CrossList *A,CrossList *B){OLNode *pa,*pb,*p,*pre,*cp[100];int i,j,t;t=A->tu+B->tu;for(j=1;j<=A->nu;j++) cp[j]=A->chead[j];for(i=1;i<=A->mu;i++){pa=A->rhead[i];pb=B->rhead[i];pre=NULL;while(pb){if(pa==NULL || pa->j>pb->j){p=(OLink)malloc(sizeof(OLNode));if(!pre)A->rhead[i]=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->chead[p->j]){A->chead[p->j]=cp[p->j]=p;p->down=NULL;}else{cp[p->j]->down=p;cp[p->j]=p;}pb=pb->right;}else if(pa->j<pb->j) {pre=pa;pa=pa->right;}else if(pa->e+pb->e){t--;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;}else{t=t-2;if(!pre)A->rhead[i]=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->chead[p->j]==p) A->chead[p->j]=cp[p->j]=p->down;else cp[p->j]->down=p->down;free(p);pb=pb->right;}}}A->mu=A->mu>B->mu? A->mu:B->mu;A->nu=A->nu>B->nu? A->nu:B->nu;return 1;} //十字链表实现两稀疏矩阵相加int MultSMatrix_OL(CrossList M,CrossList N,CrossList &Q){int i,j,e;OLink p0,q0,p,p1,p1a;if(M.nu!=N.mu){cout<<"稀疏矩阵A的列数和B的行数不相等，不能相乘";return 0;}Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(!(Q.rhead=(OLink *)malloc((Q.mu+1)*sizeof(OLink))))exit(-2);if(!(Q.chead=(OLink *)malloc((Q.nu+1)*sizeof(OLink))))exit(-2);for(i=1;i<=Q.mu;i++) Q.rhead[i]=NULL;for(i=1;i<=Q.nu;i++) 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(p0->j>q0->i) q0=q0->down;else if(p0->j<q0->i) p0=p0->right;else{e+=p0->e*q0->e;q0=q0->down;p0=p0->right;}}if(e){if(!(p=(OLink)malloc(sizeof(OLNode))))exit(-2);Q.tu++;p->i=i;p->j=j;p->e=e;p->right=NULL;p->down=NULL;if(Q.rhead[i]==NULL)Q.rhead[i]=p1=p;else p1->right=p;p1=p;if(Q.chead[j]==NULL)Q.chead[j]=p;else{p1a=Q.chead[j];while(p1a->down)p1a=p1a->down;p1a->down=p;}}}return 1;} //十字链表实现两稀疏矩阵相乘int ShowSMatrix(CrossList *A){int a;OLink p;for(a=1;a<=A->mu;a++)if(A->rhead[a]) {p=A->rhead[a];}while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;}return 1;} //十字链表显示void main(){int n;char c;CrossList MM,TT,SS;CreatSMatrix_OL(MM);cout<<"您输入的稀疏矩阵（只列出非零元素）："<<endl;cout<<"行列大小"<<endl;ShowSMatrix(&MM);cout<<"请选择操作："<<endl;cout<<"1：实现稀疏矩阵的转置"<<endl;cout<<"2：实现两稀疏矩阵的相加"<<endl;cout<<"3：实现两稀疏矩阵的相乘"<<endl;cout<<"4：退出程序"<<endl;cin>>n;switch(n){case 1:TurnSMatrix_OL(MM);cout<<"转置后的稀疏矩阵：行列大小"<<endl;ShowSMatrix(&MM);break;case 2:cout<<"请输入另一个稀疏矩阵："<<endl;CreatSMatrix_OL(TT);AddSMatrix_OL(&MM,&TT);cout<<"相加后的矩阵为："<<endl;ShowSMatrix(&MM);break;case 3:cout<<"请输入另一个稀疏矩阵："<<endl;CreatSMatrix_OL(TT);MultSMatrix_OL(MM,TT,SS);cout<<"相乘后的矩阵为："<<endl;ShowSMatrix(&SS);break;case 4:exit(0);default:cout<<"error!"<<endl;}system("pause");}六、总结整个实验中学会了稀疏矩阵的压缩存储方法，用十字链表来存储，以及在特定存储方法下的基本运算。

实验报告课程名：数据结构（ C 语言版）实验名：矩阵的压缩存储姓名：班级：学号：时间：2014.11.23一实验目的与要求1.掌握并实现稀疏矩阵的压缩存储的方法2.在该存储方法上实现矩阵的操作二实验内容?判断一个用二维数组存储的矩阵是不是稀疏矩阵?将其转化为压缩存储的形式?在压缩存储上实现矩阵的乘法和转置操作三实验结果与分析压缩转置程序：#include<stdio.h>//判断该矩阵是否为稀疏矩阵#define m 10#define n 10int a[m][n]={{1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,7,0},{0,0,0,0,0,0,8,0,0,0},{0,0,0,0,0,0,0,0,0,0},};struct three{int i,j;int value;};struct three stu[100];struct three1{int i,j;int value;};struct three1 stu1[100];int jiance(){int x=0;//赋初值为0for(x=0;x<=99;x++){stu[x].value=0;}float t=0;float v;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(a[i][j]!=0)t++;}}if((v=t/(m*n))<=0.05){printf(" 该矩阵为稀疏矩阵 %f\n",v);return 1;}else{printf(" 该矩阵不是稀疏矩阵 \n");return 0;}}void yasuo(){int t=0;for(int r=0;r<m;r++){for(int c=0;c<n;c++){if(a[r][c]!=0){stu[t].i=r;stu[t].j=c;stu[t].value=a[r][c];t++;}}}}void display(){int x=0;printf(" 压缩矩阵的三元组为 :\n");for(x=0;x<=99;x++){if(stu[x].value==0)break;printf("{%d,%d,%d} ",stu[x].i,stu[x].j,stu[x].value);}printf("\n");}void zhuanzhi(){int x=0;//赋初值为0int t=0;int num[10]={0,0,0,0,0,0,0,0,0,0};//每一列非0 的数目for(x=0;x<=99;x++){stu1[x].value=0;}for(int j=0;j<n;j++){for(int i=0;i<m;i++){if(a[i][j]!=0){num[j]++;t++;}}}int cpot[10]={0,0,0,0,0,0,0,0,0,0};cpot[0]=0;for(j=1;j<n;j++){cpot[j]=cpot[j-1]+num[j-1];}int col=0;int q=0;for(int k=0;k<t;k++){col=stu[k].j;q=cpot[col];stu1[q].i=stu[k].j;stu1[q].j=stu[k].i;stu1[q].value=stu[k].value;++cpot[col];}}void display1(){int x=0;printf(" 转置以后的三元组为 :\n");for(x=0;x<=99;x++){if(stu1[x].value==0) break;printf("{%d,%d,%d} ",stu1[x].i,stu1[x].j,stu1[x].value);}printf("\n");}void display2(){int d,b;for(d=0;d<m;d++){for(b=0;b<m;b++){printf("%d ",a[d][b]);}printf("\n");}}void main(){display2();if(jiance()==1){yasuo();display();zhuanzhi();display1();}}图 1：压缩转置程序运行结果矩阵的乘法程序：#include<stdio.h>#define m13#define n14#define m24#define n22int a1[m1][n1]={{3,0,0,5},{0,-1,0,0},{2,0,0,0},};int a2[m2][n2]={{0,2},{1,0},{-2,4},{0,0},};struct three1{int i,j;int value;};struct three1 stu1[100];struct three2{int i,j;int value;};struct three2 stu2[100];struct three3{int i,j;int value;};struct three3 stu3[100];int ar1pos[m1]={0};int ar2pos[m2]={0};int Qrpos[m1];int yasuo1(){int t=0;ar1pos[0]=0;for(int r=0;r<m1;r++){for(int c=0;c<n1;c++){if(a1[r][c]!=0){stu1[t].i=r;stu1[t].j=c;stu1[t].value=a1[r][c];t++;}}ar1pos[r+1]=t;}return t;}int yasuo2(){int t=0;ar2pos[0]=0;for(int r=0;r<m2;r++){for(int c=0;c<n2;c++){if(a2[r][c]!=0){stu2[t].i=r;stu2[t].j=c;stu2[t].value=a2[r][c];t++;}}ar2pos[r+1]=t;}return t;}void chengfa(int x1,int x2){int a1m=0;int a2m=0;int tp,p,br,t,q,ccol;int qtu=0;for(a1m=0;a1m<m1;a1m++){int ctemp[m1]={0};if(a1m<(m1-1))tp=ar1pos[a1m+1];else{tp=x1;}for(p=ar1pos[a1m];p<tp;++p){br=stu1[p].j;if(br<(m2-1))t=ar2pos[br+1];else{t=x2;}for(q=ar2pos[br];q<t;++q){ccol=stu2[q].j;ctemp[ccol]+=stu1[p].value*stu2[q].value;}}for(ccol=0;ccol<n2;++ccol)if(ctemp[ccol]!=0){stu3[qtu].i=a1m;stu3[qtu].j=ccol;stu3[qtu].value=ctemp[ccol];++qtu;}}}void display(){int x=0;printf("a1与 a2 乘积之后的三元组是： \n");for(x=0;x<=99;x++){if(stu3[x].value==0) break;printf("{%d,%d,%d} ",stu3[x].i,stu3[x].j,stu3[x].value);}printf("\n");}void display1(){int m,n;printf("a1矩阵为： \n");for(m=0;m<m1;m++){for(n=0;n<n1;n++){printf("%d ",a1[m][n]);}printf("\n");}printf("a2矩阵为： \n");for(m=0;m<m2;m++){for(n=0;n<n2;n++){printf("%d ",a2[m][n]);}printf("\n");}}void main(){int a;int x1,x2;display1();x1=yasuo1();x2=yasuo2();chengfa(x1,x2);display();}图 2：矩阵的乘法程序程序运行结果。