编辑代码

#include<iostream>
template<class t>
class triplet
{
private:
	//矩阵行数、列数、非零元个数
	int mu, nu, tu;
	//矩阵元素类型
	typedef struct _elem {
		//元素所在行列
		int i, j;
		t val;
		_elem() {
			i = 0, j = 0, val = 0;
		}
		_elem(const _elem& e) {
			i = e.i, j = e.j, val = e.val;
		}
		_elem(int i, int j, const t& val)
			: i(i), j(j), val(val)
		{
		}
		void show() {
			cout << '<' << i << ',' << j << ',' << val << '>';
		}
	}elem;
	elem* data;
	//记录各行首元素在data中的位置,下标从1开始有效
	int* crow;
public:
	triplet();
	triplet(int m, int n, int* args, int len);
	triplet(int m, int n);
	~triplet();
	void show();
	triplet<t> transposition();
	triplet<t> multiply(const triplet<t>& other);
	void setCrow();
	void insert(int row, int column, int val);
};
template<class t>
triplet<t>::triplet()
{
	mu = 0, nu = 0, tu = 0;
	data = nullptr;
	crow = nullptr;
}
template<class t>
triplet<t>::triplet(int m, int n, int* args, int len) :mu(m), nu(n), tu(len / 3)
{
	data = new elem[len / 3];
	for (int i = 0, k = 0, _k = 0; i < len; i += 3, k += 1)
	{
		//三元组插入时按照行序为主，列序为次，k为data中下一个空闲节点的坐标
		for (_k = 0; _k < k; _k++) {
			if ((args[i] == data[_k].i && args[i + 1] < data[_k].j) || args[i] < data[_k].i) {
				//_k为新节点排序后应在位置的下标
				elem* temp = new elem(data[_k]);
				data[_k].i = args[i], data[_k].j = args[i + 1], data[_k].val = args[i + 2];
				for (int k2 = k; k2 > _k + 1; k2--) {
					data[k2] = data[k2 - 1];
				}
				data[_k + 1] = *temp;
				delete temp;
				break;
			}
		}
		if (_k >= k) {
			data[k].i = args[i], data[k].j = args[i + 1], data[k].val = args[i + 2];
		}
	}
	crow = new int[m + 1];
	for (int i = 0; i < m + 1; i++) crow[i] = 0;
	for (int i = 0; i < tu; i++) crow[data[i].i == m ? 0 : data[i].i + 1]++;
	for (int i = 3; i < m + 1; i++) crow[i] += crow[i - 1];
}
template<class t>
triplet<t>::triplet(int m, int n)
{
	mu = m, nu = n, tu = 0;
	data = nullptr;
	crow = nullptr;
}
template<class t>
triplet<t>::~triplet()
{
	if (data != nullptr) 
	{
		delete[]data;
	}
	if (crow != nullptr) 
	{
		delete[]crow;
	}
}
template<class t>
void triplet<t>::show()
{
	for (int i = 0; i < tu; i++) {
		cout << '<' << data[i].i << ','
			<< data[i].j << ',' << data[i].val << '>' << endl;
	}
	for (int i = 1; i <= mu; i++) {
		cout << crow[i] << '\t';
	}
	cout << endl;
}
template<class t>
triplet<t> triplet<t>::transposition()
{
	elem* temp = new elem[tu];
	int* ccol = new int[nu+1];
	int* args = new int[tu * 3];
	for (int i = 0; i <= nu; i++) ccol[i] = 0;
	for (int i = 0; i < tu; i++) 
	{ ccol[data[i].j == nu ? 0 : data[i].j + 1]++; }
	for (int i = 3; i <= nu; i++)
	{ccol[i] += ccol[i - 1];}
	for (int i = 0; i < tu; i++) {
		temp[ccol[data[i].j]++] = data[i];
	}
	for (int i = 0, k = 0; i < tu; i++, k+=3) {
		args[k] = temp[i].j;
		args[k+1] = temp[i].i;
		args[k+2] = temp[i].val;
	}
	triplet<t> res(nu, mu, args, tu * 3);
	delete[] temp;
	delete[] ccol;
	delete[] args;
	return res;
}
template<class t>
triplet<t> triplet<t>::multiply(const triplet<t>& other)
{
	//判断是否能相乘
	if (nu != other.mu) {
		cout << "矩阵无法相乘" << endl;
		triplet<t> res;
		return res;
	}
	//每次处理一行，用temp_rows保存中间结果，在将其压入res中
	int* temp_rows = new int[other.nu + 1];
	triplet<t> res(mu, other.nu);
	//triplet<t>* res = new triplet<t>(mu, other.nu);
	for (int rows = 1; rows <= mu; rows++)
	{
		for (int i = 0; i <= other.nu; i++) temp_rows[i] = 0;
		//记录this当前行元素下标的范围
		int left1 = crow[rows], left2 = 0, right1 = 0, right2 = 0;
		if (rows == mu)right1 = tu - 1;
		else {
			right1 = crow[rows+1] - 1;
		}
		//处理每个元素，将其与另一矩阵对应行的每个元素相乘，再将结果求和
		for (int i = left1; i <= right1; i++)
		{
			left2 = other.crow[data[i].j];
			if (data[i].j == nu) right2 = other.tu - 1;
			else right2 = other.crow[data[i].j + 1] - 1;
			for (int j = left2; j <= right2; j++)
			{
				temp_rows[other.data[j].j] += data[i].val * other.data[j].val;
			}
		}
		//将第rows行元素放入目标数组
		for (int k = 1; k <= other.nu; k++) {
			if (temp_rows[k]) {
				res.insert(rows, k, temp_rows[k]);
			}
		}
	}
	delete[]temp_rows;
	return res;
}
template<class t>
void triplet<t>::setCrow()
{
	//没有元素，无需执行
	if (tu == 0) return;
	//若为空，需分配空间，并初始化为零
	if (crow == nullptr) {
		crow = new int[mu + 1];
		if (!crow) exit(0);
	}
	for (int i = 0; i <= mu; i++)crow[i] = 0;
	//crow[i]保存第i-1行元素总个数
	for (int i = 0; i < tu; i++) {
		crow[data[i].i == mu ? 0 : data[i].i + 1]++;
	}
	//第一行默认为0，从第二行起，每一行新值为其本身所保存的值与其前一行的值之和
	for (int i = 3; i <= mu; i++) crow[i] += crow[i - 1];
}
template<class t>
void triplet<t>::insert(int row, int column, int val)
{
	//新建节点
	elem* temp = new elem(row, column, val);
	//判断是否需扩大data
	if (data == nullptr) {
		data = new elem[1];
		data[0] = *temp;
		tu++;
	}
	else {
		elem* newbase = new elem[++tu];
		//标识是否插入
		bool get = 0;
		for (int i = 0, j = 0; i < tu && j < tu - 1; i++)
		{
			//不同行比较行，同行比较列
			if (!get && (data[j].i > temp->i || (data[j].i == temp->i && data[j].j > temp->j))) {
				newbase[i] = *temp;
				get = true;
			}
			else if(data[j].i == temp->i && data[j].j == temp->j) {
				cout << "插入元素重复" << endl;
				cout << data[j].i << ',' << data[j].j << ',' << data[j].val << endl;
				newbase[i] = data[j++];
				newbase[i].val = temp->val;
			}
			else {
				newbase[i] = data[j++];
			}
		}
		if (newbase[tu - 1].i == 0) {
			newbase[tu - 1] = *temp;
		}
		delete[]data;
		data = newbase;
	}
	delete temp;
	setCrow();
	return;
}

