稀疏矩阵三元组链表22页PPT

稀疏矩阵的三元组顺序表存储表示及其转置算法目录1. 引言1.1 背景和意义1.2 结构概述1.3 目的2. 稀疏矩阵的三元组顺序表存储表示2.1 稀疏矩阵的定义与特点2.2 三元组顺序表的数据结构和实现方式2.3 存储表示的优缺点分析3. 稀疏矩阵转置算法3.1 转置操作的意义与应用场景3.2 基于三元组顺序表的转置算法设计思路3.3 转置算法的具体实现步骤与复杂度分析4. 实验与结果分析4.1 实验设置和数据样本介绍4.2 转置算法在不同稀疏矩阵上的性能评估和结果比较4.3 分析结果及启示与讨论5. 结论与展望5.1 结论总结5.2 存在问题及后续工作展望1. 引言1.1 背景和意义稀疏矩阵是一种在实际问题中经常遇到的特殊矩阵结构，其绝大部分元素为零。

与稠密矩阵相比，稀疏矩阵的存储和计算效率更高。

稀疏矩阵可以应用于图像处理、网络分析、线性代数等领域。

三元组顺序表是一种存储稀疏矩阵的数据结构，通过记录非零元素的行索引、列索引和数值，有效地减少了存储空间。

同时，三元组顺序表也提供了便捷的转置操作方式。

因此，深入掌握稀疏矩阵的三元组顺序表存储表示及其转置算法对于提高稀疏矩阵相关问题的解决效率具有重要意义。

1.2 结构概述本文将从两个方面进行论述。

首先，介绍稀疏矩阵的定义与特点，以及三元组顺序表在存储表示中所采用的数据结构和实现方式。

其次，详细描述了基于三元组顺序表的稀疏矩阵转置算法的设计思路、具体实现步骤和复杂度分析。

1.3 目的本文旨在探究稀疏矩阵的三元组顺序表存储表示及其转置算法，在理论层面上深入分析其原理和优劣，并在实验中验证其性能表现。

通过本文的研究，我们希望能够提供一种高效、灵活且易于实现的方法来处理稀疏矩阵，并为进一步的相关应用提供有价值的启示和参考。

2. 稀疏矩阵的三元组顺序表存储表示2.1 稀疏矩阵的定义与特点稀疏矩阵是指在一个二维矩阵中，大部分元素都为0的情况下，只有少数非零元素的情况。

三元组表示稀疏矩阵本节介绍稀疏矩阵三元序列表的压缩存储方式。

通过《矩阵的压缩存储》一节我们知道，稀疏矩阵的压缩存储，至少需要存储以下信息：•矩阵中各非 0 元素的值，以及所在矩阵中的行标和列标；•矩阵的总行数和总列数；图 1 稀疏矩阵示意图例如，图 1 是一个稀疏矩阵，若对其进行压缩存储，矩阵中各非 0 元素的存储状态如图 2 所示：图 2 稀疏矩阵的压缩存储示意图在图2的数组中，存储了一个三元组(即一组三个部分的数据)，分别表示组中的数据(行标签、列标签和元素值)。

注意，这里矩阵的行和列标签都是从1开始的。

C 语言中，三元组需要用结构体实现，如下所示：//三元组结构体typedef struct {int i,j;//行标i，列标jint data;//元素值}triple;由于稀疏矩阵中非 0 元素有多个，因此需要建立 triple 数组存储各个元素的三元组。

除此之外，考虑到还要存储矩阵的总行数和总列数，因此可以采用以下结构表示整个稀疏矩阵：#define number 20//矩阵的结构表示typedef struct {triple data[number];//存储该矩阵中所有非0元素的三元组int n,m,num;//n和m分别记录矩阵的行数和列数，num 记录矩阵中所有的非0元素的个数}TSMatrix;可以看到，TSMatrix 是一个结构体，其包含一个三元组数组，以及用于存储矩阵总行数、总列数和非 0 元素个数的变量。

