线性链表2.4 数组

1、2.3 线性链表及其运算n线性表的顺序存储结构容易实现，可以随机存线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。取表中的任意元素。n顺序顺序表表缺点是：缺点是：n难于插入、删除操作；难于插入、删除操作；n需要预先分配空间，不管这些空间能否最大限度地需要预先分配空间，不管这些空间能否最大限度地利用。利用。n链表存储结构链表存储结构在这两个方面恰好是优点：在这两个方面恰好是优点：n容易插入、删除操作容易插入、删除操作n不需要预分空间。不需要预分空间。链表基本概念定义定义 ： 线性表的链式存储结构称为线性链表线性表的链式存储结构称为线性链表 结点（结点（NODE） ：表中元素的存储单元。

2、由数据域：表中元素的存储单元。由数据域和指针域组成。数据域存放元素数据，指针域存和指针域组成。数据域存放元素数据，指针域存放指向下一结点位置的指针。放指向下一结点位置的指针。结点形式为：结点形式为： data next数据域 指针域链表（链表（Link）：）：由结点组成的表。由结点组成的表。头指针（头指针（head）：）：指向链表中第指向链表中第1个结点的指针。个结点的指针。 举例n由食品组成的单链表由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam) grapesbiscuitbuttercheesejameggshead 头指针最后一个结点最后一

3、个结点指针域为空指针域为空单链表的物理存储 存储地址存储地址 数据域（数据域（data） 指针域（指针域（next）grapes 60biscuit 61cheese 13eggs 1jam NULLbutter 121111213606111头指针头指针 headheadl（biscuit,butter,cheese,eggs,grapes,jam)线性链表类 P57Template struct node T data ; node *next ; ;Template class linked_list private : node *head;public : linked_list()

4、; /建立空链表建立空链表 int flag_linked_list(); /判断链表状态判断链表状态 if(head = NULL )return 0; return 1; void prt_linked_list(); /从头指针开始输出从头指针开始输出 void ins_linked_list(T );/插入到链表头插入到链表头 T del_linked_list(); /删除链头删除链头参考参考P58课堂练习nP58 例子例子 2.12n定义一个空链表，依次插入定义一个空链表，依次插入1-100打印输出；然后删除前打印输出；然后删除前50个结点，并再次个结点，并再次输出。输出。 带链的

5、栈n栈也是线性表，可以采用链式存储结构栈也是线性表，可以采用链式存储结构n顺序栈最多可用于顺序栈最多可用于2个栈的共享，对于更多个栈的共享，对于更多的栈就难于表达了。的栈就难于表达了。n对于最大空间需要量事先不知的情况，就不对于最大空间需要量事先不知的情况，就不能使用顺序栈了。这时，就需要采用链栈。能使用顺序栈了。这时，就需要采用链栈。链栈：栈的链式存储结构链栈：栈的链式存储结构链栈示意图a1a2a3栈底栈底top栈顶栈顶.aiTemplate struct node T data ; node *next ; ;template class linked_Stack private: nod

6、e *top; /栈顶指针栈顶指针 栈的链式表示 链栈public:linked_stack();void prt_linked_stack ( ) ; int flag_linked_stack (); void ins_linked_stack (T); T del_linked_stack();T read_linked_stack(); n 链栈为空的条件：链栈为空的条件：n top = NULLn 链栈为满的条件链栈为满的条件(无法继续申请新结点无法继续申请新结点):n t = NULL nt 为申请的结点为申请的结点,为为NULL表示失败。表示失败。 链栈进栈操作操作步骤操作步骤:

7、nstep1 ：申请一个链栈结点，若：申请一个链栈结点，若t=NULL，则表示链满；否则，执行则表示链满；否则，执行step2 ；nstep2 ：在：在top所指结点之前插入新结点，所指结点之前插入新结点，并将并将top指向新申请的结点指向新申请的结点t。template void linked_Stack: ins_linked_stack (T x) node *p = new node ; if(p=NULL) return; p - data = x; p - next = top; top= p; 链栈进栈算法链栈出栈操作操作步骤操作步骤:nstep1 若链栈为空，则输出栈溢出信息；