template<class t>
class matrix_LN2
//十字链表存储稀疏矩阵
{
private:
	typedef struct _elem {
		int i, j;
		t val;
		_elem* down, *right;
		_elem() {
			i = 0, j = 0, val = 0;
			down = nullptr, right = nullptr;
		}
		_elem(int _i, int _j, t _val) :i(_i), j(_j), val(_val) {
			down = nullptr, right = nullptr;
		}
	}elem;
	int mu, nu, tu;
	elem** hcol, **hrow;
public:
	matrix_LN2();
	matrix_LN2(int m, int n, int* args, int len);
	matrix_LN2(int m, int n);
	~matrix_LN2();
	void add(const matrix_LN2& other);
};

template<class t>
matrix_LN2<t>::matrix_LN2()
{
	mu = 0, nu = 0, tu = 0;
	hcol = nullptr, hrow = nullptr;
}

template<class t>
matrix_LN2<t>::matrix_LN2(int m, int n, int* args, int len):mu(m), nu(n), tu(len/3)
{
	if (len % 3 != 0) {
		cout << "in 'matrix_LN2<t>::matrix_LN2(int m, int n, int* args, int len)' ,len is not right" << endl;
		exit(0);
	}
	//申请行链，列链内存空间，并初始化为0
	hcol = new elem * [nu + 1];
	hrow = new elem * [mu + 1];
	for (int i = 0; i <= nu; i++)hcol[i] = nullptr;
	for (int i = 0; i <= mu; i++)hrow[i] = nullptr;
	for (int i = 0; i < len; i += 3)
	{
		int r_index = args[i], c_index = args[i + 1];
		elem* temp = new elem(r_index, c_index, args[i + 2]), *ptr = nullptr;
		if (hrow[r_index] == nullptr) hrow[r_index] = temp;
		else {
			ptr = hrow[r_index];
			while (ptr->right != nullptr && ptr->right->j < temp->j)ptr = ptr->right;
			temp->right = ptr->right;
			ptr->right = temp;
		}
		if (hcol[c_index] == nullptr) hcol[c_index] = temp;
		else {
			ptr = hcol[c_index];
			while (ptr->down != nullptr && ptr->down->i < temp->i)ptr = ptr->down;
			temp->down = ptr->down;
			ptr->down = temp;
		}
	}
}

