用三元组存储稀疏矩阵，实现其快速转置及矩阵相乘

一、明确问题

用三元组存储稀疏矩阵，实现其快速转置及矩阵相乘。

二、问题分析

该问题分为三个小部分：1、将一个矩阵转换为三元数组；2、把三元数组转置；3、判断输入的两个矩阵是否能够相乘，若能则用三元数组完成矩阵相乘。
问题1：需要创建一个动态数组，根据输入的i，j来判断该数组的行和列。通过双层for循环完成数组的赋值即矩阵的创建。转换成三元数组即是创建一个结构体包含矩阵的行数、列数以及非零元个数，同时嵌套一个结构体用于存储每一个非零值的行、列和具体值。
问题2：三元数组的转置，首先是需要将三元数组的行列互换，其次是按照列的大小顺序重新排序。创建了一个cpot数组用于计算每一列的非零值的个数，按照cpot数组的值来用于转置矩阵的排序。
问题3：两矩阵相乘，首先判断第一个矩阵的列数和第二个矩阵的行数，只有其相等才能相乘。通过矩阵相乘的公式，并按照c语言的写法，将子函数写出来。即将一矩阵的列值和二矩阵行值相等的值相乘，若不止一个非零值，则将其相加。

三、主要函数和伪代码

创建一个结构体JD，保存非零值得行数i、列数j和具体值e。
struct JD{
int i,j;
int e;
};
创建一个结构体，包含一个含MAX+1个JD结构体的部分，（用MAX+1是为了从1开始，便于之后的计算），也包含三个整型变量，存储原矩阵行数mu，列数ru和非零元tu的个数。
struct matrix{
struct JD data[MAX+1];//想从1开始!!!
int mu,ru,tu;//矩阵的行数、列数和非零元个数
};
创建了5个子函数，用于模块化代码，并且简洁代码。
void transmatrix(struct matrix M,struct matrix T);该函数用于将一个用三元数组存储的矩阵M转置，并用另一个三元数组T存储。
void printmartix(struct matrix M);将三元矩阵M按照行列从小到大的顺序打印出来。
int* createarray(int i,int j);//创建一个i行j列的二维数组，该函数返回二维数组的首地址。
void MultSMatrix(struct matrix O,struct matrix P,struct matrix *R );//计算两个用三元数组存储的矩阵O、P相乘后的值，用结构体R来存储
void initialize(struct matrix *M,int i,int j,int **a);该函数用于矩阵初始化，即将一个正常矩阵a转化为用三元数组M存储。

四、源代码和运行结果

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX  100//设置矩阵最大可容纳的非零值为100 
struct JD{
	int i,j;
	int e;
};

struct matrix{
	struct JD data[MAX+1];//想从1开始!!! 
	int mu,ru,tu;//矩阵的行数、列数和非零元个数 
};

void transmatrix(struct matrix M,struct matrix *T);//把矩阵转置 
void printmartix(struct matrix M);//把矩阵打印下来 
int** createarray(int i,int j);//创建一个i行j列的二维数组 
void MultSMatrix(struct matrix O,struct matrix P,struct matrix *R );//计算两个矩阵的值 
void initialize(struct matrix *M,int i,int j,int **a);

int** createarray(int i,int j){
	 int** a;
	 int m,n,k;
	a =(int**)malloc(i*sizeof(int*)); 
    for(k=0;k<i;k++)
    a[k]=(int*)malloc(j*sizeof(int));
         
 	for(m=0;m<i;m++){
 		for(n=0;n<j;n++){
 			scanf("%d",&a[m][n]);
		 } 
	 }
	return a;
}

