[알고리즘] ep4+++) 비활성화 방식 삭제

문제) 크기가 M인 해시테이블에 키 값을 입력받아 저장하고, 개방주소법 중 이중 해싱을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오.

 

[프로그램 요구사항]

1)  해시테이블의 사이즈 M = 23 으로 정의할 것.

2)  이중해싱에 기반해야 하며 h 및 h’은 각자 적절히 정의하여 사용할 것.

3)  저장 원소는 0에서 99 사이의 정수로 제한할 것.

4)  삽입(i) 명령시, 중복 키 또는 해시테이블이 만원일 경우 적절한 안내 메시지와 함께 명령수행을 거절할 것.

5)  탐색(f) 또는 삭제(r) 명령시, 함께 주어진 키가 존재하지 않을 경우 NoSuchKey를 반환 및 인쇄할 것.

 

[주의]

인쇄(p) 명령시에만, 아래 예시처럼 현재 해시테이블의 내용을 두 개의 라인으로 보여줄 것. 윗 라인은 해시테이블의 배열첨자, 아래 라인은 저장된 원소들임. 비어있는 셀은 점으로 표시할 것.

 

 

 

(전체코드)

// 개방주소법 - 이중 해싱
// "비활성화 방식 삭제"
// h 및 h'는 각자 적절히 정의하여 사용할 것
#include <stdio.h>
#include <stdlib.h>

int* hashtable;
int* bucketStatus;
int M = 23;

// 버켓 상태 코드
#define EMPTY 0 // 초기 상태
#define ACTIVE 1 // 활성
#define DELETED -1 // 비활성

void initHashtable();
int hashFunction(int key);
int doubleHashFunction(int key);
void activate(int idx); // 버켓을 활성으로 전환
void deactivate(int idx); // 버켓을 비활성으로 전환
int isActive(int idx); // 버켓이 활성인지 여부를 반환
void findKey(int key);
void insertKey(int key);
void removeKey(int key);
void printHashtable();

int main() {
    char cmd;
    int key; // 0에서 99 사이의 정수

    initHashtable();
    while (1) {
        scanf(" %c", &cmd);
        if (cmd == 'f') {
            scanf("%d", &key);
            findKey(key);
        }
        else if (cmd == 'i') {
            scanf("%d", &key);
            insertKey(key);
        } 
        else if (cmd == 'r') {
            scanf("%d", &key);
            removeKey(key);
        }
        else if (cmd == 'p') {
            printHashtable();
        } 
        else if (cmd == 'q') {
            free(hashtable);
            free(bucketStatus);
            return 0;
        }
    }
}

void initHashtable() {
    hashtable = (int*)malloc(M * sizeof(int));
    bucketStatus = (int*)malloc(M * sizeof(int));
    for (int i = 0; i < M; i++) {
        hashtable[i] = -1; // 빈 버켓은 -1으로 초기화
        bucketStatus[i] = EMPTY; // 초기 상태는 EMPTY
    }
}

int hashFunction(int key) {
    return key % M;
}

int doubleHashFunction(int key) {
    return 7 - (key % 7);
}

void activate(int idx) { // 버켓을 활성으로 전환
    bucketStatus[idx] = ACTIVE;
}

void deactivate(int idx) { // 버켓을 비활성으로 전환
    bucketStatus[idx] = DELETED;
}

int isActive(int idx) { // 버켓이 활성인지 여부를 반환
    return bucketStatus[idx] == ACTIVE;
}

void findKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int stepSize = doubleHashFunction(key);
    while (bucketStatus[idx] != EMPTY) { // 충돌이 발생하는 동안 반복
        if (isActive(idx) && hashtable[idx] == key) {
            printf("%d\n", key);
            return;
        }

        idx = (idx + stepSize) % M;
        if (idx == originalIdx) { // 한 바퀴를 다 돌았을 경우
            break;
        }
    }
    printf("NoSuchKey\n");
}

void insertKey(int key) {
     if (key < 0 || key > 99) {
        printf("Key must be between 0 and 99\n");
        return;
    }

    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int stepSize = doubleHashFunction(key);
    while (bucketStatus[idx] != EMPTY && bucketStatus[idx] != DELETED) { // 충돌이 발생하는 동안 반복
        if (isActive(idx) && key == hashtable[idx]) { // 중복 키 삽입 시
            printf("The key you're trying to insert is duplicated\n");
            return;
        }

        idx = (idx + stepSize) % M;

        if (idx == originalIdx) { // 해시테이블이 가득 찬 경우
            printf("Hash table is full!\n");
            return;
        }
    }
    hashtable[idx] = key;
    activate(idx); // 버켓을 활성으로 전환
}

void removeKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int stepSize = doubleHashFunction(key);
    while (bucketStatus[idx] != EMPTY) { // 충돌이 발생하는 동안 반복
        if (isActive(idx) && hashtable[idx] == key) {
            printf("%d\n", key);
            deactivate(idx); // 버켓을 비활성으로 전환
            return;
        }

        idx = (idx + stepSize) % M;
        if (idx == originalIdx) { // 한 바퀴를 다 돌았을 경우
            break;
        }
    }
    printf("NoSuchKey\n"); // 삭제할 키가 없음
}

void printHashtable() {
    for (int i = 0; i < M; i++) { // 배열첨자 출력
        printf("%3d", i);
    }
    printf("\n");
    for (int i = 0; i < M; i++) { // 저장된 키 출력
        if (isActive(i)) {
            printf("%3d", hashtable[i]);
        }
        else {
            printf("  .");
        }
    }
    printf("\n");
}

/*
i 34
i 23
i 26
i 21
f 36
f 26
f 34
f 21
p
r 21
f 34
r 8
q

i 25
i 13
i 16
i 15
i 70
p
i 28
i 31
i 20
i 14
f 20
f 27
i 38
q
*/

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)