【数据结构】稀疏矩阵乘法

1.传统矩阵相乘的算法使用三个嵌套循环实现，算法复杂度为O（m * n1 * n2）
2.使用三元组顺序表存储稀疏矩阵时，实现 Q= M * N，对于M中M（i，j）元素来说，只需要与N中第j行元素N（j,q）相乘，再存入Q（i，q）中。为了实现这一操作，增加一个向量rpos，表示每一行的第一个非零元在三元组中的位置，rpos作用相当于快速转置中的cpot向量。
这种结构叫做 行链接的顺序表

typedef struct {
	Triple data[MAXSIZE + 1]; //非零三元组表，data0未用
	int rpos[MAXRC + 1];	  //各行第一个非零元的位置表
	int mu, nu, tu;			  //三元组行数，列数，非零元素值
}RLSMatrix;

在创建矩阵时，需要求得矩阵的rpos向量，求法与cpot一致。

Status CreateRLSMatrix(RLSMatrix &M) {
	cout << "输入矩阵行数，列数，非零元素个数：" << endl;
	cin >> M.mu >> M.nu >> M.tu;
	cout << "依次输入" << M.tu << "个元素的行数，列数，元素值:" << endl;
	for (int i = 1; i <= M.tu; i++)
	{
		cin >> M.data[i].i >> M.data[i].j >> M.data[i].e;
	}
	int* num = (int*)malloc(M.mu * sizeof(int));
	int arow;
	int q;
	if (M.tu) {
		for ( arow = 1; arow <= M.mu; ++arow) num[arow] = 0;
		for (int t = 1; t <= M.tu; ++t) ++num[M.data[t].i];//求M中每一行含非零元个数
		M.rpos[1] = 1;
		//求第col列中第一个非零元在b.data 中的序号
		for (arow = 2; arow <= M.mu; ++arow)M.rpos[arow] = M.rpos[arow - 1] + num[arow - 1];
	}
		cout << "矩阵构造完成" << endl;
	return OK;
}

稀疏矩阵乘法
算法思路：
大循环是对M中的每一行进行。
rpos向量用来确定每行元素个数
再对该行每个元素M（i，j）进行处理，找到N中对应的第 j 行，将这一行所有元素与M（i，j）相乘，结果存入ctemp累加器中，该行元素都处理完成后，ctemp中所存储的便是Q中第 i 行数据

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
	//求稀疏矩阵乘积 Q = M x N  采用行逻辑链接存储表示
	if (M.nu != N.mu)return ERROR;
	Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;
	int arow,tp,p,brow,t,q,ccol;
	int* ctemp = (int*)malloc((M.mu+1) * sizeof(int));
	if (M.tu * N.tu != 0) {
		for (arow = 1; arow <= M.mu; ++arow) {
		//对M的每行进行处理
			for (int i = 0; i <= M.mu; i++)ctemp[i] = 0;//累加器清零
			Q.rpos[arow] = Q.tu + 1;
			if (arow < M.mu)tp = M.rpos[arow + 1];
			else tp = M.tu + 1;//确定M中该行元素个数
			for ( p = M.rpos[arow]; p < tp; p++)
			{//M中对该行的每个元素进行处理
				brow = M.data[p].j;
				if (brow < N.mu) t = N.rpos[brow + 1];
				else t = N.tu + 1;
				for (q = N.rpos[brow]; q < t; ++q) {
				//将该元素与矩阵N中对应行的元素进行相乘，结果存入累加器
					ccol = N.data[q].j;
					ctemp[ccol] += M.data[p].e *N.data[q].e;
				}
			}
			for(ccol =1;ccol<=Q.nu;++ccol)
				if (ctemp[ccol]) {
				//第arow行处理完毕，将累加器中值存入Q中
					if (++Q.tu > MAXSIZE)return ERROR;
					Q.data[Q.tu] = { arow, ccol, ctemp[ccol] };
				}//if
		}//for arow
	}//if
}