template<class t>
matrix_LN2<t>::matrix_LN2(int m, int n):mu(m), nu(n)
{
	hcol = new elem * [nu + 1];
	hrow = new elem * [mu + 1];
	for (int i = 0; i <= nu; i++)hcol[i] = nullptr;
	for (int i = 0; i <= mu; i++)hrow[i] = nullptr;
	tu = 0;
}

template<class t>
matrix_LN2<t>::~matrix_LN2()
{
	if (tu == 0 && hcol == nullptr && hrow == nullptr) return;
	if (tu == 0) {
		delete[] hcol;
		delete[] hrow;
		return;
	}
	elem* ptr = nullptr;
	for (int i = 0; i < mu; i++) {
		hrow[i] = nullptr;
	}
	for (int i = 0; i <= nu; i++) {
		if (hcol[i] != nullptr)
		{
			for (ptr = hcol[i]; ptr != nullptr; ptr = hcol[i]) {
				hcol[i] = ptr->down;
				ptr->right = nullptr;
				cout << '<' << ptr->i << ',' << ptr->j << ',' << ptr->val << '>' << endl;
				delete ptr;
			}
		}
	}
	delete[]hcol;
	delete[]hrow;
	cout << endl;
}

template<class t>
void matrix_LN2<t>::add(const matrix_LN2& other)
{
	//修改this，使其为与other的和
	elem* pre = nullptr;
	elem* pa = nullptr, *pb = nullptr;
	for (int rows = 1; rows <= mu; rows++) {
		pa = this->hrow[rows], pb = other.hrow[rows], pre = nullptr;
		//other在该行没有元素，可直接跳过
		while (pb != nullptr)
		{
			if (pa == nullptr || pa->j > pb->j)
			{
				elem* temp = new elem(pb->i, pb->j, pb->val);
				if (pre == nullptr) this->hrow[rows] = temp;
				else {
					pre->right = temp;
				}
				temp->right = pa;
				pre = temp;
				if (this->hcol[temp->j] == nullptr || this->hcol[temp->j]->i > temp->i)
				{
					temp->down = this->hcol[temp->j];
					this->hcol[temp->j] = temp;
				}
				else {
					elem* hl = nullptr;
					for (hl = this->hcol[temp->j]; hl->down != nullptr && hl->down->i < temp->i; hl = hl->down)
					{
					}
					temp->down = hl->down;
					hl->down = temp;
				}
			}
			else if (pa != nullptr && pa->j < pb->j)
			{
				pre = pa;
				pa = pa->right;
				continue;
			}
			else if (pa->j == pb->j)
			{
				if (pa->val + pb->val != 0) {
					pa->val += pb->val;
					pa = pa->right;
				}
				else {
					elem* temp = nullptr;
					if (pre == nullptr) this->hrow[rows] = pa->right;
					else {
						pre->right = pa->right;
					}
					temp = pa;
					pa = pre->right;
					if (this->hcol[temp->j] == temp) {
						this->hcol[temp->j] = temp->down;
					}
					else {
						elem* hl = nullptr;
						for (hl = this->hcol[temp->j]; hl->down != nullptr && hl->down != temp; hl = hl->down)
						{
						}
						hl->down = temp->down;
					}
					delete temp;
				}
			}
			pb = pb->right;
		}
	}
}