// 稀疏矩阵的三元组表示
#include <stdio.h>
#define M 6
#define N 7
#define MaxSize M*N
typedef int ElemType;
struct TupNode
{
int i, j;
ElemType data;
};
class TSMatrix
{
private:
int rows, cols, nums;
struct TupNode data[MaxSize];
public:
TSMatrix(ElemType A[M][N]);
TSMatrix(const TSMatrix &other);
TSMatrix()
{
nums = 0;
}
bool SetValue(int i, int j, ElemType x);
bool GetValue(int i, int j, ElemType &x) const;
void print() const;
TSMatrix Trans() const; //转置
};
template <typename T>
void inline Swap(T &a, T &b)
{
T tmp = a;
a = b;
b = tmp;
}
TSMatrix::TSMatrix(const TSMatrix &other)
{
rows = other.rows;
cols = other.cols;
nums = other.nums;
for (int i = 0; i<nums; i++)
{
data[i] = other.data[i];
}
}
TSMatrix TSMatrix::Trans() const { //求转置矩阵
TSMatrix value;
if (nums != 0){
for (int k = 0; k<cols; k++)
{
for (int w = 0; w<nums; w++)
{
if (data[w].j == k)
{
value.data[value.nums].i = data[w].j;
value.data[value.nums].j = data[w].i;
value.data[value.nums].data = data[w].data;
value.nums++;
}
}
}
}
return value;
}
TSMatrix::TSMatrix(ElemType A[M][N]) //以二元数组构造稀疏矩阵
{
rows = M;
cols = N;
nums = 0;
for (int i = 0; i<M; i++)
{
for (int j = 0; j<N; j++)
{
if (A[i][j] != 0)
{
data[nums].i = i;
data[nums].j = j;
data[nums].data = A[i][j];
nums++;
}
}
}
}
void TSMatrix::print() const
//打印
{
for (int i = 0; i<nums; i++)
{
printf("[ %d | %d | %d ]
", data[i].i, data[i].j, data[i].data);
}
}
bool TSMatrix::SetValue(int i, int j, ElemType x)
{
int k, w;
if (i >= rows || j >= cols) return false;
if (x == 0) //有可能出现设定值为0的情况（删除）
{
for (k = 0; data[k].i<i || data[k].j<j&&k < nums; k++);
if (data[k].i == i&&data[k].j == j)
{
//删除第k个元素
nums--;
for (w = k; w<nums; w++)
{
Swap(data[w], data[w + 1]);
}
return true;
}
else //本来就是0了
{
return true;
}
}
else
{
for (k = 0; data[k].i<i || data[k].j<j&&k < nums; k++); //空循环直接查找待插入的位置
if (data[k].i == i&&data[k].j == j)
{
data[k].data = x;
return true;
}
else
{
data[nums].data = x;
data[nums].i = i;
data[nums].j = j;
nums++;
for (w = k; w<nums; w++)
{
Swap(data[w], data[k]);
}
return true;
}
}
}
bool TSMatrix::GetValue(int i, int j, ElemType &x) const
{
int k;
if (i >= rows&&j >= cols) return false;
for (k = 0; k<rows&&data[k].i<i || data[k].j<j; k++);
if (data[k].i == i&&data[k].j == j)
{
x = data[k].data;
}
else {
x = 0;
}
return true;
}
int main()
{
ElemType A[M][N] =
{
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 2, 0, 0, 0, 0, 0 },
{ 3, 0, 0, 0, 4, 0, 0 },
{ 0, 0, 0, 5, 0, 0, 0 },
{ 0, 0, 0, 0, 6, 0, 0 },
{ 0, 0, 0, 0, 0, 7, 4 }
};
TSMatrix t = A;
printf("三元组为：
");
t.print();
printf("设定2,0,1;2,3,9之后三元组为:
");
t.SetValue(2, 0, 1);
t.SetValue(2, 3, 9);
t.print();
printf("设定5,5,0;5,6,0之后三元组为:
");
t.SetValue(5, 5, 0);
t.SetValue(5, 6, 0);
t.print();
ElemType x;
if (t.GetValue(2, 4, x)) printf("[2,4]=%d
", x);
if (t.GetValue(1, 7, x)) printf("[1,7]=%d
", x);
printf("转置矩阵三元组为：
");
t.Trans().print();
return 0;
}