稀疏矩阵的应用

已知两个稀疏矩阵A和B采用三元组顺序表存储，
求：M= A+B、M= A-B和M= A×B。
【测试数据】

A的三元组表为：
（0, 2, -9）（0, 4, 5）（1, 0, -7）（1, 2, 7）（3, 1, 8）（4, 2, 9）
B的三元组表为：
（1, 0, 7）（1, 2, 7）（2, 1, 1）（3, 0, 1）（4, 4, 1）

和：

差：
积：

#include <iostream>

#define M 5
#define N 5
#define MAXSIZE 25
using namespace std;
typedef struct TupNode
{
   
	int r;
	int c;
	int data;
} Tup;

typedef struct TSMatrix
{
   
	int rows;//整个矩阵的行数
	int cols;//整个矩阵的列树
	int nums;//三元组中储存的元素个数，其实就代表着矩阵中的非零元素个数
	TupNode arr[MAXSIZE];//三元组本体
} Mat;


Mat *createMat(int (&a)[M][N])//根据传进来的二维数组引用创建三元组
{
   
	Mat *mat = new Mat;
	int i, j;
	mat->cols = N;
	mat->rows = M;
	mat->nums = 0;
	for (i = 0; i < M; i++)
	{
   
		for (j = 0; j < N; j++)
		{
   
			if (a[i][j] != 0)
			{
   
				mat->arr[mat->nums].r = i;
				mat->arr[mat->nums].c = j;
				mat->arr[mat->nums].data = a[i][j];
				mat->nums++;
			}
		}
	}
	return mat;
}
Mat *createMat(Mat *mat)//根据传进来的三元组创建三元组的拷贝，若传NULL，则返回空三元组
{
   
	Mat *res = new Mat;
	res->cols = N;
	res->rows = M;
	res->nums = 0;
	if (mat)
		*res = *mat;
	return res;
}



int binSearch(Mat *mat, int r, int c, bool returnLastPos, bool *isSucc)
{
   
	int a = 0, b = mat->nums - 1;
	int mid;
	while (a <= b)
	{
   
		mid = (a + b) / 2;
		if (mat->arr[mid].r == r && mat->arr[mid].c == c)
		{
   
			if (isSucc)
				*isSucc = true;
			return mid;
		}
		else if (mat->arr[mid].r < r || (mat->arr[mid].r == r && mat->arr[mid].c < c))
		{
   
			a = mid + 1;
		}
		else if (mat->arr[mid].r > r || (mat->arr[mid].r == r && mat->arr[mid].c > c))
		{
   
			b = mid - 1;
		}
	}
	if (isSucc)
		*isSucc = false;
	return returnLastPos ? mid : -1;
}
void value(Mat *mat, int data, int r, int c)
{
   
	if (r > M || c > N || r < 0 || c < 0)
	{
   
		cout << "Parameter illegal." << endl;
		return;
	}
	r--, c--;
	int k = binSearch(mat, r, c, false, NULL);
	if (k != -1 && data != 0)
	{
   
		mat->arr[k].data = data;
		return;
	}

	if (k == -1 && data != 0)
	{
   
		for (int l = mat->nums; l > k; l--)
			mat->arr[l] = mat->arr[l - 1];
		mat->arr[k].r = r;
		mat->arr[k].c = c;
		mat->arr[k].data = data;
		++mat->nums;
		return;
	}
	if (k != -1 && data == 0)
	{
   
		for (int i = k; i < mat->nums - 1; i++)
			mat->arr[i] = mat->arr[i + 1];
		--mat->nums;
	}
}
void print(Mat *mat)//输出整个矩阵
{
   
	int cur = 0;
	for (int i = 0; i < M; i++)
	{
   
		for (int j = 0; j < N; j++)
		{
   
			cur = 0;
			for (int k = 0; k < mat->nums; k++)
			{
   
				if (mat->arr[k].r == i && mat->arr[k].c == j)
				{
   
					cur = mat->arr[k].data;
				}
			}
			cout << cur << " ";
		}
		cout << endl;
	}
	cout << endl;
}
void destroy(Mat *mat)//销毁三元组
{
   
	delete mat;
}

