稀疏矩阵——精选推荐

稀疏矩阵

稀疏矩阵的定义

对于那些零元素数⽬远远多于⾮零元素数⽬，并且⾮零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。

⼈们⽆法给出稀疏矩阵的确切定义，⼀般都只是凭个⼈的直觉来理解这个概念，即矩阵中⾮零元素的个数远远⼩于矩阵元素的总数，并

且⾮零元素没有分布规律。

稀疏矩阵的压缩存储

由于稀疏矩阵中⾮零元素较少，零元素较多，因此可以采⽤只存储⾮零元素的⽅法来进⾏压缩存储。

由于⾮零元素分布没有任何规律，所以在进⾏压缩存储的时侯需要存储⾮零元素值的同时还要存储⾮零元素在矩阵中的位置，即⾮零元

素所在的⾏号和列号，也就是在存储某个元素⽐如aij的值的同时，还需要存储该元素所在的⾏号i和它的列号j，这样就构成了⼀个三元组

(i,j,a[i][j])的线性表。

三元组可以采⽤顺序表⽰⽅法，也可以采⽤链式表⽰⽅法，这样就产⽣了对稀疏矩阵的不同压缩存储⽅式。

稀疏矩阵的存储⽅式

1.稀疏矩阵的三元组表⽰

若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。

顺序表中除了存储三元组外，还应该存储矩阵⾏数、列数和总的⾮零元素数⽬，这样才能唯⼀的确定⼀个矩阵。

typedef struct Triple

{

int row,col,e;

}Triple;

typedef struct TSMarix

{

Triple data[max+1];//data是⾮零元素三元组表，data[0]未⽤

int m,n,len;//m:矩阵的⾏数，n:矩阵的列数，len：⾮零元素的个数

}TSMarix;

稀疏矩阵的转置

⾏列递增转置法---算法思想：

采⽤按照被转置矩阵三元组表A的序列（即转置后三元组表B中的⾏序）递增的顺序进⾏转置，并以此送⼊转置后矩阵的

三元组表B中，这样⼀来，转置矩阵的三元组表B恰好是以“⾏序为主序”的

这种⽅法中，转置后的三元组表B仍按⾏序递增存放，必须多次扫描被转置矩阵的三元组表A，以保证被转置矩阵递增形

式进⾏转置，因此要通过双重循环来完成

#include

#include

#define max 3

typedef struct Triple

{

int row,col,e;

}Triple;

typedef struct TSMarix

{

Triple data[max+1];//data是⾮零元素三元组表，data[0]未⽤

int m,n,len;//m:矩阵的⾏数，n:矩阵的列数，len：⾮零元素的个数

}TSMarix;

void CreateTSMarix(TSMarix *T)

{

int i;

printf("请输⼊矩阵的⾏数，列数，⾮零元素个数：\n") ;

scanf("%d%d%d",&T->m,&T->n,&T->len);

if(T->m<1||T->n<1||T->len<1||T->len>=max)

{

printf("输⼊的数据有误!\n");

exit(1);

}

printf("请输⼊⾮零元素的⾏下标，列下标，值(空格分开输⼊):\n");

for(i=1;ilen+1;i++) scanf("%d%d%d",&T->data[i].row,&T->data[i].col,&T->data[i].e);

}

void TransposeTSMarix(TSMarix T,TSMarix *B)//B保存转置后的矩阵

{

B->n=T.m;//转置后B的列存储的T的⾏

B->m=T.n;//转置后B的⾏存储的T的列

B->len=T.len;//B的元素的个数和T的元素的个数⼀样不变

int i,j,k;

if(B->len>0)

{

j=1;//转置后B元素中的下标

for(k=1;k<=T.m;k++)//采⽤被转置矩阵的列序即转置后矩阵的⾏序增序排列

{

for(i=1;i<=T.len;i++)

{

if(T.data[i].col==k)//从头到尾扫描表A,寻找col值为k的三元组进⾏转置

{

B->data[j].row=T.data[i].col;

B->data[j].col=T.data[i].row;

B->data[j].e=T.data[i].e;

j++;

}

}

}

}

}

void Print(TSMarix T)

{

int i;

printf("元素的⾏下标，列下标，值为:\n");

for(i=1;i<=T.len;i++)

{

printf("\t%d\t%d\t%d\n",T.data[i].row,T.data[i].col,T.data[i].e);

}

}

int main()

