题目描述

要求

  1. 数据类型请使用 int,本题中所有运算的结果均视作对 int 型自然溢出
  2. 各操作需在稀疏矩阵上进行，充分考虑数据的稀疏性， 不得直接或间接转换为二维数组形式计算 ，否则取消成绩

题目

  • 创建 稀疏矩阵类 （参照课本 MatrixTerm 三元组定义） ,采用行主顺序把稀疏矩阵非 0 元素映射到一维数组中,提供操作:两个稀疏矩阵相加、两个稀疏矩阵相乘、稀疏矩阵的转置、输出矩阵。
  • 键盘输入矩阵的行数、列数;并按行优先顺序输入矩阵的各元素值,建立矩阵;
  • 对建立的矩阵执行相加、相乘、转置的操作,输出操作的结果矩阵。

操作

  • 为方便操作描述,我们假设存在一个矩阵 P,下列各操作实际为对矩阵 P 的操作。
  • 重置矩阵 :
    1
    矩阵的行数n 矩阵的列数m
    [n行m列 表示矩阵中的所有元素]
    即重置矩阵 P 的尺寸为 n 行 m 列,且随后按行优先顺序输入矩阵 P 的各个元素。
  • 矩阵乘法:
    2
    矩阵的行数 矩阵的列数
    矩阵中非零元素个数t
    [t行 表示矩阵中非零元素]
    t 行非零元素已按行优先顺序给出，矩阵中非零元素的表示为 x y v，其中 x 表示行序号，y 表示列序号，v 表示非零元素值，行列序号从 1 开始。
    设输入的矩阵为 Q,若 PxQ 运算合法,则将 PxQ 的结果矩阵赋给 P,若不合法,则将 Q 赋给 P,同时输出 -1。
  • 矩阵加法:
    3
    矩阵的行数 矩阵的列数
    矩阵中非零元素个数t
    [t行 表示矩阵中非零元素]
    t 行非零元素已按行优先顺序给出，矩阵中非零元素的表示为 x y v，其中 x 表示行序号，y 表示列序号，v 表示非零元素值，行列序号从 1 开始。
    设输入的矩阵为 Q,若 P+Q 运算合法,则将 P+Q 的结果矩阵赋给 P,若不合法,则将 Q 赋给 P,同时输出 -1。
  • 输出操作:
    4
    设当前矩阵 P 的尺寸为 n 行 m 列,第一行输出矩阵 P 的行数和列数，随后 n 行按行优先顺序输出矩阵 P,每行 m 个数字,来表示当前的矩阵内容，每行数字之间用空格分隔。
  • 转置操作:
    5
    设当前矩阵 P 的尺寸为 n 行 m 列，将其转置为 m 行 n 列的矩阵，无需输出。

输入输出格式 

输入

第一行一个 w 代表操作个数，接下来若干行是各个操作,其中保证第一个操作一定为重置矩阵。

输出

当执行操作 4 时,输出矩阵 P;当执行操作 2 或 3 时,若对应运算不合法,则输出 -1。

数据结构与算法描述    

建一个列包含私有成员行数、列数、非零元素的个数初始化为0，以及存非零元素的结构体数组。

struct matrixterm {
	int row, col, value;
	void operator=(matrixterm& a) {//重载=
		row = a.row;
		col = a.col;
		value = a.value;
	}
};
class sparseMatrix {
private:
	int rows, cols;//行、列
	int num_value=0;//非零元素的个数初始化为0
	matrixterm* element;//存非零元素的结构体数组
public:
	sparseMatrix(int n, int m) {
		rows = n;
		cols = m;
		element = new matrixterm[(n+13) * (m+13)];
	}
	void operator=(sparseMatrix& a) {//重载=，将一个矩阵赋给另一个矩阵
		rows = a.rows;
		cols = a.cols;
		num_value = a.num_value;
		for (int i = 0; i < num_value; i++) element[i] = a.element[i];
	}
	void input(int x, int y, int v);
	void reset(int n, int m);
	void multiply(sparseMatrix& b);
	void add(sparseMatrix& b);
	void output();
	void transpose();
	~sparseMatrix() { delete[] element; }
};
void sparseMatrix::input(int x, int y, int v) {//输入x行序号，y列序号,v非零元素值
	element[num_value].row = x;
	element[num_value].col = y;
	element[num_value].value = v;
	num_value++;
}

