26 min to read

자료구조(4) - 배열

배열의 ADT를 만들고, 구현

Featured image

🔚 짧게 하는 복습

✅ 1. 정적할당을 동적할당으로 구현할 수 있다.

✅ 2. 동적할당의 원리를 안다.

✅ 3. 동적할당을 이용하는 방법을 안다.

혹시 기억이 안 난다면, 다시 돌아가자

이번 강의부터는 본격적으로 자료구조의 ADT 작성과 구현에 대해 다루어 볼 것이다.

자료구조를 나누는 기준이 있는데, 배열처럼 일직선으로 연속적인 데이터를 다루면 선형 자료구조 아니라면 비선형 자료구조라고 한다.

선형 자료구조의 가장 기본, 배열에 대해 다루겠다.

배열의 ADT 작성

우리가 지금까지 다룬 배열은 간단한 작업만 했다. 인덱스를 이용해서 값을 참조하고, 수정하기 등의 간단한 것들 말이다.

이번에는 조금 더 자세하게 ADT를 작성해보겠다.

거의 모든 ADT에 있어서 기본적인 기능은 삽입, 수정, 삭제, 조회, 순회이다.

조회와 순회가 조금 안 익숙할 텐데, 조회는 전체 자료에서 원하는 값을 검색하는 기능이고 순회는 전체 자료를 보여주는 기능이다.

배열 ADT

  • 자료 : 정수
  • 기능1 삽입 : 인덱스와 값을 받으면 그 인덱스에 입력한다.
  • 기능2 수정 : 인덱스와 값을 받으면 그 인덱스의 기존값을 입력값으로 수정한다.
  • 기능3 삭제 : 인덱스를 받으면 그 인덱스의 기존값을 삭제한다.
  • 기능4 조회 : 값을 입력받으면 그 값이 있는 인덱스를 반환한다.
  • 기능5 순회 : 처음부터 끝까지 인덱스와 값을 출력한다.

    • ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정이 가능하다.

    배열의 ADT 구현

    #include <stdio.h>
#define MAX 10 //전처리를 통한 배열 최대 크기 설정

/*
자료 : 정수
기능1 삽입 : 인덱스와 값을 받으면 그 인덱스에 입력한다.
기능2 수정 : 인덱스와 값을 받으면 그 인덱스의 기존값을 입력 값으로 수정한다.
기능3 삭제 : 인덱스를 받으면 그 인덱스의 기존값을 삭제한다.
기능4 조회 : 값을 입력받으면 그 값이 있는 인덱스를 반환한다.
기능5 순회 : 처음부터 끝까지 인덱스와 값을 출력한다.
*/

// + 입력 받은 index가 지금 현재 배열 사이즈보다 작은지(유효한 지) 확인함.
int is_index_valid(const int index, const int cur_size) {
	if (index >= 0 && index <= cur_size) {
		return 1;//참
	}
	else {
		return 0;//거짓
	}
}// 정적 배열이기 때문에 0 ~ MAX사이의 인덱스가 나와야 함.


