각종 노하우 [C를 활용한 문제해결 기법의 근간] 학습용!! hash의 근간!! hash_table

#include <stdio.h>

#include <string.h>

#define KEY_SIZE 10

#define TABLE_SIZE 13 // 소수

#define MAX_STRING 30

typedef struct

{

    char name[MAX_STRING];

    char phone[MAX_STRING];

    int empty;

}element;

element hash_table[TABLE_SIZE];

void InitTable(element *ht) // 해시테이블 초기화

{

    int i;

    for (i = 0; i<TABLE_SIZE; i++)

    {

        memset(&ht[i].name, 0, sizeof(ht[i].name));

        memset(&ht[i].phone, 0, sizeof(ht[i].phone));

        ht[i].empty = -1;

    }

}

int Transform(char *key) // 문자를 숫자로 변환

{

    int number = 0;

    while (*key)

        number += (*key++);

    return number;

}

int HashFunction(char *key)

{

    return Transform(key) % TABLE_SIZE;

}

int HashAdd(element item, element *ht) // 항목 추가

{

    int i, value;

    value = i = HashFunction(item.name);

    while (ht[i].empty == 1) // 빈 버켓을 찾는다.

    {

        if (strcmp(item.name, ht[i].name) == 0)

        {

            printf("이름이 중복되었습니다\n");

            return -1;

        }

        i = (i + 1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

        if (i == value) // 테이블 전체가 검사되었을 때

        {

            printf("테이블이 가득찼습니다\n");

            return -1;

        }

    }

    item.empty = 1;

    ht[i] = item; // 버켓이 비어있다면 바로 삽입

    return 1;

}

int HashDelete(element item, element *ht) // 데이터 삭제

{

    int i, value;

    value = i = HashFunction(item.name);

    while (!(ht[i].empty == -1)) // 버켓이 비어있지 않다면

    {

        if (strcmp(item.name, ht[i].name) == 0)

        {

            printf("삭제 데이터 : 위치 = %d, 이름 : %s, 전화번호 : %s\n", i, ht[i].name, ht[i].phone);

            memset(&ht[i].name, 0, sizeof(ht[i].name));

            memset(&ht[i].phone, 0, sizeof(ht[i].phone));

            ht[i].empty = 0; // 삭제 표시,한번 사용된 버켓

            return 1;

        }

        i = (i + 1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

        if (i == value) // 테이블 전체가 검사되었을 때

        {

            printf("찾는 값이 테이블에 존재하지 않습니다.\n");

            return -1;

        }

    }

    printf("테이블이 비어있습니다..\n");

    return -1;

}

int HashSearch(element item, element *ht) // 데이터 탐색

{

    int i, value;

    value = i = HashFunction(item.name);

    while (!(ht[i].empty == -1)) // 버켓이 비어있지 않다면

    {

        if (strcmp(item.name, ht[i].name) == 0)

        {

            printf("탐색 성공 : 위치 = %d, 이름 : %s, 전화번호 : %s\n", i, ht[i].name, ht[i].phone);

            return 1;

        }

        i = (i + 1) % TABLE_SIZE; // 0~TABLE_SIZE 내에서 값이 1씩 증가한다.

        if (i == value) // 테이블 전체가 검사되었을 때

        {

            printf("찾는 값이 테이블에 존재하지 않습니다.\n");

            return -1;

        }

    }

    printf("찾는 값이 테이블에 존재하지 않습니다.\n");

    return -1;

}

int main()

{

    element temp;

    int input;

    int i;

    InitTable(hash_table);

    while (1)

    {

        printf("1:입력\n2:삭제\n3:탐색\n4:종료\n");

        scanf_s("%d", &input);

        fflush(stdin);

        printf("이름 입력 : ");

        gets_s(temp.name);

        switch (input)

        {

        case 1:

            printf("전화번호 입력 : ");

            gets_s(temp.phone);

            HashAdd(temp, hash_table);

            break;

        case 2:

            HashDelete(temp, hash_table);

            break;

        case 3:

            HashSearch(temp, hash_table);

            break;

        default:

            return 0;

        }

        for (i = 0; i<TABLE_SIZE; i++)

            printf("hashtable[%d] :%s\n", i, hash_table[i].name);

    }

    return 0;

}