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

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

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

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

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

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

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

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

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

稀疏矩阵压缩存储方法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）格式等。

《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.4.24一、实验题目实验5 稀疏矩阵的转置二、实验目的1. 稀疏矩阵的压缩存储方法2. 掌握稀疏矩阵的转置算法三、算法设计分析（一）实验内容1.从键盘输入数据，建立稀疏矩阵的三元组顺序存储2.实现稀疏矩阵的转置算法3.输出原矩阵及转置后的矩阵4．实现矩阵的快速转置算法（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。

例如：①创建稀疏矩阵函数②转置矩阵T函数③快速转置函数④输出函数⑤输出原矩阵和转置函数其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能Status main()（2）①创建稀疏矩阵函数Status CreateSMatrix(TSMatrix &M){printf("请输入原矩阵：\n");printf("行数、列数：");scanf("%d%d", &M.mu, &M.nu);printf("元素总数：");scanf("%d", &M.tu);printf("输入各个对应压缩值：\n");for (int i = 1; i <= M.tu; ++i)scanf("%d%d%d", &M.data[i].i, &M.data[i].j, &M.data[i].e); return OK;}②转置矩阵T函数Status TransposeSMatrix(TSMatrix M, TSMatrix &T){ int p, q, col;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;}}printf("\n\n稀疏矩阵M转置成功。

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

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

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

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

例如，对于一个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.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

§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 。

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

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

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

在许多科学计算和⼯程应⽤中，经常要⽤到矩阵的概念，我们⽤的最多的其实就是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.对称压缩算法对称压缩算法（Symmetric Compressions）是一种利用矩阵的对称性质来压缩数据的算法。

对称矩阵是它本身的转置，因此可以将其上三角和下三角存储在一起，从而可以使用对称压缩算法将其压缩。

使用对称压缩算法可以将原始矩阵的存储需求减半。

3.小波变换压缩算法小波变换压缩算法（Wavelet Compressions）是一种利用小波变换来压缩数据的算法。

小波变换是一种将信号分解成各个不同频率的基本成分的数学方法。

可以使用小波变换压缩算法将信号分为不同的频带进行处理，并将每个频带中的系数进行压缩。

4.奇异值分解压缩算法奇异值分解压缩算法（Singular Value Decomposition，SVD）是一种利用奇异值分解来压缩数据的算法。

该算法将矩阵分解为三个不同的矩阵乘积的形式，其中每个矩阵的维数都较小。

使用奇异值分解压缩算法可以将原始矩阵的存储需求降低到很小的程度，并且可以在压缩后轻松地还原数据。

总的来说，矩阵压缩算法是一项非常有用的技术，可以帮助计算机科学家在处理大型数据集时节省存储空间和计算时间。

但是，每种压缩算法都有其优点和缺点，选择哪种算法取决于数据本身的特性和所需的精度。

实验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. 学习针对不同类型矩阵（对称矩阵、三角矩阵、稀疏矩阵）的压缩存储技术。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一、实验目的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 }。

实验报告五特殊矩阵和广义表的存储和运算班级：姓名：学号：专业：一、实验目的：1、了解多维数组的存储方式和存取特点2、熟悉稀疏矩阵的存储方式3、用三元组法实现稀疏矩阵的相、减、转置算法。

二、实验内容：1、在矩阵类Matrix中，增加下列操作：1)判断一个矩阵是否为上（下）三角矩阵、对称矩阵。

2)判断两个矩阵是否相等。

3)计算两个矩阵的乘积。

