11、稀疏矩阵的压缩存储

1、稀疏矩阵的压缩存储定义和初始化

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
#include<memory.h>#define ElemType int
#define MAXSIZE 100typedef struct Triple{int row;//数据所在行 int col;//数据所在列 ElemType value;//数据 
}Triple;typedef struct SMatrix{Triple data[MAXSIZE];int total_row;//总行数 m行 int total_col;//总列数  n行int not_zero_count;//非零元素个数 
}SMatrix;// Spare Mastrixvoid CreateMatrix(SMatrix *M){FILE *fp = fopen("C:\\Users\\16326\\Desktop\\ds\\matrix.txt","r");if(fp == NULL){exit(1);}fscanf(fp, "%d %d", &M->total_col, &M->total_row);//printf("%d %d", M->mu, M->nu);int value;int k = 0;//记录data数组下标 ,也是非零元素个数 int i =0, j = 0;for(i = 0;i < M->total_col;i++){//遍历行 for(j = 0;j < M->total_row;j++){//遍历列 fscanf(fp,"%d",&value);if(value != 0){M->data[k].value = value;//记录数据 M->data[k].row = i;//记录行 M->data[k].col = j;//记录列k++; //非零元素个数 ++
            }}}M->not_zero_count = k;//记录非零元素个数 fclose(fp);//关闭流 
}
/*

matrix.txt

6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
*/

2、稀疏矩阵转置和快速转置方法

//将 M 转置后储存到 T 中 
void transposeMatrix(SMatrix *M,SMatrix *T){T->total_row = M->total_col;T->total_col = M->total_row;T->not_zero_count = M->not_zero_count;int i = 0,k = 0,q = 0;//遍历列,从第一列开始转置for(i;i < M->total_col;i++){//遍历所有非零元素 for(k = 0;k < M->not_zero_count;k++){if(M->data[k].col == i){T->data[q].value = M->data[k].value;T->data[q].col = M->data[k].row;T->data[q].row = M->data[k].col;q++;}}} }void FastTransposeMatrix(SMatrix* M,SMatrix* T){if(M->not_zero_count == 0)return;T->total_row = M->total_col;T->total_col = M->total_row;T->not_zero_count = M->not_zero_count;//用于记录每一列非零元素的个数 int* num = (int*)malloc(sizeof(int) * M->total_col);assert(num != NULL);//用于记录每一列的应该存储在数组的下标位置int* cpos = (int*)malloc(sizeof(int) * M->total_col);    assert(cpos != NULL);int col = 0;//初始化num for(col = 0;col < M->total_col;col++)num[col] = 0;//遍历所有的非零元素,记录每一列非零元素的个数int i = 0;for(i = 0;i < M->not_zero_count;i++){col = M->data[i].col;num[col]++; } //初始化第一列的元素在对应起始下标位置为0 cpos[0] = 0;//其他列为上一列的起始位置加上一列非零元素的个数 for(col = 1;col < M->total_col;col++){cpos[col] = cpos[col - 1] + num[col - 1];}//进行转置int pos = 0;for(i = 0;i < M->not_zero_count;i++){//获取该元素所在列 col = M->data[i].col;//获取该元素应该存储在目标数组的下标 pos = cpos[col]; T->data[pos].value = M->data[i].value;T->data[pos].col = M->data[i].row;T->data[pos].row = M->data[i].col;//该列的下一个元素存储在目标数据下标 cpos[col]++;} 
}

3、其他方法实现

void PrintMatrix(SMatrix *M){ int i = 0;printf("row=%d, col=%d\n",M->total_row,M->total_col); for(i = 0;i < M->not_zero_count;i++){//注意：行和列从0开始printf("(%d,%d,%d)\n",M->data[i].row,M->data[i].col,M->data[i].value);}
}void CopyMatrix(SMatrix *M, SMatrix *T){T->total_row = M->total_row;T->total_col = M->total_col;T->not_zero_count = M->not_zero_count;int k = 0;for(k;k < M->not_zero_count;k++){T->data[k].row = M->data[k].row; T->data[k].col = M->data[k].col; T->data[k].value = M->data[k].value; }
}