C - 자료구조 배열/구조체/포인터/동적 메모리 할당

* 배열의 응용 : 다항식

수학에서 나오는 다항식을 배열을 이용해 표현 해보자.

다항식은 p(x)=a(n)x^n+a(n-1)x^n-1+....+a(1)x+a(0)의 형태를 가진다.

a : 계수

x : 변수

n : 차수라고 부른다.

 

다항식을 나타내는 두가지의 자료 구조가 있는데

첫번째 방법이다.

모든 차수의 계수 값을 배열에 저장하는 방법이다.

가령 10x^5+6x+3 이라는 다항식이 있다면,

0번 인덱스	1번 인덱스	2번 인덱스	3번 인덱스	4번 인덱스	5번 인덱스
10x^5	0x^4	0x^3	0x^2	6x^1	3x^0

의 형식으로 배열에 저장이 될 것이다.

#include <stdio.h>
#define MAX_DEGREE 101

typedef struct {
	int degree;
	float coef[MAX_DEGREE];
} polynomial;

int main(void) {
	polynomial a = { 5, {10, 0, 0, 0, 6, 3} }; //다항식의 차수는 5
}

이 방법의 단점은 대부분의 항의 계수가 0인 경우 공간의 낭비가 심하다는 점이다.

가령 10x^100 + 6의 다항식의 경우 101개의 공간중에서 오직 2개만 사용되기 때문이다.

장점으로는 다항식을 계산할때 같은 차수의 계수를 쉽게 찾을 수 있기에 알고리즘이 간단해진다.

 

이 방법을 이용해 다항식 덧셈 프로그램을 살펴보자

#include <stdio.h>
#define MAX_DEGREE 101
#define MAX(a,b) (((a)>(b))?(a):(b)) //a가 b보다 크다의 조건이 참이면 a를 거짓이면 b

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

//C = A+B  
polynomial poly_add1(polynomial A, polynomial B) {
	polynomial C;	//결과 다항식
	int Apos = 0, Bpos = 0, Cpos = 0; //배열 인덱스 변수
	int degree_a = A.degree;  //degree_a는 A의 차수
	int degree_b = B.degree;  //degree_b는 B의 차수
	C.degree = MAX(A.degree, B.degree); //구조체 C의 차수는 A,B 구조체 둘중에 더 큰 차수와 같다
	
	while (Apos <= A.degree && Bpos <= B.degree) { 
		if (degree_a > degree_b) { //a의 차수가 b의 차수보다 클 경우
			C.coef[Cpos++] = A.coef[Apos++]; //c의 계수는 A의 계수와 같다
			degree_a--;	//a의 차수를 --
		}
		else if (degree_a == degree_b) { //a의 차수와 b의 차수가 같다
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++]; //c의 계수는 a와 b의 계수를 더한 값이다.
			degree_a--, degree_b--; //a와 b의 차수를 --
		}
		else { //b의 차수가 a의 차수보다 클 경우
			C.coef[Cpos++] = B.coef[Bpos++]; //c의 계수는 B의 계수와 같다
			degree_b--; //b의 차수를 --
		}
	}
	return C;	//위 조건문을 통해 정해진 구조체 C의 차수와 계수들을 반환함
}


void print_poly(polynomial p) {
	for (int i = p.degree; i > 0; i--)  //해당 구조체 다항식의 차수부터 1회 반복될때마다 --
		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); //3.0x^5 + 6.0x^4 + 0.0x^3 + 0.0x^2 + 0.0x^1 + 10.0
	print_poly(b); //7.0x^4 + 0.0x^3 + 5.0x^2 + 0.0x^1 + 1.0
	c = poly_add1(a, b);
	printf("=============================\n");
	print_poly(c); //3.0x^5 + 13.0x^4 + 0.0x^3 + 5.0x^2 + 0.0x^1 + 11.0
	return 0;

}

출력 결과

3.0x^5 + 6.0x^4 + 0.0x^3 + 0.0x^2 + 0.0x^1 + 10.0
7.0x^4 + 0.0x^3 + 5.0x^2 + 0.0x^1 + 1.0
=============================
3.0x^5 + 13.0x^4 + 0.0x^3 + 5.0x^2 + 0.0x^1 + 11.0

나 자신 너무 멋있어!!!!

주석 잘 달아놓았으니 더이상의 설명은 생략 하겠다.

 

두번째 방법으로는 공간을 절약하기 위하여 0이 아닌 항만을 하나의 전역 배열에 저장하는 방법도 있다.

다항식의 0이 아닌 항들은 (계수, 차수)형식으로 구조체 배열에 저장된다.

가령 10x^5+6x+3의 경우 ((10,5), (6,1), (3,0))로 표시하는 것

#define MAX_TERMS 101

struct {
	float coef;
	int expon;
} terms[MAX_TERMS];
int avail;

 

이 방법 또한 단점이 존재한다. 

첫번째로 하나의 다항식이 시작되고 끝나는 위치를 가리키는 인덱스 변수들에 대한 관리가 필요하다

두번째로 차수도 저장해야 하기 때문에 다항식에 따라서는 계수만을 저장하는 첫번째 방식보다 공간을 더 많이 필요로 할 수도 있다. 

세번째로 다항식의 덧셈을 비롯한 연산들의 구현이 첫번째 방법보단 어렵다.

/

/

/

/

