그로블

프로그램의 기능은 Dynamic array를 구현했던 프로그램과 동일하다.

사용된 구조체도 이전 프로그램과 동일하다.

[tNames]

typedef struct {
	int		len;		// 배열에 저장된 이름의 수
	int		capacity;	// 배열의 용량 (배열에 저장 가능한 이름의 수)
	tName	*data;		// 이름 배열의 포인터
} tNames;

[tName]

typedef struct {
	char	name[20];		// 이름
	char	sex;			// 성별 M or F
	int		freq[MAX_YEAR_DURATION]; // 연도별 빈도
} tName;

해당 프로그램에는 총 6개의 함수가 정의되어 있다.

수정된 함수와 새로 생긴 binary_search함수만 확인해보자.

[compare]

int compare( const void *n1, const void *n2)
{
	int result;
	
	result =  strcmp((const char *)n1, (const char *)n2);
	if(result)
		return result;
	else
	{
		result = (unsigned int)(*((char *)n1 + 20) - *((char *)n2 + 20));
		return result;
	}
}

이름을 strcmp를 이용해 비교한 뒤 만약 이름이 같다면 성별 변수에 접근하여 성별이 같은지에 대한 여부를 return하도록 수정하였다.

[binary_search]

int binary_search( const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void *, const void *))
{
	int first = 0;
	int last = nmemb - 1;
	int mid, check;
	
	while(first <= last)
	{
		mid = (first + last)/2;
		
		check = compare(key, base + size*mid);
		if(!check)
			return mid;
		if(check <= 0)
			last = mid-1;
		else
			first = mid+1;
	}
	
	return first;
}

binary search를 수행하여 이름 구조체가 삽입될 위치를 return해준다.

[load_names]

void load_names(FILE *fp, int year_index, tNames *names)
{
	char *i = 0;
	int *key = 0;
	char tmp[100];
	tName input;
	int index;
	
	while(fgets(tmp, sizeof(tmp), fp))
	{
		//comma -> tab
		for(i = tmp; ; i++)
		{
			if(!*i)
				break;
			if(*i == ',')
				*i = '\t';
		}
		sscanf(tmp, "%s\t%c\t%d", input.name, &input.sex, &input.freq[0]);
		
		//compare함수에서 +20부분에 sex가 위치해야 함. -> tName 구조체 이용.
		key = bsearch(input.name, names->data, names->len, 64, compare);
		
		if(key)	
		{
			key[year_index + 6] = input.freq[0];	//name(20) + sex(4) + freq
		}
		else
		{
			//full memory
			if(names->capacity == names->len)
			{
				names->data = (tName*)realloc(names->data, names->capacity * 2 * sizeof(tName));
				assert(names->data != NULL);
				if(!names->data)
				{
					fprintf(stderr, "Insufficient memory capacity!");
					return;
				}
				names->capacity *= 2;
			}
			
			index = binary_search(input.name, names->data, names->len, 64, compare);
			
			memmove(&(names->data[index+1]), &(names->data[index]), ((names->len)-index)*64);
			
			strcpy(names->data[index].name, input.name);
			names->data[index].sex = input.sex;
			memset(names->data[index].freq, 0, 40);
			names->data[index].freq[year_index] = input.freq[0];
			names->len++;
		}
	}
}

대략적인 구조는 이전과 동일하지만 bsearch함수를 사용하여 이름이 삽입될 위치를 확인하고 기존에 존재했던 이름이면 freq변수의 해당 연도 인덱스에 추가만해주고 기존에 존재하지 않았던 이름이라면 메모리 확인을 해준 후 binary_search함수를 사용해서 tName배열에 삽입될 index를 return받은 뒤 memmove로 그 뒤에 있는 리스트를 한칸씩 미룬 후 그 위치에 이름, 성별, 빈도를 저장한다.

[전체 코드&이름 파일]

연도별 입력 파일을 읽어들어서 이름 정보(이름, 성별, 빈도)를 이름 구조체에 저장한 후 사전순서대로 이름을 정렬하여 출력하는 프로그램을 구현해보자. 프로그램 실행 시 인자로 파일의 이름을 넣어줘야 한다.

사용되는 구조체는 이름 배열의 포인터를 가지고 있는 tNames, 이름 정보를 담고 있는 tName.

[tNames]