算法原代码：public class Matrix {private int[][] matrix;private int row;private int column;public Matrix(int[][] matrix){row = matrix.length;column = matrix[0].length;this.matrix = new int[row][column];for(int i=0;i<matrix.length;i++){for(int j=0;j<matrix[i].length;j++){this.matrix[i][j] = matrix[i][j];}}}public Matrix(int row, int column){this.row = row;this.column = column;matrix = new int[row][column];}/*** 判断上三角* @param matrix* @return*/public static boolean isUpTri(Matrix matrix){if(matrix.column!=matrix.row){throw new IllegalArgumentException("矩阵的行列不相等");}for(int i=0;i<matrix.getRow();i++){for(int j=i+1;j<matrix.getColumn();j++){if(0 == matrix.getElement(i, j)){return false;}}}return true;}/*** 判断下三角* @param matrix* @return*/public static boolean isDownTri(Matrix matrix){//先判断行列相不相等if(matrix.column!=matrix.row){throw new IllegalArgumentException("矩阵的行列不相等");}for(int j=0;j<matrix.getColumn();j++){for(int i=j+1;i<matrix.getColumn();i++){if(matrix.getElement(i,j)==0){return false;}}}return true;}/*** 判断matrix是不是对称矩阵* @param matrix* @return*/public static boolean isSymmetry(Matrix matrix){for(int i=0;i<matrix.getRow();i++){for(int j=i+1;j<matrix.getColumn();j++){if(matrix.getElement(i,j) != matrix.getElement(j,i)){return false;}}return true;}/*** 判断两个矩阵是否相等* @param matrix1* @param matrix2* @return*/public static boolean equals(Matrix matrix1, Matrix matrix2){if(matrix1.getRow()!=matrix2.getRow()||matrix1.getColumn()!=matrix2.getColumn()){ return false;}for(int i=0;i<matrix1.row;i++){for(int j=0;j<matrix1.column;j++){if(matrix1.getElement(i,j)!=matrix2.getElement(i,j)){return false;}}return true;}/*** 将两个矩阵相乘* @param TemPMatrix* @return*/public Matrix multiply(Matrix TemPMatrix) {if(column!=TemPMatrix.row){throw new IllegalArgumentException("行列不匹配，两个矩阵无法相乘");}Matrix matrix1 = new Matrix(row,TemPMatrix.column);for(int i=0;i<matrix1.row;i++){for(int j=0;j<matrix1.column;j++){int sum = 0;for(int k=0;k<column;k++){sum += (this.matrix[i][k])*(TemPMatrix.getElement(k,j));}matrix1.setElement(i,j,sum);}}return matrix1;}/*** 两个矩阵相加* @param matrix* @return*/public Matrix plus(Matrix matrix){if(row!=matrix.getRow()&&column!=matrix.getColumn()){throw new IllegalArgumentException("行列不匹配");}int[][] tempMatrix = new int[row][column];for(int i=0;i<row;i++){for(int j=0;j<column;j++){tempMatrix[i][j] = this.matrix[i][j]+ matrix.getElement(i,j);}}return new Matrix(tempMatrix);}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Matrix matrix1 = (Matrix) o;if (row != matrix1.row) return false;if (column != matrix1.column) return false;return Arrays.deepEquals(matrix, matrix1.matrix);}public void setElement(int row, int column, int element){matrix[row][column] = element;}public int getElement(int row, int column){ return matrix[row][column];}public int getRow() {return row;}public int getColumn() {return column;}@Overridepublic String toString() {String string = new String();for(int i=0;i<row;i++){for(int j=0;j<column;j++){string += matrix[i][j]+" ";}string += "\n";}return string;}}public class Test {public static void main(String[] args) throws Exception {Matrix matrix1 = new Matrix(newint[][]{{1,0,0,0,0},{1,2,0,0,0},{1,2,3,0,0},{1,2,3,4,0},{1,2,3,4,5}});Matrix matrix2 = new Matrix(newint[][]{{1,2,3,4,5},{0,2,3,4,5},{0,0,3,4,5},{0,0,0,4,5},{0,0,0,0,5}});Matrix matrix3 = new Matrix(newint[][]{{1,2,3,4,5},{2,1,6,7,8},{3,6,1,9,10},{4,7,9,1,11},{5,8,10,11,1}});Matrix matrix4 = new Matrix(newint[][]{{1,0,0,0,0},{1,2,0,0,0},{1,2,3,0,0},{1,2,3,4,0},{1,2,3,4,5}});System.out.println(matrix1);System.out.println(matrix2);System.out.println("matrix1是否是上三角:"+Matrix.isUpTri(matrix1));System.out.println("matrix2是否是上三角:"+Matrix.isUpTri(matrix2));System.out.println("matrix1是否是下三角:"+Matrix.isDownTri(matrix1));System.out.println("matrix2是否是下三角:"+Matrix.isDownTri(matrix2));System.out.println("matrix3是否是对称矩阵"+Matrix.isSymmetry(matrix3));System.out.println("matrix2是否是对称矩阵"+Matrix.isSymmetry(matrix2));System.out.println("matrix1是否等于matrix2:"+matrix1.equals(matrix2));System.out.println("matrix1是否等于matrix4:"+matrix1.equals(matrix4));System.out.println();System.out.println("matrix1*matrix2");System.out.println(matrix1.multiply(matrix2));}}测试结果如下：2、在三元组行的单链表表示的稀疏矩阵类LinkedMatrix中，增加判断矩阵相等、判断对称矩阵、计算矩阵乘积等操作。

1.课程设计的目的(1> 熟练使用 C ++语言编写程序，解决实际问题。

(2> 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。

(3> 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

(4> 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

2.需求分析问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。

基本要求：1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。

2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。

特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。

最常见的特殊矩阵有对称矩阵、上(下>三角矩阵、对角矩阵等。

b5E2RGbCAP 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。

p1EanqFDPw3.矩阵的压缩与解压缩问题的设计图1-14.调试分析图1-2程序运行界面图1-3 程序运行界面图1-4 文件的输入5.小结经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。

以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！DXDiTa9E3d6、参考文献[1]严蔚敏，吴伟民编著. 数据结构(C 语言版>--北京: 清华大学出版社，2007.2[2]严蔚敏，吴伟民M宁编著. 数据结构题集(C 语言版>--北京: 清华大学出版社，2007.3[3]网上搜索相关程序作为参考附录：#include <iostream>#include<fstream>using namespace std。

实验：矩阵的压缩存储及相关操作一、实验目的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。

实验报告课程名：数据结构（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］。