下载文档原格式
矩阵压缩存储矩阵是在计算机科学和数学中常见的数据结构，用于表示具有行和列的二维数据。
在很多应用中，矩阵的大小可能非常大，占用大量的存储空间。
为了节省存储空间并提高计算效率，在某些情况下可以使用矩阵压缩存储技术。
什么是矩阵压缩存储？矩阵压缩存储是一种将稀疏矩阵（其中大部分元素为零）以更紧凑形式表示的技术。
通过只存储非零元素及其位置，可以显著减少所需的存储空间。
稀疏矩阵稀疏矩阵是指其中大部分元素为零的矩阵。
在实际应用中，很多情况下只有少数元素非零，例如图像处理、网络分析、自然语言处理等领域。
对于这些稀疏矩阵，传统的二维数组表示方法会浪费大量的存储空间。
稀疏矩阵压缩存储方法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）是一种利用奇异值分解来压缩数据的算法。
该算法将矩阵分解为三个不同的矩阵乘积的形式，其中每个矩阵的维数都较小。
使用奇异值分解压缩算法可以将原始矩阵的存储需求降低到很小的程度，并且可以在压缩后轻松地还原数据。
总的来说，矩阵压缩算法是一项非常有用的技术，可以帮助计算机科学家在处理大型数据集时节省存储空间和计算时间。
但是，每种压缩算法都有其优点和缺点，选择哪种算法取决于数据本身的特性和所需的精度。
数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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。
图5-3 三对角矩阵A与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。
a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1k= 0 1 2 3 4 …3n-3 3n-2图5-4下三角矩阵的压缩存储A中的一对下标(i,j)与ma中的下标k之间有如下的关系：公式中采用了C语言的符号，int()表示取整，‘%’表示求余。
二、稀疏矩阵在m×n的矩阵中，有t个非零元。
令δ=,称δ矩阵的稀疏因子，常认为δ≤0.05时称为稀疏矩阵。
稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。
如何进行稀疏矩阵的压缩存储呢？为节省存储空间，应只存储非零元素。
除了存储非零元的值之外，还必须记下所在行和列的位置（i,j），即一个三元组（i,j, ）唯一确定了矩阵A的一个非零元素。
1. 三元组顺序表以顺序存储结构来表示三元组表，则可称稀疏矩阵的一种压缩存储方式。
//稀疏矩阵的三元组顺序表存储表示。
#define MaxSize 10 //用户自定义typedef int Datatype; //用户自定义typedef struct{ //定义三元组int i； //非零元的行下标int j; //非零元的列下标Datatype v; //非零元的数据值}TriTupleNode;typedef struct{TriTupleNode data[MaxSize]; //非零元的三元组表int m,n,t; //矩阵行，列及三元组表长度}TriTupleTable;2. 十字链表当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表，采用纵横交叉的十字链表就比较好。
在十字链表中，每个非零元可用一个含五个域的结点表示，其中i, j和e三个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行中下一个非零元。
向下域down用以链接同一列中下一个非零元。
同一行中的非零元通过right域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，如图5-5所示。
图5-5 稀疏矩阵M的十字链表typedef int Datatype; //用户自定义typedef struct OLNode{int i,j; //该非零元的行和列下标Datatype v;Struct OLNode *right,*down //该非零元所在行表和列表的后继链域}OLNode;*OLink;typedef struct {OLink *rhead,*cheadint mu,nu,tu;}CrossList;第二节用三元组表实现稀疏矩阵的基本操作【问题描述】用三元组表实现稀疏矩阵的按列转置。
【数据描述】typedef int Datatype; //用户自定义typedef struct{ //定义三元组int i,j; // 非零元素的行下标和列下标Datatype v;}TriTupleNode;typedef struct{ //定义三元组表TriTupleNode data[MaxSize];int m,n,t; //矩阵行，列及三元组表长度}TriTupleTable;【算法描述】按照列序来进行转置。
为了找到每一列中所有的非零元素，需要对其三元组表从第一行起整个扫描一遍。
Status TransposeSMatrix(TriTupleTable a, TriTupleTable &b){b.m=a.n;b.n=a.m;b.t=a.t;if(b.t){q=0;for(col=1;col<=a.n;++col)for(p=0;p<=a..t;++p)if(a.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;++q;}}return OK;}【C源程序】#include <stdio.h>#include <string.h>#define Ok 1#define Maxsize 10 //用户自定义三元组最大长度typedef struct{ /*定义三元组表*/int i，j;int v;}TriTupleNode;typedef struct{ /*定义三元组表*/ TriTupleNode data[Maxsize];int m;int n;int t; /*矩阵行，列及三元组表长度*/}TriTupleTable;void InitTriTupleNode (TriTupleTable *a){ /*输入三元组表*/ int i,j,k,val,maxrow,maxcol;char contiue;maxrow=0;maxcol=0;i=j=0;k=0;while(i!=-1&&j!=-1){ /*rol=-1&&col=-1结束输入*/printf("input row \n");scanf("%d",&i);printf("input col \n");scanf("%d",&j);printf("input value\n");scanf("%d",&val);a->data[k].i=i;a->data[k].j=j;a->data[k].v=val;if (maxrow<i) maxrow=i;if (maxcol<j) maxcol=j;k++;}a->m=maxrow;a->n=maxcol;a->t=k-1;}void showMatrix(TriTupleTable *a){ /*输出稀疏矩阵*/ int p,q;int t=0;for(p=1;p<=a->m;p++){for(q=1;q<=a->n;q++){ if (a->data[t].i==p&&a->data[t].j==q){printf("%d ",a->data[t].v);t++;}else printf("0 ");}printf("\n" );}}TransposeSMatrix(TriTupleTable *a,TriTupleTable *b) {int q,col,p;b->m=a->n;b->n=a->m;b->t=a->t;if(b->t){q=0;for(col=1;col<=a->n;++col)for(p=0;p<a->t;++p)if(a->data[p].j==col){ b->data[q].i=a->data[p].j;b->data[q].j=a->data[p].i;b->data[q].v=a->data[p].v;++q;}}}void main( void){TriTupleTable *a,*b;InitTriTupleNode(a);showMatrix(a); /*转置前*/TransposeSMatrix(a,b);showMatrix(b); /*转置后*/}【测试数据】输入：输出：1 2 0 0 1 4 04 3 0 7 2 3 00 0 0 8 0 0 00 7 8【说明】分析算法,主要的工作是在p和col的两重循环中完成，算法的时间复杂度为O(n*t)。
如果非零元素个数t和m*n同数量级时，算法的时间复杂度变为O(m*n2)。
【实验题】1. 稀疏矩阵按行序进行转置。
2. 两个稀疏矩阵的相加运算。
第三节十字链表表示稀疏矩阵的基本操作【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算【数据描述】typedef struct ele {/* 十字链表结点类型*/int row, col;double val;struct ele *right, *down;}eleNode;【算法描述】(1) 若q->j>v->j，则需要在C矩阵的链表中插入一个值为bij的结点,，修改v=v->right。