8、否若链栈为空，则输出栈溢出信息；否则，执行则，执行step 2。nstep2 (保存保存top)并使并使top 指向被删除结点的指向被删除结点的后件结点，删除后件结点，删除top所指结点。所指结点。nstep 3 释放被删除结点的存储空间。返回出释放被删除结点的存储空间。返回出栈元素值。栈元素值。template T linked_Stack: del_linked_stack() T y ; node *q; if( top = = NULL ) cout“空栈空栈”data; top = q- next; delete q; return (y); 课堂练习nP62, 参考参考2.13;n

9、建立空栈，入栈建立空栈，入栈 10,20,30,40,50；n退栈退栈2次，然后输出栈中所有的元素；次，然后输出栈中所有的元素；4 带链的队列1). 队列也是线性表，可以采用链式存储结构。队列也是线性表，可以采用链式存储结构。data next数据域数据域 指针域指针域2). 存储结构的存储结构的C+ 语言描述，语言描述，template /模板声明，数据元素虚拟类型为模板声明，数据元素虚拟类型为T class linked_Queue /循环队列类循环队列类 private: /数据成员数据成员 int mm; /存储空间容量存储空间容量 node* front; /排头指针排头指针 nod

10、e * rear; /队尾指针队尾指针public: /成员函数成员函数linked_Queue(int); /构造函数，建立空循环队列构造函数，建立空循环队列 void prt_linked_Queue(); /输出排头与队尾指针以输出排头与队尾指针以及队中元素及队中元素int flag_linked_Queue(); /检测循环队列的状态检测循环队列的状态void ins_linked_Queue(T); /入队入队T del_linked_Queue(); ; /退队退队链队列为空的表示链队列为空链队列为空， Queue.front = Queue.rear 表示形式：表示形式： fro

11、nt rearfront rear . ana2a1链队满的条件为链队满的条件为: :T = NULLT = NULL。T T 为新创建的结点为新创建的结点, ,非空队列非空队列:NULL链队列的入队操作要求：要求：在链队列中插入一个元素在链队列中插入一个元素x x（入队运算）。（入队运算）。 算法操作步骤算法操作步骤: : Step1：申请建立一个新结点：申请建立一个新结点p；Step2：判别：判别p是否为空；若空，表示是否为空；若空，表示 队列已满；队列已满；Step3：非空，将：非空，将p插入链中，修改插入链中，修改rear指针。指针。template /入队入队T linked_Que

12、ue:ins_linked_Queue(T x) node *p; p = new node ; if (p=NULL) coutdada =x; p-next = NULL; if （ rear = = NULL） front =p; else rear - next =p; rear = p; return ; 链队列的出队操作出队操作要考虑两种情况出队操作要考虑两种情况:q当队列长度为当队列长度为1时，除了修改队头指针外，还要修时，除了修改队头指针外，还要修改队尾指针。改队尾指针。QueueQueueQueueQueuefrontrearrearfronta1 an a1a2 .a2 .

13、an q 当队列长度大于当队列长度大于1时时,只修改队头指针即可只修改队头指针即可QueueQueuean rearQueueQueuefrontrearTfrontNULL链队列的出队操作要求：要求：在链队列中删除一个元素（退队运在链队列中删除一个元素（退队运算）。算）。算法描述算法描述:Step1：判别队列是否为空；若空，则显示队：判别队列是否为空；若空，则显示队列列下溢下溢；Step2 ：非空，则判别队列长度是否为：非空，则判别队列长度是否为1； Step2.1：不为：不为1，修改头指针；，修改头指针； Step2.2：为：为1，则修改头、尾指针；，则修改头、尾指针；Step3：释放：释

14、放T。 template /出队出队T linked_Queue:del_linked_Queue() T y; node *q; if ( front = = NULL) coutdata; q=front; front = q-next; delete q; if (front = = NULL ) rear = NULL ; return(y);课堂练习nP65 例子例子 2.14 n建立空队列，插入建立空队列，插入1-100；n作作40次退队操作；次退队操作；n打印输出；打印输出；2.3.2 线性链表基本运算 1. 单链表的查找单链表的查找 find2. 单链表的的插入单链表的的插入i

15、nsert3. 单链表的删除单链表的删除delete 指针的基本操作n设指针变量设指针变量p、q的定义为：的定义为： NODE *p，*q；n对链表的操作实际上是对指针的操作。例如，对链表的操作实际上是对指针的操作。例如，要删除结点要删除结点ai，首先要使指针，首先要使指针p指向指向ai，即：，即：a1.headaianp指针指针p是存储单元的地址，地址内的内容可以通过是存储单元的地址，地址内的内容可以通过p-data得到，指向下个元素的指针用得到，指向下个元素的指针用p-next 得到得到 指针的基本操作列表np=（NODE*）malloc（sizeof（NODE） 申请一个结点空间，并将地

