[자료구조] 배열과 구조체

1. 많은 자료의 처리

 배열, 구조체

- 성적 처리 프로그램에서 여러명의 성적을 저장하는 방법 -> 배열

- 사람들의 다양한 정보를 통합하여 저장하는 방법 -> 구조체

- 배열, 구조체는 고급 자료 구조를 만드는데 핵심 요소

 

2. 배열

- 배열은 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용됨.

- ex) 6개의 정수를 저장할 공간이 필요한 경우, 배열이 없다면 변수를 독립적으로 선언해야 함.

int a1,a2,a3,a4,a5,a6; // 6개의 정수형 변수를 각각 선언
int A[6]; // 배열로 6개의 정수형 변수 선언

 

배열의 특징

1. <인덱스, 요소> 쌍의 집합

- 인덱스가 주어지면 해당되는 요소가 대응되는 구조

- 모든 요소는 동일한 자료형

- 동일한 이름을 사용하고 인덱스로 항목을 접근함

int num[3] = {1,2,3}; // 자료형이 int형으로 동일함
if ( num[1] == 2 ) // True

 

2. 직접 접근 방식

- K번째 항목 참조 시 이 항목의 위치가 바로 계산되어 이 항목을 참조함

- 항목 접근의 시간 복잡도가 O(1)

- 배열과 다른 접근 법을 사용한 자료구조 : 연결 리스트

 

1차원 배열

- 일차원 배열 선언 형식 : 자료형 배열이름[배열의_크기]; ex ) int A[3];

- 배열에서는 모든 요소들이 연속된 공간에 저장됨

- A(L:U) 일 때 원소의 개수 : U - L + 1 = 3

- 인덱스가 i인 원소 A[i]의 주소 : Base address + i * size

배열의 복사

- 배열은 대입연산자로 한꺼번에 복사할 수 없으며, 각 항목을 일일이 복사해야함.

- 변수의 복사와 배열의 복사

#include <stdio.h>

int main()
{
	int A[5] = { 1,2,3};
	int B[5], x = 2023, y = 0;

	printf("변수 복사 전 y : %d \n", y);
	y = x;
	printf("변수 복사 후 y : %d \n", y);

	printf("배열 복사 후\n");
	for (int i = 0; i < 5; i++)
	{
		B[i] = A[i];
		printf("B[%d] : %d\n", i, B[i]);
	}

	return 0;
}

문자열 : 특별한 1차원 배열

- char s[8] = "Hello";

- 문자열 처리

-> 문자열의 복사나 비교를 위해 =나 == 또는 <등의 연산자를 사용할 수 없음. ( strcmp(), strcpy(), ... )

 

2차원 배열

- 1차원 배열이 여러 개 모여서 이루어짐. 2차원 배열에서 가로줄을 행, 세로줄을 열이라고 함

- 자료형 배열이름[행의_크기][열의_크기]; ex) int A[4][2];

- A(L1:U1, L2:U2)일 때 원소의 개수 : (U1-L1+1) * (U2-L2+1)

- A[i, j]의 주소 : Base address + (i*u2 + j ) * size

 

다차원 배열

- 자료형 배열이름[면의_크기][행의_크기][열의_크기]; ex ) int A[2][3][2];

- A(L1:U1, L2:U2, L3:U3)일 때 원소의 개수 : (U1-L1+1) * (U2-L2+1) * (U3-L3+1)

- A[k,i,j]의 주소 : Base address + (u1*u2*k + (i*u2+j)) * size

 

함수의 매개변수로서의 배열

- 변수의 전달 -> 값을 복사 (call by value) // 메모리 공유 안되고 값만 복사됨.

- 배열의 전달 -> 첫 번째 항목의 주소를 전달함 (주소를 복사함) // 메모리 공유

- 함수의 매개변수로서의 변수와 배열 프로그램 예시

#include <stdio.h>

void copy_array(int a[], int b[], int len)
{
	for (int i = 0; i < len; i++)
		b[i] = a[i];
}

void copy_var(int a, int b)
{
	b = a;
}

int main()
{
	int A[5] = { 1,2,3};
	int B[5], x = 2023, y = 0;

	printf("변수 복사 전 y : %d \n", y);
	copy_var(x, y);
	printf("변수 복사 후 y : %d \n", y);

	copy_array(A, B, 5);
	printf("배열 복사 후\n");
	for (int i = 0; i < 5; i++)
	{
		printf("B[%d] : %d\n", i, B[i]);
	}

	return 0;
}

배열에서의 주의 사항

1. 매개 변수로 배열의 길이도 전달해야 함.

2. 2차원 이상의 다차원 배열의 매개 변수 전달에 조심

 

3. 구조체

- 기존의 자료형들을 조합해 새로운 자료형을 만드는 방법 ( 다양한 자료형의 데이터의 모임 )

 

구조체의 정의와 선언

- 구조체의 정의와 선언은 정확히 구분되어야 함.

- 구조체를 정의하는 것 -> 기존의 자료형들을 조합해 새로운 자료형을 정의하는 것

- 구조체를 선언하는 것 -> 새로운 구조체 변수를 생성하는 것

 

구조체 정의 형식

struct 구조체이름 {
	자료형1 변수면1;
	자료형2 변수명2;
	. . .
	자료형N 변수명N;
};

 

ex) 학생의 정보를 저장하기 위한 구조체 정의, 새로운 구조체 s를 선언