/
*배열을 함수의 매개변수로 사용하는 프로그램

#include <stdio.h>
#define SIZE 6

void get_integers(int list[]) {
	printf("6개의 정수를 입력하시오 : ");
	for (int i = 0; i < SIZE; ++i) {
		scanf("%d", &list[i]);
	}
}

int cal_sum(int list[]) {
	int sum = 0;
	for (int i = 0; i < SIZE; ++i) {
		sum += *(list + i);
	}
	return sum;
}

int main(void) {
	int list[SIZE];
	get_integers(list);
	printf("합 = %d\n", cal_sum(list));

}

* 이 코드의 핵심에 대해 정리해보자

* 배열의 값을 바꿀땐 포인터로 지정해줘서 값이 바뀐다
* 값 복사가 아닌 주소에 직접 접근하여 바꾸는 것이 핵심!
get_integers(list) 이 함수가 실행이 되면
get_integers의 list 포인터가 메인 함수 list 배열 0번 인덱스를 가리킨다.
배열 인덱스 [0]은 배열의 주소값과 같다는 사실을 숙지하자.
위의 배열들은 모두 스택에 자동변수 할당을 통해
컴퓨터가 스스로 메모리를 할당 해주고 사용이 끝나면 해제가 된다
힙은 개발자가 직접 할당해주고 사용이 끝나면 직접 해제를 해줘야 한다는 차이점이 있는데,
위에서 짠 프로그램은 결국 스택에 할당 됐기에 배열(주소)를 매개변수로 사용하면서
함수가 끝나고 값이 사라지는 것이 아닌 바뀐 값이 그대로 존재한다는 것이 핵심 포인트이다.

* 동적 메모리 할당

- C언어에서는 운영체제가 사용되지 않는 메모리 공간을 모아둔 히프라는 곳이 존재한다.

필요한만큼만 할당 받고 다 사용하고 난 후에 반납하기 때문에 메모리를 매우 효율적으로 사용할 수 있다.

위에서 정리한 것과 마찬가지로 사용자가 직접 해제 해주기 전까진 히프 공간안에 존재한다는 것이 핵심

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

int main() {
    int *p;
    p = (int *)malloc(sizeof(int));
    *p = 2000;
    free(p)

}

malloc함수를 사용하려면 <stdlib.h>가 필요하다

포인터 p가 Heap공간에 생성되고 값이 2000이 저장된 것을 확인할 수 있다.

이후에 free(p)함수를 통해

포인터 안에 값은 똥값이 남고 Heap 영역에 할당 받은 공간 또한 사라진 것을 확인할 수 있다.

 

malloc 함수는 size 바이트만큼의 메모리 블록을 할당하고 단위는 바이트이다.

malloc()은 동적 메모리 블럭의 시작 주소를 반환하며 반환되는 주소의 타입은 기본적으로 void * 이므로 이를 적절한 포인터로 형변환을 해줄 필요가 있다.

메모리 확보가 불가능하면 NULL을 함수의 반환값으로 반환한다.

 

동적메모리는 오직. 포인터로만 사용할 수 있다.

위 구문을 예시로 들자면 *p는 p가 가리키는 장소이고 *p=2000 문장을 실행하면 p가 가리키는 장소에 2000이라는 값이 저장된다.

free()함수를 통해 할당된 메모리 블록을 운영체제에 반환한다. 이때 포인터 값을 잊어버리면 반환할 수 없다는 것을 주의하자

malloc을 사용할땐 반환값이 NULL(메모리 부족으로 인해 할당 실패)값인지 검사할 필요가 있는데

아래 예제를 통해 알아보자

 

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

int main() {
   int *p;
    p = (int*)malloc(SIZE*sizeof(int));
    if(p==NULL){
        fprintf(stderr, "메모리가 부족해서 할당할 수 없습니다.\n");
        exit(1);
    }
    for (int i=0;i<SIZE;i++){
        p[i] = i;
    }
    
    for (int i=0;i<SIZE;i++){
        printf("%d", p[i]);
    }
    
    free(p);

}

먼저 main 함수 두번째줄이 실행이 되면

이렇게 int형 변수를 담을 수 있는 10개의 메모리 공간을 할당 받았다

메모리 공간이 있어서 할당을 받았기에 if문은 그냥 지나가고

첫번째 반복문이 실행되며 할당받은 공간에 0~9까지의 값이 저장이 된다.

두번째 반복문이 실행되며 각 공간에 저장된 값들을 출력한다.

그 후 코드가 끝났으니 free 함수를 통해 할당받은 메모리를 다시 반납한다.

 

예제를 통해 더 이해해보자

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

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

int main() {
    student *s;
    s = (student *) malloc(sizeof(student));

    if (s == NULL){
        fprintf(stderr,"메모리가 부족해서 할당할 수 없습니다\n");
        exit(1);
    }

    strcpy(s->name, "Park");
    s->age=20;
    printf("%d %s\n", s->age, s->name);
    free(s);
    printf("%d %s\n", s->age, s->name);


}

구조체 포인터 s를 선언하고 구조체 크기에 맞게 메모리를 할당 받았다

간접참조를 통해 값을 바꿔준 후 메모리 할당 전후로 출력을 해보면

20 Park
20 Park

똑같이 나온다. 왜냐하면 포인터안의 값을 바꿔줬기 때문에 메모리가 해제 된 후에도 값이 남아있다.