16、址送入申请一个结点空间，并将地址送入p中。中。nfree（p） 释放释放p指针所指结点的空间指针所指结点的空间np=q 指针指针p指向指针指向指针q所指的结点所指的结点np=q-next 指针指针p指向指针指向指针q所指结点的后件所指结点的后件np=p-next 指针指针p向后移动一个结点向后移动一个结点 np-next=q 将指针将指针q所指结点改接为指针所指结点改接为指针p所指结点所指结点 的后件的后件np-next=NULL 将指针将指针p所指结点与后件结点断开所指结点与后件结点断开 线性链表的查找算法要求：在头指针为要求：在头指针为HEADHEAD的非空线性链的非空线性链表中寻找包含元

17、素表中寻找包含元素x x的前一个结点的前一个结点p p 算法操作步骤算法操作步骤:nstep1 初始化初始化,指针指针p指向头指针指向头指针nstep2 p非空且非空且p指向的下一个元素指向的下一个元素不是不是x, 循环循环nstep3 每循环一次每循环一次,p后移一个位置后移一个位置nstep4 循环结束循环结束,返回指针返回指针p.template ListNode * List :Find ( T x ) p = head; /当前指针 p 指示第一个结点while ( p -next != NULL & (p-next)-data!= x ) p=p-next; return p; 返

18、回的指针返回的指针p要么是指向要么是指向x的前一个结点，的前一个结点，要么指向最后一个结点要么指向最后一个结点 线性链表插入算法要求：在头指针为要求：在头指针为HEADHEAD的线性链表中包含的线性链表中包含元素元素x x的结点之前插入新元素的结点之前插入新元素b b 算法操作步骤算法操作步骤:nstep1 找到找到x的位置的位置,使指针使指针p指向指向x的前的前一个结点；一个结点；nstep2 申请并生成新结点申请并生成新结点snstep3 使使s插入到插入到x所在结点之前所在结点之前 考虑几种特殊情况：空链表，首元素为考虑几种特殊情况：空链表，首元素为x template void lin

19、ked_llist:del_linked_llist(T x, T b) node *p,*q; p= new node ; p-data =b; if( head = NULL) head=p;p-next=NULL;return; if( head - dada = x) p-next =head;head=p;return; q =head; while(q-next !=NULL)&(q-next)-dada)!=x) q=q-next; p-next =q-next; q-next= p; return;对于空表和第一个结点处理必须单独考虑对于空表和第一个结点处理必须单独考虑（后面引

20、入头结点概念）（后面引入头结点概念） 线性链表删除算法要求：在头指针为要求：在头指针为HEADHEAD的线性链表中删除包含的线性链表中删除包含元素元素x x的结点。的结点。算法操作步骤算法操作步骤:nstep1 找到找到x的前件的前件,使指针使指针q指向指向x的前件；的前件；nstep2 使指针使指针p指向指向x所在结点；所在结点；nstep3 使使p所指结点所指结点x脱链脱链nstep4 释放释放p template int linked_llist:ins_linked_llist(T x) node *p,*q; if(head=NULL) return 0; if(head-dada=

21、x) p=head-next; delete head; head =p; return 1 q=head ; while(q-next!=NULL)& (q-next)-d != x) ) q = q- next; if( q-next = NULL ) return 0; p=q-next; q-next = p- next; delete p; return 1; 课堂练习n参考参考P70 例例2.15n(1)建立空线性链表建立空线性链表n(2)插入插入1-30；n(3)输出链表；输出链表；n(4)将单数的节点删除；将单数的节点删除；n(5)再次输出链表；再次输出链表；2.3.3 循环链

22、表和双向链表引入头节点头结点头结点 ：为方便操作，在头指针和第为方便操作，在头指针和第1个结点之个结点之 间设置的结点。间设置的结点。首元结点首元结点 第一个结点（第一个结点（a1）。）。head头指针头指针a1首元结点首元结点 ai.第第i i个结点个结点头结点头结点空表和非空表表示形式在头结点上得到统一空表和非空表表示形式在头结点上得到统一（任何情况下至少存在一个结点）（任何情况下至少存在一个结点）空表的形式空表的形式 : head - next = NULL head头结点头结点head头结点头结点非空表的形式非空表的形式: head - Next = Address引入头节点n无头结点