该算法总的时间复杂度为O（M.mu * N.nu + M.tu * N.tu/N.mu）
ctemp初始化 O（M.mu * N.nu）
求Q中所有非零元 O（M.tu * N.tu / N.mu）
压缩存储 O（M.mu * N.nu）

代码：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 1000
typedef struct{
int row;//第几行
int col;//第几列
int e;//存储的值
}Triple;

typedef struct
{
    Triple data[MAXSIZE];
    int m,n,len;//稀疏矩阵的行，列，非零元素的个数
}TSMatrix;

void createTSMatrix(TSMatrix *A)//创建矩阵
{    int i=0;     //data【0】未用
    scanf("%d?%d",&A->m,&A->n);
    int flag = 1;
    int a,b,c;
    char c1,c2,c3;
    while(flag)
    {
        scanf("%d?%d?%d",&a,&b,&c);


          if(a==0&&b==0&&c==0)
            break;
            i++;
          A->data[i].row=a;
          A->data[i].col=b;
          A->data[i].e=c;


    }
    A->len=i;
}

void printMatrix(TSMatrix *B)//输出矩阵
{
    for(int i=1;i<=B->len;i++)
    {
        printf("%d?%d?%d\n",B->data[i].row,B->data[i].col,B->data[i].e);
    }

}

void MulTSMatrix(TSMatrix *A,TSMatrix *B,TSMatrix *C)//矩阵相乘
{
    C->len=0;
    int p,q,x,cnt;
    int i1,j1;
    int sum;
    cnt=1;
    for(int i=1;i<=A->m;i++)
    {

        for(int j=1;j<=B->n;j++)//遍历每行每列
        {
           sum=0;
            for(int k=1;k<=A->n;k++)//每个行与每个列单个数的遍历
            {    p=0;q=0;
                for(i1=1;i1<=A->len;i1++){  //遍历A找符合i行k列的数
                    if(A->data[i1].row==i&&A->data[i1].col==k) p=A->data[i1].e;
                   }
                   for(j1=1;j1<=B->len;j1++){//遍历B找符合k行j列的数
                    if(B->data[j1].row==k&&B->data[j1].col==j) q=B->data[j1].e;
                   }
                sum=sum+(p*q);

            }
            if(sum!=0) {cnt++;
            C->data[cnt].e=sum;
            C->data[cnt].row=i;
            C->data[cnt].col=j;}

        }
    }
    C->len=cnt;

}

int main()
{
    TSMatrix A,B,C;
    createTSMatrix(&A);
    createTSMatrix(&B);
    MulTSMatrix(&A,&B,&C);
    printMatrix(&C);
    return 0;

}

第二个程序：
首先将矩阵每行的非0元个数记下来，那么矩阵每行第一个非0元在三元表的位置就是上一行非0元个数加上上一行首个非0元位置之和。这样就可以不用遍历三元表，就可以快速找到相应的三元组表元素。相乘时先将结果存入一个数组中，然后取其中非0元素存入新的三元组表。最后输出新三元组表即可。

#include <stdio.h>
#include <stdlib.h>

struct Triple
{
    int ti;
    int tj;
    int value;
};

struct tripleList
{
    struct Triple T[2000];
    int li;
    int lj;
    int ln;
};

void createNewTripleList (struct tripleList *list);
void getRowPot (struct tripleList *list,int rowPot[]);
void clear (struct tripleList *list);
void printTripleList (struct tripleList *list);
void mul (struct tripleList *list1,struct tripleList *list2,struct tripleList *list3,int rowPot1[],int rowPot2[]);
void run ();

int main()
{
    run ();

    return 0;
}

