[자료구조] Generic Dynamic Array 구현하기 ( 포인터 활용하기 )

 이번에 구현해볼 것은, logN 만에 id를 찾아서 값을 update 하는 동적 Array입니다. linked_list 가 아니라 Array이기에 삽입, 삭제에 있어 O(N) 의 시간복잡도로 비효율적이라 사용하진 않지만 pointer 활용에 이해를 돕고자 구현해봤습니다. 

 

 또한 자료구조 수업에서 첫 번째 과제로 많이 나오는 내용이므로 코드를 활용하셔도 됩니다. 단, 댓글로 사용한다고만 남겨주시면 됩니다. valgrind 로 확인을 걸쳤으니 아마 문제는 없을겁니다.

 

아래 포스팅에서 비슷한 구조를 설명했기에 이번 포스팅에서는 디테일하게 설명하지는 않을 것 같습니다. 

[자료구조] Ordered Linked List 구현하기

 

 

 

1. 초기 선언

#include <stdio.h>
#include <stdlib.h> // malloc, realloc, free, qsort
#include <string.h> // strdup, strcmp, memmove

const size_t PTRSIZE = 8;

typedef struct Array
{
	int count;
	int capacity;
	void *datas;
	int (*compare)(void*, void*);
	void (*update)(void*);
}Array;

typedef struct Word
{
	char *str;
	int freq;
}Word;

Array* create_array(int (*compare)(void*, void*), void (*update)(void*));
int search_array(Array* array, void *data, int *idx);
int addData(Array* array, void *data);
Word* create_word(char *str);
void delete_word(void* v1);
void update(void* word);
int compare(void* v1, void* v2);
int size_array(Array *array);
void print_array(Array *array, void (*print_func)(void*));
void print_func(void* v1);
void destroy_array(Array *array, void (*delete_func)(void*));

 

 Generic하게 구현하고 싶어서 datas 를 void* (배열) 로 선언해줬습니다. 그리고 예시로는 Word 구조체를 만들었지만, 사용자 마음대로 작성하면 됩니다. 그 아래 함수들은 앞으로 구현할 함수들입니다. 

 

 

2. 생성 함수 및 기타

Array* create_array(int (*compare)(void*, void*), void (*update)(void*))
{
	Array* array = (Array*)malloc(sizeof(Array));
	if(!array) return NULL;
	
	array->count = 0;
	array->capacity = 100;
	array->datas = (void*)malloc(PTRSIZE * array->capacity);
	array->compare = compare;
	array->update = update;
	return array;
}

Word* create_word(char *str)
{
	Word* word = (Word*)malloc(sizeof(Word));
	char* _word = (char*)malloc(sizeof(10));
	
	strcpy(_word, str);
	word->str = _word;
	word->freq = 1;
	return word;
}

void update(void* word)
{
	((Word*)word)->freq += 1;
}

int compare(void* v1, void* v2)
{
	Word *w1 = (Word*)v1;
	Word *w2 = (Word*)v2;
	printf("compare %s %s\n", w1->str, w2->str);
	return strcmp(w1->str, w2->str);
}

 

 create_array에서는 배열에서 사용할 함수을 연결해주고, create_word에는 인스턴스 str를 만들어서 부여해주면 되겠습니다. 그리고 word(문자) 의 빈도를 구하기 위해서 word를 key로 하는 compare 함수와 update 함수를 작성했습니다.

 

 

 

3. Array 핵심 함수

int search_array(Array* array, void *data, int *idx)
{
	int s = 0, e = array->count - 1, m = 0;
	while(s<=e){
		m = (s+e)/2;
		*idx = m;

		void **p = (void*)((char*)array->datas + PTRSIZE * m);
		int cmp = array->compare(data, *p);
		if(cmp == 0) return 1;
		if(cmp < 0) s=m+1;
		else e=m-1;
	}
	*idx = s;
	return 0;
}

