数据结构-三元组顺序表稀疏矩阵基本 *** 作代码实现

数据结构-三元组顺序表稀疏矩阵基本 *** 作代码实现

#include 
#include 
using namespace std;

const int MAXSIZE = 100;
typedef int ElemType;
typedef struct {
	int i, j;//行列
	ElemType e;//值
}Triple;//三元组
typedef struct {
	Triple data[MAXSIZE];
	int mu, nu, tu;//行数 列数 非零元个数
}TSMatrix;//稀疏矩阵

bool CreateTSMatrix(TSMatrix& M);//构建稀疏矩阵
bool PrintTSMatrix(TSMatrix M);//以三元组格式输出稀疏矩阵
bool TransposeTSMatrix(TSMatrix M, TSMatrix& T);//将该稀疏矩阵转置
void AddTSMatrix(TSMatrix A, TSMatrix B, TSMatrix& C);//将稀疏矩阵A与B相加，结果用C返回

bool CreateTSMatrix(TSMatrix& M) {
	cout << "请输入行数与列数：" << endl;
	cin >> M.mu >> M.nu;
	int k = 0;
	while (1) {
		cout << "请输入该元素的横坐标、纵坐标、值（横坐标输入-1完成输出）";
		cin >> M.data[k].i;
		if (M.data[k].i == -1)break;
		cin >> M.data[k].j >> M.data[k].e;
		k++;
	}
	M.tu = k;
	return 1;
}
bool PrintTSMatrix(TSMatrix M) {
	cout << "该矩阵" << M.mu << "行" << M.nu << "列" << "，非零元个数为" << M.tu << endl;
	cout << "--------------" << endl;
	cout << setw(4) << "i" << setw(4) << "j" << setw(4) << "e" << endl;
	cout << "--------------" << endl;
	for (int k = 0; k < M.tu; k++)
		cout << setw(4) << M.data[k].i << setw(4) << M.data[k].j << setw(4) << M.data[k].e << endl;
	cout << "--------------" << endl;
	return 1;
}
bool TransposeTSMatrix(TSMatrix M, TSMatrix& T) {
	T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
	int num[10];//num[col]表示第col列中非零元的个数
	int cpot[10];//cpto[col]的值表示M的第col列第一个非零元在T.data中的位置
	if (T.tu) {
		int col, p, q;
		for (col = 1; col < M.nu; col++)
			num[col] = 0;//先令num全为0
		for (int k = 0; k < M.tu; k++)
			num[M.data[k].j]++;//为num赋值
		cpot[1] = 0;//M中第一列第一个非零元在T.data中必然位于第一个
		for (col = 2; col <= M.nu; col++)
			cpot[col] = cpot[col - 1] + num[col - 1];//上一列第一个非零元的位置加上一列非零元个数等于本列第一个非零元位置
		for (p = 0; p < M.tu; p++) {
			col = M.data[p].j;//M中此元素的列号
			q = cpot[col];//此元素对应到T.data中的位置号
			T.data[q].i = M.data[p].j;
			T.data[q].j = M.data[p].i;
			T.data[q].e = M.data[p].e;
			cpot[col]++;//该列存入一个元素之后，位置应后移一位
		}
	}
	return 1;
}
void AddTSMatrix(TSMatrix A, TSMatrix B, TSMatrix& C){//条件判断即可
	C.mu = A.mu;C.nu = A.nu;C.tu = 0;
	int m = 0; int n = 0; int q = 0;
	while (m < A.tu && n < B.tu) {
		if (A.data[m].i < B.data[n].i) {
			C.data[q].i = A.data[m].i;
			C.data[q].j = A.data[m].j;
			C.data[q].e = A.data[m].e;
			C.tu++;
			m++;q++;
		}
		else if (A.data[m].i == B.data[n].i) {
			if (A.data[m].j < B.data[n].j) {
				C.data[q].i = A.data[m].i;
				C.data[q].j = A.data[m].j;
				C.data[q].e = A.data[m].e;
				C.tu++;
				m++;q++;
			}
			else if (A.data[m].j == B.data[n].j) {
				if ((A.data[m].e + B.data[n].e) != 0) { 
					C.data[q].e = A.data[m].e + B.data[n].e;
					C.data[q].i = A.data[m].i;
					C.data[q].j = A.data[m].j;
					C.tu++;
					m++;n++;q++;
				}
				else {
					m++;n++;
				}
			}
			else {
				C.data[q].i = B.data[n].i;
				C.data[q].j = B.data[n].j;
				C.data[q].e = B.data[n].e;
				C.tu++;
				n++;q++;
			}
		}
		else {
			C.data[q].i = B.data[n].i;
			C.data[q].j = B.data[n].j;
			C.data[q].e = B.data[n].e;
			C.tu++;
			n++;q++;
		}
	}
	while (m < A.tu) {
		C.data[q].i = A.data[m].i;
		C.data[q].j = A.data[m].j;
		C.data[q].e = A.data[m].e;
		C.tu++;
		m++;q++;

	}
	while (n < B.tu) {
		C.data[q].i = B.data[n].i;
		C.data[q].j = B.data[n].j;
		C.data[q].e = B.data[n].e;
		C.tu++;
		n++;q++;
	}
	
}

int main()
{
	TSMatrix M1, M2;
	cout << "输入一个稀疏矩阵n";
	CreateTSMatrix(M1);
	cout << "输入完成n";
	PrintTSMatrix(M1);
	if (TransposeTSMatrix(M1, M2)) {
		cout << "转置矩阵n";
		PrintTSMatrix(M2);
	}
	else
		cout << "该矩阵无非零元素" << endl;

	TSMatrix A, B, C;
	cout << "输入稀疏矩阵An";
	CreateTSMatrix(A);
	cout << "输入完成n";
	PrintTSMatrix(A);
	cout << "输入稀疏矩阵Bn";
	CreateTSMatrix(B);
	cout << "输入完成n";
	PrintTSMatrix(B);
	if (A.mu == B.mu && A.nu == B.nu) {
		AddTSMatrix(A, B, C);
		cout << "C=A+B，矩阵C为：";
		PrintTSMatrix(C);
	}
	else
		cout << "矩阵行或列不相等，不能相加！" << endl;
	if (C.tu > C.mu * C.nu / 3)
		cout << "矩阵相加后不是稀疏矩阵！" << endl;
	return 0;
}

​

实验样例