[자료구조] Chapter2. Arrays and Structures(1)

※ 이 카테고리의 글들은 knu EK.Ryu 교수님의 <자료구조> 수업을 듣고 나름대로 필자가 정리한 글입니다.

※ 부족한 설명이 있거나, 잘못 알고 작성한 부분이 보인다면 편하게 댓글로 알려주시면 정말 감사하겠습니다😊

2.1 Arrays 배열

배열은 인덱스와 값 <index, value>의 쌍으로 구성된 집합으로서, 정의된 각 인덱스는 그 인덱스와 관련된 값을 가집니다.

배열의 추상 데이타 타입(ADT)은 아래와 같습니다.

 

※ADT(추상 데이터 타입)란? 객체의 명세와 그 연산의 명세가 그 객체의 표현과 연산의 구현으로부터 분리된 데이터 타입입니다. 쉽게 말해, ADT는 데이터와 그 데이터를 다루는 연산을 추상적으로 정의한 것으로, 구현 세부 사항에 구애받지 않고 데이터 구조를 다룰 수 있는 개념입니다.

 

(1)  C언어에서의 배열

먼저 1차원 배열만을 생각해봅시다.

C에서 1차원 배열은 변수의 이름 끝에 [ ] 와 같은 중괄호를 추가하여 선언합니다.

int list[5], *plist[5];

위의 선언은 각각 5개의 원소를 포함하는 두 배열을 선언한 것입니다.

첫 번째 배열은 5개의 정수를 정의한 반면, 두 번째는 정수에 대한 5개의 포인터를 정의했습니다.

즉, list[0], list[1], ... , list[4]는 배열 원소의 이름이고, 이들 각자는 하나의 정수 값(int 값)을 포함합니다.

마찬가지로 plist[0], plist[1], ... 은 정수에 대한 포인터를 포함합니다.

 

예제를 먼저 봅시다.

예제 2.1 다음과 같이 배열을 선언할 경우를 가정해봅시다.

int one[] = {0, 1, 2, 3, 4};

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void print1(int* ptr, int rows)
{
	int i;
	printf("Address Contents\n");
	for (i = 0; i < rows; i++)
		printf("%8u%5d\n", ptr + i, *(ptr + i));
	printf("\n");
}

int main()
{
	int one[] = {1, 2, 3, 4, 5};
	int rows = 5;
	print1(one, rows);
}

위 사진은 print1 함수를 실행해서 얻은 결과를 보여주고 있습니다.

이 프로그램에서 i가 1씩 증가해도 메모리 주소는 4씩 증가하는 것으로 보이는 이유는, 배열의 각 요소가 4바이트 크기의 int이기 때문입니다.

 

2.2 Dynamically Allocated Array 동적으로 할당된 배열

프로그램에서 100의 크기를 가지는 배열을 선언했다고 해봅시다.

int box[100];

만일 이 배열에 100개보다 많은 수를 담으려고 한다면, 어떻게 해야 할까요?

이에 대한 좋은 해답은, 이 결정을 실행 시간까지 미루었다가 필요한 배열 크기의 적당한 추정치가 나올 때 배열을 할당하는 것입니다.

int i, n, *list;
printf("Enter the number of number to generate: ");
scanf("%d, &n");

if(n < 1 )
{
	fprintf(stderr, "Improper value of n\n");
    exit(EXIT_FAILURE);
}
MALLOC(list, n * sizeof(int));

 

(1) 2차원 배열

C 언어는 다차원 배열을 표현하기 위하여 소위 배열의 배열을 사용합니다.

int x[3][5];

라고 하면, 실제로 길이가 3인 1차원 배열 x가 생성되는데, 이 x의 각 원소는 길이가 5인 1차원 배열입니다.

아래 그림을 통해 이에 대한 메모리 구조를 자세히 볼 수 있습니다.