23、时，空表和非空表的运算不统一；无头结点时，空表和非空表的运算不统一；n链表检索只能从头指针开始，且只能顺链表方向移链表检索只能从头指针开始，且只能顺链表方向移动。动。n在单链表中，从表的任一结点在单链表中，从表的任一结点ai找其前件结点，时间找其前件结点，时间复杂度是复杂度是O（n）。）。n如果让链表首尾相接，构成环形，这就是如果让链表首尾相接，构成环形，这就是单循环链单循环链表表。n如果在结点中增加一个指向前一个结点的指针域，如果在结点中增加一个指向前一个结点的指针域，链表可以从两个方向检索，效果更佳；这就是链表可以从两个方向检索，效果更佳；这就是双向双向循环链表循环链表。循环单链表(1)单

24、循环链表表示形式：单循环链表表示形式：headhead.a1a2an单循环链表为空的条件单循环链表为空的条件: head-next=head表示形式为表示形式为:(2)单循环链表特点：单循环链表特点：n从表中任一结点出发，均可以找到表中其它结点。从表中任一结点出发，均可以找到表中其它结点。n找其前件结点的时间复杂度是找其前件结点的时间复杂度是O（n）。）。双向循环链表n在单向循环链表中，也存在检索前件结点费时的在单向循环链表中，也存在检索前件结点费时的问题（所需时间是问题（所需时间是O（n）。）。n双向循环链表，其存储结构：双向循环链表，其存储结构：template struct node T

25、 d; node *next，*prior； ；其它定义与单向链表相同。（1）双向循环链表结点结构指向后件结点指针域数据域指向前件结点指针域 prior data next（2）双向循环链表表示形式双向循环链表表示形式：双向循环链表表示形式：headhead.ana2a1双向循环链表为空的条件双向循环链表为空的条件: head -prior = head-next = head表示形式为表示形式为:总结:双向循环链表特点n 适合于两个方向的移动。适合于两个方向的移动。n 找其前件结点的时间复杂度是找其前件结点的时间复杂度是O(1)。循环链表的运算特点n空表与非空表统一空表与非空表统一n判断链表

26、结束的条件改变了判断链表结束的条件改变了nP-next=nullnP-next=headn双向链表的运算要修改两个指针双向链表的运算要修改两个指针循环链表的插入循环链表的插入template void linked_llist:ins_linked_llist(T x) node *p,*q; p= new node ; p-dada =b; q =head;while(q-next !=head)&(q-next)-dada)!=x) q=q-next; p-next =q-next; q-next= p; return;循环链表的删除循环链表的删除template int linked_l

27、list:ins_linked_llist(T x) node *p,*q; q=head ; while(q-next!=head)& (q-next)-dada != x) ) q = q- next; if( q-next = head ) return 0; p=q-next; q-next = p- next; delete p; return 1; 链表存储结构的特点n插入、删除操作极为方便插入、删除操作极为方便n数据非连续存放、顺序存取数据非连续存放、顺序存取n逻辑上相邻，物理上不一定相邻逻辑上相邻，物理上不一定相邻n存储结构较复杂、需要额外的存储空间存储结构较复杂、需要额外的存

28、储空间结论结论： 链表存储结构适合于表中元素频繁变动链表存储结构适合于表中元素频繁变动的线性表。的线性表。课堂练习n参考参考P74 例例2.16n(1)建立单向空循环链表建立单向空循环链表;n(2)插入插入1-100；n(3)删除单数结点；删除单数结点；作业nP152: 2.3 2.71.思考题：思考题：1）假设一单循环链表的长度大于）假设一单循环链表的长度大于1，且表中即无头结点，且表中即无头结点也无头指针。已知也无头指针。已知S为指向链表中某结点的指针。试为指向链表中某结点的指针。试写出删除表中结点写出删除表中结点S 的算法。的算法。2）假设以数组）假设以数组sequm-1存放循环队列的元