重置矩阵函数：释放原来的空间，重新分配内存，将非零元素存进数组。

void sparseMatrix::reset(int n, int m) {//重置矩阵
	rows = n;
	cols = m;
	num_value = 0;
	delete[] element;//释放原来申请的空间
	element = new matrixterm[(n+13)*(m+13)];//重新分配内存
	for (int i = 1; i <= rows; i++) {
		for (int j = 1; j <= cols; j++) {
			int v;
			cin >> v;
			if (v != 0) {
				element[num_value].row = i;
				element[num_value].col = j;
				element[num_value].value = v;
				num_value++;
			}
		}
	}
}

矩阵乘法函数：当满足第一个矩阵的列数等于第二个矩阵的行数时，在声明一个类c作为结果，并用三个数组，分别记录第二个矩阵的每一行非零元素的个数、每一行第一个非零元素的索引、乘后每一行的结果。设乘法为a*b=c，当a非零元素所在的行序号等于c所求的行序号时，如果此时a的该元素所在的列序号对应的b的行序号所在行由非零元素，则将b该行的非零元素，依次与a的该元素相乘，并存到result数组中，保证result的序号和b的元素的列相等。然后讲求得的乘后每一行的结果result传到c中。

void sparseMatrix::multiply(sparseMatrix& b) {//乘法
	if (cols != b.rows) {
		*this = b;
		cout << -1 << endl;
	}
	else {
		sparseMatrix c(rows, b.cols);
		int* num_row_nz=new int[b.rows+1];//b第i行非零元素的个数
		int* row_nz_index=new int[b.rows+1];//b第i行第一个非零元素的索引（在b.element中的位置）
		int* result=new int[b.cols+1];//乘后中每一行的结果
		for (int i = 1; i <= b.rows; i++) num_row_nz[i] = 0;//初始化b每行非零个数为0
		for (int i = 0; i < b.num_value; i++) num_row_nz[b.element[i].row]++;//统计b每行非零元素的个数
		row_nz_index[1] = 0;//保证b第一行索引从第一个开始
		for (int i = 2; i <= b.rows; i++) row_nz_index[i] = row_nz_index[i - 1] + num_row_nz[i - 1];//统计b每行第一个非零元素的索引
		int id = 0;
		for (int i = 1; id < num_value; i++)//i为结果的行序号，循环停止条件为a没有了非零元素了
		{
			for (int j = 1; j <= b.cols; j++) result[j] = 0;//初始化第i行每列的结果为0
			while (element[id].row == i) {//该while循环求出第i行所有结果
				if (num_row_nz[element[id].col] != 0) {//a列与b对应的所在行，非零元素个数不为0
					for (int x = row_nz_index[element[id].col]; x < row_nz_index[element[id].col] + num_row_nz[element[id].col]; x++)
						result[b.element[x].col] += element[id].value * b.element[x].value;//该a列的值与b对应行的素有元素依次相乘，并加到结果与之对应的列中
				}
				id++;//b该行乘完一遍，换下一个
			}
			for (int p = 1; p <= b.cols; p++) {//将该行的结果传给矩阵c
				if (result[p] != 0 ) {
					c.element[c.num_value].value = result[p];
					c.element[c.num_value].row = i;
					c.element[c.num_value].col = p;
					c.num_value++;
				}
			}
		}
		*this = c;//求的结果在给P(a)
		delete[] num_row_nz;
		delete[] row_nz_index;
		delete[] result;
	}
}

