General list 구현(동적 배열 + 정렬된 선형리스트)

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

 

1. load_names와 compare 함수의 기능을 수정하였으며 binary search를 수행한다. 2. 새로운 이름이 들어오면 제일 뒤에 추가하는 것이 아니라 정렬된 리스트를 유지하도록 위치를 찾아 삽입한다. 3. memmove함수를 사용해 구조체가 삽입될 위치 뒤에있는 리스트를 한칸씩 민다.

 

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

 

[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개의 함수가 정의되어 있다.

1. create_names: 이름 구조체를 초기화해준다.(len을 0으로, capacity를 1로 초기화한 후 구조체 포인터를 return한다) 2. load_names: 입력 파일을 읽어들인다. 3. compare: bsearch를 위한 비교 함수이다. 4. print_names: 구조체 배열을 화면에 출력해준다. 5. destroy_names: 이름 구조체 메모리를 해제해준다. 6. binary_search: 이진 탐색 함수이다. key가 발견되는 경우 배열의 인덱스를 return하고 key가 발견되지 않는 경우에 key가 삽입되어야 할 배열의 인덱스가 return된다.

 

수정된 함수와 새로 생긴 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로 그 뒤에 있는 리스트를 한칸씩 미룬 후 그 위치에 이름, 성별, 빈도를 저장한다.

 

[전체 코드&이름 파일]

GeneralList.zip

1.12MB