void run ()
{
    int rowPot1[2000]={0},rowPot2[2000]={0};
    struct tripleList list1,list2,list3;

    createNewTripleList (&list1);//输入两个三元组表
    createNewTripleList (&list2);
    getRowPot (&list1,rowPot1);//得到它们的位置数组
    getRowPot (&list2,rowPot2);

    mul (&list1,&list2,&list3,rowPot1,rowPot2);//相乘
    printTripleList (&list3);//输出
}
void createNewTripleList (struct tripleList *list)
{
    int i=0,a,b,c;
    scanf ("%d?%d",&(list->li),&(list->lj));//输入行数列数
    while (1)
    {
        scanf ("%d?%d?%d",&a,&b,&c);//输入行 列 数据
        if (a==0&&b==0&&c==0)//都为0时停止输入
        {
            break;
        }
        list->T[i].ti=a-1;//赋值，因为题目输入的行列数据是从1开始的，这里将它转为以0开始，最后输出时在加上1
        list->T[i].tj=b-1;
        list->T[i].value=c;
        i++;
    }
    list->ln=i;//得到三元组表元素个数
}

void printTripleList (struct tripleList *list)
{
    int i;
    for (i=0;i<=list->ln-1;i++)//输出三元组表的所有元素
    {
        printf ("%d?%d?%d\n",list->T[i].ti+1,list->T[i].tj+1,list->T[i].value);
    }
}

void mul (struct tripleList *list1,struct tripleList *list2,struct tripleList *list3,int rowPot1[],int rowPot2[])
{
    int i,j,k,l,no,max,n,len1,len2,A[2000]={0};
    list3->li=list1->li;//得到行列
    list3->lj=list2->lj;
    for (i=0,n=0;i<=list1->li-1;i++)//遍历第一个矩阵的行
    {
        len1=rowPot1[i+1]-1;//得到这一行的所有非0元在三元组表的位置区间的右端
        for (j=rowPot1[i],max=0;j<=len1;j++)//在这一行所有非0元在三元组表中的位置区间中遍历
        {
            len2=rowPot2[list1->T[j].tj+1]-1;//得到第二个矩阵中列号与上一个for中的行号相等的所有非0元在三元组表的位置区间的最左端
            for (k=rowPot2[list1->T[j].tj];k<=len2;k++)//在这一行所有非0元在三元组表中的位置区间遍历
            {
                no=list2->T[k].tj;
                A[no]+=list1->T[j].value*list2->T[k].value;//在数组中添加相乘结果
                max=no>max?no:max;
            }
        }
        for (l=0;l<=max;l++)
        {
            if (A[l]!=0)//将非0的结果存入新的三元组表中
            {
                list3->T[n].ti=list1->T[j-1].ti;
                list3->T[n].tj=l;
                list3->T[n].value=A[l];
                ++n;
                A[l]=0;
            }
        }
    }
    list3->ln=n;//得到新三元组表的元素个数
}

void getRowPot (struct tripleList *list,int rowPot[])
{
    int n[2000]={0};
    int i,pre1=0,pre2=0;
    for (i=0;i<=list->ln-1;i++)//得到矩阵每行的非0元个数
    {
        (n[list->T[i].ti])++;
    }
    for (i=0;i<=list->li;i++)
    {
        rowPot[i]=pre1+pre2;//本行第一个非0元素在三元组表中的位置，上一行的非0元个数加上上一行第一个非0元在三元组表中的位置
        pre1=n[i];
        pre2=rowPot[i];
    }
}

运行截图：

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

//稀疏矩阵存储结构体 第一个元素为矩阵头，包含行列长度，元素总个数
typedef struct
{
	int row;
	int col;
	int element;
}sparse_mat;

void SparseMatrixRectPrint(sparse_mat* s_mat);
void SparseMatrixTriPrint(sparse_mat* s_mat);
sparse_mat* SparseMatrixMul(sparse_mat* s_mat_A, sparse_mat* s_mat_B);

