Data structure day 8 - two dimensional array and matrix multiplication, and transpose of compressed matrix

The first is matrix multiplication

#include<stdio.h>
#include<stdlib.h>

/**
 *Dynamic two-dimensional array
 */
 
typedef struct TwoDArray{
	int rows;
	int columns;
	int **elements;
} TwoDArray, *TwoDArrayPtr;

/**
 *Static two-dimensional array
 */
 
typedef struct TwoDStaticArray{
	int rows;
	int columns;
	int elements[4][5];
} TwoDStaticArray, *TwoDStaticArrayPtr;

/**
 *Create array
 */
 
TwoDArrayPtr initTwoDArray(int paraRows, int paraColumns) {
	int i;
	TwoDArrayPtr resultPtr = (TwoDArrayPtr)malloc(sizeof(TwoDArray));
	resultPtr->rows = paraRows;
	resultPtr->columns = paraColumns;
	resultPtr->elements = (int **)malloc(sizeof(int *) * paraRows);
	for (i = 0; i < paraRows; i ++) {
		resultPtr->elements[i] = (int *)malloc(sizeof(int) * paraColumns);
	}
	
	return resultPtr;
}

/**
 *assignment
 */
 
void randomizeTwoDArray(TwoDArrayPtr paraPtr, int paraLowerBound, int paraUpperBound) {
	int i, j;
	for (i = 0; i < paraPtr->rows; i ++) {
		for (j = 0; j < paraPtr->columns; j ++) {
			paraPtr->elements[i][j] = rand() % (paraUpperBound - paraLowerBound) + paraLowerBound;
		}
	}
}

/**
 *Print
 */
 
void printTwoDArray(TwoDArrayPtr paraPtr) {
	int i, j;
	for (i = 0; i < paraPtr->rows; i ++) {
		for (j = 0; j < paraPtr->columns; j ++) {
			printf("%d, ", paraPtr->elements[i][j]);
		}
		printf("\n");
	}
}

/**
 *matrix multiplication 
 */
 
TwoDArrayPtr matrixMultiply(TwoDArrayPtr paraPtr1, TwoDArrayPtr paraPtr2) {
	int i, j, k, sum;
	if (paraPtr1->columns != paraPtr2->rows) {
		printf("Matrices cannot be multiplied.\n");
		return NULL;
	}
	
	TwoDArrayPtr resultPtr = initTwoDArray(paraPtr1->rows, paraPtr2->columns);
	
	for (i = 0; i < paraPtr1->rows; i ++) {
		for (j = 0; j < paraPtr2->columns; j ++) {
			sum = 0;
			for (k = 0; k < paraPtr1->columns; k ++) {
				sum += paraPtr1->elements[i][k] * paraPtr2->elements[k][j];
			}
			resultPtr->elements[i][j] = sum;
			printf("sum = %d, ", sum);
		}
		printf("\n");
	}
	
	return resultPtr;
}

void twoDArrayTest() {
	TwoDArrayPtr tempPtr1, tempPtr2, tempPtr3;
	tempPtr1 = initTwoDArray(3, 2);
	randomizeTwoDArray(tempPtr1, 1, 5);
	printf("The first matrix:\n");
	printTwoDArray(tempPtr1);
	
	tempPtr2 = initTwoDArray(2, 4);
	randomizeTwoDArray(tempPtr2, 4, 9);
	printf("The second matrix:\n");
	printTwoDArray(tempPtr2);
	
	tempPtr3 = matrixMultiply(tempPtr1, tempPtr2);
	printf("The result:\n");
	printTwoDArray(tempPtr3);
}

/**
 *Create static array 
 */
 
TwoDStaticArrayPtr initTwoDStaticArray() {
	int i, j;
	TwoDStaticArrayPtr resultPtr = (TwoDStaticArrayPtr)malloc(sizeof(TwoDStaticArray));
	resultPtr->rows = 4;
	resultPtr->columns = 5;
	for (i = 0; i < 4; i ++) {
		for (j = 0; j < 5; j ++) {
			resultPtr->elements[i][j] = i * 10 + j;
			printf("(%d, %d): %p\n", i, j, &(resultPtr->elements[i][j]));
		}
	}
	
	return resultPtr;
}

int main() {
	twoDArrayTest();
	TwoDStaticArrayPtr tempPtr = initTwoDStaticArray();
	
	return 0;
}

Operation results

The first matrix:
2, 4,
3, 1,
2, 1,
The second matrix:
7, 7, 6, 8,
4, 4, 5, 6,
sum = 30, sum = 30, sum = 32, sum = 40,
sum = 25, sum = 25, sum = 23, sum = 30,
sum = 18, sum = 18, sum = 17, sum = 22,
The result:
30, 30, 32, 40,
25, 25, 23, 30,
18, 18, 17, 22,
(0, 0): 00000000001E15B8
(0, 1): 00000000001E15BC
(0, 2): 00000000001E15C0
(0, 3): 00000000001E15C4
(0, 4): 00000000001E15C8
(1, 0): 00000000001E15CC
(1, 1): 00000000001E15D0
(1, 2): 00000000001E15D4
(1, 3): 00000000001E15D8
(1, 4): 00000000001E15DC
(2, 0): 00000000001E15E0
(2, 1): 00000000001E15E4
(2, 2): 00000000001E15E8
(2, 3): 00000000001E15EC
(2, 4): 00000000001E15F0
(3, 0): 00000000001E15F4
(3, 1): 00000000001E15F8
(3, 2): 00000000001E15FC
(3, 3): 00000000001E1600
(3, 4): 00000000001E1604

