1.对称矩阵
对称矩阵即从左上角到右下角这一条线（对称线）相对称的矩阵。
我们可以只保存对称线以下包括对称线上的数。
那么转换的新数组下标k，根据数学数列知识，令n-1=i，我们发现每一行的第一个数的行标为i(i+1)/2。
那么，k=i(i+1)/2+j(i>=j)。
如果，j>i时，可以利用aij=aji，转化为k=j(j+1)/2+i。
综上：
2.三角矩阵
上（下）三角矩阵就是对称线以上（下）元素不同，其他相同的矩阵。
对比对称矩阵，只需要多出一个内存保存相同的元素。
下三角矩阵容易得到：
?
上三角矩阵，我们可以将其关于对称线翻转。此时，i和j互换。
只需将上式i和j变换即可。
3.对角矩阵
方法一：
方法二：
?一维数组序号还可以这样求：
主对角线左下：k=3i-1，i=j+1
主对角线： k=3i，i=j
主对角线右上：k=3i+1，i=j-1
分别将一个i换成j，都得k=2i+j。
4.稀疏矩阵
稀疏矩阵就是指矩阵中零元素个数远远多于非零元素的个数，且非零元素分布无规律。
可以将稀疏矩阵每个非零元素表示成如下三元组：
#pragma once
#include<iostream>
#include<queue>
template<class T>
class triple
{
struct Node
{
int row;
int col;
T data;
Node(int first=0, int second=0,const T& third=0):row(first),col(second),data(third){}
void setNodeValue(int first, int second, const T& third)
{
row = first;
col = second;
data = third;
}
void operator=(const Node& obj)
{
if (this == &obj)
return;
row = obj.row;
col = obj.col;
data = obj.data;
}
};
Node* matrix;//三元组表
int numRow;//矩阵行数
int numCol;//矩阵列数
int size;//三元组表当前长度
int max_size;
public:
triple(int first, int second, int size = 10);
~triple() { delete []matrix; }
void setValue(int i, int j, const T& d);
T getValue(int i, int j);
void print();
//转置矩阵的三种方法
void transform1();
void transform2();
void quicktransform();
void resize();
};
template<class T>
triple<T>::triple(int first, int second, int maxsize )
{
if (first <= 0 || second <= 0 || maxsize < 0)
throw("error");
numRow = first;
numCol = second;
size = 0;
max_size = maxsize > numRow * numCol ? numRow * numCol :maxsize ;
if (max_size)
matrix = new Node[maxsize];
else matrix = nullptr;
}
template<class T>
void triple<T>::print()
{
for (int i = 0; i < size; i++)
std::cout << "row:" << matrix[i].row << " col:" <<
matrix[i].col << " value:" << matrix[i].data << std::endl;
}
template<class T>
void triple<T>::resize()
{
if (numCol * numRow == size)
throw("resize error");
Node* p = matrix;
max_size = max_size *2>numRow*numCol?numRow * numCol:max_size*2;
matrix = new Node[2 * max_size];
for (int i = 0; i < size; i++)
matrix[i] = p[i];
delete[] p;
}
template<class T>
void triple<T>::setValue(int i, int j, const T& d)
{
if (d == 0) return;
if (i < 0 || j < 0||i>=numRow||j>=numCol) throw("setValue error");
if (size >= max_size) resize();
int m=0;
for ( m = 0; m < size; m++)
{
//应该插入的地方
if (matrix[m].row > i || (matrix[m].row == i) && (matrix[m].col > j))
break;
else if (matrix[m].row == i && matrix[m].col == j)//有了直接赋值
{
matrix[m].data = d;
return;
}
}
for (int n = size - 1; n > m; n--)
matrix[n] = matrix[n - 1];
matrix[m].setNodeValue(i,j, d);
size++;
}
template<class T>
T triple<T>::getValue(int i, int j)
{
if (i < 0 || j < 0 || i >= numRow || j >= numCol) throw("getValue error");
for (int m = 0; m < size; m++)
{
if (matrix[m].row == i && matrix[m].col == j)
return matrix[m].data;
}
return -1;
}
template<class T>
void triple<T>::transform1()
{
//方法一：先换后排序
auto f = [](const Node& a, const Node& b) {return (a.row > b.row) ||
(a.row == b.row && a.col > b.col); };
std::priority_queue<Node, std::vector<Node>, decltype(f)> a(f);
for (int i = 0; i < size; i++)
{
int temp = matrix[i].row;
matrix[i].row = matrix[i].col;
matrix[i].col = temp;
a.push(matrix[i]);
}
for (int i = 0; i < size; i++)
{
matrix[i] = a.top();
a.pop();
}
return;
}
template<class T>
void triple<T>::transform2()
{
//按列插入，行相对的也是从小到大的。
Node* p = new Node[size];
for (int i = 0; i < size; i++)
p[i] = matrix[i];
std::vector<bool> visit(size, false);//标记是否改过
int count = 0;
for (int i = 0; i < numCol; i++)
{
for (int j = 0; j < size; j++)
{
if (p[j].col == i&&!visit[j])
{
int temp = p[j].row;
p[j].row = p[j].col;
p[j].col = temp;
matrix[count++] = p[j];
visit[j] = true;
}
}
}
return;
}
template<class T>
void triple<T>::quicktransform()
{
//顺序取，直接存
//需计算每列第一个元素，每列有多少个元素
int* position = new int[numCol];
position[0] = 0;
int* num = new int[numCol];
Node* temp = new Node[size];
for (int i = 0; i < size; i++)
temp[i] = matrix[i];
for (int i = 0; i < numCol; i++)//置零
num[i] = 0;
for (int i = 0; i < size; i++)//数每列的个数
num[matrix[i].col]++;
for (int i = 1; i < numCol; i++)//每列第一个元素位置等于前一列第一个元素位序加数量
position[i] = position[i - 1] + num[i - 1];
for (int i = 0; i < size; i++)
{
int t = temp[i].row;
temp[i].row = temp[i].col;
temp[i].col = t;
matrix[position[temp[i].row]++] = temp[i];
}
}
