下载文档原格式
数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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。
稀疏刚度矩阵存储稀疏刚度矩阵存储是一种在计算机科学和工程领域中常用的数据结构，用于有效地存储大规模稀疏矩阵的信息。
稀疏矩阵是指大部分元素为零的矩阵，而稀疏刚度矩阵则是在有限元分析等工程领域中常见的一种特殊矩阵，用于描述结构体系的刚度信息。
在实际工程计算中，由于稀疏刚度矩阵的特殊性，采用传统的存储方式会造成大量的存储空间浪费，而且会增加计算的复杂度和时间。
因此，研究者们提出了一种更加高效的稀疏矩阵存储方法，即稀疏刚度矩阵存储。
稀疏刚度矩阵存储的核心思想是只存储矩阵中非零元素的信息，通过记录非零元素的位置和数值，避免了存储大量冗余的零元素，从而节省了存储空间。
同时，稀疏矩阵存储方法还可以提高计算效率，因为在进行矩阵运算时，只需要考虑非零元素的计算，而无需关注零元素。
常见的稀疏刚度矩阵存储方法包括压缩稀疏行存储（Compressed Sparse Row, CSR）、压缩稀疏列存储（Compressed Sparse Column, CSC）和双重压缩稀疏矩阵存储（Compressed Row Storage, CRS）等。
这些存储方法在存储矩阵的非零元素时，采用不同的方式来组织和存储数据，以便更加高效地进行矩阵运算和计算。
在实际工程计算中，稀疏刚度矩阵存储方法被广泛应用于有限元分析、计算流体力学、结构优化等领域。
通过合理选择和使用稀疏矩阵存储方法，工程师和研究者们可以有效地提高计算效率，节约存储空间，从而更好地完成复杂结构体系的计算和分析工作。
总的来说，稀疏刚度矩阵存储是一种重要的数据存储方法，可以在工程计算和科学研究中发挥重要作用。
通过深入研究和应用稀疏矩阵存储方法，可以更好地解决大规模稀疏矩阵存储和计算的问题，为工程和科研工作提供更加有效的支持。
稀疏矩阵存储和操作稀疏矩阵的数据结构与算法稀疏矩阵是指具有大量零元素和少量非零元素的矩阵。
在实际场景中，由于矩阵中大部分元素为零，传统的矩阵存储方式会造成大量的存储空间的浪费以及数据操作的低效性。
因此，为了节省存储空间和提高数据操作的效率，稀疏矩阵的存储和操作需要借助于特定的数据结构和算法。
一、稀疏矩阵存储的数据结构1.1. 压缩存储方法压缩存储方法是一种常用的稀疏矩阵存储方法。
常见的压缩存储方法有三种：行压缩法（CSR）、列压缩法（CSC）和十字链表法。
1.1.1. 行压缩法（CSR）行压缩法是通过两个数组来存储稀疏矩阵的非零元素。
第一个数组存储非零元素的值，第二个数组存储非零元素在矩阵中的位置信息。
1.1.2. 列压缩法（CSC）列压缩法与行压缩法相似，只是存储方式不同。
列压缩法是通过两个数组来存储稀疏矩阵的非零元素。
第一个数组存储非零元素的值，第二个数组存储非零元素在矩阵中的位置信息。
1.1.3. 十字链表法十字链表法是一种更加灵活的稀疏矩阵存储方法。
通过使用链表的方式，将非零元素存储在链表中，并且每个非零元素还具有行和列的指针，方便进行数据操作。
1.2. 坐标存储法坐标存储法是一种简单直观的稀疏矩阵存储方法。
每个非零元素包括行列坐标和元素值，通过三元组的方式进行存储。
二、稀疏矩阵的操作算法2.1. 矩阵转置矩阵转置是指将原矩阵的行变为列，列变为行的操作。
对于稀疏矩阵，常用的转置算法为快速转置算法。
该算法通过统计每列非零元素的个数，并根据列的非零元素个数确定每个非零元素转置后的位置。
2.2. 矩阵相加矩阵相加是指将两个矩阵对应位置上的元素相加得到一个新的矩阵。
对于稀疏矩阵的相加，可以遍历两个矩阵的非零元素，对相同位置上的元素进行相加。
2.3. 矩阵相乘矩阵相乘是指将两个矩阵相乘得到一个新的矩阵。
对于稀疏矩阵的相乘，常用的算法为稀疏矩阵乘法算法。
该算法通过遍历两个矩阵的非零元素，按照矩阵乘法的规则计算得到新矩阵的非零元素。
稀疏矩阵压缩的存储方法是稀疏矩阵压缩是一种数据结构，可以有效地占用存储空间，合理地存储稀疏矩阵。
通常来说，稀疏矩阵的元素大部分为0，只有少部分非零，所以采用压缩存储方法可以大大减少存储空间的使用。
稀疏矩阵的压缩存储方法有三种：顺序表压缩、链表压缩和十字链表压缩。
下面将对这三种方法进行详细介绍。
1.顺序表压缩方法：顺序表压缩方法是使用一个一维数组来存储稀疏矩阵。
数组的第一行存储矩阵的行数、列数、非零元素的个数。
数组的后续元素按行优先顺序存储矩阵的每一个非零元素。
例如，对于一个3*3的稀疏矩阵：1 0 00 0 23 0 0它的顺序表压缩形式为：3 3 2 第一行分别为行数、列数和非零元素个数1 1 1 第1个非零元素在第1行第1列，值为12 3 2 第2个非零元素在第2行第3列，值为23 1 3 第3个非零元素在第3行第1列，值为3在这个例子中，非零元素的个数为3，而原先需要占据9个空间的矩阵，现在只需要使用7个元素的数组就可以存储。
2.链表压缩方法：链表压缩方法首先将稀疏矩阵存储在单链表中。
单链表中的每一个节点包含4个数据域：行数，列数，元素值和指针域。
其中，指针域指向下一个非零元素节点。
例如，对于一个5*5的稀疏矩阵：0 0 0 0 03 0 0 0 00 0 1 0 00 0 0 2 00 0 0 0 0它的链表表示形式如下：(1,2,3)->(2,1,3)->(3,3,1)->(4,4,2)其中，每个元素依次表示行数、列数和元素值。
指针域则指向下一个非零元素。
相对于顺序表压缩，链表压缩更适用于稀疏矩阵比较大时，且存在大量的非零元素。
因为链表压缩能够动态分配存储空间，可以严格掌控存储空间的使用效率。
3.十字链表压缩方法：十字链表压缩是一种特殊的链表压缩方式，因为它在存储矩阵的同时，能够比较直观地表示矩阵的结构信息。
下面是一个矩阵以十字链表方式存储的示例：首先，将矩阵按行、列分别建立链表。
题目：一维数组A采用顺序存储结构，每个元素占用4个字节，第8个元素的存储地址为120，则该数组的首地址是（）。
选项A：88选项B：92选项C：32选项D：90答案：92题目：稀疏矩阵采用压缩存储的目的主要是（）。
选项A：减少不必要的存储空间的开销选项B：表达变得简单选项C：去掉矩阵中的多余元素选项D：对矩阵元素的存取变得简单答案：减少不必要的存储空间的开销题目：一个非空广义表的表头（）。
选项A：不可能是原子选项B：只能是原子选项C：可以是子表或原子选项D：只能是子表答案：可以是子表或原子题目：常对数组进行的两种基本操作是（）。
选项A：建立与删除选项B：查找与索引选项C：查找和修改选项D：索引与、和修改答案：查找和修改题目：在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。
选项A：80选项B：270选项C：100选项D：240答案：240题目：设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A10,8在一维数组B中的下标是（）。
选项A：58选项B：18选项C：45选项D：53答案：53题目：广义表((a))的表尾是（）。
选项A：(a)选项B：0选项C：((a))选项D：a答案：0题目：设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。
选项A：41选项B：85选项C：32选项D：33答案：33题目：设广义表类（(a,b,c)），则L的长度和深度分别为（）。
选项A：1和3选项B：1和1选项C：2和3选项D：1和2答案：1和2题目：广义表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表头是________。
稀疏矩阵及其压缩存储方法1.基本概念稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。
设m行n列的矩阵含t个非零元素，则称以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。
特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。
如下三角阵、三对角阵、稀疏矩阵。
压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。
目的是节省大量存储空间。
n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。
2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构）三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。
它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。
当矩阵中的非0元素少于1/3时即可节省存储空间。
（1）稀疏矩阵的三元组顺序表存储表示方法#define MAXSIZE 12500 // 假设非零元个数的最大值为12500typedef struct {int i, j; // 该非零元的行下标和列下标ElemType e; //非零元素的值} Triple; // 三元组类型typedef union { //共用体Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用int mu, nu, tu; // 矩阵的行数、列数和非零元个数} TSMatrix; // 稀疏矩阵类型（2）求转置矩阵的操作◆用常规的二维数组表示时的算法for (col=1; col<=nu; ++col)for (row=1; row<=mu; ++row)T[col][row] = M[row][col];其时间复杂度为: O(mu×nu)◆用三元组顺序表表示时的快速转置算法Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵TT.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];// 求M 中每一列所含非零元的个数cpot[1] = 1;for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1];// 求M 中每一列的第一个非零元在b.data 中的序号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];} // for} // ifreturn OK;} // FastTransposeSMatrix其时间复杂度为: O(mu +nu)3.行逻辑联接的顺序表——压缩存储稀疏矩阵方法之二（链接存储结构）行逻辑联接的顺序表：稀疏矩阵中为了随机存取任意一行的非0元素，需要知道每一行的第一个非0元素在三元组表中的位置，因此将上述快速转置算法中指示行信息的辅助数组cpot 固定在稀疏矩阵的存储结构中，让每一行对应一个单链表，每个单链表都有一个表头指针，这种“带行链接信息”的三元组表即称为行逻辑联接的顺序表。
稀疏矩阵的特征稀疏矩阵是指矩阵中大部分元素为零的矩阵。
相对于密集矩阵，稀疏矩阵在存储和计算上具有很大的优势。
稀疏矩阵的特征主要包括稀疏度、存储格式以及稀疏矩阵的运算。
一、稀疏度稀疏度是指矩阵中非零元素的比例。
稀疏度越高，矩阵中的非零元素越少，矩阵越稀疏。
稀疏度可以用非零元素个数与矩阵总元素个数的比值来表示。
对于一个n×n的矩阵，如果非零元素的个数为m，则稀疏度为m/(n×n)。
稀疏度的高低直接影响着存储和计算的效率。
当稀疏度很高时，矩阵中的零元素占据了很大一部分，此时可以通过合理的存储格式来减少存储空间的占用，提高存储效率。
同时，在进行矩阵运算时，可以通过跳过大量的零元素来减少计算量，提高计算效率。
二、存储格式稀疏矩阵的存储格式有多种，常见的有压缩稀疏矩阵（Compressed Sparse Matrix，简称CSR）、坐标存储法（Coordinate Storage，简称COO）和对角线存储法（Diagonal Storage，简称DIA）等。
1. 压缩稀疏矩阵（CSR）是一种广泛应用的存储格式。
它将矩阵分为三个部分：非零元素数组、行偏移数组和列索引数组。
非零元素数组存储矩阵中的非零元素，行偏移数组记录每一行的非零元素在非零元素数组中的起始位置，列索引数组记录每个非零元素所在的列号。
2. 坐标存储法（COO）是最简单的存储格式之一。
它将矩阵中的每个非零元素存储为一个三元组，包括元素的行号、列号和值。
COO 格式适用于非结构化的稀疏矩阵。
3. 对角线存储法（DIA）适用于具有大量对角线元素的稀疏矩阵。
它将矩阵中的每个对角线存储为一个数组，数组的长度为对角线元素的个数，每个元素对应一个对角线的偏移量。
不同的存储格式适用于不同的稀疏矩阵，选择合适的存储格式可以提高存储效率和计算效率。
三、稀疏矩阵的运算稀疏矩阵的运算包括加法、减法、乘法等。
在进行矩阵运算时，由于稀疏矩阵的特殊性，可以通过跳过大量的零元素来减少计算量，提高运算效率。
第3讲 稀疏矩阵压缩存储上——教学讲义
稀疏矩阵是指矩阵中大多数元素为零的矩阵。
从直观上讲，当非零元素个数低于总元素的30 %时,这样的矩阵为稀疏矩阵。
如下图所示的矩阵M 、 N 中,非零元素个数均为8个,矩阵元素总数均为6 ×7 =42 ,显然8 /42 <30 %,所以M 、 N 都是稀疏矩阵。
1 稀疏矩阵的三元组表表示法 ( 1 ) 稀疏矩阵的三元组存储表示
对于稀疏矩阵的压缩存储,采取只存储非零元素的方法。
由于稀疏矩阵中非零元素aij 的分布没有规律 ,因此,要求在存储非零元素值的同时还必须存储该非零元素在矩阵中所处的行号和列号的位置信息,这就是稀疏矩阵的三元组表表示法。
每个非零元素在一维数组中的表示形式如下图所示。
说明:为处理方便,将稀疏矩阵中非零元素对应的三元组按“行序为主序”用一维结构体数组进行存放,将矩阵的每一行(行由小到大)的全部非零元素的三元组按列号递增存放。
由此得到矩阵M 、 N 的三元组表A 和B 。
如下图所示。
0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0
M=
6×7 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0
0 0 0 0 -7 0 0 0 0 0 0 0
0 14 0 0 0 0
0 0 0 0 0
7×6
N= 稀疏矩阵M 和N
三元组的结构
( 2 )稀疏矩阵三元组表的类型定义 稀疏矩阵三元组表类型定义如下:
#define MAXSIZE 1000 /*设非零元素的个数最多为1000*/ typedef struct { int row, col; /*该非零元素的行下标和列下标*/ ElementType e ； /*该非零元素的值*/ }Triple; typedef struct
{ Triple data[MAXSIZE+1]; /* 非零元素的三元组表。
data[0]未用*/ int m, n, len; /*矩阵的行数、列数和非零元素的个数*/ }TSMatrix ；
在稀疏矩阵情况下，采用三元组表表示法大量节约了存储空间,以图5.10中的M 6*7矩阵为例，需要6*7=42个存储单元，但M 采用三元组表A 存放，共有8个非零元素,每个非零元按占3个单元计算，需要3*8=24个单元，显然比矩阵常规存储来讲还是大大节省存储。
( 3 )三元组表实现稀疏矩阵的转置运算
需要强调的是，矩阵常规存储是二维的，而三元组存储是一维的，由于矩阵存储结构的变化也带来了运算方法的不同，必需认真分析。
下面给出稀疏矩阵的转置运算问题，希望从中体会实现算法的处理思路和改进算法的技术。
矩阵转置指变换元素的位置,把位于( row,col)位置上的元素换到( col,row)位置上,把元素的行列互换。
如图5 .10的6 ×7矩阵M,它的转置矩阵就是7×6的矩阵N,并且N( row,col)= M( col,row),其中,1 ≤ row ≤ 7 ,1 ≤ col ≤ 6 。
①矩阵转置的经典算法
采用矩阵的正常存储方式(二维数组)实现矩阵转置。
稀疏矩阵转置经典算法
void TransMatrix （ElementType source[m][n], ElementType dest[n][m]）
{/*source 和dest 分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/ int i, j;
for(i=0;i<m;i++) for (j=0;j< n;j++)
dest[j][ i]=source[i] [j] ;
}
下标
行号 列号 元素值 1 1 2 12 2 1 3 9 3 3 1 -3 4 3 6 14 5 4 3 24 6 5 2 18 7 6 1 15 8 6
4
-7
下标 行号 列号 元素值
1 1 3 3
2 1 6 15
3 2 1 12
4 2
5 18 5 3 1 9
6 3 4 24
7 4 6 -7 8
6
3
14
（a ）矩阵M 的三元组表A
（b ）矩阵N 的三元组表B
稀疏矩阵M 和N 的三元组表表示
②三元组表实现稀疏矩阵的转置
假设A 和B 是稀疏矩阵source 和dest 的三元组表,实现转置的简单方法如下。
a.矩阵source 的三元组表A 的行、列互换就可 以得到B 中的元素,如下图所示。
b.如a 操作,转置后矩阵的三元组表B 中的三元组不是以“行序为主序”进行存放,为保证转置后的矩阵的三元组表B 也是以“行序为主序”进行存放,则需要对行、列互换后的三元组B 按B 的行下标(即A 的列下标)按递增有序进行重新排序,如下图所示。
由此可知,步骤a 很容易实现,但步骤b 重新排序势必会大量移动元素,从而影响算法的效率。
为了避免上述简单转置算法中行、列互换后重新排序引起的元素移动,可以采取以下两种处理方法。
方法一:“列序”递增转置法
【算法思想】采用按照“被转置矩阵”三元组表A 的“列序”(即转置后三元组表B 的行序)递增的顺序进行转置,并依次送入转置后矩阵的三元组表B 中,这样一来,转置后矩阵的三元组表B 恰好是以“行序为主序”。
【具体做法】
如下图所示,找出第1行全部元素:第一遍从头至尾扫描三元组表A,找出其中所有col =1的三元组,转置后按顺序送到三元组表B 中;
row col e 1 1 2 12 2 1 3 9 3 3 1 -3 4 3 6 14 5 4 3 24 6 5 2 18 7 6 1 15 8 6 4 -7 矩阵的转置（用三元组表示矩阵） B （row ，col ，e ）————（col ，row ，e ）
A
从头至尾扫描三元组表A,寻找col 值为k 的三元组进行转置
找出第2行全部元素:第二遍从头至尾扫描三元组表A,找出其中所有col =2的三元 组,转置后按顺序送到三元组表B 中;
如此类推……
找出第k 行全部元素:第k 遍扫描三元组表A,找出其中所有col =k 的三元组,转置后按顺序送到三元组表B 中。
k 的含义:每次扫描三元组表时,寻找的三元组的列值col=k 的三元组; k 的取值: 1 ≤ k ≤ A.n 。
为实现处理附设一个当前存放位置计数器j,用于指向当前转置后元素应放入三元组表B 中的位置下标。
j 初值为1 ,当处理完一个元素后,j 加1 。
【算法描述】 稀疏矩阵“列序”递增转置算法
void TransposeTSMatrix(TSMatrix A, TSMatrix * B)
{ /*把矩阵A 转置到B 所指向的矩阵中去。
矩阵用三元组表表示*/ int i , j, k ;
B->m= A.n ; B->n= A.m ; B->len= A.len ; if(B->len>0) { j=1; /*j 为辅助计数器，记录转置后的三元组在三元组表B 中的下标值*/
for(k=1; k<=A.n; k++) /*扫描三元组表A 共A.n 次，每次寻找列值为k 的三元组进行转
置*/
for(i=1; i<=A.len; i++) if(A.data[i].col==k) { B->data[j].row=A.data[i].col; B->data[j].col=A.data[i].row;
B->data[j].e=A.data[i].e;
j++;
/*计数器j 加1，指向本行下一 个转置后元素的位置下标*/
}/*内循环中if 的结束*/ }/* if(B->len>0)的结束*/ }/* end of TransposeTSMatrix */
（a） 三元组表A
（b）三元组表B
row col e 1 1 2 12 2 1 3 9 3 3 1 -3 4 3 6 14 5 4 3 24 6 5 2 18 7 6 1 15 8 6
4
-7
矩阵的转置示意
【算法分析】算法的时间耗费主要是在双重循环中,其时间复杂度为O( A.n×A.len)。
最坏情况为:当A.len=A.m×A.n时(即矩阵中全部是非零元素),时间复杂度为O( A.m×A.n2 ),若采用正常方式经典算法实现矩阵转置的算法时间复杂度为O( A.m×A.n)。
因此,三元组表示法仅适用于存储表示稀疏矩阵。
例5-2 已知A矩阵A.m=100 ,A.n=500 ,A.len=100 ,计算其采用三元组表存储空间和其上的“列序递增转置法”占用时间情况，并给出对比改进的思路分析。
此矩阵常规存储空间耗费为A.m×A. n=50000，三元组表存储耗费为A.len×3=300，节省存储。
采用矩阵转置的经典算法时间耗费为A.m×A. n=50000次;采用稀疏矩阵的“列序”递增转置算法，时间耗费为A.n×A.len=50000次，虽然存储空间减少，但时间复杂度并未降低，原因是要多次（如A.n=500次）扫描稀疏矩阵三元组。
