rlsmatrix.c

实现稀疏矩阵的加法、减法、乘法、还有转置

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

#include "RLSMatrix.h"

Status CreateSMatrix_Triple(RLSMatrix *pM)
{
	int k, t;

	printf("输入矩阵的行数、列数和非零元个数：\n");
	scanf("%d %d %d", &pM->mu, &pM->nu, &pM->tu);//矩阵的行数、列数和非零元个数

	for (k = 1; k <= pM->mu; ++k)//初始化化rpos
		pM->rpos[k] = 0;

	printf("以行序为主序输入三元组：（格式 Row,Col,Elem)\n");
	t = 0;
	for (k = 1; k <= pM->tu; ++k){
		scanf("%d,%d,%d", &pM->data[k].i, &pM->data[k].j, &pM->data[k].e);//非零元输入
		if (t != pM->data[k].i){//记录各行第一个非零元在data中的位置
			t = pM->data[k].i;
			pM->rpos[t] = k;
		}
	}

	return 0;
}//CreateSMatrix_Triple

Status CreateSMatrix_Matrix(RLSMatrix *pM)
{
	int k, t, pos;
	int row, col;

	printf("输入矩阵的行数和列数：\n");
	scanf("%d %d", &pM->mu, &pM->nu);//矩阵的行数、列数

	for (k = 1; k <= pM->mu; ++k)//初始化化rpos
		pM->rpos[k] = 0;

	printf("输入矩阵：\n");
	pM->tu = 0;
	pos = 0;
	for (row = 1; row <= pM->mu; ++row){
		for (col = 1; col <= pM->nu; ++col){
			scanf("%d", &t);
			if (t != 0){//非零元
				++pM->tu;
				pM->data[pM->tu].i = row;
				pM->data[pM->tu].j = col;
				pM->data[pM->tu].e = t;
				if (pos != row){//记录各行第一个非零元在data中的位置
					pos = row;
					pM->rpos[pos] = pM->tu;
				}
			}
		}
	}

	return 0;
}//CreateSMatrix_Matrix

Status PrintSMatrix(const RLSMatrix *pM)
{
	int i, row, col;
	const char fmt[]="%3d";//输出格式
	
	row = 1;
	col = 1;
	for (i = 1; i <= pM->tu; ++i){
		while (row < pM->data[i].i || 
			   (row == pM->data[i].i && col < pM->data[i].j)){//输出非零元前的0
			printf(fmt, 0);
			++col;
			if (col > pM->nu){
				printf("\n");
				++row;
				col = 1;
			}
		}
		printf(fmt, pM->data[i].e);
		++col;
		if (col > pM->nu){
			printf("\n");
			++row;
			col = 1;
		}
	}//for
	while (row <= pM->mu){//输出最后一个非零元后的0
		printf(fmt, 0);
		++col;
		if (col > pM->nu){
			printf("\n");
			++row;
			col = 1;
		}
	}
	
	return OK;
}//PrintSMatrix

Status AddSMatrix(const RLSMatrix *pM, const RLSMatrix *pN, RLSMatrix *pQ)
{
	int i, j;

	if (pM->mu != pN->nu && pM->nu != pN->nu)//是否为同一类型矩阵
		return ERROR;
	
	pQ->mu = pM->mu;
	pQ->nu = pM->nu;
	pQ->tu = 0;

	//相加
	i = 1;
	j = 1;
	while (i <= pM->tu && j <= pN->tu){
		if (pM->data[i].i < pN->data[j].i){
			pQ->data[++pQ->tu]=pM->data[i++];
		}else if (pM->data[i].i > pN->data[j].i){
			pQ->data[++pQ->tu]=pM->data[j++];
		}else if (pM->data[i].j < pN->data[j].j){
			pQ->data[++pQ->tu]=pM->data[i++];
		}else if (pM->data[i].j > pN->data[j].j){
			pQ->data[++pQ->tu]=pM->data[j++];
		}else{
			++pQ->tu;
			pQ->data[pQ->tu].e=pM->data[i].e + pN->data[j].e;
			pQ->data[pQ->tu].i=pM->data[i].i;
			pQ->data[pQ->tu].j=pM->data[i].j;
			++i, ++j;
		}
	}
	//处理剩余
	while (i <= pM->tu)
		pQ->data[++pQ->tu]=pM->data[i++];
	while (j <= pN->tu)
		pQ->data[++pQ->tu]=pN->data[j++];

	return OK;
}//AddSMatrix

