Quadratic rehashing을 이용하여 프로그램을 작성하시오

소개글

Quadratic rehashing을 이용하여 프로그램을 작성하시오에 대한 보고서 자료입니다.

목차

1)문제

2)프로그램소스

3)실행결과 및 화면

4)문제점

본문내용

key; // Hash Table 에 저장.
strcpy(rectable[hkey].r, rec);
rectable[hkey].flag = TRUE;
}
void DeleteOp(table rectable) // 삭제할 key값을 입력받는다.
{
int key;
printf("Enter Key : ");
scanf("%d", &key);
Delete(rectable, key);
}
void Delete(table rectable, int key)
{
int hkey, rh, cnt=0;
hkey = key % TABLESIZE;
rh = hkey;
while(key != rectable[rh].k && rectable[rh].rhcnt > 0)
{ // 키값이 같지 않고 Rehash 자취가 있을때 반복
rectable[rh].rhcnt--; // Rehash 자취를 감소
cnt++;
rh = (hkey + cnt*cnt) % TABLESIZE;
}
rectable[rh].k = 0; // Hash Table 값을 지움.
strcpy(rectable[rh].r, "");
rectable[rh].flag = FALSE;
}
void printhash(table rectable) // 각 단계의 Hash Table 상태를 표시.
{
system("cls");
printf(" Hash Table \n");
printf("================================================\n");
printf(" key record FLAG Rehash Count \n");
printf("================================================\n");
for(int i = 0; i < TABLESIZE; i++)
printf(" %2d %10s %d %d\n",
rectable[i].k, rectable[i].r, rectable[i].flag, rectable[i].rhcnt);
printf("================================================\n");
}
3) 실행경과 및 화면
1) 초기화면 명령선택
1) 30 computer 입력
30 % 7 = 2
3) 93 program 입력
93 % 7 = 2
rh(1) = (2 + 1) % 7 = 3
4) 39 language 입력
39 % 7 = 4
5) 66 science 입력
66 % 7 = 3
rh(1) = (3 + 1) % 7 = 4
rh(2) = (3 + 4) % 7 = 0
6) 72 system 입력
72 % 7 = 2
rh(1) = (2 + 1) % 7 = 3
rh(2) = (2 + 4) % 7 = 6
7) 30 Delete -> key, record, flag 삭제 후에도 Rehash Count는 존재
8) 93 삭제 -> 아래보이는 세 번째(테이블[2]) Rehash Count 감소
9) 39 삭제 -> Rehash 된 것이 없으므로 key, record, flag 만 삭제
10) 66 삭제 -> 66이 Rehash 되어온 네 번째(테이블[3]), 세번째(테이블[2]) Rehash Count 감소
11) 72 삭제 -> 모든 데이터가 삭제된 Table
4) 문제점
Rehash 되지 않은 부분을 삭제 후 Hash Table 에 있는 키 값을 입력 할 때는 중복되어 입력 저장됨.
(예 : 30 삭제후 93 입력하면 93이 세 번째(테이블[2]) 와 네 번째(테이블[3])에 중복 저장됨)
삭제 시 자리 옮김 하는 방법을 사용해야 되는지.
삽입 시 Rehash를 따라 들어가서 삭제해야 하는지 검토 후 적용해 볼까 합니다.

키워드

Quadratic,   Hash,   Rehashing,   프로그램소스,   해쉬 함수,   리해쉬함수