[자료구조] - 자료구조 구현을 위한 C 프로그래밍 기법

👋 본 글은 "C로 배우는 쉬운 자료구조" 책을 읽고 요약, 정리한 글입니다.

---

책 구매 링크에서 책을 확인하실 수 있습니다.

 

🎯 1. 배열

---

📌 1 - 1. 배열의 개념

배열이란? : 자료형이 같은 자료를 나열하여 메모리에 연속으로 저장하여 만든 자료 그룹

• 배열의 요소를 구별하기 위해 인덱스를 사용, C 언어에서 인덱스는 항상 0부터 시작
• 모든 자료형으로 배열을 구성할 수 있음
• 1차원뿐만 아니라 2차원, 3차원 등 다차원 배열로 구성할 수 있음

 

📌 1 - 2. 1차원 배열

1차원 배열의 선언 형식

자료형

배열 이름

[배열 요소의 개수];

 

선언 예시)

배열 선언 예	의미	배열 요소	메모리 할당 크기
char c[100];	char형 배열 요소 100개로 구성된 배열 c	c[0] ~ c[99]	1byte x 100
int i[100];	int형 배열 요소 100개로 구성된 배열 i	i[0] ~ i[99]	4byte x 100
short s[100];	short형 배열 요소 100개로 구성된 배열 s	s[0] ~ s[99]	2byte x 100
long l[100];	long 형 배열 요소 100개로 구성된 배열 l	l[0] ~ l[99]	4byte x 100

 

C 언어로 배열 요소의 크기와 배열의 크기 출력하는 방법

#include <stdio.h>

void main(){
	int i, i_array[100];
    
    printf("int i 크기 = %d \t int i_array 크기 = %d", sizeof(i), sizeof(i_array));
}

 

1차원 배열의 초기화 형식

자료형

배열 이름

[배열 크기]

=

{초깃값 리스트}

초깃값 리스트에는 초깃값을 쉼표로 구분하여 나열, 초깃값들을 순서대로 지정됨

초기화를 할 경우, 배열의 크기를 생략하면 작성한 초깃값의 개수로 배열의 크기가 지정됨

 

선언, 초기화 예시) 아래 세 가지 방법은 모두 같은 요소를 가진 배열을 선언하고 초기화하는 코드

int i[5] = {10, 20, 30, 40, 50};

int i[] = {10, 20, 30, 40, 50};

int i[5];
i[0] = 10;
i[1] = 20;
i[2] = 30;
i[3] = 40;
i[4] = 50;

 

배열 크기 > 초깃값 개수일 경우, 초깃값을 지정하지 않은 나머지 요소는 기본값 0이 할당되고

int i[5] = {1, 2, 3};

i[0]	i[2]	i[3]	i[4]	i[5]
1	2	3	0	0

 

배열 크기 < 초깃값 개수일 경우, 배열 크기만큼의 초깃값만 할당되고 나머지 값들은 사용할 수 없는 값이 됨

int i[3] = {1, 2, 3, 4, 5};

i[0]	i[1]	i[2]
1	2	3

 

문자 배열

• C 언어에는 문자형은 있지만, 문자열형은 없으므로 문자열을 문자 배열로 구현함
• 문자들을 배열에 연속적으로 저장하는 형태이기 때문에 배열의 자료형은 char형이 됨
• 문자열이 저장될 때는 배열의 마지막에 항상 문자열의 끝을 나타내는 널 문자('\0', NULL)가 들어가기 때문에 배열의 크기는 실제 문자열의 크기보다 1바이트가 더 커야 함

 

char string[10] = "String";

string[0]	string[1]	string[2]	string[3]	string[4]	string[5]	string[6]	string[7]	string[8]	string[9]
S	t	r	i	n	g	\0

 

char string[] = {'S', 't', 'r', 'i', 'n', 'g', '\0'};

string[0]	string[1]	string[2]	string[3]	string[4]	string[5]	string[6]
S	t	r	i	n	g	\0

 

📌 1 - 3. 다차원 배열

• 배열은 2차원, 3차원 등으로 구성하여 2차원 배열, 3차원 배열로 나타낼 수 있음
• C 언어에서 배열은 행 우선 방식이기 때문에, 다차원에서 가로(행)가 먼저 채워지고 세로(열)가 추가됨

 

다차원 배열의 선언

2차원 배열의 선언 형식

		행 개수	열 개수
자료형	배열 이름	[배열 크기]	[배열 크기]

 

2차원 배열의 선언 C 코드

int i[2][3];

