[C언어] Hash

소개글

야구팀 이름과 승/패/승률을 hash table에 저장한 후, 팀 이름을 입력으로 받아서 이를 열람할 수 있도록 만든 알고리즘이다. 해당하는 팀의 정보를 한데 묶어 구조체로 만들고, hash table 검색을 위한 function은 open addressing quadratic probing 방식을 사용하였다. 본 리포트는 한글로 작성되었으며, 해당하는 알고리즘과 소스 코드가 모두 첨부되어있다.

목차

1. Hash Table의 Open addressing quadratic probing 방식
2. 설계 과정
3. 최종적으로완성된 코드
4. 실행결과 및 토의

본문내용

1. Hash Table의 Open addressing quadratic probing 방식
Hashing이란 자료 저장 및 열람을 위한 데이터구조 중 검색기능에 가장 특화된 구조이다. 이 때 검색을 위한 Key를 Hash Function을 이용해 숫자로 변환 후 Hash Table의 Entry에 저장하는데, open addressing이란 이 데이터를 저장하는 방식을 가리킨다. 이 방식은 그 data를 hash function을 이용해 변환시켜 할당된 공간이 비어있지 않을 경우 미리 정해놓은 함수의 계산을 통해 그 자리로부터 일정한 거리(숫자)만큼 이동하면서 다른 빈자리를 찾아가는 식이다. Quadratic probing은 F(i)=i2만큼 (즉, +1, +4, +9, +16, …)이동하는 방식을 말한다.

2. 설계 과정
Hashing에 관한 기본적인 code는 본문에 대부분 수록되어 있으므로 이를 상당부분 참고하였다. 책에서도 삭제는 고려하지 않았으나, 불필요하다고 판단되는 내부함수 몇 개는 포함시키지 않았다 (rehash(), retrieve() 등등). 헤더파일에 들어갈 내용은 본문과 거의 유사하다.
#ifndef_HashQuad_H

typedef unsigned intIndex;
typedefconst char* Name; //내부함수의변수 type으로쓰일 Name
typedefIndex Position;

structHashTbl;
typedefstructHashTbl *HashTable;

HashTableInitializeTable(Index Size);
Position Find(Name Key,HashTable H);
void Insert(Name Key,intw,intl,floatwr,HashTable H);

#endif
↑헤더파일 hash_header.h에 들어갈 code

그 다음은 구조체의 정의인데, 이 부분도 본문을 많이 참고했다. 이 과제에서는 Key로 쓰일 변수가 char형 변수이므로 변수형을 바꾸고 승, 패, 승률을 포함할 변수를 더 추가했다.

참고 자료

없음