稀疏二维数组的压缩和数组的转置

张

张建站

2026/5/21 1:56:24

10分钟阅读

代码#include stdio.h #include malloc.h //便于后续代码工整 typedef int elem; /* * 三元组存储行号、列号、元素值 */ typedef struct Triple{ int i; // 行 int j; // 列 elem e; // 元素值 } Triple, *TriplePtr; /** * 稀疏矩阵压缩存储结构 */ typedef struct CompressedMatrix{ int rows,columns,numElements; // 总行数、总列数、非零元素个数 Triple* elements; // 存储所有非零元素的三元组数组 } CompressedMatrix, *CompressedMatrixPtr; /** * 初始化压缩矩阵 */ CompressedMatrixPtr initCompressedMatrix(int paraRows, int paraColumns, int paraElements, int** paraData){ int i; //有多少个非零元素就申请多少个三元组空间 CompressedMatrixPtr resultPtr (CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix)); //存总个数 resultPtr-rows paraRows; resultPtr-columns paraColumns; resultPtr-numElements paraElements; resultPtr-elements (TriplePtr)malloc(paraElements * sizeof(struct Triple)); //把非零元素填进去 for(i 0; i paraElements; i ){ resultPtr-elements[i].i paraData[i][0];//行 resultPtr-elements[i].j paraData[i][1];//列 resultPtr-elements[i].e paraData[i][2];//值 } return resultPtr; }// 函数结束 /** * 打印压缩矩阵 */ void printCompressedMatrix(CompressedMatrixPtr paraPtr){ int i; for(i 0; i paraPtr-numElements; i ){ printf((%d, %d): %d\r\n, paraPtr-elements[i].i, paraPtr-elements[i].j, paraPtr-elements[i].e); }// 循环结束 }// 函数结束 /** * 压缩矩阵的快速转置 */ CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){ // 申请临时空间 int i, tempColumn, tempPosition; int *tempColumnCounts (int*)malloc(paraPtr-columns * sizeof(int)); int *tempOffsets (int*)malloc(paraPtr-columns * sizeof(int)); for(i 0; i paraPtr-columns; i ){ tempColumnCounts[i] 0; } CompressedMatrixPtr resultPtr (CompressedMatrixPtr)malloc(sizeof(struct CompressedMatrix)); resultPtr-rows paraPtr-columns; resultPtr-columns paraPtr-rows; resultPtr-numElements paraPtr-numElements; resultPtr-elements (TriplePtr)malloc(paraPtr-numElements * sizeof(struct Triple)); // 统计每一列有多少元素 for(i 0; i paraPtr-numElements; i ) { tempColumnCounts[paraPtr-elements[i].j] ; } tempOffsets[0] 0; for(i 1; i paraPtr-columns; i ){ tempOffsets[i] tempOffsets[i - 1] tempColumnCounts[i - 1]; printf(tempOffsets[%d] %d \r\n, i, tempOffsets[i]); } // 遍历并填充转置后的数据 for(i 0; i paraPtr-numElements; i ) { tempColumn paraPtr-elements[i].j; tempPosition tempOffsets[tempColumn]; resultPtr-elements[tempPosition].i paraPtr-elements[i].j; resultPtr-elements[tempPosition].j paraPtr-elements[i].i; resultPtr-elements[tempPosition].e paraPtr-elements[i].e; tempOffsets[tempColumn]; } return resultPtr; } /** * 压缩矩阵测试 */ void compressedMatrixTest(){ CompressedMatrixPtr tempPtr1, tempPtr2; int i, j, tempElements; tempElements 4; int** tempMatrix1 (int**)malloc(tempElements * sizeof(int*)); for(i 0; i tempElements; i ){ tempMatrix1[i] (int*)malloc(3 * sizeof(int)); } int tempMatrix2[4][3] {{0, 0, 2}, {0, 2, 3}, {2, 0, 5}, {2, 1, 6}}; for(i 0; i tempElements; i ){ for(j 0; j 3; j ) { tempMatrix1[i][j] tempMatrix2[i][j]; } } tempPtr1 initCompressedMatrix(2, 3, 4, tempMatrix1); printf(初始化后\r\n); printCompressedMatrix(tempPtr1); tempPtr2 transposeCompressedMatrix(tempPtr1); printf(转置后\r\n); printCompressedMatrix(tempPtr2); } int main(){ compressedMatrixTest(); return 0; }运行结果初始化后 (0, 0): 2 (0, 2): 3 (2, 0): 5 (2, 1): 6 tempOffsets[1] 2 tempOffsets[2] 3 转置后 (0, 0): 2 (0, 2): 5 (1, 2): 6 (2, 0): 3 -------------------------------- Process exited after 0.01309 seconds with return value 0 请按任意键继续. . .运行结果为1.用三元组将稀疏数组进行压缩只保留非零元素并记录行列2.将数组进行转置满矩阵用普通结构体稀疏矩阵用三元组结构体大小固定用静态数组大小不固定用动态内存。