int _tmain(int argc, _TCHAR* argv[])
{
	int i, j, k;
	const int mat_A_row = 4;
	const int mat_A_col = 4;
	const int mat_B_row = 4;
	const int mat_B_col = 4;

	//原矩阵
	int mat_A[mat_A_row][mat_A_col] = { 1, 1, 0, 0,
										0, 0, 1, 0, 
										0, 1, 0, 0, 
										0, 0, 1, 0 };

	int mat_B[mat_B_row][mat_B_col] = { 1, 0, 0, 0,
										0, 1, 0, 0, 
										0, 0, 1, 0, 
										0, 0, 0, 1 };

	//计算有效元素数量
	int mat_A_ele_count = 0;
	int mat_B_ele_count = 0;

	for (i = 0; i < mat_A_row; i++)
	{
		for (j = 0; j < mat_A_col; j++)
		{
			if (mat_A[i][j] != 0) mat_A_ele_count++;
		}
	}

	for (i = 0; i < mat_B_row; i++)
	{
		for (j = 0; j < mat_B_col; j++)
		{
			if (mat_B[i][j] != 0) mat_B_ele_count++;
		}
	}

	//动态分配
	sparse_mat* sparse_m_A = (sparse_mat*)malloc((mat_A_ele_count + 1)*sizeof(sparse_mat));
	sparse_mat* sparse_m_B = (sparse_mat*)malloc((mat_B_ele_count + 1)*sizeof(sparse_mat));

	//存入稀疏矩阵信息
	sparse_m_A[0].row		= mat_A_row;
	sparse_m_A[0].col		= mat_A_col;
	sparse_m_A[0].element	= mat_A_ele_count;
	sparse_m_B[0].row		= mat_B_row;
	sparse_m_B[0].col		= mat_B_col;
	sparse_m_B[0].element	= mat_B_ele_count;

	for (i = 0, mat_A_ele_count = 0; i < mat_A_row; i++)
	{
		for (j = 0; j < mat_A_col; j++)
		{
			if (mat_A[i][j] != 0)
			{
				mat_A_ele_count++;
				sparse_m_A[mat_A_ele_count].element = mat_A[i][j];
				sparse_m_A[mat_A_ele_count].row = i;
				sparse_m_A[mat_A_ele_count].col = j;
			}
		}
	}

	for (i = 0, mat_B_ele_count = 0; i < mat_B_row; i++)
	{
		for (j = 0; j < mat_B_col; j++)
		{
			if (mat_B[i][j] != 0)
			{
				mat_B_ele_count++;
				sparse_m_B[mat_B_ele_count].element = mat_B[i][j];
				sparse_m_B[mat_B_ele_count].row = i;
				sparse_m_B[mat_B_ele_count].col = j;
			}
		}
	}

	//打印原数组
	SparseMatrixRectPrint(sparse_m_A);
	SparseMatrixRectPrint(sparse_m_B);
	//SparseMatrixTriPrint(sparse_m_A); 
	//SparseMatrixTriPrint(sparse_m_B);

	//计算稀疏矩阵乘法
	sparse_mat* sparse_m_C = (sparse_mat*)SparseMatrixMul(sparse_m_A, sparse_m_B);
	SparseMatrixRectPrint(sparse_m_C);

	system("Pause");
	return 0;
}