矩阵加法函数：在a,b行数列数相等时，声明一个结果类c，在while循环中分别求出a,b的非零元素在整个矩阵中的索引，当a和b的索引相同时相加，如果结果为非零数则存入c中，如果a的索引小则说明此时b该位置元素为0，c存a的元素，反之存b的元素。当某一个矩阵中的元素没有后，将有剩余的数组剩下的非零元素全赋给c。

void sparseMatrix::add(sparseMatrix& b) {//加法
	if (cols != b.cols || rows != b.rows) {
		*this = b;
		cout << -1 << endl;
	}
	else {
		sparseMatrix c(rows, cols);
		int an = 0;
		int bn = 0;
		while (an < num_value && bn < b.num_value) {
			int aindex = (element[an].row-1) * cols + element[an].col;//a非零元素在整个矩阵中的索引
			int bindex = (b.element[bn].row-1) * cols + b.element[bn].col;//b非零元素在整个矩阵中的索引
			if (aindex < bindex) {//a非零，b为零
				c.element[c.num_value] = element[an];
				an++;
				c.num_value++;
			}
			else if (aindex == bindex) {//a,b都为非零
				if (element[an].value + b.element[bn].value != 0) {//相加结果非零时
					c.element[c.num_value].col = element[an].col;
					c.element[c.num_value].row = element[an].row;
					c.element[c.num_value].value = element[an].value+b.element[bn].value;
					c.num_value++;
				}
				an++;
				bn++;
			}
			else {//a为零，b非零
				c.element[c.num_value] = b.element[bn];
				bn++;
				c.num_value++;
			}
		}
		//将剩余的非零元素赋给c
		while (an != num_value) {
			c.element[c.num_value] = element[an];
			c.num_value++;
			an++;
		}
		while (bn != b.num_value) {
			c.element[c.num_value] = b.element[bn];
			c.num_value++;
			bn++;
		}
		*this = c;//将c给P(a)
	}
}

输出函数：如果在element数组中存在则输出数，否则输出0.

void sparseMatrix::output() {//输出
	cout << rows << " " << cols << endl;
	int t = 0;
	for (int i = 1; i <= rows; i++) {
		for (int j = 1; j <= cols; j++) {
			if (t < num_value && element[t].row == i && element[t].col == j) {
				cout << element[t].value << " ";
				t++;
			}
			else {
				cout << 0 << " ";
			}
		}
		cout << endl;
	}
}

转置函数：用两个数组记录矩阵的每一列的非零元素的个数和每一列第一个非零元素的索引。这样就相当于建立了一个对原矩阵的列映射，通过每一列对应的索引传给b，而b应该是行映射的，所以完成了转置。

void sparseMatrix::transpose() {//转置
	sparseMatrix b(cols, rows);
	b.cols = rows;
	b.rows = cols;
	b.num_value = num_value;
	int* num_col_nz = new int[cols + 1];//矩阵每列的非零元素个数
	int* col_nz_index = new int[cols + 1];//矩阵每列第一个非零元素索引，因为b为行映射所以a要按列索引
	for (int i = 1; i <= cols; i++) num_col_nz[i] = 0;
	for (int i = 0; i < num_value; i++) num_col_nz[element[i].col]++;
	col_nz_index[1] = 0;
	for (int i = 2; i <= cols; i++) col_nz_index[i] = col_nz_index[i - 1] + num_col_nz[i - 1];
	for (int i = 0; i < num_value; i++) {
		int j = col_nz_index[element[i].col];//因为a为按行映射，将a中元素对应列的第一个非零数所在索引赋给j
		b.element[j].col = element[i].row;
		b.element[j].row = element[i].col;
		b.element[j].value = element[i].value;
		col_nz_index[element[i].col]++;//该列的索引到下一个非零元素
	}
	*this = b;
}

测试结果

完整代码（含注释）

