C언어로 자료구조를 만들어보는 것은 내가 예전에 했던 것인데, 부득이하게도 포트폴리오로써는 존재하지 않고 있기 때문에 늦었지만 다시 써보기로 했다. 이는 정보처리기사를 준비할 적에 만들어둔 코드인데, 어쩌다보니 자료구조까지 만들어버린 것이다. 만든 자료구조는 정적 배열, 데크, 링크드 리스트, 큐, 스택, 트리다.
정적 배열(Fixed Array)
정적 배열은 C언어에서 문법적으로 제공하는 기능이지만, 별도로 구조체, 함수를 이용하여 구현해보기로 했다. 물론 내부적으로 사용하는 것은 결국 기본 배열이지만 말이다.
배열은 연속된 메모리 공간이다. 따라서 가장 처음의 메모리 주소만 알고있더라도 다른 원소에 접근할 수 있다. 그래서 함수에서 배열을 받을 때 포인터로 받을 수 있는 것이다. 배열을 그림으로 표현하면 다음과 같고, 각 원소에 값이 담겨있다.
내가 구현한 모든 자료구조의 구현은 자료구조 자체의 개념 이외에는 어느 것도 참고하지 않고 스스로 생각하여 만들어 낸 것이므로 적절한 시간복잡도가 나오지 않을 수도 있다.
Array
여기에서는 정적 배열을 생성하기 위한 구조체와 초기화 함수를 살펴보자. 먼저 __Array__ 구조체는 Array 라는 이름으로 사용할 수 있게 했으며 내부에서는 배열의 길이, 위치, 내부 배열을 가질 수 있도록 하였다.
typedef struct __Array__ {
int length;
/**
* @private
*/
void** _elements;
int _position;
} Array;
Array array(size_t, ...);
/**
* Create Array
*
* @public
*/
Array array(size_t size, ...) {
Array array = { .length = size, ._elements = malloc(sizeof(void*) * size), ._position = 0 };
va_list ap;
va_start(ap, size);
for (int i = 0; i < size; i++) {
array._elements[i] = va_arg(ap, void*);
}
va_end(ap);
return array;
}array() 함수는 배열의 크기를 파라매터로 받아서 처리해줄 수 있다. 정적 배열이기 떄문에 해당 사이즈 만큼만 동적할당을 해주면 된다. 값의 경우는 가변 매개변수로 받을 수 있도록 파라매터를 구성한다. 이 구현에 따르면 정적 배열을 처음 초기화한 이후에는 값을 추가하거나 삭제할 수 없다. 말 그대로 정적이다.
ar_*
해당 자료구조를 위해 지원하는 함수는 다음과 같으며, 내가 구현한 것의 경우, 루프를 돌기 위한 반복자도 지원하고 있다. 무엇을 하는 함수인지는 이름만 봐도 알 수 있을 것이며, 이 이후에 소개할 자료구조에도 아래와 같은 네이밍 접미사가 붙을 것이다.
void* ar_at(Array*, int);
void ar_clear(Array*);
void* ar_begin(Array*);
void* ar_next(Array*);
void* ar_end(Array*);
void* ar_prev(Array*);
int ar_done(void*);자료구조의 이름 함수는 자료구조를 초기화하며, *_begin, *_next, *_done 와 같은 함수들은 반복자와 관련이 있으며, *_at 은 검색을, *_clear 는 내부의 값을 몽땅 비워주는 역할을 한다. C언어는 가비지 컬렉션이 없는 언어이므로 만약에 생성시 동적 할당을 했다면 이 함수에서 메모리를 해제하는 것도 잊어서는 안 된다.
ar_at(Array*, int), at_clear(Array*)
ar_at() 은 배열에서 원소를 가져오는 함수, at_clear() 는 내부 배열의 메모리 할당을 해제한다. array() 함수에서 동적 할당으로 처리했기 때문에, at_clear() 에서 반대로 메모리 할당을 해제한다.
/**
* Get element with position
*
* @public
*/
void* ar_at(Array* array, int position) {
return array->_elements[position];
}
/**
* Clear Array
*
* @public
*/
void ar_clear(Array* array) {
free(array->_elements);
}ar_begin(Array*), ar_next(Array*), ar_end(Array*), ar_prev(Array*)
이 함수들은 배열에서 값을 반환해주는데, 각자 반환해주는 것이 다르다. ar_begin() 함수는 배열의 가장 첫 번째 값을 반환하고 위치를 0 으로 바꾼다. 나머지도 마찬가지다. ar_end() 는 마지막으로, ar_next() 는 다음으로, ar_prev() 이전 값이다. 이 과정에서 인덱스의 오버플로나 언더플로가 발생할 것을 염려하여 사전에 검사하여 NULL 을 반환한다.
/**
* Get first element
*
* @public
*/
void* ar_begin(Array* array) {
array->_position = 0;
return array->_elements[array->_position];
}
/**
* Get next element
*
* @public
*/
void* ar_next(Array* array) {
if (array->_position < array->length - 1) {
return array->_elements[++array->_position];
} else return NULL;
}
/**
* Get last element
*
* @public
*/
void* ar_end(Array* array) {
array->_position = array->length - 1;
return array->_elements[array->_position];
}
/**
* Get prev element
*
* @public
*/
void* ar_prev(Array* array) {
if (array->_position > 0) {
return array->_elements[--array->_position];
} else return NULL;
}
ar_done(void* iter)
파라매터로 넘어오는 값이 NULL 인지 체크하고 NULL 이면 1, 아니면 0 을 반환한다. 함수의 이름이 is_null() 와 같은 형태가 아닌 이유는 이는 반복자와 함께 사용할 것을 유도한 네이밍이기 때문이다.
/**
* is Done
*
* @public
*/
int ar_done(void* iter) {
if (iter == NULL) {
return 1;
}
return 0;
}어떻게 사용해볼까?
우리가 구현한 배열은 아래와 같이 사용해볼 수 있다. 배열을 초기화하고, 반복자를 사용하여 배열을 순회하여 출력한다. 배열을 초기화할 때 값은 void* 형으로 하기 때문에 적절한 형 변환이 필요하다.
Array arr = array(1, "Hello, world!");
for (void* iter = ar_begin(&arr); 1 != ar_done(iter); iter = ar_next(&arr)) {
// Hello, world!
printf("%s", (const char*) iter);
}
ar_clear(&arr);
데크(Deque)
데크는 크기가 변할 수 있는 동적 배열이다. 초기화 시에는 정적 배열과 비슷하게 처리하지만, 데이터 삽입 삭제시 수시로 메모리를 재할당하여 동적으로 관리한다. 양옆은 물론, 배열의 중간에서도 삽입과 삭제가 가능하도록 구성했다.
Deque
deque() 의 구현이 array() 와 다른 점은, 값을 할당할 때 dq_push_back() 을 사용한다는 점이다. 이것은 아래에서 차츰 이야기 하게 되겠지만, 데크의 맨 뒤에 값을 추가하는 함수다. 메모리는 size 만큼 할당하되 length 는 0 으로 초기화한다는 점을 살펴보자. 데크의 length 필드는 dq_push_back() 에서 증가시켜 줄 것이다.
typedef struct __Deque__ {
int length;
/**
* @private
*/
void** _elements;
int _position;
} Deque;
Deque deque(size_t, ...);
/**
* @private
*/
void __realloc(Deque* deque, int length) {
deque->_elements = (void**) realloc(deque->_elements, sizeof(void*) * length);
}
/**
* Create Deque
*
* @public
*/
Deque deque(size_t size, ...) {
Deque dq = { .length = 0, ._elements = malloc(sizeof(void*) * size), ._position = 0 };
va_list ap;
va_start(ap, size);
for (int i = 0; i < size; i++) {
dq_push_back(&dq, va_arg(ap, void*));
}
va_end(ap);
return dq;
}dq_*
데크와 관련된 함수는 dq_ 를 접두사로 하며 다음과 같은 함수들이 있다. 다만 일부 구현은 ar_* 과 같이 때문에 코드를 생략하는 경우도 있을 것이다.
void dq_push_front(Deque*, void*);
void dq_pop_front(Deque*);
void dq_push_back(Deque*, void*);
void dq_pop_back(Deque*);
void dq_insert(Deque*, void*, int);
void dq_erase(Deque*, int);
void* dq_at(Deque*, int);
void dq_clear(Deque*);
void* dq_begin(Deque*);
void* dq_next(Deque*);
void* dq_end(Deque*);
void* dq_prev(Deque*);
int dq_done(void*);눈여겨 봐야하는 것은 dq_push_front(), dq_pop_front(), dq_push_back(), dq_pop_back(), dq_insert(), dq_erase() 함수다. 나머지 구현은 정적 배열의 구현과 똑같다.
dq_push_back(Deque*, void*), dq_pop_back(Deque*, void*)
먼저 쉬운 것부터 알아보자. 해당 함수는 요소를 데크의 맨 뒤에 넣거나 삭제한다. 구현은 심플한데, 추가의 경우에는 동적으로 증가해야 하므로 데크의 크기를 다시 재할당해주고 length - 1 에 해당하는 위치, 그러니까 맨 뒤에 요소를 넣으면 된다. 그리고 삭제의 경우에는 더 쉽다. 그냥 메모리를 줄여버리자.
/**
* Push new node at Back
*
* @public
*/
void dq_push_back(Deque* deque, void* element) {
__realloc(deque, ++deque->length);
deque->_elements[deque->length-1] = element;
}
/**
* Remove node at Back
*
* @public
*/
void dq_pop_back(Deque* deque) {
__realloc(deque, --deque->length);
}__realloc() 함수로 데크의 크기를 재할당하는 모습을 볼 수 있다. 이 함수에 대한 구현은 더 위쪽의 코드에 나와있다.
dq_push_front(Deque*, void*), dq_pop_front(Deque*)
이 두 함수의 경우는 구현이 조금 더 어렵다. 배열의 앞에 추가하는 것과 뒤에 추가하는 것은 해야 하는 행동이 매우 다르다. 제일 앞에 원소를 추가한다는 것은 단순히 메모리를 늘려서 해결될 문제가 아니다. 메모리를 늘린 다음, 배열의 모든 요소를 하나의 인덱스 만큼 뒤로 밀어버린 다음, 앞에다가 덮어 씌워야 한다. 진행 방향이 뒤에서 앞이라는 것을 기억하라.
이렇게 덮어 씌운 데이터의 처리 결과는 다음과 같다.
마찬가지로, 배열의 제일 앞의 요소를 제거한다는 것은 단순히 마지막 메모리 영역을 재할당한다고 해서 되는 것이 아니라, 먼저 요소를 하나 하나씩 앞으로 당긴다음 그 이후가 되어야 메모리를 재할당해야 한다. 따라서 위의 그림에서 화살표 방향이 반대로 진행되면 될 것이다.
/**
* Push new node at Front
*
* @public
*/
void dq_push_front(Deque* deque, void* element) {
__realloc(deque, ++deque->length);
for (int i = deque->length-2; i >= 0; i--) {
deque->_elements[i+1] = deque->_elements[i];
}
deque->_elements[0] = element;
}
/**
* Remove node at Front
*
* @public
*/
void dq_pop_front(Deque* deque) {
for (int i = 1; i < deque->length; i++) {
deque->_elements[i-1] = deque->_elements[i];
}
__realloc(deque, --deque->length);
}dq_insert(Deque*, void*, int), dq_erase(Deque*, int)
이 두 함수는 중간에 값을 넣거나 삭제할 수 있다. 중간에 값을 넣거나 삭제하는 행위를 하는 것도 위에 소개한 dq_push_front(), dq_pop_front() 와 비슷한 과정을 거치는데, 시작 지점이 세번째 파라매터의 값에 따라 달라질 뿐이다. 값을 넣을 때 값을 뒤의 인덱스에 덮어씌우는 작업들을 하는 것은 position 까지만 처리하면 된다.
이 상태에서 값을 옮기고 해당 위치에 값을 추가하면 다음과 같이 변한다.
값을 지울 때는 뒤에 있는 인덱스의 값을 앞으로 당기는데, 데크의 길이만큼 처리 한 후, 메모리를 줄여서 재할당 해주면 된다.
/**
* Push element at Position
*
* @public
*/
void dq_insert(Deque* deque, void* element, int position) {
__realloc(deque, ++deque->length);
for (int i = deque->length-2; i >= position; i--) {
deque->_elements[i+1] = deque->_elements[i];
}
deque->_elements[position] = element;
}
/**
* Remove element at Position
*
* @public
*/
void dq_erase(Deque* deque, int position) {
for (int i = position+1; i < deque->length; i++) {
deque->_elements[i-1] = deque->_elements[i];
}
__realloc(deque, --deque->length);
}어떻게 사용해볼까?
데크는 처음에 적게 할당하더라도 동적으로 추가가 가능하기 때문에 사용하기가 더욱 용이하다. 다음과 같이 사용할 수 있다.
Deque dq = deque(1, "Hello, world!");
dq_push_back(&dq, "Example");
for (void* iter = dq_begin(&dq); 1 != dq_done(iter); iter = dq_next(&dq)) {
// Hello, world!
// Example
printf("%s", (const char*) iter);
}
dq_clear(&dq);더 읽을거리
C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)
C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)
C언어로 자료구조 만들기 - 링크드 리스트(Linked List)