假设采用 TSMatrix 结构体存储图 1 中的稀疏矩阵，其 C 语言实现代码应该为：#include<stdio.h>#define number 3typedef struct {int i,j;int data;}triple;typedef struct {triple data[number];int n,m,num;}TSMatrix;//输出存储的稀疏矩阵void display(TSMatrix M);int main() {TSMatrix M;M.m=3;M.n=3;M.num=3;M.data[0].i=1;M.data[0].j=1;M.data[0].data=1;M.data[1].i=2;M.data[1].j=3;M.data[1].data=5;M.data[2].i=3;M.data[2].j=1;M.data[2].data=3;display(M);return 0;}void display(TSMatrix M){for(int i=1;i<=M.n;i++){for(int j=1;j<=M.m;j++){int value =0;for(int k=0;k<M.num;k++){if(i == M.data[k].i && j ==M.data[k].j){printf("%d ",M.data[k].data); value =1;break;}}if(value == 0)printf("0 ");}printf("\n");}}输出结果为：1 0 00 0 53 0 0。

稀疏矩阵——三元组顺序表⽬录稀疏矩阵假设m*n的矩阵中，有t的⾮零元，令s=t/m * n,当，s<=0.05时，称此矩阵为稀疏矩阵，简单理解就是⾮零元特别少的矩阵//⼀般矩阵a1 2 3a= 4 5 67 8 9//稀疏矩阵s0 0 0 0 00 2 0 0 5s= 0 0 3 0 00 0 0 0 4矩阵的转置⼀个m * n的矩阵转置后变为 n * m的矩阵//3*2的矩阵-转置前1 24 57 8//转置后变为2*31 4 72 5 8转置后的矩阵每个元素的下表与原来的下表刚好相反，例如上⾯4转置前的下标为（2，1），转置后变为（1，2）；矩阵压缩存储-三元组顺序表之所以引⼊三元组顺序表，是因为，对于稀疏矩阵⽽⾔，⽤传统的存储⽅法会造成存储空间的浪费0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 0M= 0 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0//上⾯矩阵⽤三元组表⽰i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7typedef struct{int i,j; //⾏坐标、列坐标ElemType e; //元素}Triple;typedef struct{Triple date[MAXSIZE+1]; //0不存储元素int mu,nu,tu; //⾏数、列数、⾮零元个数}TSMatrix;稀疏矩阵的转置传统⽅法的转置算法时遍历矩阵的每⼀项，交换其下标值即可for(col=1;col<=nu;col++){for(row=1;row<=mu;row++){T[col][row]=M[row][col]}}//时间复杂度 : O(nu*mu)利⽤三元组顺序表进⾏存储的稀疏矩阵要想实现转置显然不能⽤上⾯的算法，下⾯介绍两种⽅法：第⼀种：以列序为主序的转置//置换前存储位置i j v1 2 12 -> M.date[1]1 3 9 -> M.date[2]3 1 -3 -> M.date[3]3 6 14 -> M.date[4]4 3 24 -> M.date[5]5 2 18 -> M.date[6]6 1 15 -> M.date[7]6 4 -7 -> M.date[8]//置换后存储位置i j v1 3 -3 -> T.date[1]1 6 15 -> T.date[2]2 1 12 -> T.date[3]2 5 18 -> T.date[4]3 1 9 -> T.date[5]3 4 24 -> T.date[6]4 6 -7 -> T.date[7]6 3 14 -> T.date[8]void TransposeSMatrix(TSMatrix *T1,TSMatrix *T2){T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){int q=1,col,p;for(col=1;col<=T1->nu;col++) //矩阵列循环{for(p=1;p<=T1->tu;p++) //遍历所有元素{if(T1->date[p].j==col) //当元素在col列时{T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;q++;}}}}}//上述代码，当矩阵运算为满时，即tu=mu*nu,其时间复杂度为O(nu*nu*mu)//这种情况与经典算法相⽐，虽节省了存储空间，但是效率较低第⼆种：快速转置第⼀种算法是通过遍历所有元素的下标，从⽽确定其在转置后数组中的位置，快速转置的思想就是，预先确定每⼀列第⼀个⾮零元在对应转置后的数组date中的位置；因此需要两个辅助数组num[]:⽤来存放每⼀列的⾮零元个数cpot[]:存放第⼀个⾮零元在转置后数组date中的位置num[]数组的值很好求，只需要遍历⼀次所有元素即可for(t=1;t<=T1->tu;t++)++num[T1->date[t].j];对于cpot[]，有⼀个规律col 1 2 3 4 5 6 7num[col] 2 2 2 1 0 1 0cpot[col] 1 3 5 7 8 8 9//规律copt[1]=1copt[col]=copt[col-1]+num[col-1]代码：void FastTransposeSMatrix(TSMatrix *T1,TSMatrix *T2){int num[T1->nu],cpot[T1->nu];int col,p,q,t;T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){//初始化每列⾮零元个数为0for(col=1;col<=T1->nu;col++){num[col]=0;}//求每列⾮零元个数for(t=1;t<=T1->tu;t++){++num[T1->date[t].j];}//求每列第⼀个⾮零元转置后的位置cpot[1]=1;for(col=2;col<=T1->nu;col++){cpot[col]=num[col-1]+cpot[col-1];}//遍历所有元素for(p=1;p<=T1->tu;p++){col=T1->date[p].j; //获取列坐标q=cpot[col]; //获取新位置T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;++cpot[col]; //之所以这个地⽅要++，因为每列⾮零元可能不⽌⼀个 }}}完整代码：#include <stdio.h>#include <stdlib.h>#define MAXSIZE 12500 //⾮零元个数的最⼤值typedef int ElemType;typedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple date[MAXSIZE+1];int mu,nu,tu;}TSMatrix;//输⼊元素void Insert(TSMatrix *T){printf("请依次输⼊⾏数i、列数j、⾮零元个数sum:\n");int sum ;scanf("%d%d%d",&T->mu,&T->nu,&sum);T->tu=sum;int x,y,num;printf("请依次输⼊矩阵⾮零元的⾏坐标i、列坐标j、元素值x:\n");printf("i j v\n");for(int i=1 ;i<=sum;i++){scanf("%d%d%d",&x,&y,&num);T->date[i].i=x;T->date[i].j=y;T->date[i].e=num;}}//第⼀种转置⽅法void TransposeSMatrix(TSMatrix *T1,TSMatrix *T2)T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){int q=1,col,p;for(col=1;col<=T1->nu;col++){for(p=1;p<=T1->tu;p++){if(T1->date[p].j==col){T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;q++;}}}}}//输出矩阵⾮零元void Show(TSMatrix *T){printf("转置后的矩阵：\n");printf("i j v\n");for(int i=1;i<=T->tu;i++){printf("%d %d %d\n",T->date[i].i,T->date[i].j,T->date[i].e); }}//快速转置void FastTransposeSMatrix(TSMatrix *T1,TSMatrix *T2){int num[T1->nu],cpot[T1->nu];int col,p,q,t;T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){//初始化每列⾮零元个数为0for(col=1;col<=T1->nu;col++){num[col]=0;}//求每列⾮零元个数for(t=1;t<=T1->tu;t++){++num[T1->date[t].j];}cpot[1]=1;for(col=2;col<=T1->nu;col++){cpot[col]=num[col-1]+cpot[col-1];}for(p=1;p<=T1->tu;p++){col=T1->date[p].j;q=cpot[col];T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;++cpot[col];}}}int main(){TSMatrix T,T1,*q,*p;p=&T;q=&T1;Insert(p);//测试第⼀种转置⽅法TransposeSMatrix(p, q);Show(q);//测试快速转置FastTransposeSMatrix(p, q);Show(q);}/* 测试请依次输⼊⾏数i、列数j、⾮零元个数sum:6 7 8请依次输⼊矩阵⾮零元的⾏坐标i、列坐标j、元素值x:1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7转置后的矩阵：i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14转置后的矩阵：i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14Program ended with exit code: 0*/我不⽣产代码，我只是代码的搬运⼯。