{

TSMarix T,B;

printf("创建三元组表:\n");

CreateTSMarix(&T);

printf("输出三元组表:\n");

Print(T);

TransposeTSMarix(T,&B);

printf("转置后的矩阵B为:\n");

Print(B);

return 0;

}

⼀次快速定位转置法---算法思想

1.待转置矩阵三元组表A每⼀列⾮零元素的总个数，即转置后矩阵三元组表B的每⼀⾏中⾮零元素的总个数

2.待转置矩阵每⼀列中第⼀个⾮零元素在三元组表B中的正确位置，即转置后矩阵每⼀⾏中的第⼀个⾮零元素在三元组表B

中的正确位置，需要增设两个数组，num[col]⽤来存放三元组表A第col列⾮零元素总个数（三元组表第col⾏⾮零元素总个

数），position[col]⽤来存放转置前三元组表A中第col列（转置后三元组表B中第col⾏）中第⼀个⾮零元素在三元组表B中的存储位置（下标

值）。num[col]：将三元组表A扫描⼀遍，对于其列号为col的元素，给相应的num数组下标为col的元素加⼀（下标计数法）；

position[col]：position[1]=1，表⽰三元组表A中，列值为1的第⼀个⾮零元素在三元组表B中的下标值；position[col]=position[col-

1]+num[col-1],其中2<=col<=A.n

通过position[col]的初始值为三元组表A中第col列（三元组表B第col⾏）中第⼀个⾮零元素正确的位置，当三元组表A第

col列有⼀个元素加⼊到三元组表B时，则position[col]=position[col]+1，令position[col]始终指向三元组表A第col列中下⼀个⾮零元素在三元

组表B中的正确存放位置。

#include

#include

#define max 10

typedef struct

{

int row,col;

int e;

}Triple;

typedef struct

{

Triple data[max+1];

int m,n,len;}TSMatrix;

void Create(TSMatrix *T)

{

printf("请输⼊矩阵⾏数，列数，⾮零元素个数:\n");

scanf("%d%d%d",&T->m,&T->n,&T->len);

if(T->m<1||T->n<1||T->len<1||T->len>max)

{

printf("输⼊的数据有误!\n");

exit(1);

}

printf("请输⼊元素的⾏下标，列下标，值：\n");

for(int i=1;ilen+1;i++)

scanf("%d%d%d",&T->data[i].row,&T->data[i].col,&T->data[i].e);

}

void FastTranspose(TSMatrix T,TSMatrix *B)

{

int col,t,p,q;

int num[max],position[max];

B->len=T.len;

B->m=T.n;

B->n=T.m;

if(B->len>0)

{

for(col=1;col<=T.n;col++)

num[col]=0;

for(t=1;t<=T.len;t++)//采⽤数组下标计数法计算每⼀列⾮零元素的个数

num[T.data[t].col]++;

position[1]=1;

for(col=2;col<=T.n;col++)//求col列中第⼀个⾮零元素在B.data[]中的正确位置

position[col]=position[col-1]+num[col-1];

for(p=1;p<=T.len;p++)

{

col=T.data[p].col;

q=position[col];

B->data[q].row=T.data[p].col;

B->data[q].col=T.data[p].row;

B->data[q].e=T.data[p].e;

position[col]++;

}

}

}

void Print(TSMatrix T)

{

printf("\t⾏下标\t列下标\t值:\n");

for(int i=1;i

printf("\t%d\t%d\t%d\n",T.data[i].row,T.data[i].col,T.data[i].e);

}

int main()

{

TSMatrix T,B;

printf("创建三元组：\n");

Create(&T);

printf("输⼊的三元组为:\n");

Print(T);

printf("快速排序后的三元组为:\n");

FastTranspose(T,&B);

Print(B);

return 0;

}

⼗字链表

⼗字链表结点分为三类 :

表结点，它由五个域组成，其中i和j存储的是结点所在的⾏和列，right和down存储的是指向⼗字链表中该结点所有⾏和列的下

⼀个结点的指针，v⽤于存放元素值。

⾏头和列头结点，这类结点也有域组成，其中⾏和列的值均为零，没有实际意义，right和down的域⽤于在⾏⽅向和列⽅向上指向

表结点，next⽤于指向下⼀个⾏或列的表头结点。

总表头结点，这类结点与表头结点的结构和形式⼀样，只是它的i和j存放的是矩阵的⾏和列数。

⼗字链表可以看作是由各个⾏链表和列链表共同搭建起来的⼀个综合链表，每个结点aij既是处在第i⾏链表的⼀个结点，同时也是