代码拉取完成,页面将自动刷新
#pragma once
#include <stdexcept>
#include <iostream>
#include <cstdlib>
using namespace std;
namespace sparse_matrix
{
template <class TValue>
struct TriTuple
{
int row; // 行索引
int col; // 列索引
TValue value; // 值
// 重载=号,使默认的浅拷贝变成深拷贝
// 有返回值是为了实现“a = b = c”的效果,即链式编程
TriTuple<TValue>& operator=(const TriTuple<TValue>& tri_tuple)
{
if (&tri_tuple == this)
return *this;
row = tri_tuple.row;
col = tri_tuple.col;
value = tri_tuple.value;
return *this;
}
};
}
template <class TValue>
class SparseMatrix
{
// 重载<<,实现打印稀疏矩阵的功能
friend ostream& operator<<<>(ostream& out, SparseMatrix<TValue>& sparse_matrix);
// 重载>>,实现输入稀疏矩阵的功能
friend istream& operator>><>(istream& in, SparseMatrix<TValue>& sparse_matrix);
friend void delElememt(SparseMatrix<TValue>& sparse_matrix, int index);
private:
int rows_; // 稀疏矩阵的行数
int cols_; // 稀疏矩阵的列数
int size_; // 三元组数组当前已有元素数
int capacity_; // 三元组数组可容纳的最大元素数
sparse_matrix::TriTuple<TValue>* elements_; // 三元组数组,每一个三元组记录稀疏矩阵中的非0元素的行列下标及其存储的值
public:
explicit SparseMatrix(int capacity = 10);
SparseMatrix(const SparseMatrix<TValue>& sparse_matrix);
/*析构函数前加上 virtual 关键字的主要作用是 确保在继承关系中正确地调用析构函数,从而避免内存泄漏和资源未释放的情况。
具体来说,virtual 关键字的意义在于允许 动态绑定,确保当你通过基类指针或引用删除对象时,调用的是实际派生类的析构函数,而不是仅仅调用基类的析构函数。*/
virtual ~SparseMatrix() { delete[] this->elements_; }
int getRows() const { return this->rows_; }
void setRows(int rows) { this->rows_ = rows; }
int getCols() const { return this->cols_; }
void setCols(int cols) { this->cols_ = cols; }
/*! @brief **获取元素数** */
int getSize() const { return this->size_; }
/*! @brief **设置元素数** */
void setSize(int size) { this->size_ = size; }
/*! @brief **获取容量** */
int getCapacity() const { return this->capacity_; }
/*! @brief **设置最大元素数** */
void setCapacity(int capacity) { this->capacity_ = capacity; }
bool getElement(int row, int col, TValue& value);
bool setElement(int row, int col, TValue& value);
// 转置运算
SparseMatrix<TValue>* transpose();
// 优化的转置运算
SparseMatrix<TValue>* fastTranspose();
// 矩阵加法 // to do
SparseMatrix<TValue>& add(SparseMatrix<TValue>& sparse_matrix);
// 矩阵乘法 //to do
SparseMatrix<TValue>& multiply(SparseMatrix<TValue>& sparse_matrix);
};
template <typename TValue>
inline istream& operator>>(istream& in, SparseMatrix<TValue>& sparse_matrix)
{
cout << "输入rows,cols和size(从1开始)" << endl;
int rows = 0;
int cols = 0;
int size = 0;
in >> rows >> cols >> size;
if (size > sparse_matrix.capacity_)
throw length_error("size wrong");
sparse_matrix.setRows(rows);
sparse_matrix.setCols(cols);
sparse_matrix.setSize(size);
for (int i = 0; i < sparse_matrix.size_; i++)
{
cout << "输入第" << i + 1 << "个row,colum和term的值" << endl;
in >> sparse_matrix.elements_[i].row
>> sparse_matrix.elements_[i].col
>> sparse_matrix.elements_[i].value;
}
cout << sparse_matrix << endl;
return in;
}
template <typename TValue>
ostream& operator<<(ostream& out, SparseMatrix<TValue>& sparse_matrix)
{
out << "rows = " << sparse_matrix.getRows() << endl;
out << "cols = " << sparse_matrix.getCols() << endl;
out << "NonZero element count:" << sparse_matrix.getSize() << endl;
for (int i = 0; i < sparse_matrix.getSize(); i++)
{
out << "sparse_martix[" << sparse_matrix.elements_[i].row << "][" <<
sparse_matrix.elements_[i].col << "] = " <<
sparse_matrix.elements_[i].value << endl;
}
return out;
}
template<class TValue>
inline SparseMatrix<TValue>::SparseMatrix(int capacity)
:rows_(0),cols_(0),size_(0),capacity_(capacity)
{
if (capacity <= 0)
throw length_error("wrong max size");
this->elements_ = new sparse_matrix::TriTuple<TValue>[this->capacity_];
if (!this->elements_)
throw bad_alloc();
}
template<class TValue>
inline SparseMatrix<TValue>::SparseMatrix(const SparseMatrix<TValue>& sparse_matrix)
:rows_(sparse_matrix.getRows()),cols_(sparse_matrix.getCols()),
size_(sparse_matrix.getSize()),capacity_(sparse_matrix.getCapacity())
{
this->elements_ = new sparse_matrix::TriTuple<TValue>[this->capacity_];
if (!this->elements_)
throw bad_alloc();
for (int i = 0; i < this->size_; i++)
{
this->elements_[i] = sparse_matrix.elements_[i];
}
}
template<class TValue>
inline bool SparseMatrix<TValue>::getElement(int row, int col, TValue& value)
{
for (int i = 0; i < this->getSize(); i++)
{
if (this->elements_[i].row == row && this->elements_[i].col == col)
{
value = this->elements_[i].value;
return true;
}
}
return false;
}
template <typename TValue>
void swap_(sparse_matrix::TriTuple<TValue>* a, sparse_matrix::TriTuple<TValue>* b)
{
sparse_matrix::TriTuple<TValue> temp = *a;
*a = *b;
*b = temp;
}
template<class TValue>
inline bool SparseMatrix<TValue>::setElement(int row, int col, TValue& value)
{
if (row >= this->rows_ || col >= this->cols_)
return false;
if (this->size_ == this->capacity_ || this->size_ == this->rows_ * this->cols_)
return false;
// ---------- 2 获取该位置在elements_数组中对应的索引 ----------
// 这里的index是为了保证三元组数组是按照row从小到大,当row相同时,按照col从小到大排序
int index = -1;
for (int i = 0; i < this->size_; i++)
{
if (this->elements_[i].row == row)
{
if (this->elements_[i].col >= col)
{
index = i;
break;
}
}
else if (this->elements_[i].row > row)
{
index = i;
break;
}
}
// ---------- 3 更新非0元素的情况处理 ----------
if (index != -1
&& this->elements_[index].row == row
&& this->elements_[index].col == col)
{
this->elements_[index].value = value;
return true;
}
// ---------- 4 插入新元素的情况处理 ----------
if (index == -1)
index = this->size_;
// 新插入的三元组首先先插入到最后的位置
this->elements_[this->size_].row = row;
this->elements_[this->size_].col = col;
this->elements_[this->size_].value = value;
// 通过这个循环移动新插入的三元组到其合适的位置
for (int i = this->size_; i > index; i--)
{
swap_(&this->elements_[i],&this->elements_[i-1]);
}
// ---------- 5 更新size ----------
this->size_++; // size_加1
// ---------- 6 退出函数 ----------
return true;
}
// O(n) = T(n^2)
template<class TValue>
inline SparseMatrix<TValue>* SparseMatrix<TValue>::transpose()
{
SparseMatrix<TValue>* trans_sparse_martix = new SparseMatrix<TValue>(this->capacity_);
trans_sparse_martix->setRows(this->getCols());
trans_sparse_martix->setCols(this->getRows());
trans_sparse_martix->setSize(this->getSize());
// 原稀疏矩阵内的元素都为0
if (this->size_ == 0)
return trans_sparse_martix;
// 转置操作
int cur_elements_index = 0;
for (int row = 0; row < trans_sparse_martix->getRows(); row++)
{
for (int i = 0; i < this->size_; i++)
{
if (this->elements_[i].col == row)
{
trans_sparse_martix->elements_[cur_elements_index].row = row;
trans_sparse_martix->elements_[cur_elements_index].col = this->elements_[i].row;
trans_sparse_martix->elements_[cur_elements_index].value = this->elements_[i].value;
cur_elements_index++;
}
}
}
return trans_sparse_martix;
}
// O(n) = T(n),以空间换时间
template<class TValue>
inline SparseMatrix<TValue>* SparseMatrix<TValue>::fastTranspose()
{
// 辅助数组
int* row_sizes = new int[this->cols_]; // 表示原稀疏数组每列(该数组的下标就代表第几列)有多少个非0元素
int* iterator_positions = new int[this->cols_]; // 表示原稀疏数组每列第一个元素的在转置后的三元组数组中的位置,若下标为index,则表示第index目前的元素应该放到转置后的三元组数组的iterator_positions[index]位置
// 给转置后的稀疏矩阵的三元组数组分配内存
SparseMatrix<TValue>* trans_sparse_matrix = new SparseMatrix<TValue>(this->capacity_);
if (!trans_sparse_matrix)
throw bad_alloc();
trans_sparse_matrix->setRows(this->cols_);
trans_sparse_matrix->setCols(this->rows_);
trans_sparse_matrix->setSize(this->size_);
// 原稀疏矩阵内元素都为0
if (this->size_ == 0)
return trans_sparse_matrix;
// 构造row_sizes
for (int i = 0; i < this->cols_; i++)
{
// 初始化全为0
row_sizes[i] = 0;
}
for (int i = 0; i < this->size_; i++)
{
// 计算原稀疏数组中每列的非0元素有几个
int cur_row = this->elements_[i].col;
row_sizes[cur_row]++;
}
// 构造iterator_positions
iterator_positions[0] = 0; // 第0列的第一个非0元素在转置后的稀疏矩阵的三元组数组中的位置是0(开始)
for (int row = 1; row < this->getCols(); row++)
{
iterator_positions[row] = iterator_positions[row - 1] + row_sizes[row - 1];
}
// 快速转置,上面的辅助数组,row_size作用是为了构造iterator_positions,真正有用的便是iterator_positions
for (int i = 0; i < this->size_; i++)
{
int row = this->elements_[i].col;
int cur_elememts_index = iterator_positions[row];
trans_sparse_matrix->elements_[cur_elememts_index].row = this->elements_[i].col;
trans_sparse_matrix->elements_[cur_elememts_index].col = this->elements_[i].row;
trans_sparse_matrix->elements_[cur_elememts_index].value = this->elements_[i].value;
iterator_positions[row]++;
}
delete[] iterator_positions;
delete[] row_sizes;
return trans_sparse_matrix;
}
template<class TValue>
inline SparseMatrix<TValue>& SparseMatrix<TValue>::add(SparseMatrix<TValue>& sparse_matrix)
{
if (this->cols_ != sparse_matrix.cols_ || this->rows_ != sparse_matrix.rows_)
return *this;
// 在堆区创建对象并使用拷贝构造函数
SparseMatrix<TValue>* new_matrix = new SparseMatrix<TValue>(*this);
int cur_element_index = 0;
for (int i = 0; i < new_matrix->getSize(); i++)
{
if (cur_element_index == sparse_matrix.getSize() - 1)
break;
for (int j = cur_element_index; j < sparse_matrix.getSize(); j++)
{
if (sparse_matrix.elements_[j].row != new_matrix->elements_[i].row)
break;
if (sparse_matrix.elements_[j].row == new_matrix->elements_[i].row
&& sparse_matrix.elements_[j].col == new_matrix->elements_[i].col)
{
new_matrix->elements_[i].value += sparse_matrix.elements_[j].value;
if (j == cur_element_index)
break;
else
{
for (int z = cur_element_index; z < j; z++)
{
new_matrix->setElement(sparse_matrix.elements_[z].row,sparse_matrix.elements_[z].col,sparse_matrix.elements_[z].value);
cur_element_index = j + 1;
}
}
}
}
}
if (cur_element_index != sparse_matrix.getSize() - 1)
{
for (int i = cur_element_index; i < sparse_matrix.getSize(); i++)
{
new_matrix->setElement(sparse_matrix.elements_[i].row, sparse_matrix.elements_[i].col, sparse_matrix.elements_[i].value);
}
}
return *new_matrix;
}
template<class TValue>
inline SparseMatrix<TValue>& SparseMatrix<TValue>::multiply(SparseMatrix<TValue>& sparse_matrix)
{
if (this->rows_ != sparse_matrix.cols_ || this->cols_ != sparse_matrix.rows_)
return *this;
SparseMatrix<TValue>* new_matrix = new SparseMatrix<TValue>(*this);
SparseMatrix<TValue>* res_matrix = new SparseMatrix<TValue>();
res_matrix->setRows(this->rows_);
res_matrix->setCols(sparse_matrix.cols_);
res_matrix->setSize(this->size_);
res_matrix->setCapacity(this->capacity_);
// 转置sparse_matrix
sparse_matrix = sparse_matrix.fastTranspose();
int left = 0, right = -1; // 代表new_matrix的同一行的区间范围
bool find1 = false;
int up = 0, down = -1; // 代表sparse_matrix的同一列的区间范围
bool find2 = false;
for (int i = 0; i < new_matrix->getRows(); i++)
{
find1 = find2 = false;
// 找到left的值
for (int j = left; j < new_matrix->getSize(); j++)
{
if (new_matrix->elements_[j].row == i)
{
left = j;
find1 = true;
break;
}
}
// 找到right的值
for (int j = left; j < new_matrix->getSize(); j++)
{
if (new_matrix->elements_[j].row != i)
{
right = j - 1;
break;
}
}
// 找到up的值
for (int j = up; j < sparse_matrix.getSize(); j++)
{
if (sparse_matrix->elements_[j].row == i)
{
up = j;
find2 = true;
break;
}
}
// 找到down的值
for (int j = up; j < sparse_matrix.getSize(); j++)
{
if (sparse_matrix->elements_[j].row != i)
{
down = j - 1;
break;
}
}
if (!find1)
{
up = down + 1;
continue;
}
else if (find1 && !find2 )
{
for (int z = left; z <= right; z++)
{
delElememt(new_matrix,z);
}
}
else if (find1 && find2)
{
}
}
return *new_matrix;
}
template <typename TValue>
void delElememt(SparseMatrix<TValue>& sparse_matrix,int index)
{
for (int i = index; i < sparse_matrix.getSize() - 1; i++)
{
swap_(&sparse_matrix.elements_[i],&sparse_matrix.elements_[i+1]);
}
sparse_matrix.setSize(sparse_matrix.getSize() - 1);
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。