Status SubSMatrix(const RLSMatrix *pM, const RLSMatrix *pN, RLSMatrix *pQ)//矩阵相减
{
	int i, j;

	if (pM->mu != pN->nu && pM->nu != pN->nu)//是否为同一类型矩阵
		return ERROR;
	
	pQ->mu = pM->mu;
	pQ->nu = pM->nu;
	pQ->tu = 0;

	//相减
	i = 1;
	j = 1;
	while (i <= pM->tu && j <= pN->tu){
		if (pM->data[i].i < pN->data[j].i){
			pQ->data[++pQ->tu]=pM->data[i++];
		}else if (pM->data[i].i > pN->data[j].i){
			++pQ->tu;
			pQ->data[pQ->tu]=pM->data[j++];
			pQ->data[pQ->tu].e = -pQ->data[pQ->tu].e;
		}else if (pM->data[i].j < pN->data[j].j){
			pQ->data[++pQ->tu]=pM->data[i++];
		}else if (pM->data[i].j > pN->data[j].j){
			++pQ->tu;
			pQ->data[pQ->tu]=pM->data[j++];
			pQ->data[pQ->tu].e = -pQ->data[pQ->tu].e;
		}else{
			++pQ->tu;
			pQ->data[pQ->tu].e=pM->data[i].e - pN->data[j].e;
			pQ->data[pQ->tu].i=pM->data[i].i;
			pQ->data[pQ->tu].j=pM->data[i].j;
			++i, ++j;
		}
	}
	//处理剩余
	while (i <= pM->tu)
		pQ->data[++pQ->tu]=pM->data[i++];
	while (j <= pN->tu){
		pQ->data[++pQ->tu]=pN->data[j++];
		pQ->data[pQ->tu].e = -pQ->data[pQ->tu].e;
	}
	return OK;
}

Status MultSMatrix(const RLSMatrix *pM, const RLSMatrix *pN, RLSMatrix *pQ)//矩阵相乘
{
	int t;
	int arow, brow, ccol, p, tp, q, tq;
	ElemType *ctemp;

	if (pM->nu != pN->mu)//能否相乘
		return ERROR;

	pQ->mu = pM->mu;
	pQ->nu = pN->nu;
	pQ->tu = 0;

	if (pM->tu * pN->tu != 0){//非空矩阵
		ctemp = (ElemType*) malloc((pQ->nu + 1) * sizeof(ElemType));

		for (arow = 1; arow <= pM->mu; ++arow){//处理每一行

			for (t = 1; t <= pQ->nu; ++t)
				ctemp[t] = 0;

			pQ->rpos[arow] = pQ->tu + 1;

			if (arow < pM->mu)
				tp = pM->rpos[arow + 1];
			else 
				tp = pM->tu + 1;

			for (p = pM->rpos[arow]; p < tp; ++p){
				brow = pM->data[p].j;
				if (brow < pN->mu)
					tq = pN->rpos[brow + 1];
				else
					tq = pN->tu + 1;

				for (q = pN->rpos[brow]; q < tq; ++q){
					ccol = pN->data[q].j;
					ctemp[ccol] += pM->data[p].e * pN->data[q].e;
				}
			}//for
			for (ccol = 1; ccol <= pQ->nu; ++ccol){
				if (ctemp[ccol]){
					if (++pQ->tu > MAXSIZE){
						free(ctemp);
						return ERROR;
					}
					pQ->data[pQ->tu].i = arow;
					pQ->data[pQ->tu].j = ccol;
					pQ->data[pQ->tu].e = ctemp[ccol];
				}//if
			}//for
		}//for
		free(ctemp);
	}//if
	return OK;
}//MultSMatrix

Status FastTransposeSMatrix(const RLSMatrix *pM, RLSMatrix *pT)//转置矩阵
{
	int t, col, p, q;
	int *num, *cpot;

	pT->mu = pM->nu;
	pT->nu = pM->mu;
	pT->tu = pM->tu;

	if (pT->tu){
		num = (int*) malloc((pM->nu + 1) * sizeof(int));
		cpot = (int*) malloc((pM->nu + 1) * sizeof(int));

		for (col = 1; col <= pM->nu; ++col)
			num[col] = 0;
		for (t = 1; t <= pM->tu; ++t)
			++num[pM->data[t].j];
		pT->rpos[1] = cpot[1] = 1;
		for (col = 2; col <= pM->nu; ++col)
			pT->rpos[col] = cpot[col] = cpot[col - 1] + num[col - 1];

		for (p = 1; p <= pM->tu; ++p){
			col = pM->data[p].j;
			q = cpot[col];
			pT->data[q].i = pM->data[p].j;
			pT->data[q].j = pM->data[p].i;
			pT->data[q].e = pM->data[p].e;
			++cpot[col];
		}

		free(num);
		free(cpot);
	}//if

	return OK;
}//FastTransposeSMatrix