void transmatrix(struct matrix M,struct matrix *T)
{
    int col,num[100],cpot[100],t,q;
 	
 	//稀疏矩阵的转置 
 	(*T).mu=M.ru;(*T).ru=M.mu;(*T).tu=M.tu;
 	if((*T).tu){
        for(col=1;col<=M.ru;col++) num[col]=0;//将值全部赋为0 
        for(t=1;t<=M.tu;t++) ++num[M.data[t].j];//计算每一列上面非0数的出现次数 
        cpot[1]=1;//把值初始化 
        for(col=2;col<=M.tu;col++){
            cpot[col]=cpot[col-1]+num[col-1];//把重新排序后第i列在新三元矩阵的第几行表示出来 
        }
        for(t=1;t<=M.tu;t++){//按照行的大小将转置后的三元矩阵做出来 
            col=M.data[t].j;
            q=cpot[col];
            (*T).data[q].j=M.data[t].i;
            (*T).data[q].i=M.data[t].j;
            (*T).data[q].e=M.data[t].e;
            ++cpot[col];//将列一样的加一 
        }
    }
 } 

void printmartix(struct matrix M){
	int s;
	for(s=1;s<=M.tu;s++){
	 printf("%10d%10d%10d\n",M.data[s].i,M.data[s].j,M.data[s].e);
	}
	printf("***********\n");
} 

void MultSMatrix(struct matrix O,struct matrix P,struct matrix *R )
{		int m = 1;	int n = 1;	int k = 1;	int q;
int l=0;
 	if( O.ru!= P.mu ){  	
	 printf( "两矩阵不能相乘！\n" );
	 	}
	else{				
	    (*R) .mu  = O.mu;			
	    (*R) .ru  = P.ru;		
	    for( k = 1; k <= O.ru * P.mu; k++ )				
     	(*R) .data[k].e= 0;	
    	k = 0;
	    while( m <= O.tu ){				
         	for( n = 1; n <= P.tu; n++ ){			
	          if(O.data[m].j==P.data[n].i){
               k++;
	    	   (*R) .data[k].i = O.data[m].i;				
		       (*R) .data[k].j = P.data[n].j;				
		       (*R) .data[k].e = O.data[m].e*P.data[n].e; 			
						for( q = 1; q < k; q++ ){			
							if( (*R) .data[k].i ==(*R) .data[q].i && (*R) .data[k].j== (*R) .data[q].j){		
								(*R) .data[q].e+=(*R) .data[k].e; 						
								k--;		
							}	
						}		
				}
		    }
		    m++;
     	}
	(*R) .tu=k;
	printf("两个矩阵乘积的结果\n");
	} 
} 

void initialize(struct matrix *M,int i,int j,int **a){
	int m,n;
	(*M).mu=i;(*M).ru=j;(*M).tu=0;//三元数组值初始化
	for(m=0;m<i;m++){
		for(n=0;n<j;n++){
			if(a[m][n]!=0){
				(*M).tu++;
				(*M).data[(*M).tu].i=m+1;
				(*M).data[(*M).tu].j=n+1;
				(*M).data[(*M).tu].e=a[m][n];	
			}
		}
	}
	printf("该矩阵的非零值得个数为：%d\n",(*M).tu) ;
}
int main()
 {
 	struct matrix M,T;
 	int i,j,x,y,z;
 	printf("输入1：将矩阵化为三元数组\n输入2：将矩阵转置\n输入3：两矩阵相乘\n输入0：结束\n");
 	scanf("%d",&z);
    while(z!=0){
 		switch(z){
		 case 1:
		   {
 			printf("请依次输入矩阵的行数和列数\n");
	        scanf("%d %d",&i,&j);
	        printf("请按行的顺序依次将%d行%d列的值输入\n",i,j);
	        int **a;
            a=createarray(i,j);
            initialize(&M,i,j,a);
            printmartix(M);
            break;
		    }
		case 2:
		  {
			transmatrix(M,&T);
            printmartix(T);
			break; 	
		  }
		case 3:
		  {
		    struct matrix O,P,R;
		    int **a,**b;
		    printf("请输入第一个矩阵的行数和列数\n");
		    scanf("%d %d",&i,&j);
	        printf("请按行的顺序依次将%d行%d列的值输入\n",i,j);
            a=createarray(i,j);
            initialize(&O,i,j,a);
            printmartix(O);
            printf("请输入第二个矩阵的行数和列数\n");
		    scanf("%d %d",&x,&y);
	        printf("请按行的顺序依次将%d行%d列的值输入\n",x,y);
            b=createarray(x,y);
            initialize(&P,x,y,b);
            printmartix(P);
		    MultSMatrix(O,P,&R);
		    printmartix(R);	
		break;
		  }
		default:printf("请重新输入\n"); 
	 }
	 printf("输入1：将矩阵化为三元数组\n输入2：将矩阵转置\n输入3：两矩阵相乘\n输入0：结束\n");
	 scanf("%d",&z);
   }
}

