[CDS] chapter 3 : 배열, 구조체, 포인터
1. 배열과 구조체
상세한 내용은 KNK 정리 파트에서 확인하기로 하고, 여기서는 간단히 개념을 짚고 넘어가자.
(1) 배열
C언어의 기본적인 자료구조 배열(array)은 동일한 데이터 타입의 요소들을 연속적으로 저장하는 구조이다. 배열이라는 자료구조가 갖는 이점은 '대량의 데이터를 저장하고 다루는 것'에 있다. 배열은 연속적인 메모리 공간이 할당되고 인덱스 번호를 사용하기 때문에 반복문을 활용한 여러 작업을 간편하게 할 수 있다.
(2) 구조체
C언어의 구조체(structure)는 서로 다른 타입의 변수들을 하나의 단위로 묶어주는 '사용자 정의 자료형'이다. 아래의 간단한 예시 코드를 통해 사용방법에 익숙해져보자.
#include <stdio.h>
#include <string.h>
// 구조체 정의
typedef struct {
char name[50];
int age;
} Person;
int main() {
// 구조체 변수 선언
Person p1;
// 구조체 멤버에 값 할당
strcpy(p1.name, "Alice");
p1.age = 30;
// 선언과 동시에 초기화 가능
// Person p1 = {"Alice", 30};
// 구조체 멤버 출력
printf("Name: %s\n", p1.name);
printf("Age: %d\n", p1.age);
return 0;
}2. 배열의 활용 - 다항식
(1) 방법 1
다항식을 프로그램에서 표현하려면 어떻게 해야 할까? 가장 직관적으로는 다항식의 계수들을 하나의 배열에 저장하는 방법을 생각해 볼 수 있다.
#define MAX_DEGREE 101
typedef struct {
int degree;
float coef[MAX_DEGREE];
} polynomial;
polynomial a = { 5, { 10, 0, 0, 0, 6, 3 }};
이를 기반으로 두 다항식의 덧셈을 구현해보면 다음과 같다.
polynomial poly_add1(polynomial A, polynomial B){
polynomial 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){
if (degree_a > degree_b){
C.coef[Cpos++] = A.coef[Apos++];
degree_a--;
}
else if (degree_a < degree_b){
C.coef[Cpos++] = B.coef[Bpos++];
degree_b--;
}
else {
C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
degree_a--;
degree_b--;
}
}
return C;
}
(2) 방법 2
방법 1의 경우 다항식의 모든항의 계수를 배열에 저장하고 있기 때문에 계수가 0인항이 많을수록 공간의 낭비가 커진다는 단점이 있다. 이를 보완하기 위해 0이 아닌 항들에 대하여 (계수, 차수)의 형식으로 배열에 저장하는 방법을 구상해볼 수 있는데, 이 경우 (계수, 차수) 쌍을 구조체로 선언한 뒤 해당 구조체의 배열을 생성하여 다항식을 표현하게 된다. 메모리 공간의 낭비를 방지한다는 두번째 방법의 취지를 고려하면, 여러 다항식들을 하나의 배열에 저장하는 것이 바람직할 것이다. 따라서 아래 예시와 같이 배열에 각 다항식의 위치 및 비어있는 요소의 인덱스를 가리키는 avail 변수가 필요하다.
#define MAX_TERMS 101
struct {
float coef;
int expon;
} terms[MAX_TERMS];
int avail;
마찬가지로 위 방식을 기반으로 한 두 다항식의 덧셈을 구현한 코드를 살펴보면 다음과 같다.
char compare(int a, int b){
if(a>b) return '>';
else if (a==b) return '=';
else return '<';
}
void attach(float coef, int expon){
if( avail > MAX_TERMS){
fprintf(stderr, "항의 개수가 너무 많음\n");
exit(1);
}
terms[avail].coef = coef;
terms[avail++].expon = expon;
}
void poly_add2(int As, int Ae, int Bs, int Be, int *Cs, int *Ce){
float tempcoef;
*Cs = avail;
while (As <= Ae && Bs <= Be){
switch(compare(terms[As].expon, terms[Bs].expon)){
case '>':
attach(terms[As].coef, terms[As].expon);
As++;
break;
case '=':
tempcoef = terms[As].coef + terms[Bs].coef;
if (tempcoef) attach(tempcoef, terms[As].expon);
As++;
Bs++;
break;
case '<':
attach(terms[Bs].coef, terms[Bs].expon);
Bs++;
break;
}
}
for(; As<= Ae; As++)
attach(terms[As].coef, terms[As].expon);
for(; Bs<= Be; Bs++)
attach(terms[Bs].coef, terms[Bs].expon);
*Ce = avail - 1;
}
3. 포인터
마찬가지로 상세한 내용은 KNK 정리 파트에서 확인하기로 하고, 여기서는 개념만 간단히 짚고 넘어간다.
(1) 개념
프로그래밍에서 모든 변수는 메모리 공간에 저장되고 여기서 메모리의 각 바이트에는 주소가 있다. 즉 모든 변수는 주소를 가지고 있는데, 포인터는 이러한 다른 변수의 주소를 가지고 있는 변수이다.
(2) 동적 메모리 할당
지금까지 살펴본 배열의 경우 고정된 크기를 갖고 있어 불합리한 측면이 있었다. 이 크기보다 큰 입력의 경우 제대로 처리할 수 없고, 더 작은 입력의 경우 공간이 낭비되기 때문이다. 이를 해결하기 위해 C언어에서는 필요한 크기의 메모리를 운영체제로 부터 할당받아 사용하고, 사용후에는 메모리를 반납하도록 하는 효율적인 기능이 있는데, 이를 동적 메모리 할당이라고 한다.
int *p
p = (int *)malloc(sizeof(int)); // 동적 메모리 할당
*p = 1000; // 동적 메모리 사용
free(p); // 동적 메모리 반납