typedef struct {
	int		len;		// 배열에 저장된 이름의 수
	int		capacity;	// 배열의 용량 (배열에 저장 가능한 이름의 수)
	tName	*data;		// 이름 배열의 포인터
} tNames;

[tName]

typedef struct {
	char	name[20];		// 이름
	char	sex;			// 성별 M or F
	int		freq[MAX_YEAR_DURATION]; // 연도별 빈도
} tName;

이러한 형태의 구조체를 가지고 있다.

총 5개의 함수가 정의된다.

[create_names]

tNames *create_names(void)
{
	tNames *pnames = (tNames *)malloc( sizeof(tNames));
	
	pnames->len = 0;
	pnames->capacity = 1;
	pnames->data = (tName *)malloc(pnames->capacity * sizeof(tName));

	return pnames;
}

pnames에 malloc으로 tNames 의 구조체를 할당해주고 len은 0, capacity는 1, data는 capacity*tName구조체의 크기만큼 할당해준 후 pnames를 return해준다.

[load_names]

void load_names(FILE *fp, int year_index, tNames *names)
{
	char *i;
	int j, check = 0;
	char tmp[100];
	char name[40];
	char sex;
	int freq;
	
	while(fgets(tmp, sizeof(tmp), fp))
	{
		//comma -> tab
		for(i = tmp; ; i++)
		{
			if(!*i)
				break;
			if(*i == ',')
				*i = '\t';
		}
		sscanf(tmp, "%s\t%s\t%d", name, &sex, &freq);
		
		//check overlap
		for(j = 0; j < names -> len; j++)
		{
			if(!strcmp(name, names->data[j].name) && (sex == names->data[j].sex))
			{
				check = 1;
				names -> data[j].freq[year_index] = freq;
				break;
			}
			
		}	

		//no overlap
		if(!check)
		{
			//full memory
			if(names->capacity == names->len)
			{
				names->data = (tName*)realloc(names->data, names->capacity * 2 * sizeof(tName));
				assert(names->data != NULL);
				if(!names->data)
				{
					fprintf(stderr, "Insufficient memory capacity!");
					return;
				}
				names->capacity *= 2;
			}
			
			strcpy(names->data[names->len].name, name);
			names->data[names->len].sex = sex;
			memset(names->data[names->len].freq, 0, 40);
			names->data[names->len++].freq[year_index] = freq;
		}
		check = 0;
	}
		
	
}

파일에 이름, 성별, 빈도가 ","로 구분되어 있다. 파일을 한 줄씩 입력받으면서 ","를 tab으로 바꿔주고 sscanf로 tab을 구분 기호로 하여 name, sex, freq변수에 넣어준다.

이름을 입력받아서 중복 체크를 해준다. tName 구조체 배열의 길이만큼 구조체를 하나씩 확인하면서 성별과 이름이 같은 구조체가 있는지 확인한다. 만약 중복된 구조체가 존재한다면 freq의 해당 연도의 인덱스에 빈도를 저장한다.

만약 중복된 구조체가 존재하지 않는다면 tNames에 tName구조체를 추가해주어야 한다. 그 전에 capacity와 len이 같은지 확인하여 메모리가 꽉 차지 않았는지 확인해준다. 만약 메모리가 꽉찼다면 realloc을 사용해서 capacity*2만큼의 메모리를 재할당해준 후 capacity 값을 업데이트 해준다.

그 후 tNames의 data 배열 포인터 마지막에 name, sex, freq를 추가해주고 len값을 1 올려준다.

[compare]

int compare( const void *n1, const void *n2)
{
	return strcmp((const char *)n1, (const char *)n2);
}

strcmp함수를 이용해 사전순으로 정렬할 수 있도록 해준다.

[print_names]

void print_names(tNames *names, int num_year)
{
	int i, j;
	
	for(i = 0; i < names->len; i++)
	{
		printf("%s\t%c", names->data[i].name, names->data[i].sex);
		for(j = 0; j < num_year; j++)
			printf("\t%d", names->data[i].freq[j]);
		printf("\n");
	}
}

이름, 성별, 빈도 수를 tab을 구분 문자로 하여 출력해준다.

[destroy_names]

void destroy_names(tNames *pnames)
{
	free(pnames->data);
	pnames->len = 0;
	pnames->capacity = 0;

	free(pnames);
}	

tName구조체 배열의 메모리를 해제한 후 tNames의 메모리도 해제해준다.

[전체 코드&이름 파일]