稀疏矩阵类（以三元组链表表⽰）这是⼀个⽤三元组链表表⽰的稀疏矩阵类。

这⾥将类与主函数放在⼀起以便于阅读，如有其他需要请⾃⾏封装。

运⾏结果及源码在下⽅给出。

注：蓝⾊下划线需要通过键盘键⼊//XL_Array.h//稀疏矩阵类（以三元组链表表⽰）#include<iostream>#include<iomanip>using namespace std;//定义三元组链表结点类型template<class T>struct B{int i; //⾮零元素所在的⾏号int j; //⾮零元素所在的列号T v; //⾮零元素值B<T> *next; //指向下⼀个结点的指针域};//三元组链表表⽰的稀疏矩阵类template<class T> //类模板，T为虚拟类型class XL_Array{private: //数据成员int mm; //稀疏矩阵⾏数int nn; //稀疏矩阵列数int tt; //稀疏矩阵中⾮零元素个数B<T> *head; //三元组链表头指针public: //成员函数XL_Array(){head=NULL;return;}//三元组链表初始化void in_XL_Array(); //以三元组形式从键盘输⼊稀疏矩阵⾮零元素void th_XL_Array(int,int,T []);//由⼀般稀疏矩阵转换void prt_XL_Array(); //按⾏输出稀疏矩阵XL_Array tran_XL_Array(); //稀疏矩阵转置XL_Array operator + (XL_Array &);//稀疏矩阵相加};//以三元组形式从键盘输⼊稀疏矩阵⾮零元素template<class T> //函数模板，T为虚拟类型void XL_Array<T>::in_XL_Array(){int k,m,n;T d;B<T> *p,*q;cout<<"输⼊函数列数⾮零元素个数：";cin>>mm>>nn>>tt;q=NULL;cout<<"输⼊⾏数列号⾮零元素值："<<endl;for (k=0;k<tt;k++) //输⼊三元组{cin>>m>>n>>d;p=new B<T>; //申请⼀个三元组结点p->i=m-1; p->j=n-1;p->v=d; p->next=NULL;if(head==NULL)head=p;else q->next=p;q=p;}return;}//由⼀般稀疏矩阵转换template<class T> //函数模板，T为虚拟类型void XL_Array<T>::th_XL_Array(int m,int n,T a[]){int t=0,p,q;B<T> *s,*k;T d;mm=m; nn=n;k=NULL;for(p=0;p<m;p++)for(q=0;q<n;q++){d=a[p*n+q];if(d!=0) //⾮零元素{s=new B<T>; //申请⼀个三元组结点s->i=p; s->j=q; s->v=d;s->next=NULL;if(head==NULL)head=s;else k->next=s;k=s;t=t+1;}}tt=t;return;}//按⾏输出稀疏矩阵template<class T> //函数模板，T为虚拟函数void XL_Array<T>::prt_XL_Array(){int k,kk;B<T> *p;p=head;for(k=0;k<mm;k++) //按⾏输出{for(kk=0;kk<nn;kk++) //输出⼀⾏if(p!=NULL){if((p->i==k)&&(p->j==kk))//输出⾮零元素{cout<<setw(8)<<p->v;p=p->next;}else cout<<setw(8)<<0;//输出0}else cout<<setw(8)<<0; //输出0cout<<endl;}return;}//稀疏矩阵转置template<class T> //函数模板，T为虚拟函数XL_Array<T> XL_Array<T>::tran_XL_Array(){XL_Array<T> at; //定义转置矩阵对象int p;B<T> *s,*k,*q;at.mm=nn; //转置矩阵⾏、列数及⾮零元素个数 at.nn=mm;at.tt=tt;k=NULL;for(p=0;p<nn;p++)for(q=head;q!=NULL;q=q->next){if(q->j==p){s=new B<T>; //申请⼀个三元组结点s->i=q->j;s->j=q->i;s->v=q->v;s->next=NULL;if(k==NULL)at.head=s;else k->next=s;k=s;}}return(at); //返回转置矩阵}//稀疏矩阵相加template<class T> //函数模板，T为虚拟函数XL_Array<T> XL_Array<T>::operator + (XL_Array<T> &b){XL_Array<T> c; //定义和矩阵对象T d;B<T> *m,*n,*q,*s;int k=0;q=NULL; //记住链尾if((mm!=b.mm)||(nn!=b.nn))cout<<"不能相加！"<<endl;else{m=head;n=b.head;while ((m!=NULL) && (n!=NULL)){if(m->i==n->i) //⾏号相同{if(m->j==n->j) //列号相同则相加{d=m->v+n->v;if(d!=0) //相加后⾮零{s=new B<T>; //申请⼀个三元组结点s->i=m->i;s->j=m->j;s->v=d;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1}m=m->next;n=n->next;}else if(m->j < n->j)//列号不同则复制列号⼩的⼀项{s=new B<T>; //申请⼀个三元组结点s->i=m->i;s->j=m->j;s->v=m->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1m=m->next;}else//列号不同复制另⼀项{s=new B<T>; //申请⼀个三元组结点s->i=n->i;s->j=n->j;s->v=n->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1n=n->next;}}else if(m->i<n->i) //复制矩阵中⾏号⼩的⾮零元素{s=new B<T>; //申请⼀个三元组结点s->i=m->i;s->j=m->j;s->v=m->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1m=m->next;}else//复制另⼀矩阵中本⾏的⼀个⾮零元素 {s=new B<T>; //申请⼀个三元组结点s->i=n->i;s->j=n->j;s->v=n->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1n=n->next;}}while (m!=NULL) //复制矩阵中剩余的⾮零元素{s=new B<T>; //申请⼀个三元组结点s->i=m->i;s->j=m->j;s->v=m->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1m=m->next;}while (n!=NULL) //复制另⼀矩阵中剩余的⾮零元素{s=new B<T>; //申请⼀个三元组结点s->i=n->i;s->j=n->j;s->v=n->v;s->next=NULL;if(q==NULL)c.head=s;else q->next=s;q=s; //记住链尾k=k+1; //⾮零元素个数加1n=n->next;}c.mm=mm; c.nn=nn; c.tt=k;}return(c); //返回相加结果}void main(){double a[7][8]={ {0,0,3,0,0,0,0,1},{0,0,0,0,0,0,0,0},{9,0,0,0,0,0,0,0},{0,0,0,0,7,0,0,0},{0,0,0,0,0,0,6,0},{0,0,0,2,0,3,0,0},{0,0,5,0,0,0,0,0}};XL_Array<double>x,y,z,xt,c;x.th_XL_Array(7,8,&a[0][0]);cout<<"输出稀疏矩阵x："<<endl;x.prt_XL_Array();xt=x.tran_XL_Array(); //稀疏矩阵转置cout<<"输出稀疏矩阵x的转置xt:"<<endl;xt.prt_XL_Array();y.in_XL_Array(); //以三元组形式从键盘输⼊稀疏矩阵⾮零元素 cout<<"输出稀疏矩阵y:"<<endl;y.prt_XL_Array();z=x+y; //稀疏矩阵相加cout<<"输出稀疏矩阵z=x+y:"<<endl;z.prt_XL_Array();}。

