[자료구조] 3장

《 배열 》

 - 동일한 타입의 데이터를 한번에 여러개 만들 때 사용

 

[1차원 배열 예제]

// C code
#include <stdio.h>

int main(void) {

	int arr[5];
	int byte_size, size;

	byte_size = sizeof(arr); // int 자료형의 크기 4byte * 5 = 20
	printf("배열의 바이트 크기 : %d\n", byte_size);

	size = sizeof(arr) / sizeof(arr[0]); // (4*5)20 / 4 = 5
	printf("배열의 크기 : %d\n", size);

	for (int i = 0; i < size; i++) {
		arr[i] = 0;
		printf("%d ", arr[i]);
	}
	return 0;
}

출력문 실행 결과

 

[2차원 배열 예제]

// C code
#include <stdio.h>
#define ROW 3
#define COL 5

int main(void) {
	int arr[ROW][COL];

	int byte_size, size;
	byte_size = sizeof(arr);
	size = sizeof(arr) / sizeof(arr[0]);

	printf("배열의 바이트 크기 : %d\n", byte_size);
	printf("배열의 크기 : %d행\n", size);

	for (int i = 0; i < ROW; i++) {
		for (int j = 0; j < COL; j++) {
			arr[i][j] = 0;
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}

	return 0;
}

출력문 실행 결과

 

《 구조체 》

 - 타입이 다른 데이터를 하나의 자료형으로 선언할 때 사용

 

[구조체 예제]

// C code
#include <stdio.h>

typedef struct studentTag {
	char name[10];
	int age;
	double gpa;
} STUDENT;

int main(void) {

	printf("studentTag 구조체의 크기 = %d\n", sizeof(struct studentTag));
	STUDENT a = { "kim", 20, 4.3 };
	printf("a 구조체의 크기 : %d\n", sizeof(a));
	printf("학생 a의 이름 : %s\n", a.name);
	printf("학생 a의 나이 : %d\n", a.age);
	printf("학생 a의 평점 : %.2f\n", a.gpa);
	return 0;
}

출력문 실행 결과

 

《 배열/구조체의 응용 》

 

 [ 다항식 덧셈 프로그램 ]

 - 다항식의 모든 항을 배열에 저장

 - 다항식의 0이 아닌 항만을 배열에 저장하는 방법

// C code
#include <stdio.h>
#define MAX(a, b) a>b?a:b
#define MAX_DEGREE 101

typedef struct {
	int degree;				// 다항식의 차수
	float coef[MAX_DEGREE]; // 다항식의 계수
} polynomial;

polynomial poly_add1(polynomial A, polynomial B) {

	polynomial C;					   // 다항식 A + B 의 결과 다항식인 C
	int Apos = 0, Bpos = 0, Cpos = 0;  // 배열 인덱스 변수
	int degree_a = A.degree;
	int degree_b = B.degree;
	C.degree = MAX(A.degree, B.degree); // 결과 다항식 차수

	while (Apos <= A.degree && Bpos <= B.degree) {
    	// A항의 차수 > B항의 차수
		if (degree_a > degree_b) {
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
        // A항의 차수 == B항의 차수
		else if (degree_a == degree_b) {
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
			degree_a--;
			degree_b--;
		}
        // A항의 차수 < B항의 차수
		else {
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
	}
	return C;
}

void print_poly(polynomial p) {
	
	for (int i = p.degree; i > 0; i--) {
		printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
	}
	printf("%3.1f \n", p.coef[p.degree]);
}

int main(void) {

	polynomial a = { 5, {3, 6, 0, 0, 0, 10} };
	polynomial b = { 4, {7, 0, 5, 0, 1} };
	polynomial c;
	
	print_poly(a);
	print_poly(b);
	c = poly_add1(a, b);
	printf("-------------------------------------------\n");
	print_poly(c);
	return 0;
}

출력문 실행 결과

 

[ 희소행렬 ]

 - 행렬의 값이 대부분 0인 행렬

 

 ① 2차원 배열로 전체 요소를 저장하여 표현 하는 방법

     - 전체 요소를 2차원 배열로 저장

     - 행렬의 연산을 간단히 구현 가능

     - 배열의 행렬 인덱스 값이 0인 경우 메모리 공간 낭비

 

 ② 0이 아닌 요소들만 저장하여 표현 하는 방법

     - 2차원 배열 내 0이 아닌 요소들만 저장

     - 메모리 공간 절약

     - 행렬 연산들의 구현이 복잡해짐

일반적인 2차원 배열이 희소행렬로 변환

 

 

 [ 희소행렬의 전치 ]

 

  ① 2차원 배열로 전체 요소를 저장하는 행렬을 전치하는 방법

      - 배열의 요소(i, j) → (j, i)로 교환하면 간단하게 구현 가능

①번 방법

// C code

// 기존 행렬 A → 전치 → 행렬 B
void matrix_transpose(int A[row][col], int b[row][col]){
	for(int i=0; i<row; i++)
    	for(int j=0; j<col; j++)
        	b[j][i] = a[i][j];
}

 

  ② 0이 아닌 요소만 (row, col, value)로 표현하는 방법

      - 전치 연산을 위해 구조체 사용

②번 방법

// C code
#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100

typedef struct {
	int row;
	int col;
	int value;
} ELEMENT;

typedef struct SparseMatrix {
	ELEMENT data[MAX_TERMS];
	int rows;  // 행의 개수
	int cols;  // 열의 개수
	int terms; // 항의 개수
} SparseMatrix;

SparseMatrix matrix_transpose2(SparseMatrix a) {

	SparseMatrix b;
	int c, i, bindex; // 행렬 b에서 현재 저장 위치
	b.rows = a.rows;
	b.cols = a.cols;
	b.terms = a.terms;

	if (a.terms > 0) {
		bindex = 0;
		for (c = 0; c < a.cols; c++) {
			for (i = 0; i < a.terms; i++) {
				if (a.data[i].col == c) {
					b.data[bindex].row = a.data[i].col;
					b.data[bindex].col = a.data[i].row;
					b.data[bindex].value = a.data[i].value;
					bindex++;
				}
			}
		}
	}
	return b;
}

void matrix_print(SparseMatrix a) {
	int i;
	printf("=========================\n");

	for (i = 0; i < a.terms; i++)
		printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);

	printf("=========================\n");
}

int main(void) {

	SparseMatrix m = {
		{{0, 3, 7},
		{1, 0, 9},
		{1, 5, 8},
		{3, 0, 6},
		{3, 1, 5},
		{4, 5, 1},
		{5, 2, 2}},
		6,
		6,
		7
	};
	SparseMatrix result;

	matrix_print(m);
	printf("\n------- transpose -------\n\n");
	result = matrix_transpose2(m);
	matrix_print(result);

	return 0;
}

②번코드 실행 결과

 

《 포인터 》

 - 다른 변수의 주소를 가지고 있는 변수

 - &연산자 : 변수의 주소를 반환

 - *연산자 : 포인터가 가리키는 곳의 값을 반환 

 

 [ 포인터를 함수의 매개변수로 사용하는 예제(포인터에 의한 호출) ]

// C code 
#include <stdio.h>

void swap(int* a, int* b) {
	int temp;

	temp = *a;
	*a = *b;
	*b = temp;
}

int main(void) {

	int a = 1, b = 2;

	printf("swap을 호출하기 전 a=%d, b=%d\n", a, b);
	swap(&a, &b);
	printf("swap을 호출하기 후 a=%d, b=%d\n", a, b);

	return 0;
}

출력문 실행 결과

 

 [ 배열을 함수의 매개변수로 사용하는 예제 ]

// C code
#include <stdio.h>
#define SIZE 6
#define _CRT_SECURE_NO_WARNINGS

void get_int(int arr[]) {

	printf("6개의 정수를 입력하시오 : ");

	for (int i = 0; i < SIZE; i++)
		scanf("%d", &arr[i]);
}

int arr_sum(int arr[]) {

	int sum=0;

	for (int i = 0; i < SIZE; i++)
		// sum += *(arr + i)
		sum += arr[i];

	return sum;
}

int main(void) {

	int arr[SIZE];
	
	get_int(arr);
	printf("arr의 합 : %d\n", arr_sum(arr));
	return 0;
}

출력문 실행 결과

 

 

[ 좌표 두개를 전달받아 좌표 사이의 거리 구하기 ]

// C code
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
	int x_coord;
	int y_coord;
}Coord;

double get_distance(Coord p1, Coord p2) {

	double dx = p1.x_coord - p2.x_coord;
	double dy = p1.y_coord - p2.y_coord;
	
	double distance = sqrt((dx * dx) + (dy * dy));

	return distance;
};

int main(void) {

	Coord p1 = { 1, 2 };
	Coord p2 = { 9, 8 };

	double distance = get_distance(p1, p2);

	printf("p1와 p2 점 사이의 거리 : %.2f\n", distance);

	return 0;
}

출력문 실행 결과