struct Student {
	int id;
	char name[20];
	double score;
};

struct Student s;

※ 많은 경우엔 불편하므로 typedef문을 사용하여 구조체를 정의함

 

ex ) typedef문 사용한 구조체 정의, 새로운 구조체 s를 선언

typedef struct Student {
	int id;
	char name[20];
	double score;
}Student;

Student s;

 

ex ) 구조체의 초기화

Student s = {1234,"HGD", 94.7 };

 

멤버 접근 : 항목 연산자 '.'

a.id = 2345;
a.score = 89.2;
strcpy(a.name,"KYD"); // a.name = "KYD";은 오류 발생함

- 문자열도 배열이므로 대입연산자를 이용해 한꺼번에 복사할 수 없음.

- C언어의 표준 라이브러리에서 문자열 관련 함수를 통해 문자열을 복사함. <string.h>

 

구조체의 연산

- 대입 연산은 가능함 ( 다른 연산자 사용 불가 )

Student a,b = {1234,"HGD",76,8};
a = b; // 구조체 변수의 복사 가능함

구조체를 포함하는 구조체와 구조체 배열

- 구조체를 포함한 구조체도 정의 가능. 구조체의 배열 또한 가능함.

typedef struct {
	int month;
	int date;
}Birthday;

typedef struct {
	char name[20];
	Birthday birthday;
}Info;

int main() {
	Info list[3]; // 구조체 배열 선언
	list[0].birthday.month = 10;
	list[0].birthday.date = 9;
	strcpy(list[0].name, "CN");
}

 

구조체와 함수

- 구조체도 함수의 매개 변수나 반환형으로 사용될 수 있음

#include <stdio.h>

typedef struct {
	double real;
	double imag;
}Complex;

void print_complex(Complex c) {
	printf("%4.1f + %4.1f\n", c.real, c.imag);
}

void reset_complex(Complex c) {
	c.real = c.imag = 0.0;
}

int main() {
	Complex c = { 1.0, 2.0 };
	printf("초기화 이전 : ");
	print_complex(c);
	reset_complex(c);
	printf("초기화 이후 : ");
	print_complex(c);

	return 0;
}

- 생각과 다르게 초기화 이후의 복소수 값이 변하지 않음 -> 값에 의한 호출 방식 (call by value) 때문

- 값이 전달되는 것이 아닌 새로운 복소수 변수가 만들어지고 내용이 복사되기 때문에 원래 값 바뀌지 않음.

- 이를 해결하려면 ? 포인터 사용해야함.

 

4. 배열과 구조체의 응용 : 다항식 프로그램

다항식의 표현

- 모든 계수들을 배열에 저장하는 방법

ex ) p(x) = 10x^5 + 0x^4 + 0x^3 + 0x^2 + 6x^1 + 3x^0

-> 계수 리스트 (10, 0, 0, 0, 6, 3) 저장

- 최고차항 저장하는 변수 필요함

 

다항식 구조체 정의

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

 

다항식의 구현

다항식의 화면 출력 함수

- 매개변수로 구조체를 받아야함.

void print_poly(Polynomial p)
{
	for (int i = 0; i < p.degree; i++)
	{
		printf("%5.1f x^%d + ", p.coef[i], p.degree -i);
	}
	printf("%f \n",p.coef[p.degree-1]);
}

 

다항식의 입력 함수

- 사용자가 다항식을 입력 가능하도록 함.

- 입력을 받고 다항식 구조체를 반환해야함.

Polynomial read_poly() {
	Polynomial p;

	printf("다항식의 최고 차수를 입력하시오 : ");
	scanf("%d", &p.degree);
	printf("각 항의 계수를 입력하시오 : ");
	for(int i = 0; i < p.degree ; i++)
		scanf("%f", p.coef + i);
	return p;
}

 

두 다항식의 합

- 다항식의 합을 구하는 함수에는 두 다항식 구조체가 전달되어야 함.

- 다른 구조체를 만들어 입력 다항식의 합을 저장한 후 반환하면 됨.

Polynomial add_poly(Polynomial a, Polynomial b) {
	Polynomial p;
	if (a.degree > b.degree) {
		p = a;
		for (int i = 0; i <= b.degree; i++)
			p.coef[i + (p.degree - b.degree)] += b.coef[i];
	}
	else {
		p = b;
		for (int i = 0; i <=a.degree; i++)
			p.coef[i + (p.degree - a.degree)] += a.coef[i];
	}
	return p;
}

 

다항식 프로그램 & 결과

int main() {
	Polynomial a, b, c;
	a = read_poly();
	b = read_poly();
	c = add_poly(a, b);
	print_poly(a);
	print_poly(b);
	print_poly(c);

	return 0;
}

 

희소 다항식의 표현

- 대부분의 항의 계수가 0인 다항식

- 이러한 다항식을 구현한다면 메모리 낭비가 매우 심함 -> 모든 계수 저장하는 것이 아닌 (계수,지수) 형식으로 저장

 

희소 다항식 처리를 위한 구조체 정의

typedef struct {
    int expon; //항의 지수
    float coef; // 항의 계수
} Term;

typedef struct {
    int nTerms; // 0이 아닌 항의 개수
    Term term[MAX_TERMS];
} SparsePoly;

- 기존 구현했던거 보단 복잡해지지만 희소 다항식의 경우 메모리 낭비가 크므로 이러한 구현 방식이 효율적임