First, create a static and a dynamic two-dimensional array, and then you can see through the static two-dimensional array that the two-dimensional array is stored line by line in the memory space

In addition, when applying for space for a dynamic two-dimensional array, first apply for space for the overall two-dimensional array, and then apply for the array. When applying for an array, it is divided into two parts. My understanding is that the first part is the applied row, and the second part is the applied space column, so as to form a two-dimensional array

2, Transpose of compressed matrix

Core: transpose code

CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr) {
	int i, tempColumn, tempPosition;
	int *tempColumnCounts = (int *)malloc(sizeof(int) * paraPtr->columns);
	int *tempOffsets = (int *)malloc(sizeof(int) * paraPtr->columns);
	for (i = 0; i < paraPtr->columns; i ++) {
		tempColumnCounts[i] = 0;
	}
	
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrix));
	resultPtr->rows = paraPtr->columns;
	resultPtr->columns = paraPtr->rows;
	resultPtr->numElements = paraPtr->numElements;
	
	resultPtr->elements = (TriplePtr)malloc(sizeof(Triple) * paraPtr->numElements);
	
	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\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;
}

Total code

#include<stdio.h>
#include<stdlib.h>

/**
 *Create a structure with rows and columns and values
 */
 
typedef struct Tripe{
	int i;
	int j;
	int e;
} Triple, *TriplePtr;
 
typedef struct CompressedMatrix{
	int rows, columns, numElements;
	TriplePtr elements;
} CompressedMatrix, *CompressedMatrixPtr;

/**
 *initialization
 */
 
CompressedMatrixPtr initCompressedMatrix(int paraRows, int paraColumns, int paraElements, int **paraData) {
	int i;
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrix));
	resultPtr->rows = paraRows;
	resultPtr->columns = paraColumns;
	resultPtr->numElements = paraElements;
	resultPtr->elements = (TriplePtr)malloc(sizeof(Triple) * paraElements);
	
	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;
}

/**
 *Print
 */
 
void printCompressedMatrix(CompressedMatrixPtr paraPtr) {
	int i;
	for (i = 0; i < paraPtr->numElements; i ++) {
		printf("(%d, %d): %d\n", paraPtr->elements[i].i, paraPtr->elements[i].j, paraPtr->elements[i].e);
	}
}

/**
 *Transpose
 */
 
CompressedMatrixPtr transposeCompressedMatrix(CompressedMatrixPtr paraPtr) {
	int i, tempColumn, tempPosition;
	int *tempColumnCounts = (int *)malloc(sizeof(int) * paraPtr->columns);
	int *tempOffsets = (int *)malloc(sizeof(int) * paraPtr->columns);
	for (i = 0; i < paraPtr->columns; i ++) {
		tempColumnCounts[i] = 0;
	}
	
	CompressedMatrixPtr resultPtr = (CompressedMatrixPtr)malloc(sizeof(CompressedMatrix));
	resultPtr->rows = paraPtr->columns;
	resultPtr->columns = paraPtr->rows;
	resultPtr->numElements = paraPtr->numElements;
	
	resultPtr->elements = (TriplePtr)malloc(sizeof(Triple) * paraPtr->numElements);
	
	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\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(sizeof(int *) * tempElements);
	for (i = 0; i < tempElements; i ++) {
		tempMatrix1[i] = (int *)malloc(sizeof(int) * 3);
	}
	
	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("After initialization\n");
	printCompressedMatrix(tempPtr1);
	
	tempPtr2 = transposeCompressedMatrix(tempPtr1);
	printf("After transpose.\n");
	printCompressedMatrix(tempPtr2);
}

int main() {
	compressedMatrixTest();
	
	return 0;
}

Operation results

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

The difficulty lies in the two arrays tempColumnCounts and tempOffsets

The first is tempColumnCounts, which I think is used to store the number of different columns (i.e. j) in the original matrix. For example, the test shows that there are two columns in column 0, one in column 1 and one in column 2. Why use it? It is mainly because after transposing, the column of the original matrix becomes the row of the transposed matrix, so it is convenient for us to use in the process of sorting and transposing later

Then comes the array tempOffsets. First of all, what does this array mean? This array is actually to provide the transposed array with corresponding bits for the number of corresponding rows (i.e. I). Then every time a number finds a bit, this bit will move back. Because the original position has been occupied, it will be + 1

In the tempColumnCounts array, there are two numbers in column 0. When it becomes a transpose matrix, it will be the number of row 0, and the number of row 0 must start from position 0, while there is one number in column 1. When it becomes a transpose matrix, it will be the number of row 1 after row 0. It will be arranged row by row, so in tempOffsets, the starting position of row 1 is 2, Since row 0 occupies positions 0 and 1, row 1 can only be arranged from position 2

Tags: C data structure matrix

Posted by g00bster on Thu, 19 May 2022 00:09:30 +0300