int addData(Array* array, void *data)
{
	int idx = 0;
	if(search_array(array, data, &idx)){
		void **p = (void*)((char*)array->datas + idx * PTRSIZE);
		array->update(*p);
		return 2;
	}
	else{
		if(array->count + 1 > array->capacity){
			array->capacity += 100;
			array->datas = realloc(array->datas, PTRSIZE * array->capacity);
		}
		memmove((char*)array->datas+PTRSIZE*(idx+1), (char*)array->datas+PTRSIZE*idx, (array->count - idx) * PTRSIZE);
		array->count += 1;
		void **ptr =(void*)((char*)array->datas + idx * PTRSIZE);
		*ptr = data;
		
		return 1;
	}
}

 

 O(logN)으로 검색하기 위해 binary_search 를 이용했습니다. 여기에 중요한 점이 3가지가 있습니다. 일단 첫 번째는 memmove를 사용한다는 점 입니다. 그리고 나머지 두 개는 아래 그림과 함께 설명하겠습니다. 

 

참고 그림

 

 두 번째는 void* 를 char* 로 캐스팅하여 연산한다는 점입니다. void* 는 연산이 불가능하기에 char* 로 캐스팅한 후 몇 바이트 움직일지를 연산해주면 됩니다! char는 1bite라서 한 칸씩 움직일 수 있기 때문입니다. 

 

 세 번째는 void **ptr 로 접근한다는 점 입니다. (char*)array->datas + (움직일 bite 수) 가 의미하는건, array의 idx 번째 원소의 주소입니다. 하지만 우리가 원하는 건 그 주소가 가지고 있는 값(word 주소)이기에 위와 같이 작성했습니다. 이게 더 보기 좋은 것 같아서 두 줄을 사용했지만 한 번에 작성하셔도 상관 없습니다 (단 void**로 형변환하고 역참조를 해줘야합니다.)

 

 참고로 binary_search할 때 *idx (탐색 위치) = s 로 해줘야 합니다. 왜냐하면 s = pPre라는 의미이고 e = pLoc 의미가 있는데, while이 끝난 상황에서 m 은 pLoc이기에 제대로 정렬이 이루어지지 않습니다. 

 

4. 기타 함수

int size_array(Array *array)
{
	return array->count;
}

void print_array(Array *array, void (*print_func)(void*))
{
	for(int i=0;i<array->count;i++){ 
		void **p = (void*)((char*)array->datas + PTRSIZE * i);
		print_func(*p);
	}
}

void print_func(void* v1)
{
	Word* word = (Word*)v1;
	printf("%s:\t%d\t%p\n",word->str, word->freq, v1);
}

void destroy_array(Array *array, void (*delete_func)(void*))
{
	for(int i=0;i<array->count;i++){
		
		delete_func(*(void**)((char*)array->datas + PTRSIZE * i));
	}
	free(array->datas);
	free(array);
}

 

destroy_array에서 delete_func 를 보시면 위에서 두 줄을 쓰던 것을 한 줄로 축약해서 쓴 것 입니다.

 

 

5. 메인 함수

int main()
{
	Array* array = create_array(compare, update);
	char str[10];
	char cmd[10];
	
	while(1)
	{
		printf("push (word), size, print, exit\n");
		scanf("%s", cmd);
		if(!strcmp(cmd, "push")){
			scanf("%s",str);
			Word* word = create_word(str);
			if(addData(array, word) == 2){
				delete_word(word);
			}
			else printf("%s단어를 추가했습니다\n",str);
			/// ERROR 나는 경우는 그냥 무시하고 작성했습니다.
		}
		else if(!strcmp(cmd, "size")){
			printf("크기는 : %d입니다\n",size_array(array));
		}
		else if(!strcmp(cmd, "print")){
			print_array(array, print_func);
		}
		else if(!strcmp(cmd, "exit")){
			break;
		}
	}
	destroy_array(array, delete_word);
}

 

중복된 값은 원소가 '추가'된게 아니라 update되고 끝나기에 destroy해줍니다.

 

---

 

 비효율적인 자료구조라 쓰이진 않지만 포인터를 이해하는데 도움이 되기에 한 번씩은 구현해보는 것이 좋을 듯 합니다. 특히 generic 하게 코드를 작성할라면 void* 를 잘 다뤄야하는데, linked_list 는 직관적이지만 dynamic array에서 datas 를 관리할 때 생각보다 골치 아팠습니다.

 

 물론 제가 작성한 코드가 100% 맞다고는 보장할 수는 없지만, 여러 번 테스트를 진행했을 때 문제는 없었습니다. 만약 문제가 생긴다면 댓글로 알려주세요!