基本概念

在学习线性代数的时候，经常用到矩阵。在C语言中，表示矩阵的最直观形式就是二维数组。然而在实际应用中，很多高阶矩阵中的非零元素非常少，这个时候如果继续使用二维数组存储，那么就会浪费很多存储空间。

在数据结构中，我们用三元组存储稀疏矩阵。三元组定义为(i,v,j)，这三个值一次表示矩阵的行、列、值。

有了基本的概念之后，就可以定义数据结构了

定义一个结构体，来表示三元组的基本属性

typedef struct
{
	int row, col;
	int e;
}Triple;

然后再定义一个存储容器，用来存放三元组的

为了简单起见，我们用数组来实现，并定义最大存储单元MAXSIZE为100

typedef struct
{
	Triple data[MAXSIZE];
	Int m,n,len;
}TSMatrix;
//(TSMatrix表示 Triple Sparse Matrix)

实现矩阵的转置
         实现用三元组表示的矩阵的转置，可以直接把行列互换，然后再执行按行序为主的排序过程。为了避免重新排序引起的元素移动，可以采用列序递增转置法。

         具体做法，就是遍历列的下表值，从列数低的值到列数高的值，依次添加到缓存三元组中。很显然，这是一个双重for循环结构，内层循环实现遍历整个表，寻找合适的列。外层循环，则记录要寻找的列数。

//实现转置 
void TransposeTSMatrix(TSMatrix A, TSMatrix* B)
{
	int i,j,k;
	B->m = A.n;
	B->n = A.m;
	B->len = A.len;
	j=0;
	
	for( k=0; k<A.len; ++k)
	{
		for( i=0; 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;
			}
		}
	}
	
}

完整代码

#include <stdio.h>
#define MAXSIZE 100
//三元组的定义 
typedef struct
{
	int row, col;//表示行列 
	int e;		//表示值 
}Triple;

//三元组容器的定义 
typedef struct
{
	Triple data[MAXSIZE];
	int m,n,len;
}TSMatrix;

//实现转置 
void TransposeTSMatrix(TSMatrix A, TSMatrix* B)
{
	int i,j,k;
	B->m = A.n;
	B->n = A.m;
	B->len = A.len;
	j=0;
	
	for( k=0; k<A.len; ++k)
	{
		for( i=0; 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;
			}
		}
	}
	
}

//测试驱动函数 
int main()
{
	//将输入重定向到根目录下的data.txt 
	freopen("data.txt", "r", stdin);
	TSMatrix A,B;
	int i,j,e; 
	int k=0;
	printf("请输入三元组：");
	while(scanf("%d%d%d", &i, &j, &e)!=EOF)
	{
		A.data[k].row = i-1;
		A.data[k].col = j-1;
		A.data[k].e = e;
		A.len = ++k;
	}
	printf("\n原始三元组为:\n");
	for(i=0; i<A.len; ++i )
	{
		printf("%3d%3d%3d\n", A.data[i].row+1, A.data[i].col+1, A.data[i].e);
	}
	
	printf("\n转置后:\n");
	TransposeTSMatrix(A, &B);
	for(i=0; i<B.len; ++i )
	{
		printf("%3d%3d%3d\n", B.data[i].row+1, B.data[i].col+1, B.data[i].e);
	}
	return 0;
}

程序截图

内容:

设m*n的矩阵中有t个非零元素且t<<m*n,这样的矩阵成为稀疏矩阵，在存储稀疏矩阵时，按照常规方法存储时相当浪费内存，因此提出另外一种存储方法，即只存储非零元素，但在这类矩阵中，通常零元素的排列没有规律，为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列。于是采取如下办法：将非零元素所在的行、列以及它的值构成一个三元组(i,j,v),然后再按某种规律存储这些三元组，这种方法可以节约存储空间。编写程序用三元组表实现稀疏矩阵的按列转置操作。

步骤：

1. 算法分析

本题需要利用三元组实现稀疏矩阵的按列转置操作。

何为转置操作？所谓矩阵转置，是指变换元素的位置，把位于(row,col)位置上的元素换到(col,row)位置上，也就是说，将元素的行、列互换。

采用三元组表压缩存储稀疏矩阵，实现矩阵的转置时，得到的转置矩阵的三元组表时要按一行一行存放且每行中的元素是按列号从小到大的规律顺序存放，因此在转换时，对a的每一列扫描三元组，找出相应的元素，若找到，则交换其行号与列号，并存储到b的三元组里。

程序中设置了三个函数：

1. 函数InitSPNode()用来建立一个稀疏矩阵的三元组表。首先输入行数、列数和非零元素的值，输入(-1,-1,-1)结束输入。
2. 函数showMatrix()用来输出稀疏矩阵。算法中按矩阵a的列进行循环处理，对a的每一列扫描三元组，找出相应的元素，若找到，则交换其行号和列号，并存储到矩阵b的三元组中。
3. 函数TransposeSMatrix()用来完成稀疏矩阵的转置算法。算法的主要工作是在p和col的两重循环中完成，时间复杂度为O(n*t)。如果非零元素个数t和m*n同数量级，则算法的时间复杂度变为O(m*n^2)。

   2.概要设计

使用C语言，其中设置了以下函数

程序运行流程图如下：

 3.测试

测试样例如下:

 运行结果：

 经测试运行无误。

经过不断的修改和调试，该算法已经基本能够满足要求，对于用户输入的稀疏矩阵，可以方便快捷的完成稀疏矩阵的转置。当非零元素的个数与m*n同数量级时，算法的时间复杂度为O(m*n^2),与传统存储方式下矩阵转置算法相比，节约了一定量的存储空间，但算法的时间性能更差一些，该算法的主要时间耗费在p和col的二重循环上，若能直接确定a中每一个三元组在b中的位置，则对a的三元组表扫描一次即可。算法程序还有待优化。

4.源码如下

#include <stdio.h>
#include <string.h>
#define OK 1
#define Maxsize 10 //用户自定义三元组最大长度
typedef struct { //定义三元组表
	int i,j;
	int v;
}SPNode;
typedef struct
 { //定义三元组表
	SPNode data[Maxsize];
	int m,n,t;//矩阵行、列及三元表长度
}SPMatrix;
void InitSPNode(SPMatrix*a) { //输入三元组表
	int i,j,k,val,maxrow,maxcol;
	maxrow=0;
	maxcol=0;
	i=j=0;
	k=0;
	while(i!=-1&&j!=-1)//row=-1&&col=-1 结束输入
	 { 
		printf(" 输入(行 列 值):  ");
		scanf(" %d %d %d",&i,&j,&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(SPMatrix *a) { //输出稀疏矩阵
	int p,q;
	int t=0;
	for(p=0; p<=a->m; p++) {
		for(q=0; 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"  );
	}
}
void TransposeSMatrix(SPMatrix *a,SPMatrix *b) { //稀疏矩阵转置
	int q,col,p;
	b->m=a->n;
	b->n=a->m;
	b->t=a->t;
	if(b->t) {
		q=0;
		for(col=0; col<=a->n; ++col) //按a的列序转置
			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;
				}
	}
}
int main() {
	SPMatrix a,b;
	printf("\n 结束请输入(-1 -1 -1)\n"  );
	InitSPNode(&a);
	printf(" 输入矩阵为：\n" );
	showMatrix(&a);//转置前
	TransposeSMatrix(&a,&b);
	printf(" 输出矩阵为: \n" );
	showMatrix(&b);//转置后
}