//기능 1. 삽입
int insert(int* arr, const int index, const int value, int* cur_size) {
	if (*cur_size == MAX) {
		printf("Array is already full!\n");
		return -1;
		// 더 이상 삽입 할 수 없다면 함수 종료
	}

	if (is_index_valid(index, *cur_size)) {
		for (int i = *cur_size-1; i >= index; i--) {
			arr[i + 1] = arr[i];
		}// 한 칸씩 뒤로 밀어서, 삽입할 위치를 비움

		*cur_size += 1;
		//배열의 현제 사이즈를 늘린다.

		arr[index] = value;
		// 배열에 값을 삽입함

		printf("sucessfully inserted %d in index %d\n", value, index);
		return 0;
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}

//기능2. 수정
int update(int* arr, const int index, const int value, int* cur_size) {
	if (is_index_valid(index, *cur_size)) {
		arr[index] = value;
		// 배열에 값을 삽입함

		printf("sucessfully changed value to %d in index %d\n", value, index);
		return 0;
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}

int delete(int* arr, const int index, int* cur_size) {
	if (*cur_size == 0) {
		printf("Array is empty!\n");
		return -1;
		// 더 이상 삽입 할 수 없다면 함수 종료
	}

	if (is_index_valid(index, *cur_size)) {
		for (int i = index; i < *cur_size; i++) {
			arr[i] = arr[i+1];
		}
		// 특정 인덱스의 값을 지우고, 한 칸씩 뒤로 당김

		*cur_size -= 1;
		//배열의 현제 사이즈를 늘린다.

		printf("sucessfully deleted value in index %d\n\n", index);
		return 0;
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}


int search(int* arr, const int value, const int cur_size) {
	for (int i = 0; i < cur_size; i++) {
		if (arr[i] == value) {
			printf("%d's index : %d", value, i);
			return i;
		}
	}

	printf("There is no %d in array.(Error code -1)", value);
	return -1;
	// 전체 탐색 결과 없을시 -1 에러 코드 반환
}

int traversal(int* arr, const int cur_size) {
	if (cur_size == 0) {
		printf("Array has no element!\n");
		return -1;
	}
	//array가 비었을 때, 순회할 원소가 없다.

	printf("traversal:\n");

	for (int i = 0; i < cur_size; i++) {
		printf("%d ", arr[i]);
	}
	//순회

	printf("\n\n");
	return 0;
}

int main(void) {
	int arr[MAX] = { 0, };
	// 정수형 정적 배열 선언

	int cur_size = 0;
	// 정적 배열의 현재 사이즈

	traversal(arr, cur_size);

	insert(arr, 0, 1, &cur_size);
	insert(arr, 1, 2, &cur_size);
	insert(arr, 2, 3, &cur_size);
	insert(arr, 3, 4, &cur_size);
	insert(arr, 4, 5, &cur_size);
	insert(arr, 2, 6, &cur_size);
	insert(arr, 8, 8, &cur_size); // invalid operation

	traversal(arr, cur_size); // 1 2 6 3 4 5 출력

	update(arr, 2, 3, &cur_size);
	update(arr, 3, 4, &cur_size);
	update(arr, 7, 3, &cur_size); // invalid operation

	traversal(arr, cur_size); // 1 2 3,4,4,5 출력

	delete(arr, 4, &cur_size);

	traversal(arr, cur_size);

	delete(arr, 4, &cur_size);

	traversal(arr, cur_size);

	for(int i= 0; i<5; i++){
		delete(arr, 0, &cur_size);
	}// 비었다고 오류 날 때까지 지우기

	for (int i = 0; i < 11; i++) {
		insert(arr, 0, i, &cur_size);
		traversal(arr, cur_size);
	}// 다 찼다고 오류 날 때까지 지우기

}

    대부분 주석으로 설명했기에, 자세한 설명은 생략한다.

    삽입과 제거 부분에서 인덱스를 수정하는 조금 까다로운데, 이는 직접 손이나 눈으로 디버깅(코드의 오류, 버그를 잡는 과정)하는 과정이 필요하다.

    또한, 모든 코드를 void형이 아니라 int형으로 선언했는데 이는 굉장히 중요한 작업이다.

    void형 함수는 특별한 일이 있지 않으면 사용하지 말자, 모든 함수가 성공적으로 실행된다는 보장이 없기 때문이다.

    반면에 아래와 같이 작성하면,

      if(traversal(arr, cur_size) == -1){
    printf("error!");
  }

    성공적으로 실행되었을 때는 0, 아니라면 -1을 통해 확인할 수도 있다.

    마지막으로, 포인터의 간접 참조와 const를 잘 이용해서 매개변수를 설정하자.

    변해야하는 값은 간접 참조로 넘겨야 하고, 변하면 안 되는 값은 const로 상수화 시켜야 한다.

    결과창

    Array has no element!
sucessfully inserted 1 in index 0
sucessfully inserted 2 in index 1
sucessfully inserted 3 in index 2
sucessfully inserted 4 in index 3
sucessfully inserted 5 in index 4
sucessfully inserted 6 in index 2
Invalid operation!

traversal:
1 2 6 3 4 5

sucessfully changed value to 3 in index 2
sucessfully changed value to 4 in index 3
Invalid operation!

traversal:
1 2 3 4 4 5

sucessfully deleted value in index 4

traversal:
1 2 3 4 5

sucessfully deleted value in index 4

traversal:
1 2 3 4

sucessfully deleted value in index 0

sucessfully deleted value in index 0

sucessfully deleted value in index 0

sucessfully deleted value in index 0

Array is empty!
sucessfully inserted 0 in index 0
traversal:
0

sucessfully inserted 1 in index 0
traversal:
1 0

sucessfully inserted 2 in index 0
traversal:
2 1 0

sucessfully inserted 3 in index 0
traversal:
3 2 1 0

sucessfully inserted 4 in index 0
traversal:
4 3 2 1 0

sucessfully inserted 5 in index 0
traversal:
5 4 3 2 1 0

sucessfully inserted 6 in index 0
traversal:
6 5 4 3 2 1 0

sucessfully inserted 7 in index 0
traversal:
7 6 5 4 3 2 1 0

sucessfully inserted 8 in index 0
traversal:
8 7 6 5 4 3 2 1 0

sucessfully inserted 9 in index 0
traversal:
9 8 7 6 5 4 3 2 1 0

Array is already full!
traversal:
9 8 7 6 5 4 3 2 1 0

    동적 배열로 구현하기

    정적 배열로 ADT를 구현하는 일은 어렵지 않다.

    그런데 이렇게 하면 단점이 있다. 정해진 사이즈 이상의 원소를 담을 수 없다는 점이다.

    그렇다면 정적 배열이 아니라 동적 배열로 구현을 할 수 있을까? 조금 복잡하지만 malloc, realloc등을 이용하면 충분히 수정할 수 있다.

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

/*
자료 : 정수
기능1 삽입 : 인덱스와 값을 받으면 그 인덱스에 입력한다.
기능2 수정 : 인덱스와 값을 받으면 그 인덱스의 기존값을 입력 값으로 수정한다.
기능3 삭제 : 인덱스를 받으면 그 인덱스의 기존값을 삭제한다.
기능4 조회 : 값을 입력받으면 그 값이 있는 인덱스를 반환한다.
기능5 순회 : 처음부터 끝까지 인덱스와 값을 출력한다.
*/

// + 입력 받은 index가 지금 현재 배열 사이즈보다 작은지(유효한 지) 확인함.
int is_index_valid(const int index, const int cur_size) {
	if (index >= 0 && index <= cur_size) {
		return 1;//참
	}
	else {
		return 0;//거짓
	}
}// 정적 배열이기 때문에 0 ~ MAX사이의 인덱스가 나와야 함.


//기능 1. 삽입
/*
매우 중요. int* arr;은 동적배열의 주소값을 저장함.
동적 배열안의 값만 바꾼다면 arr의 포인터만 넘기면 됨,
하지만 arr 자체의 값을 바꿔야함
그 말은 arr의 포인터를 넘겨서 arr의 값을 간접 참조로 수정해야함.
즉 이중포인터를 넘겨야 함.
*/
int insert(int** arr, const int index, const int value, int* cur_size) {
	if (*cur_size == 0 && index == 0) {
		*arr = (int*)malloc(sizeof(int) * ++(*cur_size));
		//원소가 없을 땐 처음 malloc

		*arr[index] = value;
		printf("sucessfully inserted %d in index %d\n", value, index);
		return 0;
	}

	else if (is_index_valid(index, *cur_size)) {
		int* newarr = (int*)realloc(*arr, sizeof(int) * (*cur_size + 1));
		*arr = newarr;
		// 이미 원소가 있다면, realloc으로 재할당

		for (int i = *cur_size - 1; i >= index; i--) {
			*(*arr + i+1) = *(*arr + i);
			// 포인터의 간접 참조연산을 잘 생각해보면 이해할 수 있음
			// 배열 arr이라면, *(*arr + i+1)은 arr[i+1]과 같음
		}// 한 칸씩 뒤로 밀어서, 삽입할 위치를 비움

		*cur_size += 1;
		*(*arr+index) = value;// 배열에 값을 삽입함

		printf("sucessfully inserted %d in index %d\n", value, index);
		return 0;
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}

//기능2. 수정
/*
 위의 삽입과 대비되게, arr의 값을 바꿀 필요가 없음.
 동적 배열의 값만 바꾸면 되니까 이중 포인터를 넘길 필요가 전혀 없음.
*/
int update(int* arr, const int index, const int value, int* cur_size) {
	if (is_index_valid(index, *cur_size)) {
		arr[index] = value;
		// 배열에 값을 삽입함

		printf("sucessfully changed value to %d in index %d\n", value, index);
		return 0;
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}

// 기능3. 삭제
// 같은 이유로 이중포인터 전달
int Delete(int** arr, const int index, int* cur_size) {
	if (*cur_size == 0) {
		printf("Array is empty!\n");
		return -1;// 더 이상 삽입 할 수 없다면 함수 종료
	}

	if (is_index_valid(index, *cur_size)) {
		if (*cur_size == 1) {
			//원소가 하나밖에 없다면 arr의 값에 NULL값으로 저장하고 반환

			*arr = NULL;
			*cur_size -= 1;
			printf("sucessfully deleted value in index %d\n\n", index);
			return 0;
		}
		else {
			for (int i = index; i < *cur_size; i++) {
				*(*arr + i) = *(*arr + i + 1);
			}
			// 특정 인덱스의 값을 지우고, 한 칸씩 뒤로 당김

			int* newarr = (int*)realloc(*arr, sizeof(int) * (*cur_size - 1));
			*arr = newarr;
			// 이미 원소가 있다면, arr을 realloc으로 재할당

			*cur_size -= 1;
			//배열의 현제 사이즈를 늘린다.

			printf("sucessfully deleted value in index %d\n\n", index);
			return 0;
		}
	}
	else {
		printf("Invalid operation!\n\n");
		return -1;
	}
}

// 기능4. 조회
int search(int* arr, const int value, const int cur_size) {
	for (int i = 0; i < cur_size; i++) {
		if (arr[i] == value) {
			printf("%d's index : %d", value, i);
			return i;
		}
	}

	printf("There is no %d in array.(Error code -1)", value);
	return -1;
	// 전체 탐색 결과 없을시 -1 에러 코드 반환
}

// 기능5. 순회
int traversal(int* arr, const int cur_size) {
	if (cur_size == 0) {
		printf("Array has no element!\n");
		return -1;
	}
	//array가 비었을 때, 순회할 원소가 없다.

	printf("traversal:\n");
	for (int i = 0; i < cur_size; i++) {
		printf("%d ", arr[i]);
	}
	//순회

	printf("\n\n");
	return 0;
}

int main(void) {
	int* arr = NULL;
	// 정수형 정적 배열 선언

	int cur_size = 0;
	// 정적 배열의 현재 사이즈

	traversal(arr, cur_size);

	insert(&arr, 0, 1, &cur_size);
	insert(&arr, 1, 2, &cur_size);
	insert(&arr, 2, 3, &cur_size);
	insert(&arr, 3, 4, &cur_size);
	insert(&arr, 4, 5, &cur_size);
	insert(&arr, 2, 6, &cur_size);
	insert(&arr, 8, 8, &cur_size); // invalid operation

	traversal(arr, cur_size); // 1 2 6 3 4 5 출력


	update(arr, 2, 3, &cur_size);
	update(arr, 3, 4, &cur_size);
	update(arr, 7, 3, &cur_size); // invalid operation

	traversal(arr, cur_size); // 1 2 3,4,4,5 출력



	Delete(&arr, 4, &cur_size);

	traversal(arr, cur_size);

	Delete(&arr, 4, &cur_size);

	traversal(arr, cur_size);

	for (int i = 0; i < 5; i++) {
		Delete(&arr, 0, &cur_size);
	}// 비었다고 오류 날 때까지 지우기

	for (int i = 0; i < 11; i++) {
		insert(&arr, 0, i, &cur_size);
		traversal(arr, cur_size);
	}// 다 찼다고 오류 날 때까지 지우기

	free(arr); //해제하는 것을 까먹지 말자
}

    나머지는 거의 같지만, 추가와 삭제가 어렵다.

    이는 익숙하지 않아서인데, 우리는 다른 함수에서 어떤 변수의 값을 바꾸려면 변수의 포인터를 넘겨야 한다고 배웠다.

    그런데 추가와 삭제는 arr변수에 할당과 재할당을 통해 값을 바꾸는 기능이 필요하다.

    그 말은 추가와 삭제에서 arr변수의 값을 변화시키려면, arr변수의 포인터를 넘겨야 한다는 것이다.

    또한, 추가와 삭제에서는 대입과 재할당의 순서를 잘 봐야 한다.

    추가는 재할당을 먼저하고 대입하고, 삭제는 대입 후에 재할당을 한다.

    이들의 순서가 바뀌면 치명적인 오류가 난다.

    추가는 정의되지 않은 공간에 값을 넣는 행동이고, 삭제는 정의되지 않은 공간의 값을 가져와 배열에 넣는 것이 된다.

    코드를 곰곰이 보고 곱씹어 보자.

    결과창

    Array has no element!
sucessfully inserted 1 in index 0
sucessfully inserted 2 in index 1
sucessfully inserted 3 in index 2
sucessfully inserted 4 in index 3
sucessfully inserted 5 in index 4
sucessfully inserted 6 in index 2
Invalid operation!

traversal:
1 2 6 3 4 5

sucessfully changed value to 3 in index 2
sucessfully changed value to 4 in index 3
Invalid operation!

traversal:
1 2 3 4 4 5

sucessfully deleted value in index 4

traversal:
1 2 3 4 5

sucessfully deleted value in index 4

traversal:
1 2 3 4

sucessfully deleted value in index 0

sucessfully deleted value in index 0

sucessfully deleted value in index 0

sucessfully deleted value in index 0

Array is empty!
sucessfully inserted 0 in index 0
traversal:
0

sucessfully inserted 1 in index 0
traversal:
1 0

sucessfully inserted 2 in index 0
traversal:
2 1 0

sucessfully inserted 3 in index 0
traversal:
3 2 1 0

sucessfully inserted 4 in index 0
traversal:
4 3 2 1 0

sucessfully inserted 5 in index 0
traversal:
5 4 3 2 1 0

sucessfully inserted 6 in index 0
traversal:
6 5 4 3 2 1 0

sucessfully inserted 7 in index 0
traversal:
7 6 5 4 3 2 1 0

sucessfully inserted 8 in index 0
traversal:
8 7 6 5 4 3 2 1 0

sucessfully inserted 9 in index 0
traversal:
9 8 7 6 5 4 3 2 1 0

sucessfully inserted 10 in index 0
traversal:
10 9 8 7 6 5 4 3 2 1 0

    📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

    ✅ 1. 정적 배열로 주어진 ADT를 구현할 수 있다.

    ✅ 2. 동적 배열로 주어진 ADT를 구현할 수 있다.

    ✅ 3. 이중 포인터를 이용하는 함수를 이해한다.

    ✅ 4. []연산자 없이 이중 포인터의 간접 참조를 이용해 배열을 다루는 법을 이해한다.

    ⚠️ 할당된 공간은 꼭 해제해주자

    ⚠️ 이중 포인터의 원리를 이해하자.

    ⚠️ 되도록 void형 함수를 만들지 말자.

    💣 과제,

    1. 배열을 뒤집는 reverse()를 구현해보자.(난이도 下) (1, 2, 3, 4, 5)면 (5, 4, 3, 2, 1)
    2. 배열을 두 개로 나누는 split()을 구현해보자.(난이도 中)
      3. ex) 
      
l_arr = split(arr, 0, cur_size/2);

r_arr = split(arr, cur_size/2, cur_size);
    3. 두 배열을 하나의 배열로 합치는 merge()를 구현해보자.(난이도 中)
      4. ex) 
      
arr = merge(l_arr, r_arr, l_cur_size, r_cur_size);
    4. 배열을 오름차순으로 정렬하는 sort()를 구현해보자. (난이도 中)_(버블 정렬 알고리즘을 검색해보자)_
    5. 이름, 성적, 나이를 저장하는 구조체 배열을 만들고, 강의에 나온 모든 ADT를 구현해보자.(난이도 中)