2차원 배열 구조

	0열	1열	2열
0행	i[0][0]	i[0][1]	i[0][2]
1행	i[1][0]	i[1][1]	i[1][2]

 

3차원 배열의 선언 형식

		면 개수	행 개수	열 개수
자료형	배열 이름	[배열 크기]	[배열 크기]	[배열 크기]

 

3차원 배열의 선언 C 코드

int i[2][3][4];

3차원 배열 구조

0면	0열	1열	2열	3열
0행	int[0][0][0]	int[0][0][1]	int[0][0][2]	int[0][0][3]
1행	int[0][1][0]	int[0][1][1]	int[0][1][2]	int[0][1][3]
2행	int[0][2][0]	int[0][2][1]	int[0][2][2]	int[0][2][3]

 

1면	0열	1열	2열	3열
0행	int[1][0][0]	int[1][0][1]	int[1][0][2]	int[1][0][3]
1행	int[1][1][0]	int[1][1][1]	int[1][1][2]	int[1][1][3]
2행	int[1][2][0]	int[1][2][1]	int[1][2][2]	int[1][2][3]

 

다차원 배열의 초기화

• 다차원 배열이 배열의 배열이라는 것을 생각하여 초깃값을 구분하여 지정하거나, 1차원 배열처럼 그냥 나열해도 됨
• 1차원 배열과 마찬가지로 배열의 크기를 생략할 수 있지만 첫 번째 크기만 생략 가능

 

2차원 배열의 초기화 C 코드

int i[][3] = {
	{1, 2, 3},
	{4, 5, 6}
};

==

int i[][3] = {1, 2, 3, 4, 5, 6};

2차원 배열의 구조

	0열	1열	2열
0행	1	2	3
1행	4	5	6

 

3차원 배열의 초기화 C 코드

int i[2][3][4] = {
	{
    	{1, 2, 3, 4}, 
    	{5, 6, 7, 8}, 
    	{9, 10, 11, 12}
    },
    {
    	{13, 14, 15, 16}, 
    	{17, 18, 19, 20}, 
    	{21, 22, 23, 24}
    }
}

3차원 배열의 구조

0면	0열	1열	2열	3열
0행	1	2	3	4
1행	5	6	7	8
2행	9	10	11	12

0면	0열	1열	2열	3열
0행	13	14	15	16
1행	17	18	19	20
2행	21	22	23	24

 

문자 다차원 배열

문자 배열 역시 다차원으로 구성할 수 있음

char c[3][10] = {
	"Gugonggu",
	"Hongchun",
    "Busan Kor"
};

 

G	u	g	o	n	g	g	u	\0
H	o	n	g	c	h	u	n	\0
B	u	s	a	n		K	o	r	\0

 

🎯 2. 포인터

---

📌 2 - 1. 포인터 개념

포인터란? : 변수가 저장되는 특정 메모리의 위치

• 포인터 변수는 메모리의 주소값을 저장하는 특별한 변수
• 포인터 변수 P가 어떤 변수 A의 주소를 저장하고 있다는 것은, 포인터 변수 P가 변수 A의 위치(메모리 주소)를 가리키고 있다(포인트 하다)는 의미

 

📌 2 - 2. 포인터 선언

 

포인터 선언 형식

자료형	*포인터 이름
포인터 자체의 자료형이 아니라, 포인터에 저장할 주소에 있는 일반 변수의 자료형	*를 붙여 포인터임을 나타냄

 

int *ptr;

 

📌 2 - 3. 포인터 연산

C 언어에서 사용하는 포인터 관련 연산자에는 주소 연산자 &와 참조 연산자 *가 있음

 

주소 연산자(&)

주소 연산자는 변수의 주소를 얻는 데 사용

다음과 같이 포인터에 &을 사용하여 변수를 저장할 경우, 변수의 값이 아닌 변수가 저장되어 있는 메모리의 주소를 저장함

int i = 10;
int *ptr = &i;

 

참조 연산자(*)

다른 변수의 주소가 저장된 포인터에 참조 연산자 *를 사용하면 저장된 주소의 값을 참조할 수 있음

int i = 10;
int *ptr = &i;

10 == *ptr // true

 

📌 2 - 4. 포인터 초기화

포인터를 초기화하는 방법은 일반 변수와 같지만, 저장하는 값이 메모리 주소라는 사실을 주의해야 함

int i = 10;
int *iptr = &i;

