声明：图片及内容基于https://www.bilibili.com/video/av97010411
特殊矩阵的压缩和存储
对称矩阵的压缩存储
三角矩阵的压缩存储
对角矩阵的压缩存储
稀疏矩阵的压缩和存储
稀疏矩阵
三元组
十字链表
完整实例
定义三元组
typedef struct {
int row, col; //三元组的行号，列号
int item;
//三元组的值
}Triple;
定义稀疏矩阵类
class TripleMatrix {
private:
Triple data[MAX]; //非零元三元组
int mu, nu, num; //矩阵的行数、列数和非零元个数
public:
TripleMatrix();
TripleMatrix(int m, int n);
~TripleMatrix();
bool setItem(int row, int col, int item);//根据行号，列号，非零元再添加一个三元组
int getItem(int row, int col);
//根据行号列号获得矩阵元素值
void printMatrix(); //按照矩阵方式打印稀疏矩阵
void printTriple(); //打印三元组数组
friend bool matrixAdd(TripleMatrix a, TripleMatrix b, TripleMatrix& result); //稀疏矩阵加法
friend bool matrixMulty(TripleMatrix a, TripleMatrix b, TripleMatrix& resultl); //稀疏矩阵乘法
};
构造函数
TripleMatrix::TripleMatrix() {
//无参构造
this->mu = 0;
this->nu = 0;
this->num = 0;
}
TripleMatrix::TripleMatrix(int m,int n) { //有参构造
this->mu = m;
this->nu = n;
this->num = 0;
}
析构函数
TripleMatrix::~TripleMatrix() {}
插入三元组
bool TripleMatrix::setItem(int row, int col, int item) {
if (row<1 || col<1 || row>mu || col>nu) return false; //异常处理
if (num == MAX) return false;
if (item == 0) return true;
int index = 0;
while (index < num) {
//稀疏矩阵排列方式先行后列
if (row > data[index].row)
index++;
else if (col > data[index].col)
index++;
else break;
}
if (row == data[index].row && col == data[index].col) { //行列均相等覆盖原值
data[index].item = item;
}
else {
for (int i = num; i > index; i--) { //index后面的元素向后移动，给新元素腾出位置
data[i] = data[i - 1];
}
data[index].row = row;
//新元素加入矩阵
data[index].col = col;
data[index].item = item;
num++;
//别忘了
}
return true;
}
获得稀疏矩阵值
int TripleMatrix::getItem(int row,int col) {
if (row > mu || col > nu) return 0;
for (int i = 0; i < num; i++) {
if (data[i].row == row && data[i].col == col)
return data[i].item;
}
return 0;
}
打印稀疏矩阵
void TripleMatrix::printMatrix() {
cout << "打印矩阵:\n" << endl;
int index = 0;
//记录矩阵中三元组的下标
for (int i = 1; i <= mu; i++) {
for (int j = 1; j <= nu; j++) {
if (i == data[index].row && j == data[index].col) {
cout << data[index].item << "\t";
index++;
//别忘了
}
else cout << "0\t";
}
cout << endl;
}
cout << "矩阵共有" << mu << "行," << nu << "列," << "共" << num << "个非零元素" << endl;
return;
}
打印三元组
void TripleMatrix::printTriple() {
cout << "打印三元组数组：" << endl;
cout<<"row\tcol\titem"<<endl;
for (int i = 0; i <num; i++) {
cout << data[i].row << "\t" << data[i].col << "\t" << data[i].item << endl;
}
}
输入元素
void inputMatrix(int m,int n,int num,TripleMatrix &triple) {
int row, col, item;
for (int i = 1; i <= num; i++) {
cout << "请输入行号，列号，非零元:";
cin >> row >> col >> item;
if (item != 0) {
if (triple.setItem(row, col, item) == false) {
cout << "输入不合法" << endl;
break;
}
}
}
}
矩阵加法
bool matrixAdd(TripleMatrix a, TripleMatrix b, TripleMatrix& result) {
if (a.mu != b.mu || b.mu != result.mu || a.nu != b.nu || b.nu != result.nu) return false;
for (int i = 1; i <= a.mu;i++) {
for (int j = 1; j <= a.nu; j++) {
int item = a.getItem(i, j) + b.getItem(i, j);
if (item != 0) {
result.setItem(i, j, item);
}
}
}
return true;
}
矩阵乘法