#include<iostream>
using namespace std;
struct matrixterm {
	int row, col, value;
	void operator=(matrixterm& a) {//重载=
		row = a.row;
		col = a.col;
		value = a.value;
	}
};
class sparseMatrix {
private:
	int rows, cols;//行、列
	int num_value=0;//非零元素的个数初始化为0
	matrixterm* element;//存非零元素的结构体数组
public:
	sparseMatrix(int n, int m) {
		rows = n;
		cols = m;
		element = new matrixterm[(n+13) * (m+13)];
	}
	void operator=(sparseMatrix& a) {//重载=，将一个矩阵赋给另一个矩阵
		rows = a.rows;
		cols = a.cols;
		num_value = a.num_value;
		for (int i = 0; i < num_value; i++) element[i] = a.element[i];
	}
	void input(int x, int y, int v);
	void reset(int n, int m);
	void multiply(sparseMatrix& b);
	void add(sparseMatrix& b);
	void output();
	void transpose();
	~sparseMatrix() { delete[] element; }
};
void sparseMatrix::input(int x, int y, int v) {//输入x行序号，y列序号,v非零元素值
	element[num_value].row = x;
	element[num_value].col = y;
	element[num_value].value = v;
	num_value++;
}
void sparseMatrix::reset(int n, int m) {//重置矩阵
	rows = n;
	cols = m;
	num_value = 0;
	delete[] element;//释放原来申请的空间
	element = new matrixterm[(n+13)*(m+13)];//重新分配内存
	for (int i = 1; i <= rows; i++) {
		for (int j = 1; j <= cols; j++) {
			int v;
			cin >> v;
			if (v != 0) {
				element[num_value].row = i;
				element[num_value].col = j;
				element[num_value].value = v;
				num_value++;
			}
		}
	}
}
void sparseMatrix::multiply(sparseMatrix& b) {//乘法
	if (cols != b.rows) {
		*this = b;
		cout << -1 << endl;
	}
	else {
		sparseMatrix c(rows, b.cols);
		int* num_row_nz=new int[b.rows+1];//b第i行非零元素的个数
		int* row_nz_index=new int[b.rows+1];//b第i行第一个非零元素的索引（在b.element中的位置）
		int* result=new int[b.cols+1];//乘后中每一行的结果
		for (int i = 1; i <= b.rows; i++) num_row_nz[i] = 0;//初始化b每行非零个数为0
		for (int i = 0; i < b.num_value; i++) num_row_nz[b.element[i].row]++;//统计b每行非零元素的个数
		row_nz_index[1] = 0;//保证b第一行索引从第一个开始
		for (int i = 2; i <= b.rows; i++) row_nz_index[i] = row_nz_index[i - 1] + num_row_nz[i - 1];//统计b每行第一个非零元素的索引
		int id = 0;
		for (int i = 1; id < num_value; i++)//i为结果的行序号，循环停止条件为a没有了非零元素了
		{
			for (int j = 1; j <= b.cols; j++) result[j] = 0;//初始化第i行每列的结果为0
			while (element[id].row == i) {//该while循环求出第i行所有结果
				if (num_row_nz[element[id].col] != 0) {//a列与b对应的所在行，非零元素个数不为0
					for (int x = row_nz_index[element[id].col]; x < row_nz_index[element[id].col] + num_row_nz[element[id].col]; x++)
						result[b.element[x].col] += element[id].value * b.element[x].value;//该a列的值与b对应行的素有元素依次相乘，并加到结果与之对应的列中
				}
				id++;//b该行乘完一遍，换下一个
			}
			for (int p = 1; p <= b.cols; p++) {//将该行的结果传给矩阵c
				if (result[p] != 0 ) {
					c.element[c.num_value].value = result[p];
					c.element[c.num_value].row = i;
					c.element[c.num_value].col = p;
					c.num_value++;
				}
			}
		}
		*this = c;//求的结果在给P(a)
		delete[] num_row_nz;
		delete[] row_nz_index;
		delete[] result;
	}
}
void sparseMatrix::add(sparseMatrix& b) {//加法
	if (cols != b.cols || rows != b.rows) {
		*this = b;
		cout << -1 << endl;
	}
	else {
		sparseMatrix c(rows, cols);
		int an = 0;
		int bn = 0;
		while (an < num_value && bn < b.num_value) {
			int aindex = (element[an].row-1) * cols + element[an].col;//a非零元素在整个矩阵中的索引
			int bindex = (b.element[bn].row-1) * cols + b.element[bn].col;//b非零元素在整个矩阵中的索引
			if (aindex < bindex) {//a非零，b为零
				c.element[c.num_value] = element[an];
				an++;
				c.num_value++;
			}
			else if (aindex == bindex) {//a,b都为非零
				if (element[an].value + b.element[bn].value != 0) {//相加结果非零时
					c.element[c.num_value].col = element[an].col;
					c.element[c.num_value].row = element[an].row;
					c.element[c.num_value].value = element[an].value+b.element[bn].value;
					c.num_value++;
				}
				an++;
				bn++;
			}
			else {//a为零，b非零
				c.element[c.num_value] = b.element[bn];
				bn++;
				c.num_value++;
			}
		}
		//将剩余的非零元素赋给c
		while (an != num_value) {
			c.element[c.num_value] = element[an];
			c.num_value++;
			an++;
		}
		while (bn != b.num_value) {
			c.element[c.num_value] = b.element[bn];
			c.num_value++;
			bn++;
		}
		*this = c;//将c给P(a)
	}
}
void sparseMatrix::output() {//输出
	cout << rows << " " << cols << endl;
	int t = 0;
	for (int i = 1; i <= rows; i++) {
		for (int j = 1; j <= cols; j++) {
			if (t < num_value && element[t].row == i && element[t].col == j) {
				cout << element[t].value << " ";
				t++;
			}
			else {
				cout << 0 << " ";
			}
		}
		cout << endl;
	}
}
void sparseMatrix::transpose() {//转置
	sparseMatrix b(cols, rows);
	b.cols = rows;
	b.rows = cols;
	b.num_value = num_value;
	int* num_col_nz = new int[cols + 1];//矩阵每列的非零元素个数
	int* col_nz_index = new int[cols + 1];//矩阵每列第一个非零元素索引，因为b为行映射所以a要按列索引
	for (int i = 1; i <= cols; i++) num_col_nz[i] = 0;
	for (int i = 0; i < num_value; i++) num_col_nz[element[i].col]++;
	col_nz_index[1] = 0;
	for (int i = 2; i <= cols; i++) col_nz_index[i] = col_nz_index[i - 1] + num_col_nz[i - 1];
	for (int i = 0; i < num_value; i++) {
		int j = col_nz_index[element[i].col];//因为a为按行映射，将a中元素对应列的第一个非零数所在索引赋给j
		b.element[j].col = element[i].row;
		b.element[j].row = element[i].col;
		b.element[j].value = element[i].value;
		col_nz_index[element[i].col]++;//该列的索引到下一个非零元素
	}
	*this = b;
}
int main() {
	int w;
	sparseMatrix a(0, 0);
	cin >> w;
	for (int i = 0; i < w; i++) {
		int x;
		cin >> x;
		if (x == 1) {
			int n, m;
			cin >> n >> m;
			a.reset(n, m);
		}
		else if (x == 2) {
			int n, m, nz;
			cin >> n >> m;
			cin>> nz;//nz为非零元素个数
			sparseMatrix b(n, m);
			for (int j = 0; j < nz; j++) {
				int x, y, v;
				cin >> x >> y >> v;
				b.input(x, y, v);
			}
			a.multiply(b);
		}
		else if (x == 3) {
			int n, m, nz;
			cin >> n >> m;
			cin >> nz;
			sparseMatrix b(n, m);
			for (int j = 0; j < nz; j++) {
				int x, y, v;
				cin >> x >> y >> v;
				b.input(x, y, v);
			}
			a.add(b);
		}
		else if (x == 4) {
			a.output();
		}
		else if (x == 5) {
			a.transpose();
		}
	}
	return 0;
}

如能打赏，不胜感激[叩谢]。

# 矩阵 # 算法 # 线性代数 # c++ # 数据结构
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