Mat *MatADD(Mat *m1, Mat *m2)
{
   
	Mat *maxx, *minn;
	if (m1->nums > m2->nums)//找出元素多的矩阵
	{
   
		maxx = m1;
		minn = m2;
	}
	else
	{
   
		maxx = m2;
		minn = m1;
	}
	maxx = createMat(maxx);//拷贝一份作为结果矩阵
	for (int i = 0; i < minn->nums; i++)
	{
   
		bool isSucc = false;
		int j = binSearch(maxx, minn->arr[i].r, minn->arr[i].c, true, &isSucc);
		if (isSucc)//两个非0元素相减
			maxx->arr[j].data -= minn->arr[i].data;
		else//maxx里的是0元素，而minn里的是非0元素，此时需要在maxx里添加元素
		{
   
			for (int k = maxx->nums; k > j; k--)
				maxx->arr[k] = maxx->arr[k - 1];
			maxx->arr[j].data = minn->arr[i].data;
			maxx->arr[j].r = minn->arr[i].r;
			maxx->arr[j].c = minn->arr[i].c;
			++maxx->nums;
		}
	}
        //减法算完后，移除结果为0的元素
	int k = 0;
	for (int i = 0; i < maxx->nums; i++)
	{
   
		if (!maxx->arr[i].data)
			k++;
		else
			maxx->arr[i - k] = maxx->arr[i];
	}
	maxx->nums -= k;
	return maxx;
}
Mat *MatSUB(Mat *m1, Mat *m2)
{
   
	Mat *maxx, *minn;
	if (m1->nums > m2->nums)//找出元素多的矩阵
	{
   
		maxx = m1;
		minn = m2;
	}
	else
	{
   
		maxx = m2;
		minn = m1;
	}
	maxx = createMat(maxx);//拷贝一份作为结果矩阵
	for (int i = 0; i < minn->nums; i++)
	{
   
		bool isSucc = false;
		int j = binSearch(maxx, minn->arr[i].r, minn->arr[i].c, true, &isSucc);
		if (isSucc)//两个非0元素相加
			maxx->arr[j].data += minn->arr[i].data;
		else//maxx里的是0元素，而minn里的是非0元素，此时需要在maxx里添加元素
		{
   
			for (int k = maxx->nums; k > j; k--)
				maxx->arr[k] = maxx->arr[k - 1];
			maxx->arr[j].data = minn->arr[i].data;
			maxx->arr[j].r = minn->arr[i].r;
			maxx->arr[j].c = minn->arr[i].c;
			++maxx->nums;
		}
	}
        //加法算完后，移除结果为0的元素
	int k = 0;
	for (int i = 0; i < maxx->nums; i++)
	{
   
		if (!maxx->arr[i].data)
			k++;
		else
			maxx->arr[i - k] = maxx->arr[i];
	}
	maxx->nums -= k;
	return maxx;
}

Mat *multiply(Mat *m1, Mat *m2)
{
   
	Mat *res = createMat(NULL);
	int sum = 0;
	int i1 = -1, i2 = -1, cur = 0;
	for (int i = 0; i < m1->rows; i++)
	{
   
		for (int j = 0; j < m2->cols; j++)
		{
   
			sum = 0;
			for (int k = 0; k < m1->cols; k++)
			{
   
				i1 = binSearch(m1, i, k, false, NULL);
				i2 = binSearch(m2, k, j, false, NULL);
				if (i1 != -1 && i2 != -1)//只有两个因数都非0的时候才处理
				{
   
					sum += m1->arr[i1].data * m2->arr[i2].data;
				}
			}
			if (sum)
			{
   
				res->arr[cur].data = sum;
				res->arr[cur].r = i;
				res->arr[cur].c = j;
				cur++;
			}
		}
	}
        //更新结果矩阵的信息
	res->rows = m1->rows;
	res->cols = m2->cols;
	res->nums = cur;

	return res;
}



int main()
{
   
	int arr[M][N] = {
   {
   0, 0, -9, 0, 5}, {
   -7, 0, 7, 0, 0}, {
   0, 0, 0, 0, 0}, {
   0, 8, 0, 0, 0}, {
   0, 0, 9, 0, 0}};
	int arr2[M][N] = {
   {
   0, 0, 0, 0, 0}, {
   7, 0, 7, 0, 0}, {
   0, 1, 0, 0, 0}, {
   1, 0, 0, 0, 0}, {
   0, 0, 0, 0, 1}};
	Mat *mat = createMat(arr);
	Mat *mat2 = createMat(arr2);
    Mat *M1= MatADD(mat,mat2);
    cout<<"和："<<endl;
    print(M1);
    Mat *M2= MatSUB(mat,mat2);
    cout<<"差："<<endl;
    print(M2);
    Mat *M3= multiply(mat,mat2);
    cout<<"积："<<endl;
    print(M3);
	return 0;
}