数据结构与算法

2024-06-29 17:24| 来源: 网络整理| 查看: 265

稀疏矩阵，矩阵中非零元素的个数远小于矩阵元素总数，且非零元素的分布没有规律，可以称该矩阵为稀疏矩阵。如果还用一个row*col的矩阵去表示这些信息，浪费空间，可以对矩阵换一种存储结构，只需要记录矩阵中非零元素的位置和值。也就是通过三元表来完成一个稀疏矩阵的表示，此外还有通过链表，这里讲一下三元表的稀疏矩阵以及稀疏矩阵的打印，转置。三元表的结构就是下图，注意它是按照先行后列升序的顺序存放的，之所以按照这个顺序存放，涉及打印的时候只需要一遍遍历稀疏矩阵判断就可以达到打印的目的，如果三元表中的每一项是乱序的还要达到打印的效果，每打印稀疏矩阵一个元素就要判断这个元素是否存在三元表，大大增加了时间复杂度。

typedef struct TRIPLE{ int row; int col; int value; }TRIPLE; typedef struct TSMATRIX { TRIPLE *triple; int matrix_row; int matrix_col; int num_count; //这个相当于triple数组的长度 }TSMATRIX;

1、三元表的初始化

初始化工作内容有：确定稀疏矩阵中元素个数以及确定稀疏矩阵的行列大小，然后给三元表申请好空间等待数据的录入。

void initSparseMatrix(TSMATRIX **tsMatrix, int matrix_row, int matrix_col, int num_count) { TSMATRIX *tp; if(NULL != (*tsMatrix) || (matrix_row*matrix_col < num_count) || matrix_col matrix_row = matrix_row; tp->matrix_col = matrix_col; tp->num_count = num_count; *tsMatrix = tp; } }

2、数据的录入

按照先行后列升序的顺序录入数据到三元表中， (row, col, value)为一组数据；

void insertDataToMatrix(TSMATRIX *tsMatrix) { int i; int row; int col; int value; printf("Insert data by row and then col ascending(row, col, value)\n"); for(i = 0; i < tsMatrix->num_count; i++) { printf("[%d/%d] data: ", i+1, tsMatrix->num_count); scanf("%d%d%d", &row, &col, &value); tsMatrix->triple[i].row = row; tsMatrix->triple[i].col = col; tsMatrix->triple[i].value = value; } }

3、打印稀疏矩阵

稀疏矩阵的信息是从三元表中得到的，三元表从第一个开始判断，然后逐个判断稀疏矩阵的位置在三元表中是否存在，存在的话就打印三元表的元素，同时三元表到下一个三元，不存在的话就打印0元素。

void showSparseMatrix(const TSMATRIX *tsMatrix) { int i; int j; int index = 0; for(i = 0; i < tsMatrix->matrix_row; i++) { for(j = 0; j < tsMatrix->matrix_col; j++) { if(tsMatrix->triple[index].row == i && tsMatrix->triple[index].col == j) { printf("%3d", tsMatrix->triple[index++].value); }else { printf("%3d", 0); } } puts(""); } puts(""); }

4、转置

稀疏矩阵的转置实质上是改变三元表的存储信息，行数据和列数据的交换，但不能是单纯的交换，交换之后的三元变也应该保持先行后列升序的规则，这一点是稀疏矩阵转置的难点，如何保持转置后的三元表仍保持先行后列升序的顺序。

方法1：每次从原三元表中按照列下标递增的方式逐个放到转置三元表里面去，转置后的三元表列是原三元表的行，转置后的三元表行是原三元表的列，那就从列着手，从小到大把列放进去，行坐标也是升序的，所以放到转置后的三元表行列也是升序的。这种方法可以达到转置的目的，但是时间复杂度高，两层循环是三元表的长度乘以矩阵的列，而不是一次遍历三元表。

//按照列下标递增的顺序去找tsMatrix->triple[j].col == i //在三元表里面当前元素的列等于i就找到一个 TSMATRIX *transposeSparseMatrix_1(const TSMATRIX *tsMatrix) { int i; int j; int index = 0; TSMATRIX *transposeMatrix = NULL; initSparseMatrix(&transposeMatrix, tsMatrix->matrix_col, tsMatrix->matrix_row, tsMatrix->num_count); for(i = 0; i < tsMatrix->matrix_col; i++) { for(j = 0; j < tsMatrix->num_count; j++) { if(tsMatrix->triple[j].col == i) { transposeMatrix->triple[index].row = tsMatrix->triple[j].col; transposeMatrix->triple[index].col = tsMatrix->triple[j].row; transposeMatrix->triple[index++].value = tsMatrix->triple[j].value; } } if(index >= tsMatrix->num_count) { //如果发现此时三元表已经填满就可以不用再进行外层循环了 break; } } return transposeMatrix; }

一次定位快速转置：首先统计原矩阵中每列有多少个非零元素，也就是转置完B的每行有多少个元素；然后计算原矩阵中每一列的元素在三元表中第几个出现，同样就是转置矩阵B每一行的元素在三元表中第几个出现；通过计算的出现位置的矩阵，挨个遍历原三元表，直接放到转置矩阵的准确位置，一遍遍历三元表就可完成。

//一次快速定位转置总体分三步 //1、先对原三元表中的元素统计每列有多少个非0元素，也就是转置完B的每行有多少个非0元素 //2、通过第一步计算B矩阵每一行元素在三元表中第几个开始 //3、把三元表A的元素直接放到B的三元表里面去一次遍历三元表A防止B中去 TSMATRIX *transposeSparseMatrix_3(const TSMATRIX *tsMatrix) { int *nums = NULL; int *postion = NULL; int i; TSMATRIX *transposeMatrix = NULL; //对转转置后的三元表初始化申请空间 initSparseMatrix(&transposeMatrix, tsMatrix->matrix_col, tsMatrix->matrix_row, tsMatrix->num_count); //申请一个记录元素出现位置的矩阵长度和原稀疏矩阵列保持一致 postion = (int *)calloc(sizeof(int), tsMatrix->matrix_col); nums = (int *)calloc(sizeof(int), tsMatrix->matrix_col); for(i = 0; i < tsMatrix->num_count; i++) { //遍历原三元表，统计矩阵的每一列有多少个非零元素 //对于矩阵 //0 14 0 0 -5 //0 -7 0 0 0 //36 0 0 28 0 //每一列包含的元素个数为 1 2 0 1 1 nums[tsMatrix->triple[i].col]++; } for(i = 1, postion[0]= 1; i < tsMatrix->matrix_col; i++) { //通过上一步计算的矩阵中每一列有多少个非零元素计算矩阵的每一列元素在三元表出现的位置 //即是1 2 4 4 5 postion[i] = nums[i - 1] + postion[i - 1]; } for(i = 0; i < tsMatrix->num_count; i++) { //原三元表当前这一项在转置的三元表中应该出现的位置 int index = postion[tsMatrix->triple[i].col]; transposeMatrix->triple[index - 1].row = tsMatrix->triple[i].col; transposeMatrix->triple[index - 1].col = tsMatrix->triple[i].row; transposeMatrix->triple[index - 1].value = tsMatrix->triple[i].value; //该列的一个元素已经有一个放进去位置往后移一个 postion[tsMatrix->triple[i].col]++; //当前列的开始位置加1 } free(postion); free(nums); return transposeMatrix; }

转置的测试

完整的代码：

SparseMatrix.c

#include #include #include"SparseMatrix.h" //一次快速定位转置总体分三步 //1、先对原三元表中的元素统计每列有多少个非0元素，也就是转置完B的每行有多少个非0元素 //2、通过第一步计算B矩阵每一行元素在三元表中第几个开始 //3、把三元表A的元素直接放到B的三元表里面去一次遍历三元表A防止B中去 TSMATRIX *transposeSparseMatrix_3(const TSMATRIX *tsMatrix) { int *nums = NULL; int *postion = NULL; int i; TSMATRIX *transposeMatrix = NULL; //对转转置后的三元表初始化申请空间 initSparseMatrix(&transposeMatrix, tsMatrix->matrix_col, tsMatrix->matrix_row, tsMatrix->num_count); //申请一个记录元素出现位置的矩阵长度和原稀疏矩阵列保持一致 postion = (int *)calloc(sizeof(int), tsMatrix->matrix_col); nums = (int *)calloc(sizeof(int), tsMatrix->matrix_col); for(i = 0; i < tsMatrix->num_count; i++) { //遍历原三元表，统计矩阵的每一列有多少个非零元素 //对于矩阵 //0 14 0 0 -5 //0 -7 0 0 0 //36 0 0 28 0 //每一列包含的元素个数为 1 2 0 1 1 nums[tsMatrix->triple[i].col]++; } for(i = 1, postion[0]= 1; i < tsMatrix->matrix_col; i++) { //通过上一步计算的矩阵中每一列有多少个非零元素计算矩阵的每一列元素在三元表出现的位置 //即是1 2 4 4 5 postion[i] = nums[i - 1] + postion[i - 1]; } for(i = 0; i < tsMatrix->num_count; i++) { //原三元表当前这一项在转置的三元表中应该出现的位置 int index = postion[tsMatrix->triple[i].col]; transposeMatrix->triple[index - 1].row = tsMatrix->triple[i].col; transposeMatrix->triple[index - 1].col = tsMatrix->triple[i].row; transposeMatrix->triple[index - 1].value = tsMatrix->triple[i].value; //该列的一个元素已经有一个放进去位置往后移一个 postion[tsMatrix->triple[i].col]++; //当前列的开始位置加1 } free(postion); free(nums); return transposeMatrix; } //按照列下标递增的顺序去找tsMatrix->triple[j].col == i //在三元表里面当前元素的列等于i就找到一个 TSMATRIX *transposeSparseMatrix_1(const TSMATRIX *tsMatrix) { int i; int j; int index = 0; TSMATRIX *transposeMatrix = NULL; initSparseMatrix(&transposeMatrix, tsMatrix->matrix_col, tsMatrix->matrix_row, tsMatrix->num_count); for(i = 0; i < tsMatrix->matrix_col; i++) { for(j = 0; j < tsMatrix->num_count; j++) { if(tsMatrix->triple[j].col == i) { transposeMatrix->triple[index].row = tsMatrix->triple[j].col; transposeMatrix->triple[index].col = tsMatrix->triple[j].row; transposeMatrix->triple[index++].value = tsMatrix->triple[j].value; } } if(index >= tsMatrix->num_count) { //如果发现此时三元表已经填满就可以不用再进行外层循环了 break; } } return transposeMatrix; } void showThreeTable(const TSMATRIX *tsMatrix) { int i; for(i = 0; i num_count; i++) { printf("(%d,%d,%d)\n", tsMatrix->triple[i].row, tsMatrix->triple[i].col, tsMatrix->triple[i].value); } } void showSparseMatrix(const TSMATRIX *tsMatrix) { int i; int j; int index = 0; for(i = 0; i < tsMatrix->matrix_row; i++) { for(j = 0; j < tsMatrix->matrix_col; j++) { if(tsMatrix->triple[index].row == i && tsMatrix->triple[index].col == j) { printf("%3d", tsMatrix->triple[index++].value); }else { printf("%3d", 0); } } puts(""); } puts(""); } void insertDataToMatrix(TSMATRIX *tsMatrix) { int i; int row; int col; int value; printf("Insert data by row and then col ascending(row, col, value)\n"); for(i = 0; i < tsMatrix->num_count; i++) { printf("[%d/%d] data: ", i+1, tsMatrix->num_count); scanf("%d%d%d", &row, &col, &value); tsMatrix->triple[i].row = row; tsMatrix->triple[i].col = col; tsMatrix->triple[i].value = value; } } void destorySparseMatrix(TSMATRIX **tsMatrix) { if(*tsMatrix == NULL) { return; } free((*tsMatrix)->triple); free(*tsMatrix); *tsMatrix = NULL; } void initSparseMatrix(TSMATRIX **tsMatrix, int matrix_row, int matrix_col, int num_count) { TSMATRIX *tp; if(NULL != (*tsMatrix) || (matrix_row*matrix_col < num_count) || matrix_col matrix_row = matrix_row; tp->matrix_col = matrix_col; tp->num_count = num_count; *tsMatrix = tp; } }

SparseMatrix.h

Demo.c

#ifndef _SPARSE_MATRIX_H #define _SPARSE_MATRIX_H typedef struct TRIPLE{ int row; int col; int value; }TRIPLE; typedef struct TSMATRIX { TRIPLE *triple; int matrix_row; int matrix_col; int num_count; //这个相当于triple数组的长度 }TSMATRIX; void initSparseMatrix(TSMATRIX **tsMatrix, int matrix_row, int matrix_col, int num_count); void destorySparseMatrix(TSMATRIX **tsMatrix); void showSparseMatrix(const TSMATRIX *tsMatrix); void insertDataToMatrix(TSMATRIX *tsMatrix); //对一个矩阵进行转置 TSMATRIX *transposeSparseMatrix_1(const TSMATRIX *tsMatrix); //一次定位转置较前两种转置降低时间复杂度对一个矩阵进行转置 TSMATRIX *transposeSparseMatrix_3(const TSMATRIX *tsMatrix); //打印矩阵的三元表 void showThreeTable(const TSMATRIX *tsMatrix); #endif #include #include"SparseMatrix.h" int main(void) { TSMATRIX *tsMatrix = NULL; TSMATRIX *transposeMatrix = NULL; int matrix_col; int matrix_row; int num_count; printf("input row col and num_count: "); scanf("%d%d%d", &matrix_row, &matrix_col, &num_count); initSparseMatrix(&tsMatrix, matrix_row, matrix_col, num_count); insertDataToMatrix(tsMatrix); showSparseMatrix(tsMatrix); transposeMatrix = transposeSparseMatrix_3(tsMatrix); showSparseMatrix(transposeMatrix); destorySparseMatrix(&tsMatrix); destorySparseMatrix(&transposeMatrix); return 0; } /* 4 5 9 0 0 1 0 2 3 0 3 4 1 1 2 1 3 1 2 2 3 2 4 1 3 1 1 3 3 1 3 5 5 0 1 14 0 4 -5 1 1 -7 2 0 36 2 3 28 */

【本文地址】

公司简介

联系我们