원소 x[i][j]를 찾을 때 제일 먼저 x[i]에 있는 포인터에 접근합니다. 이 포인터는 배열의 행 i의 0번째 원소의 메모리 주소를 제공하고, 그러면 이 포인터에 j * sizeof(int)를 더하면 행 i의 [j]번째 원소(즉, 원소 x[i][j])의 주소가 결정됩니다.

 

2.3 Structures and Unions 구조와 유니언

배열은 같은 타입의 데이터 모임입니다.

그렇다면 다른 타입의 데이터를 그룹화하는 방법이 있을까요?
이를 구조체 structure 라고 합니다.

 

typedef struct {
	char name[50];
    int age;
    float gpa;
} Student;

typedef struct {
	int x, y;
} Point;

typedef struct {
	int day;
    int month;
    int year;
} Date;

위와 같이 typedef 명령문을 사용하여 구조 데이터 타입을 생성할 수 있습니다.

typedef를 사용하면 매번 struct 키워드를 쓰지 않아도 되므로 코드가 더 간결하게 작성됩니다.

 

구조체들의 데이터 타입이 같을 때 person1 = person2와 같은 방식으로 복사가 가능하지만,

비교 연산자는 불가능합니다. (Ex. if (person1 == person2) )

따라서 구조체 간의 비교를 위해서는 아래의 방식과 같이 일일이 비교를 해야 합니다.

#define FALSE 0
#define TRUE 1

int humansEqual (humanBeing person1, humanBeing person2)
{
	if(strcmp(person1.name, person2.name))
    	return FALSE;
    if(person1.age != person2.age)
    	return FALSE;
    if(person1.salary != person2.salary)
    	return FALSE;
    return TRUE;
}

 

 

 

또한 구조체 속에 또 다른 구조체를 정의할 수도 있습니다. 예를 들어 humanBeing 구조체 속에 생년월일을 포함하고자 하는 경우 다음과 같이 작성할 수 있습니다.

typedef struct {
	int month;
    int day;
    int year;
} date;

typedef struct {
	char name[10];
    int age;
    float salary;
    date dob;
} humanBeing;

humanBeing person1;
person1.dob.month = 12;
person1.dob.day = 8;
person1.dob.year = 1993;

 

(1) Unions 공용체

공용체의 특징은 공용체 내부의 필드들이 메모리 공간을 공용한다는 것입니다.

예를 들어, 아래 공용체의 크기는 얼마인지 봅시다.

union Data 
{
   int i;
   float f;
   char str[20];
};

위의 공용체의  크기는 20바이트입니다. (가장 큰 char str[20]에 따라..)

 

반면, 구조체의 크기는 항상 4의 배수입니다.

또한, 구조체 내 필드의 순서에 따라 구조체의 크기가 달라질 수 있습다.

#include <stdio.h>

typedef struct {
	char a;
    int b;
    char c;
} InefficientStruct;

typedef struct {
	int b;
    char a;
    char c;
} EfficientStruct;

int main()
{
	printf("%lu bytes\n", sizeof(InefficientStruct));
    printf("%lu bytes\n", sizeof(EfficientStruct));
    
    return 0;
}

 

이 경우, InefficientStruct는 12바이트, EfficientStruct는 8바이트입니다.

이 두 구조체의 크기가 다른 이유는 메모리 패딩(Memory Padding) 때문입니다. 메모리 패딩은 컴파일러가 성능을 최적화하기 위해 구조체의 멤버들을 정렬(Alignment)하는 과정에서 발생합니다. (예를 들어 int 타입은 4바이트 경계에서 정렬되도록 설정됨)

결론적으로, 구조체의 멤버 순서에 따라 패딩이 달라지며, 이는 구조체의 전체 크기에 영향을 미칩니다. 따라서, 패딩을 최소화하려면, 구조체의 멤버를 큰 데이터 타입부터 작은 데이터 타입 순서로 배치하는 것이 좋습니다.