29、素，设变量存放循环队列的元素，设变量rear和和quelen分别为指示队尾元素位置和队中元素个分别为指示队尾元素位置和队中元素个数，试写出入队和出队算法。数，试写出入队和出队算法。作作 业业2.4 数组数组2.4.1 数组的顺序存储结构数组的顺序存储结构2.4.2 规则矩阵的压缩规则矩阵的压缩2.4.3 一般稀疏矩阵的表示一般稀疏矩阵的表示 2.4.1 数组的顺序存储n数组是相同类型数据元素的有限集合；数组是相同类型数据元素的有限集合；n数组中的各个分量称为数组中的各个分量称为数组元素数组元素；n每个数组元素值可以用数组名和一个下标值唯一地每个数组元素值可以用数组名和一个下标值唯一地确定确定；

30、数组是有限个数组元素的集合。数组是有限个数组元素的集合。数组中所有元素有相同的特性。数组中所有元素有相同的特性。每个数组元素由数组名和下标组成。每个数组元素由数组名和下标组成。每个具有下标值的数组元素有一个与该下标值对应的数组元素每个具有下标值的数组元素有一个与该下标值对应的数组元素值。值。 n行向量行向量 下标下标 i i 页向量页向量 下标下标 i in列向量列向量 下标下标 j j 行向量行向量 下标下标 j j 列向量列向量 下标下标 k k数组元素之间的关系 二维数组二维数组m行行n列可以看作是列可以看作是m个或个或n个一维数组个一维数组:Amn = (a11a12a1n),(a21

31、a22a2n),. (am1am2amn)111122122212nnmxnmmmnaaaaaaAaaa或数组的操作数组有两种基本的操作：数组有两种基本的操作：n给定下标，读取相应的数组元素；给定下标，读取相应的数组元素；n给定下标，修改相应数组元素的值。给定下标，修改相应数组元素的值。数组的顺序存储结构n数组元素是连续存放的，因此数组元素是连续存放的，因此采用顺序存储采用顺序存储结构。结构。n无论几维数组，在计算机中都是按一维数组无论几维数组，在计算机中都是按一维数组来存放。数组存放通常采用两种方式：来存放。数组存放通常采用两种方式：n按行优先顺序按行优先顺序(Pascal，C)n按列优先顺

32、序按列优先顺序(Fortran)1).按行优先顺序存储结构 例如：例如：二维数组二维数组Amn，可以看作，可以看作m个行向量，每个个行向量，每个行向量行向量n个元素。数组中的每个元素由元素的两个个元素。数组中的每个元素由元素的两个下标表达式唯一确定。下标表达式唯一确定。地址计算公式：地址计算公式： LOC（aij）=LOC（a11）+（i-1）n+（j-1）L 其中，其中，L 是每个元素所占的存储单元。是每个元素所占的存储单元。二维数组按行优先存储举例11121314212223244 43132333441424344aaaaaaaaAaaaaaaaa有二维数组如下：有二维数组如下：LOC(

33、 a23)= LOC( a11)+( 2-1)4+( 3-1)= 7 LOC( a34)= 1 + ( 3-1)4 + ( 4-1) = 12LOC( a14)= 1 + ( 1-1)4 + ( 4-1) = 42).按列优先顺序存储结构 按列优先顺序存放是将数组看作若干个列向量。按列优先顺序存放是将数组看作若干个列向量。 例如例如，二维数组二维数组Amxn，可以看作，可以看作n个列向量，每个个列向量，每个列向量列向量m个元素。数组中的每个元素由元素的两个个元素。数组中的每个元素由元素的两个下标表达式唯一确定。下标表达式唯一确定。 地址计算公式：地址计算公式： LOC（aij）=LOC（a11

34、）+（j-1）*m+（i-1）*L 其中，其中，L 是每个元素所占的存储单元是每个元素所占的存储单元。二维数组按列优先存储举例LOC（a23）= LOC（a11）+（3-1）* 4+（2-1）= 10LOC（a34）= 1 + （4-1）* 4 + （3-1） = 15 LOC（a14）= 1 + （4-1）* 4 + （1-1） = 13 有二维数组如下：4443424134333231242322211413121143aaaaaaaaaaaaaaaaA2.4.2 规则矩阵的压缩 实际工程问题中推导出的数组常常是实际工程问题中推导出的数组常常是高阶、高阶、含大量零元素的矩阵含大量零元素的矩