三元组顺序表表示的稀疏矩阵加法三元组顺序表表示的稀疏矩阵加法引言：稀疏矩阵是指在矩阵中大部分元素为零的情况下，只有很少非零元素的矩阵。

由于矩阵运算的复杂性，对于大型稀疏矩阵，使用传统的矩阵加法算法会消耗大量的时间和内存资源。

因此，为了高效地进行稀疏矩阵的加法运算，可以使用三元组顺序表来表示稀疏矩阵，并通过特定的算法来实现加法操作。

本文将介绍三元组顺序表和稀疏矩阵加法，并逐步回答以下问题：1. 什么是三元组顺序表？2. 什么是稀疏矩阵加法？3. 如何使用三元组顺序表进行稀疏矩阵加法操作？一、什么是三元组顺序表？三元组顺序表是一种用来高效表示稀疏矩阵的数据结构。

在三元组顺序表中，每个非零元素用一个三元组表示，包括元素的行号、列号和值。

同时，三元组顺序表中还包含两个整数，分别表示矩阵的行数和列数。

例如，如果有一个3x3的稀疏矩阵如下：1 0 20 4 03 0 5使用三元组顺序表来表示这个矩阵，可以得到如下的三元组：(0, 0, 1), (0, 2, 2), (1, 1, 4), (2, 0, 3), (2, 2, 5)二、什么是稀疏矩阵加法？稀疏矩阵加法是指对两个稀疏矩阵进行加法运算的操作。

对于给定的两个稀疏矩阵A和B，稀疏矩阵加法的结果矩阵C的每个元素等于矩阵A和B中对应位置的元素之和。

三、使用三元组顺序表进行稀疏矩阵加法操作的步骤为了实现稀疏矩阵加法，可以按照以下步骤进行：1. 定义一个存储稀疏矩阵的三元组顺序表：使用一个结构体将矩阵的行、列和非零元素存储起来。

2. 输入矩阵A和B的维度：获取矩阵A和B的行数和列数，以及非零元素的个数。

3. 输入矩阵A和B的非零元素：获取矩阵A和B的非零元素的行号、列号和值，并将其存储到三元组顺序表中。

4. 对三元组顺序表进行排序：根据三元组的行号和列号进行排序，以便后续的加法运算。

5. 进行稀疏矩阵加法运算：从头开始遍历三元组顺序表，依次取出每个三元组，根据其行号和列号在结果矩阵C中进行加法运算。