Sparse Matrix (2) - 2차원 배열을 생성하고 희소행렬로 표현하기

 

2차원 배열을 생성하고 배열 전체의 20%에만 임의의 수가 저장되게 만들어 보았다.

int** InputValue(int *valueCount) {
	int** arr;
	int i,j,rannum;
	int count = 0;

	arr = (int**)malloc(sizeof(int)*MAXSIZE);
	for(i=0;i<MAXSIZE;i++)
	{
		arr[i] = (int*)malloc(sizeof(int)*MAXSIZE);
	} // 2차원 배열 동적할당 선언

	srand(time(NULL));

	// <- 값 입력
	for(i=0;i<MAXSIZE;i++)
	{
		for(j=0;j<MAXSIZE;j++) 
		{
			// 전체 배열중 20%에만 원소를 저장시킨다.
			rannum = rand()%100;
			if(rannum<20) {
				arr[i][j] = (rand()%100)+1; // 값을 저장할 때는 1~100 범위의 숫자를 저장한다. 
				count++; // 값이 입력될때 마다 카운트를 1씩 증가시켜
						 // Sparse Matrix에 값이 몇개 저장되었는지 카운트 한다.
			}
			else
			{
				arr[i][j] = 0; // 나머지 배열의 원소에는 0을 저장한다.
			}

		}

	}
	// ->

	*valueCount = count; // 생성된 Value의 수를 참조를 통하여 저장한다.
	
	return arr;

}

 

main함수에서 

 

int **arr;

 

이라는 변수를 더블포인터 변수를 선언하고

 

arr = InputValue(&valueCount);

 

식으로 연결시켜 주었다. valueCount는 몇개의 값이 생성되었는지 알기 위한 변수로 메인에서 선언해주고 InputValue함수에

 

주소만 넘겨주었다.

 

배열 전체의 20%에만 값을 할당하기 위해 0~99 범위의 랜덤한 숫자를 생성하고 20보다 작을때만 값이 입력되게 만들었는데

 

이에 대한 검증은 따로 하도록 하겠다.

 

 

결론적으로 InputValue함수를 통해 생성된 2차원배열을 파일에 찍어보면 다음과 같이 제대로 생성됨을 볼 수 있었다.

 

 

 

이는 MAXSIZE를 15000으로 해서 15000 x 15000 사이즈의 2차원 배열이 생성되었을 때이다.

 

파일사이즈가 커서 메모장으로는 열리지도 않는다 ㅋㅋ

 

 

 

이제 생성된 2차원 배열을 희소행렬 표현방식으로 저장해 보았다.

 

 

typedef struct spsmt { int row; int col; int value; } spsmt; // 희소행렬 정보를 위한 구조체 ... ... ... spsmt* makeSpsMatrix(int valueSize, int** arrData) { spsmt *mt = (spsmt*)malloc(valueSize*sizeof(spsmt)); // valueSize만큼 구조체 배열의 메모리 동적 할당 int i,j; int mtCount = 1; // Matrix Count. index 0은 희소행렬 정보이기 때문에 1부터 시작한다. mt[0].row = MAXSIZE; mt[0].col = MAXSIZE; mt[0].value = valueSize; // 배열의 첫번째 값은 희소행렬에 대한 정보 입력 // 원본 데이터인 2차원 배열의 값을 비교해 보며 0이 아닐때, 즉 값이 있을때는 희소행렬 표현으로 바꿔준다. for(i=0;i<MAXSIZE;i++) { for(j=0;j<MAXSIZE;j++) { if(arrData[i][j] != 0) { mt[mtCount].row = i; // arrData의 행정보 mt[mtCount].col = j; // arrData의 열정보 mt[mtCount].value = arrData[i][j]; // arrData의 값 // 각각 정보를 저장한다. mtCount++; // 희소행렬 index를 1씩 증가시켜준다. } } } return mt; }

 

메인에서 가지고 있는 2차원 배열의 포인터변수와 생성된 값의 수인 valueSize를 인자로 받는 makeSpsMatrix라는 함수를 만들었다.

 

이는 역시 메인에서 희소행렬을 위한 구조체로 지정해준 spsmt라는 type의 포인터 변수로 연결된다.

 

[0]번 인덱스에는 row, colum값이 MAXSIZE가 되고 value값이 메인에서 부터 인자로 받아온 valueSize가 저장된다.

 

그리고 2중 for문을 이용해 값을 모두 비교해 보며 0이 아닐때에는 희소행렬로 저장하고 0일 경우에는 반복문을 계속 진행시켰다.

 

 

이 역시 결과를 파일로 저장해서 열어보면 다음과 같았다.

 

 

15000 x 15000 사이즈에 value가 45049011개인 희소행렬이 제대로 저장된 것을 확인 할 수 있었다.

 

 

 

2차원 배열과 희소행렬의 결과값을 비교해서 검증해 보면

 

 

 

 [0][4] 위치에 value값 76이 생성되어 있다는걸 확인할 수 있다.