35、阵，或者是一些，或者是一些有规律排列的元素。为了节省存储空间，有规律排列的元素。为了节省存储空间，通常是对这类矩阵进行压缩存储。通常是对这类矩阵进行压缩存储。 压缩的含义是压缩的含义是：n相同值的多个元素占用一个存储单元；相同值的多个元素占用一个存储单元；n零元素不分配存储单元。零元素不分配存储单元。能够采用压缩存储的矩阵n对称矩阵对称矩阵: :存储主对角线以上（下）的元存储主对角线以上（下）的元素；素；n上（下）三角矩阵上（下）三角矩阵: :只存储三角阵元素；只存储三角阵元素；n带状矩阵带状矩阵: :只存储带状元素；只存储带状元素；n稀疏矩阵稀疏矩阵: :只存储非零元素；只存储非零元素；1

36、下三角矩阵的压缩存储 开辟一个长度为开辟一个长度为n（n+1）/2的一维数组的一维数组B，然后一行接一行地依次存放然后一行接一行地依次存放A中下三角部分的中下三角部分的元素。元素。 nnnnaaaaaaA212221110以行为主压缩存储以行为主压缩存储以列为主压缩存储以列为主压缩存储 )(0)(2/ ) 1(ijijjiiBaij)(0)( 12/ ) 1)(22(ijijjijjnBaij2 对称矩阵的压缩存储 对称矩阵的元素满足：对称矩阵的元素满足：aij = aji 1 i ，j n 因此将因此将n*n 个元素压缩存放到个元素压缩存放到 n（n+1）/2 个单元的个单元的一维数组一维数

37、组S（n+1）*n/2）中。）中。 （按行存放）（按行存放）aij的地址为：的地址为：iji(i-1)/2+j i=j LOC(a )= j(j-1)/2+i ij 当 当 对称矩阵的压缩存储举例存于一维数组存于一维数组S6 S6=( a11, a21, a22, a31, a32, a33 ) 1 2 3 4 5 6 LOC(a31)=3(3-1)/2+1= 4 LOC(a22)=2(2-1)/2+2= 3 LOC(a21)=2(2-1)/2+1= 2112122313233aAaaaaa设有A3x3矩阵:3 三对角矩阵的压缩存储 在三对角矩阵中，三条对角线以外的元素均为零，在三对角矩阵中，

38、三条对角线以外的元素均为零，并且，除了第一行与最后一行外，其他每一行均并且，除了第一行与最后一行外，其他每一行均只有三个元素为非零，因此，只有三个元素为非零，因此，n阶三对角矩阵共有阶三对角矩阵共有3n-2个非零元素。个非零元素。1112021222332333401,21,11,1aaaaaaaaAaaannnnnnaan nnn对角矩阵的压缩存储以行为主存放以行为主存放 ：2(j 1)i(11)0(1 1)ijBijiajiji 或 以列为主存放 ：2(1)(11)0(1 1)ijBijijiajiji 或 2.4.3 2.4.3 一般稀疏矩阵的表示 n如果一个矩阵中绝大多数的元素值为零，

39、只有很如果一个矩阵中绝大多数的元素值为零，只有很少的元素值非零，则称该矩阵为稀疏矩阵少的元素值非零，则称该矩阵为稀疏矩阵 。00000500003020000600000000070000000000090000000010000300A1 三列二维数组表示 （1）非零元素所在的行号）非零元素所在的行号i；（2）非零元素所在的列号）非零元素所在的列号j；（3）非零元素的值）非零元素的值V。 即每一个非零元素可以用下列三元组表示：即每一个非零元素可以用下列三元组表示：（i，j，V） q例如，例如，上述稀疏矩阵上述稀疏矩阵A中的中的8个非零元素可以用以下个非零元素可以用以下8个二元组表示（以行为主的顺序排列）：个二元组表示（以行为主的顺序排列）： （1，3，3） （1，8，1）（）（3，1，9）（）（4，5，7） （5，7，6） （6，4，2）（）（6，6，3） (7，3，5）q为了表示的唯一性，除了每一个非零元素用一个三为了表示的唯一性，除了每一个非零元素用一个三元组表示外，在所有表示非零元素的三元组之前再元组表示外，在所有表示非零元素的三元组之前再添加一个三元组：（添加一个三元组：（I，J，t） q其中其中I表示稀疏矩阵的总行数，表示稀疏矩阵的总行数，J表示稀疏矩阵的总表示稀疏矩阵的总列数，列数，t表示稀疏矩阵中非零元素的个数。表示稀疏矩阵中非零元素的个数。n上述稀