5.2数组的压缩和转置

#includestdio.h #includemalloc.h typedef int elem; //a triple for row index,column index,and data //三元一组 typedef struct Triple{ int i; int j; elem e; }Triple,*TriplePtr; //a triple for row index,column index,and data //则每个都是三元形式 typedef struct CompressedMatrix{ int rows,columns,numElements; Triple* elements; }CompressedMatrix,*CompressedMatrixPtr; //initialize a compressed matrix //表的三列 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(i0;iparaElements;i){ resultPtr-elements[i].iparaData[i][0]; resultPtr-elements[i].jparaData[i][1]; resultPtr-elements[i].eparaData[i][2]; } //for i return resultPtr; } //initCompressedMatrix //print the compressed matrix void printCompressedMatrix(CompressedMatrixPtr paraPtr){ int i; for(i0;iparaPtr-numElements;i){ printf((%d,%d):%d\r\n,paraPtr-elements[i].i,paraPtr-elements[i].j,paraPtr-elements[i].e); } //for i } //printCompressedMatrix //transpose a compressed matrix CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr){ //step1 allocate space int i,tempColumn,tempPosition; int *tempColumnCounts (int*)malloc(paraPtr-columns * sizeof(int)); int *tempOffsets (int*)malloc(paraPtr-columns * sizeof(int)); for(i0;iparaPtr-columns;i){ tempColumnCounts[i]0; } //for i 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)); //step2 one scan to calculate offsets for(i0;iparaPtr-numElements;i){ tempColumnCounts[paraPtr-elements[i].j]; } //for i //找位置 //按i的顺序读 tempOffsets[0] 0; for(i1;iparaPtr-columns;i){ tempOffsets[i]tempOffsets[i-1]tempColumnCounts[i-1]; printf(tempOffsets[%d] %d \r\n,i,tempOffsets[i]); } //for i //step3 another scan to fill data for(i0;iparaPtr-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]; } //for i return resultPtr; } //transposeCompressedMatrix //test the compressed matrix void CompressedMatrixTest(){ CompressedMatrixPtr tempPtr1,tempPtr2; int i,j,tempElements; //construct the first sample matrix tempElements 4; int** tempMatrix1 (int**)malloc(tempElements * sizeof(int*)); for(i0;itempElements;i){ tempMatrix1[i] (int*)malloc(3 * sizeof(int)); } //for i int tempMatrix2[4][3]{{0,0,2},{0,2,3},{2,0,5},{2,1,6}}; for(i0;itempElements;i){ for(j0;j3;j){ tempMatrix1[i][j]tempMatrix2[i][j]; } //for j } //for i tempPtr1 initCompressedMatrix(2,3,4,tempMatrix1); printf(After initialization,\r\n); printCompressedMatrix(tempPtr1); tempPtr2 transposeCompressedMatrix(tempPtr1); printf(After transpose.\r\n); printCompressedMatrix(tempPtr2); } //main //the entrance int main(){ CompressedMatrixTest(); return 1; } //main运行结果After initialization, (0,0):2 (0,2):3 (2,0):5 (2,1):6 tempOffsets[1] 2 tempOffsets[2] 3 After transpose. (0,0):2 (0,2):5 (1,2):6 (2,0):3体会时间复杂度降低能更好理解下标。