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

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）

一、目的

1.了解稀疏矩阵相乘运算特点
2.知道稀疏矩阵存储，创建，显示，转置方法

二、设计要求

1.问题描述

利用稀疏的特点进行存储和计算可大大节省存储空间，并实现稀疏矩阵相乘运算

2.需求分析

（1）用三元组顺序表表示稀疏矩阵，用来实现两个矩阵相乘运算
（2）使用三元组表示稀疏矩阵的输入形式，以阵列形式列出运算结果
（3）先让用户输入矩阵的列数和行数，给出的两个矩阵行，列数是否和所要求的相对应
（4）列出菜单项，用户根据菜单进行所有操作

三、概要设计

1.主界面设计

(1)创建矩阵，输入非零元的行数列数，以及非零元个数
(2)按照行的顺序，写出两个矩阵所在非零元的数值
(3)根据菜单，再次输入

2.存储结构设计

稀疏矩阵存储结构用三元组顺序表示

//三元组的定义：
typedef  struct
{
     int  row; //行下标
     int  col; //列下标
     int  e; //元素值
}Triple;
//矩阵的定义;
     typedef  struct
     {
         Triple  data[MAXSIZE]; //三元组表
         int m ,n ,len; //行,列,非零元个数
     }TSMatrix;

3.系统功能设计

此系统通过菜单让用户输入数据后创建两个矩阵，接着对两个矩阵相乘运算，并输出结果，以此
实现以下功能
（1）首先创建两个矩阵，用户输入的行和列数，非0元个数，以及所有非零元的行列值
（2）其次两个矩阵相乘，由mult函数实现，输出矩阵A,B及（A*B）的阵列形式

四、模块设计

1.模块设计

此程序包含两个模块，主程序模块，矩阵运算模块
其调用关系是：主程序模块→矩阵运算模块

2.系统子程序及功能设计

此系统一共有7个子程序，子程序的功能和函数名如下：
（1）矩阵初始化
void initMatrix(TSMatrix *A)
（2）创建矩阵，调用(1)
void createTSMatrix(TSMatrix *A)
（3）找到m行n列元素在矩阵A的三元组表中的位置
int search(TSMatrix *A,int m, int n)
（4）两个矩阵相乘，调用(3)
void mult(TSMatrix *A,TSMatrix *B,TSMatrix *C)
（5）输出的矩阵
void print(TSMatrix *A)
（6）显示程序主函数，工作区函数
void showtip()
（7）主函数
void main()

3.函数主要调用关系

主函数7调用函数2，4，5，6
函数2在调用函数1，函数4再调用函数3

五、详细设计

1.数据类型定义

采用矩阵的三元组顺序表存储结构

//三元组的定义：
 typedef  struct
{
     int  row; //行下标
     int  col; //列下标
     int  e; //元素值
}Triple;
//矩阵的定义;
     typedef  struct
     {
         Triple  data[MAXSIZE]; //三元组表
         int m ,n ,len; //行,列,非零元个数
     }TSMatrix;

2.主要子程序详细设计

（1）主函数模块设计

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

（2）创建矩阵

void createTSMatrix(TSMatrix *A)//创建矩阵
{    int i=0;     //data未用
    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;
}

（3）输出矩阵

void print(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);
    }
}

(4)矩阵相乘

void mult(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;
}

//稀疏矩阵乘法（三元组）
#include <stdio.h>
#include <stdlib.h>

#define max 200
typedef struct Triple{
    int i,j;//i行j列
    int e;
}Triple;
typedef struct TSMaTrix{
    Triple elem[max];
    int rpos[max]; //行逻辑链接的顺序表,保存每行起始地址
    int mu,nu,tu;
}TSMatrix,*TSMatrixPtr;

TSMatrixPtr Matrix_Init(TSMatrixPtr M){
    M = (TSMatrixPtr)malloc(sizeof(TSMatrix));
    M->mu = 0;
    M->nu = 0;
    M->tu = 0;
    int i,j,x;
    scanf("%d %d",&M->mu,&M->nu);
    while(1){
        scanf("%d %d %d",&i,&j,&x);
        if(i == 0&&j==0&&x==0)
        break;
        else
        {
            M->elem[M->tu].i = i;
            M->elem[M->tu].j = j;
            M->elem[M->tu].e = x;
            M->tu++;
        }        
    }
    //计算rpos；
    int num[100];								//num[]保存每一行的非零元素个数  cpot[]保存每行元素起始地址
	for (int i = 0; i < M->mu; i++)
	num[i] = 0;								    //对num初始化
	for (int j = 0; j < M->tu; j++)
	num[M->elem[j].i]++;					
	M->rpos[0] = 0;                              
	for (int k = 1; k <= M->mu; k++)
	M->rpos[k] = M->rpos[k - 1] + num[k - 1];

    return M;
}

TSMatrixPtr MultiMatrix(TSMatrixPtr A,TSMatrixPtr B,TSMatrixPtr C){
    C = (TSMatrixPtr)malloc(sizeof(TSMatrix));
    if(A->nu != B->mu)
    printf("error");
    float temp[max];
    for(int i = 0;i<max;i++)//初始化
    temp[i] = 0;

    C->mu = A->mu;
    C->nu = B->nu;
    C->tu = 0;
    C->rpos[0] = 0;

    int arow,brow,ccol,p,q,ta,tb;

    if(A->tu*B->tu != 0){
        for(arow=1;arow <= A->mu;arow++)
        {
            for(int i = 0;i<max;i++)//初始化
            temp[i] = 0;
            C->rpos[arow] = C->tu;

            if (arow < A->mu)						//获得A的该行非0元数
				ta = A->rpos[arow + 1];
			else
				ta = A->tu; 
            for(p = A->rpos[arow] ; p < ta ; ++p)//A->elem[p];
            {
                brow = A->elem[p].j;
                if (brow < B->mu)									//取B的列标行的非0数
					tb = B->rpos[brow + 1];
				else
					tb = B->tu;
                for(q = B->rpos[brow];q < tb ;++q)
                {
                    ccol = B->elem[q].j;
                    temp[ccol] +=A->elem[p].e * B->elem[q].e;//累加
                }

            }

            for(ccol = 1;ccol <= C->nu; ccol++)
            {
                if(temp[ccol] != 0)
                {
                    C->elem[C->tu].i = arow;
                    C->elem[C->tu].j = ccol;
                    C->elem[C->tu].e = temp[ccol];
                    C->tu++;
                }    
            }
        }
    }
    return C;
}

void Print_List(TSMatrixPtr M){
    for(int i = 0;i<M->tu;i++)
    {
        printf("%d %d %d\n",M->elem[i].i,M->elem[i].j,M->elem[i].e);
    }
}
int main(){
    TSMatrixPtr A,B,C;
    A = Matrix_Init(A);
    B = Matrix_Init(B);
    C = MultiMatrix(A,B,C);
    Print_List(C);

    return 0;
}