int array[100];
int *iaptr1 = array;
// 배열 자료형은 일반 자료형과는 다르게 배열 이름으로 포인터를 지정할 수 있음
// 배열의 값들이 지정되는게 아니라, 배열이 시작하는 주소가 지정됨

int *iaptr2 = &array[0];
// 위와 같은 값이 저장됨 (배열이 시작하는 주소)

int *cptr = "gugonggu";
// 문자열 또한 배열 형태의 자료형이므로 문자열이 시작되는 주소가 지정됨

 

📌 2 - 5. 포인터와 문자열

포인터를 이용하면 배열에 저장된 문자열에 대한 연산을 쉽게 처리할 수 있음

char string[10] = "Gugonggu";
char *ptr = string;

// 문자열 요소 참조
*ptr == 'G'; // true
*(ptr + 1) == 'u'; // true
*(ptr + 2) == 'g'; // true

// 문자열 요소 변경
*ptr = 'a';
*(ptr + 1) = 'b';
*(ptr + 2) = 'c';

 

📌 2 - 6. 포인터 배열

포인터 배열은 여러 개의 포인터를 하나의 배열로 구성한 것으로, 배열과 포인터의 특징을 모두 활용할 수 있음

char *ptr[3] = { {"Hello"}, {"World"}, {"C Language"} };

일반 배열은 한 번 할당된 배열의 크기를 줄이거나 늘리기 어렵기 때문에 할당된 배열의 크기보다 실제 사용 공간이 작으면 메모리가 낭비되고, 필요한 공간이 할당된 크기보다 크다면 배열을 새로 만들어야 한다, 이에 비해 포인터 배열은 문자열의 길이에 따라 메모리가 할당되기 때문에 문자열의 길이를 예측할 수 없거나 문자열의 길이가 변하는 경우에도 메모리를 좀 더 효율적으로 사용할 수 있다.

 

📌 2 - 7. 포인터의 포인터(이중 포인터)

이중 포인터는 포인터를 가리키는 포인터로, *를 2개 사용한다.

int i = 10;
int *ptr1 = &i;
int **ptr2 = ptr;

10 == *ptr2; // true

 

🎯 3. 구조체

---

📌 3 - 1. 구조체 개념

구조체도 배열처럼 여러 데이터를 묶어 하나의 자료형으로 사용하는 자료형이지만 자료형이 같을 때만 사용할 수 있는 배열과는 다르게 서로 다른 자료형들도 그룹으로 묶을 수 있음

 

📌 3 - 2. 구조체 선언

배열과는 달리 요소마다 자료형을 선언하는 점에 주의한다

struct employee{
	char name[10];
    int year;
    int pay;
};

구조체 employee의 크기는 1 * 10 + 4 + 4로 총 18바이트가 된다

 

구조체 사용 형식은 다음과 같다

struct

구조체 이름

구조체 변수 이름

struct employee gugonggu;
struct employee Jung;

struct employee Lee, Kim, Park;

 

📌 3 - 3. 구조체 변수의 초기화

구조체 변수의 초기화는 배열을 초기화하는 것과 비슷하게 초깃값 리스트로 값을 지정한다

struct employee {
	char name[10];
    int year;
    int pay;
}

struct employee Gugonggu = {"Hongchun", 2023, 2800};

 

 

📌 3 - 4. 데이터 항목의 참조

구조체 변수에 있는 데이터 항목을 참조하려면 점 연산자(.)와 화살표 연산자(->)를 사용함

 

점 연산자(.)

struct employee {
	char name[10];
    int year;
    int pay;
}

struct employee gugonggu;

gugonggu.year = 2023;
guggongu.pay = 2800;

gugonggu.year == 2023; // true

 

화살표 연산자(->)

구조체형에도 포인터를 사용할 수 있는데, 구조체형 포인터에서 포인터가 가리키는 구조체 변수의 데이터 항목을 지정할 때 사용한다

struct employee {
	char name[10];
    int year;
    int pay;
}

struct employee gugonggu;

gugonggu.year = 2023;
gugonggu.pay = 2800;

struct employee *sptr = &gugonggu;

sptr->year = 2003;
sptr->pay = 5000;

gugonggu.year == 2003; // true
gugonggu.pay == 5000; // true

 

화살표 연산자(->)는 참조 연산자(*)를 사용하여 표현할 수도 있다

참조 연산자를 사용할 때 괄호를 사용하지 않으면 점 연산자(.)가 참조 연산자(*)보다 연산 우선순위가 높으므로 오류가 발생함을 주의해야 한다

sptr->year = 2003;
sptr->pay = 5000;