//三元组稀疏矩阵乘法函数 极简封装 需要花费一点时间计算申请的内存 但是肯定比链表省空间啦
//Method Written By Zhonglihao
sparse_mat* SparseMatrixMul(sparse_mat* s_mat_A, sparse_mat* s_mat_B)
{
	int i, j, k;
	int s_mat_C_row			= s_mat_A[0].row;
	int s_mat_C_col			= s_mat_B[0].col;
	int s_mat_A_ele_count	= s_mat_A[0].element;
	int s_mat_B_ele_count   = s_mat_B[0].element;

	//判断是否能够相乘 或 有一个全为0 那就不用乘啦
	if (s_mat_A[0].col != s_mat_B[0].row) return NULL;
	if (s_mat_A_ele_count == 0 || s_mat_B_ele_count == 0)
	{
		sparse_mat* s_mat_C	= (sparse_mat*)malloc((1)*sizeof(sparse_mat));
		s_mat_C[0].row		= s_mat_C_row;
		s_mat_C[0].col		= s_mat_C_col;
		s_mat_C[0].element	= 0;
		return s_mat_C;
	}

	//申请一个长度为B列宽的缓存 两个用途 计算输出大小时做列封禁，计算相乘时做和缓存
	int* col_buffer = (int*)malloc(s_mat_C_col*sizeof(int));
	//清空缓存区
	for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;

	//判断需要输出的三元大小申请内存
	int malloc_element_count = 0;
	for (i = 1; i <= s_mat_A_ele_count; i++)
	{
		if (i >= 2 && s_mat_A[i].row != s_mat_A[i - 1].row) //换行解禁
		{
			for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;
		}

		for (j = 1; j <= s_mat_B_ele_count; j++)
		{
			if ((s_mat_A[i].col == s_mat_B[j].row) && col_buffer[s_mat_B[j].col] != 1)//没有列封禁
			{
				col_buffer[s_mat_B[j].col] = 1;//列封禁
				malloc_element_count++;
			}
		}
	}

	sparse_mat* s_mat_C		= (sparse_mat*)malloc((malloc_element_count + 1)*sizeof(sparse_mat));
	s_mat_C[0].row			= s_mat_C_row;
	s_mat_C[0].col			= s_mat_C_col;
	s_mat_C[0].element		= malloc_element_count;
	int s_mat_C_ele_count	= 0;//用于存入元素时做指针

	//开始进行乘法相乘
	for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;//清理列缓存
	for (i = 1; i <= s_mat_A_ele_count; i++)
	{
		for (j = 1; j <= s_mat_B_ele_count; j++)
		{
			if (s_mat_A[i].col == s_mat_B[j].row)//有效用 压入缓存区
				col_buffer[s_mat_B[j].col] += s_mat_A[i].element * s_mat_B[j].element;
		}

		//如果要换行或者是最后一行
		if (((i != s_mat_A_ele_count) && (s_mat_A[i].row != s_mat_A[i + 1].row)) || i == s_mat_A_ele_count)
		{
			//扫描缓存组
			for (k = 0; k < s_mat_C_col; k++)
			{
				//如果该点不是0 压入三元组 清零缓存
				if (col_buffer[k] != 0)
				{
					s_mat_C_ele_count++;
					s_mat_C[s_mat_C_ele_count].row = s_mat_A[i].row;
					s_mat_C[s_mat_C_ele_count].col = k;
					s_mat_C[s_mat_C_ele_count].element = col_buffer[k];
					col_buffer[k] = 0;
				}
			}
		}
	}

	//释放缓存 返回结果
	free(col_buffer);
	return s_mat_C;
}

//稀疏矩阵打印 按矩形打印 需要确定三元组按Z排列有序
void SparseMatrixRectPrint(sparse_mat* s_mat)
{
	//获取行列信息
	int i, j;
	int row = s_mat[0].row;
	int col = s_mat[0].col;

	//打印元素递增 前提是三元组按照行列顺序排好，就只需要递增下标
	int ele_count = 1;

	//按矩阵扫描打印
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			if (i == s_mat[ele_count].row && j == s_mat[ele_count].col)
			{
				printf("%d\t", s_mat[ele_count].element);
				ele_count++;
			}
			else
			{
				printf("0\t");
			}
		}//for
		printf("\n");
	}//for
	
	//跳空换行 返回
	printf("\n");
	return;
}

//稀疏矩阵打印 按三元组结构打印
void SparseMatrixTriPrint(sparse_mat* s_mat)
{
	int i, j;
	int ele_count = s_mat[0].element;

	//按顺序打印
	for (i = 1; i <= ele_count; i++)
	{
		printf("%d\t%d\t%d\n", s_mat[i].row, s_mat[i].col, s_mat[i].element);
	}

	//跳空换行 返回
	printf("\n");
	return;
}