矩阵这章还有几种特殊矩阵，像对称矩阵，三角矩阵，带状矩阵这种只需要考虑一下一维数组的映射关系就行，只有稀疏矩阵需要重新描述。
稀疏矩阵就是元素数量较少，如果使用常规矩阵模型浪费空间且运算时效率过差。
稀疏矩阵的描述方法有很多，数组，数组描述的线性表，链表都可以描述且各有优缺点
先写一个用数组描述的，数组描述简单，查询快，但修改元素时都需要整个重写数组，性能较差。
首先写一个结构体用来存储每个元素的行号列号和数值
template<class T>//模板函数
struct element
{
int row, col;//行号，列号
T value;//值
void swap(element<T> b) {//复制
col = b.col;
row = b.row;
value=b.value;
}
};之后是稀疏矩阵的定义
template<class T>
class matrix_array//基于数组的稀疏矩阵
{
public:
matrix_array(int,int);//构造函数
matrix_array(T ** a, int r, int c);//使用二维数组构造并赋值
matrix_array(const matrix_array<T>&);//复制已有的稀疏矩阵
~matrix_array() { delete[]ls; }
void printout();//打印矩阵
int getrows() { return rows; }//返回行数
int getcols() { return cols; }//返回列数
T** output();//输出二维数组
matrix_array<T> transposition();
matrix_array<T> add(const matrix_array<T>&);
void change(int row, int col, T c_value);
protected:
int rows, cols, num;//行数，列数，元素个数
element<T> *ls;//element数组
};首先是构造函数，一个是默认构造，一个是用二维数组赋值，一个是复制已有稀疏矩阵
//默认构造函数
template<class T>
matrix_array<T>::matrix_array(int r, int c) {//输入行号列号
rows = r;
cols = c;
num = 0;//默认没有非0元素
ls = new element<T>[0];
}
//使用二维数组构造
template<class T>
matrix_array<T>::matrix_array(T ** a, int r, int c) {//输入二维数组，行号和列号
rows = r;
cols = c;
int n = 0;//计算非0元素个数
for(int i=0;i<r;i++)
for (int j = 0; j < c; j++) {
if (a[i][j] != 0)
n++;
}
num = n;
ls = new element<T>[num];
n = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (a[i][j] != 0){
ls[n].row = i + 1;//输入行号，从1开始，所以加1
ls[n].col = j + 1;//输入列号，从1开始，所以加1
ls[n].value = a[i][j];//输入值
n++;
}
}
}
//构造函数-复制已有稀疏矩阵
template<class T>
matrix_array<T>::matrix_array(const matrix_array<T> &m){//复制已有稀疏矩阵
rows = m.rows;
cols = m.cols;
num = m.num;
ls = new element<T>[num];
for (int i = 0; i < num; i++) {
ls[i].swap(m.ls[i]);
}
}下面写一个打印函数，图方便就不写重载<<了
template<class T>
void matrix_array<T>::printout() {
int n = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {//双层循环判断矩阵每个元素是否非0
if ((i == ls[n].row - 1) && (j == ls[n].col - 1))
{
cout << ls[n].value << " ";
n++;
}
else
{
cout << 0 << " ";
}
}
cout << endl;
}
}这样的打印函数虽然清晰易懂，但两层循环使得时间复杂度还是O(n^2)，虽然没有创立二维数组节省了空间，但没有发挥出稀疏数组的性能优势，下面重写一个打印函数
template<class T>
void matrix_array<T>::printout() {
int pre_row = 1, pre_col = 1;//上一个非零元素的行号，列号
for (int i = 0; i < num; i++) {//逐个非零元素处理
if (ls[i].row - pre_row > 0)//判断是否需要换行
{
for (int m = 0; m < cols - pre_col + 1;m++)//补足这行的0
cout << 0<< " ";
cout<<endl;//换行
pre_col = 1;//重置上一个非零元素的列号
pre_row++;//上一个非零元素的行号+1
}
for (int k = 0; k < ls[i].row - pre_row; k++) {//先判断当前非零元素离上个非零元素差了几行，差了两行就要输出一行0，以此类推。这里的减1是因为上一个循环实则是处理的就是差1的情况
for (int l = 0; l < cols; l++)//输出一排0
cout << 0 << " ";
cout << endl;
}
pre_row=ls[i].row;//更新pre_row;
for (int j = 0; j < ls[i].col-pre_col; j++) {//输出两个元素中间的零
cout << 0 << " ";
}
cout << ls[i].value<<" ";
pre_col = ls[i].col+1;//这里pre_col是ls[i].col+1要特别注意，因为行号和列号处理过程是不一样的，千万不能想当然。行号差一个需要处理，列号相差一个等于紧跟着，不用处理
}
//最后不能忘了剩下的0
for (int i = 0; i < cols - pre_col + 1; i++)
cout << 0 <<" ";
cout << endl;
for (int i = 0; i < rows - pre_row; i++) {
for (int l = 0; l < cols; l++)
cout << 0 << " ";
cout << endl;
}
}
写这个函数时本以为能5分钟写完，结果折腾了一个多小时，自己还是太菜了，很多地方一开始没有考虑周到。
写输出函数尤其要小心，多测试，各种情况的矩阵都要测试，比如一整行都是0，开头一行是0，最后一行是0，各种特殊情况都要重点考虑，要不然后面写其他计算函数一直出错，其实是输出函数错了却察觉不到，浪费大笔时间。
之后是一个返回二维数组的函数
//返回二维数组
template<class T>
T** matrix_array<T>::output() {
T** r = new T * [cols];//创建二维数组
for (int i = 0; i < rows; i++) {
r[i] = new T[cols]{ 0 };//每行生成全是0的一维指针
}
for(int i=0;i<num;i++){
r[ls[i].row-1][ls[i].col-1] = ls[i].value;//给非0元素赋值
}
return r;
}之后是矩阵转置，转置看上去很简单，行号列号换一下就行，但复杂的是稀疏矩阵是用数组按横向顺序存储的，直接行号列号互换顺序就错了，所以要先排个序。转置后行列互换，所以排序时列是第一索引，行是第二索引
双关键词排序其实跟但关键词排序没区别，写一个结构体的大小比较函数就行，注意写两种不同主键的比较函数
template<class T>//模板函数
struct element
{
int row, col;//行数，列数（从1开始）
T value;
int compare(element<T> b) {//双关键词比较，按先行数后列数比较，小返回0，大于等于返回1
if (row < b.row)
return 0;
else if ((row == b.row) && (col < b.col))
return 0;
else
return 1;
}
int compare_tr(element<T> b) {//双关键词比较，按先列数后行数比较，大返回1
if (col > b.col)
return 1;
else if ((col == b.col) && (row > b.row))
return 1;
else
return 0;
}
void swap(element<T> b) {//复制
col = b.col;
row = b.row;
value=b.value;
}
void swap_tr(element<T> b) {//转置复制
col = b.row;
row = b.col;
value = b.value;
}
};之后通过简单的冒泡排序得出转置后的元素的正确顺序。这里用了一个index数组来排序，就不用复制一个element数组进行排序了
//转置
template<class T>
matrix_array<T> matrix_array<T>::transposition(){
int temp;
int *index = new int[num];//index数组，用来排序
for (int i = 0; i < num; i++) index[i] = i;
for(int i=0;i<num;i++)//对index进行排序
for (int j = 0; j < num - 1; j++) {//从小到大排序
if (ls[index[j]].compare(ls[index[j + 1]])) {temp = index[j + 1]; index[j + 1] = index[j]; index[j] = temp; }
}
matrix_array<T> res(cols, rows);
res.num = num;
res.ls = new element<T>[num];
for (int i = 0; i < num; i++) {
res.ls[i].swap_tr(ls[index[i]]);
}
return res;
}到现在我们的矩阵还是静态的，下面实现对矩阵元素的修改
//修改元素
template<class T>
void matrix_array<T>::change(int row, int col, T c_value) {
element<T> new_element;//创建新元素并赋值
new_element.row = row;
new_element.col = col;
new_element.value = c_value;
if ((new_element.compare(ls[0]) == 0)&&(c_value!=0))//首先判断新元素是否在原有第一个元素前？
{
element<T>* temp = new element<T>[++num];
temp[0].swap(new_element);//第一个元素为新元素
for (int i = 1; i < num; i++)
temp[i].swap(ls[i - 1]);//后面依次复制原数组
delete[]ls;//删除原表
ls = temp;//指向新表
}
else{
for (int i = 0; i < num; i++) {
if (ls[i].row == row && ls[i].col == col) {//判断是否与已有元素坐标相同？
if (c_value != 0)//如果修改后的值不等于0,就只修改值
ls[i].value = c_value;
else if (c_value == 0) {//如果修改后的值为0，就删除当前元素
element<T>* temp = new element<T>[--num];//新建element数组，长度减一
//复制原有元素，删除修改元素
for (int j = 0; j < i; j++) {
temp[j].swap(ls[j]);
}
for (int j = i; j < num; j++) {
temp[j].swap(ls[j + 1]);
}
delete[]ls;//删除原数组
ls = temp;//重新指向
}
break;
}
if (i < num - 1) {//最后一个元素单独判断
if ((new_element.compare(ls[i]) == 1) && (new_element.compare(ls[i + 1])==0)) {//是否在两个已有元素之间？
element<T>* temp = new element<T>[++num];
for (int j = 0; j < i+1; j++)
temp[j].swap(ls[j]);
temp[i+1].swap(new_element);
for (int j = i + 2 ; j < num; j++)
temp[j].swap(ls[j-1]);
delete[]ls;
ls = temp;
break;
}
}
}
}
if((new_element.compare(ls[num]) == 1)&&(c_value)!=0)//判断新元素是否在最后一个元素后？
{
element<T>* temp = new element<T>[++num];
for (int i = 0; i < num-1; i++)
temp[i].swap(ls[i]);//依次复制原数组
temp[num - 1].swap(new_element);
delete[]ls;//删除原表
ls = temp;//指向新表
}
}最后是矩阵相加
/*---------------矩阵相加------------------------*/
template<class T>
matrix_array<T> matrix_array<T>::add(const matrix_array<T>& m) {
if (m.cols != cols || m.rows != rows) {//检查矩阵大小是否相同
cout << "矩阵大小不匹配" << endl;
abort();
}
element<T>* add_element = new element<T>[m.num + num];//结果最长不会超过原来两个矩阵有效元素个数之和
int i1 = 0, i2 = 0, i3 = 0;//设置三个索引，分别为当前矩阵非零元素，m矩阵的非零元素，结果非零元素数组add_element的索引
while (1) {
if ((i1 == num) && (i2 == m.num)) break;//同时迭代到了两个矩阵最后一个非零元素
if (i1 == num) {//第一个矩阵的非零元素先迭代到底了
for (int i = 0; i < m.num - i2; i++) {
add_element[i3].swap(m.ls[i2]);
i2++; i3++; break;
}
}
if (i2 == m.num) {//第二个矩阵的非零元素先迭代到底了
for (int i = 0; i < num - i1; i++) {
add_element[i3].swap(ls[i1]);
i1++; i3++; break;
}
}
if (ls[i1].compare(m.ls[i2]) == 2) {//当前迭代到的两个矩阵索引在相同位置
if (ls[i1].value + m.ls[i2].value != 0) {//相加后不等于0就添加新元素
add_element[i3].col = ls[i1].col;
add_element[i3].row = ls[i1].row;
add_element[i3].value = ls[i1].value + m.ls[i2].value;
i3++;
}
i1++; i2++; continue;//相加后等于0就不添加新元素，两个索引迭代一次
}
//哪个索引位置在前就添加这个索引的元素
if (ls[i1].compare(m.ls[i2]) == 0) {
add_element[i3].swap(ls[i1]);
i1++; i3++; continue;
}
if (ls[i1].compare(m.ls[i2]) == 1) {
add_element[i3].swap(m.ls[i2]);
i2++; i3++; continue;
}
}
matrix_array<T> res(rows, cols);//新建结果矩阵
res.ls = new element<T>[ i3 ];//迭代完i3就是非0元素的个数
res.num = i3;
for (int i = 0; i < i3; i++)
res.ls[i].swap(add_element[i]);
delete[]add_element;
return res;
}矩阵相乘感觉很难，不想写了，溜了
Comments NOTHING