==

(*sptr).year = 2003;
(*sptr).pay = 5000;

 

📌 3 - 5. 구조체 연산

데이터 항목 참조 연산

점 연산자와 화살표 연산자를 이용해 데이터 항목을 참조할 수 있다

struct employee gugonggu;
struct employee *sptr;
sptr = &gugonggu;

gugonggu.name == "Hongchun"; // true
sptr->year == 2023; // true;

 

구조체 변수 복사 연산

같은 구조체에 있는 구조체 변수라면 변수들끼리 한 번에 복사할 수 있다.

struct employee gugonggu, Jung;

// Jung의 데이터가 gugonggu로 복사됨
gugonggu = Jung;

 

구조체 변수의 주소 구하기 연산

struct employee gugonggu;
struct employee *sptr;

sptr = &gugonggu;

 

🎯 4. 재귀호출

---

📌 4 - 1. 재귀호출의 개념

재귀호출이란? : 함수가 자기 자신을 호출하여 순환하여 수행되는 것

재귀호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음

 

재귀호출은 현재 작업을 한 번에 해결할 수 없어서 좀 더 작은 단위의 작업으로 분할하여 문제를 해결할 때 사용한다

문제를 한 번에 해결할 수 있을 때까지 분할하다 보면 한 번에 문제를 해결할 수 있을 정도인 베이스케이스에 도달하게 되는데, 베이스케이스에서 구한 답을 반환해서 분할의 역순으로 거슬러 올라가면 처음의 문제를 해결할 수 있게 된다.

 

📌 4 - 2. 재귀호출의 예 1 : 팩토리얼 함수

대표적인 재귀호출 함수는 팩토리얼이다

 

팩토리얼을 구하려면 1부터 n까지 모든 자연수를 곱해야 하는데

n! = n x (n - 1)! 이므로 (n - 1)!을 구하려면

(n - 1)! = (n - 1) x (n - 2)! 이므로 (n - 2)!을 구해야 한다 따라서 최종적으로

n! = n x (n - 1)! x ... x 1! 형태가 되는데 1!가 현재 답을 구할 수 있는 베이스케이스이므로 1을 반환해서 상위값을 반환하는 작업을 반복해 n!을 구한다

 

아래는 재귀호출을 이용해 팩토리얼을 구하는 함수이다

long int fact(int n){
	if (n <= 1)
    	return (1);
    else
    	return (n * fact(n - 1));
}

 

📌 4 - 3. 재귀호출의 예 2 : 하노이 탑

사실 팩토리얼 함수는 단순 반복 구조라 반복문으로 구현할 수 있지만 복잡한 재귀 구조 문제는 재귀호출을 사용해야 해결할 수 있다

대표적인 예가 하노이의 탑 퍼즐인데, 하노이의 탐 퍼즐에는 세 개의 기둥과 기둥에 꽂을 수 있는 크기가 다양한 원반이 n개 있다. A에서 시작했을 때, C에 원반들이 크기 순서대로 쌓여야 퍼즐이 끝나게 된다.

 

1. 시작봉에 있는 원반들을 임시봉을 목적봉을 이용하여 임시봉으로 옮기고
2. 시작봉에 남아있는 마지막 원반을 목적봉으로 옮긴 뒤
3. 임시봉에 있는 원반들을 시작봉을 이용해 목적봉으로 옮겨야 한다

실행 순서는 다음과 같다.

 

hanoi(3, 'A', 'B', 'C');에서 시작

• hanoi(2, "A", "C", "B")
  • hanoi(1, "A", "B", "C")
    • print ➡️ A에서 1을 C로 옮김
  • print ➡️ A에서 2를 B로 옮김
  • hanoi(1, "C", "A", "B")
    • print ➡️ C에서 1을 B로 옮김
• print ➡️ A에서 원반 3을 C로 옮김
• hanoi(2, "B", "A", "C")
  • hanoi(1, "B", "C", "A")
    • print ➡️ B에서 1을 A로 옮김
  • print ➡️ B에서 2를 C로 옮김
  • hanoi(1, "A", "B", "C")
    • print ➡️ A에서 1을 C로 옮김

void hanoi(int n, char start, char temp, char target){
	if(n == 1)
    	printf("%c에서 원반 %d를  %C로 옮김 \n", start, n, target);
	else {
    	hanoi(n - 1, start, target, temp);
        printf("%c에서 원반 %d를 %c로 옮김 \n", start, n, target)
        hanoi(n - 1, temp, start, target);
    }
}