数据结构 - 稀疏矩阵的封装(三元组,行逻辑链接)
稀疏矩阵(三元组,行逻辑连接)
本次代码将关于基本三元组和行逻辑链接表示的三元组进行了封装,还附加了两个系数矩阵的乘法和加法，欢迎大家参考测试代码。
#pragma once
#include <iostream>
#include <queue>
#include <vector>
#define MAXSIZE 100
using namespace std;
typedef struct node {
int val;
int row;
int col;
node(int v, int r, int c) :val(v), row(r), col(c) {}
node() {}
}LinkNode;
class Triad
{
public:
Triad(int x, int y) :rn(x), cn(y) {}
Triad() {} //无参构造
void input(); //输入矩阵
void show(); //展示稀疏矩阵
void GetRopt(); //获取行逻辑链接
void GetCopt(); //获取列逻辑链接
int find(int r, int c); //查找矩阵中的某一个值
Triad FastTranspose(); //转置返回一个三元组类
Triad operator*(Triad &b);//乘法运算
Triad operator+(Triad &b);//加法运算
private:
LinkNode arr[MAXSIZE + 1]; //存储非零元素
int rn; //行
int cn; //列
int tn; //非零元素个数
int copt[MAXSIZE + 1];
int ropt[MAXSIZE + 1];
};
void Triad::input()
{
int x = 0,k = 1;
for (int i = 1; i <= rn; i++)
{
for (int j = 1; j <= cn; j++)
{
cin >> x;
if (x != 0)
{
LinkNode n(x, i, j);
arr[k++] = n;
}
}
}
tn = k - 1;
}
void Triad::show()
{
for (int i = 1; i <= this->tn; i++)
{
printf("arr[%d][%d] = %d\n", this->arr[i].row, this->arr[i].col, this->arr[i].val);
}
}
int Triad::find(int i, int j)
{
for (int i = 1; i <= tn; i++)
{
if (arr[i].row == i && arr[i].col == j)
return arr[i].val;
}
return 0;
}
//获取行逻辑链接
void Triad::GetRopt()
{
if (this->tn) {
int nums[MAXSIZE];
fill(nums, nums + MAXSIZE, 0);
fill(ropt, ropt + MAXSIZE + 1, 0);
for (int i = 1; i <= this->tn; i++)
++nums[this->arr[i].row];
this->ropt[1] = 1;
for (int i = 2; i <= this->tn; i++)
this->ropt[i] = this->ropt[i - 1] + nums[i - 1];
}
}
void Triad::GetCopt()
{
if (this->tn) {
int nums[MAXSIZE];
fill(nums, nums + MAXSIZE, 0);
fill(copt, copt + MAXSIZE + 1, 0);
for (int i = 1; i <= this->tn; i++)
++nums[this->arr[i].col];
this->copt[1] = 1;
for (int i = 2; i <= this->tn; i++)
this->copt[i] = this->copt[i - 1] + nums[i - 1];
}
}
//进行转置
Triad Triad::FastTranspose()
{
Triad newmaxtri;
this->GetCopt(); //获取列链接
for (int i = 1; i <= tn; i++)
{
int col = arr[i].col;
int q = copt[col];
newmaxtri.arr[q].row = arr[i].col;
newmaxtri.arr[q].col = arr[i].row;
newmaxtri.arr[q].val = arr[i].val;
++copt[col];
}
newmaxtri.tn = this->tn;
newmaxtri.cn = this->rn;
newmaxtri.rn = this->cn;
return newmaxtri;
}
Triad Triad::operator*(Triad &b)
{
Triad ans;
if (this->cn != b.rn)
{
cout << "矩阵 a 的列数不等于矩阵 b 的行数，不能计算矩阵乘法 ab" << endl;
exit(1);
}
//矩阵ans初始化
this->GetRopt();
b.GetRopt();
ans.rn = this->rn; //初始化行
ans.cn = b.cn; //初始化列
ans.tn = 0;
int ctemp[MAXSIZE + 1];
//逐行求积
if (this->tn * b.tn != 0)
{
for (int arow = 1; arow <= this->rn; ++arow)
{
//累加器清零
fill(ctemp, ctemp + MAXSIZE + 1, 0);
//计算c中第arow行的积并存入ctemp[]中
ans.ropt[arow]= ans.tn + 1;
int tp;//this中的某一行的最后一个非零元素在copt中的位置
if (arow < this->rn) tp = this->ropt[arow + 1];
else tp = this->tn + 1;
//拿出this中当前行的每个非零元素
for (int i = this->ropt[arow]; i < tp; ++i)
{
int brow = this->arr[i].col;
int t;
if (brow < b.rn)t = b.ropt[brow + 1];
else t = b.tn + 1;
for (int q = b.ropt[brow]; q < t; ++q)
{
int ccol = b.arr[q].col;
ctemp[ccol] += this->arr[i].val * b.arr[q].val;
}
}
for (int ccol = 1; ccol <= ans.cn; ++ccol)
{
if (ctemp[ccol])
{
if (++ans.tn > MAXSIZE)
{
cout << "错误:元素个数大于最大设定值" << endl;
exit(-1);
}
LinkNode tmp;
tmp.row = arow;
tmp.col = ccol;
tmp.val = ctemp[ccol];
ans.arr[ans.tn] = tmp;
}
}
}
}
return ans;
}
Triad Triad::operator+(Triad &b)
{
Triad ans;
int ia, ib,ic,ar,br,cr,ac,bc,cc;
ia = ib = ic =1;
while (ia <= this->tn && ib <= b.tn)
{
ar = this->arr[ia].row;
br = this->arr[ib].row;
if (ar > br)
{
cr = br;
while (cr == b.arr[ib].row)
{
ans.arr[ic].row = cr;
ans.arr[ic].col = b.arr[ib].col;
ans.arr[ic].val = b.arr[ib].val;
++ib; ++ic;
}
}
else if (ar < br)
{
cr = ar;
while (cr == this->arr[ia].row)
{
ans.arr[ic].row = cr;
ans.arr[ic].col = this->arr[ia].col;
ans.arr[ic].val = this->arr[ia].val;
++ic; ++ia;
}
}
else if (ar == br)
{
cr = ar;
ac = this->arr[ia].col;
bc = b.arr[ib].col;
if (ac > bc)
{
ans.arr[ic].row = cr;
ans.arr[ic].col = bc;
ans.arr[ic].val = b.arr[ib].val;
++ic; ++ib;
}
else if (ac < bc)
{
ans.arr[ic].row = cr;
ans.arr[ic].col = ac;
ans.arr[ic].val = this->arr[ia].val;
++ic; ++ia;
}
else if (ac == bc)
{
if (this->arr[ia].val + b.arr[ib].val != 0)
{
ans.arr[ic].row = cr;
ans.arr[ic].col = ac;
ans.arr[ic].val = this->arr[ia].val + b.arr[ib].val;
++ic;
}
++ia;
++ib;
}
}
}
while (ia <= this->tn)
{
ans.arr[ic].row = this->arr[ia].row;
ans.arr[ic].col = this->arr[ia].col;
ans.arr[ic].val = this->arr[ia].val;
++ic; ++ia;
}
while (ib <= b.tn)
{
ans.arr[ic].row = b.arr[ib].row;
ans.arr[ic].col = b.arr[ib].col;
ans.arr[ic].val = b.arr[ib].val;
++ic; ++ib;
}
ans.tn = --ic;
return ans;
}如果大家有什么疑问的话可以加qq向我提出哦,欢迎各位大佬指出问题。
如果你觉得对你有所帮助的话就给我点个赞,点燃我下次写文章的动力吧 ^_^ !