해시테이블 구현 / 체이닝 방식

// 이 코드는 해시 테이블을 구현한 프로그램입니다.
// 해시 테이블의 노드들은 연결 리스트로 구성되며, 충돌 해결은 체이닝 방식으로 처리됩니다.
// 제공되는 기능:
// 1. 'i': 원소 삽입 - 해시 값을 계산하여 연결 리스트의 맨 앞에 노드를 추가합니다.
// 2. 's': 원소 검색 - 주어진 값을 가진 노드를 검색하고, 발견되면 그 위치를 반환합니다.
// 3. 'd': 원소 삭제 - 주어진 값을 가진 노드를 찾아 삭제하고 성공 여부를 반환합니다.
// 4. 'p': 해시 테이블 출력 - 각 슬롯의 연결 리스트에 저장된 모든 원소를 출력합니다.
// 해시 함수는 모듈러 연산을 사용하여 입력값을 해시 테이블 크기로 나눈 나머지를 반환합니다. 1차해싱

// 이 코드는 해시 테이블을 구현한 프로그램입니다.
// 해시 테이블의 노드들은 연결 리스트로 구성되며, 충돌 해결은 체이닝 방식으로 처리됩니다.
// 제공되는 기능:
// 1. 'i': 원소 삽입 - 해시 값을 계산하여 연결 리스트의 맨 앞에 노드를 추가합니다.
// 2. 's': 원소 검색 - 주어진 값을 가진 노드를 검색하고, 발견되면 그 위치를 반환합니다.
// 3. 'd': 원소 삭제 - 주어진 값을 가진 노드를 찾아 삭제하고 성공 여부를 반환합니다.
// 4. 'p': 해시 테이블 출력 - 각 슬롯의 연결 리스트에 저장된 모든 원소를 출력합니다.
// 해시 함수는 모듈러 연산을 사용하여 입력값을 해시 테이블 크기로 나눈 나머지를 반환합니다. 1차해싱


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// 해시 테이블의 노드를 나타내는 구조체 정의
typedef struct node {
    int number;
    struct node* next;
} hashTable;

// 해시 테이블의 크기를 전역 변수로 설정
int M;

// 해시 함수: 입력 값을 해시 테이블의 크기로 나눈 나머지를 반환
int h(int x) {
    return x % M;
}

// 함수 선언
void insertitem(hashTable* H, int x);
void printHashTable(hashTable* H);
int searchitem(hashTable* H, int x);
int deleteitem(hashTable* H, int x);

int main()
{
    hashTable* A;
    int x;
    char c = 0;

    // 해시 테이블 크기 입력
    scanf("%d", &M);

    // 해시 테이블 초기화: M개의 노드를 할당하고 모두 비워둠
    A = (hashTable*)malloc(sizeof(hashTable) * M);
    for (int i = 0; i < M; i++) {
        A[i].number = 0;
        A[i].next = NULL;
    }

    // 사용자가 'e'를 입력할 때까지 명령을 반복적으로 수행
    while (c != 'e') {
        scanf(" %c", &c);

        if (c == 'e') {
            break;  // 종료 조건
        }

        // 명령에 따라 요소 삽입, 검색, 삭제, 또는 출력 수행
        if (c == 'i') { // 삽입
            scanf("%d", &x);
            insertitem(A, x);
        }
        else if (c == 's') { // 검색
            scanf("%d", &x);
            int result = searchitem(A, x);
            printf("%d\n", result);
        }
        else if (c == 'd') { // 삭제
            scanf("%d", &x);
            int result = deleteitem(A, x);
            printf("%d\n", result);
        }
        else if (c == 'p') { // 출력
            printHashTable(A);
        }
    }

    // 해시 테이블 메모리 해제
    for (int i = 0; i < M; i++) {
        hashTable* current = A[i].next;
        while (current != NULL) {
            hashTable* temp = current;
            current = current->next;
            free(temp);  // 연결된 노드들을 순차적으로 해제
        }
    }
    free(A); // 해시 테이블 배열 자체를 해제

    return 0;
}

// 해시 테이블에 원소를 삽입하는 함수
void insertitem(hashTable* H, int x) {
    int index = h(x);  // 입력값을 해시 함수로 인덱스 계산
    hashTable* p = &H[index];

    // 새 노드 생성 및 값 할당
    hashTable* newnode = (hashTable*)malloc(sizeof(hashTable));
    newnode->number = x;
    newnode->next = NULL;

    // 인덱스 위치에 새 노드를 첫 번째로 삽입
    if (p->next == NULL) {
        p->next = newnode;
    }
    else {
        // 기존 노드가 존재할 경우, 새 노드를 맨 앞에 삽입
        newnode->next = p->next;
        p->next = newnode;
    }
}

// 해시 테이블의 내용을 출력하는 함수
void printHashTable(hashTable* H) {
    for (int i = 0; i < M; i++) {
        hashTable* current = H[i].next;
        while (current != NULL) {
            printf(" %d", current->number); // 노드 값 출력
            current = current->next;
        }
    }
    printf("\n"); // 각 출력 후 줄바꿈
}

// 해시 테이블에서 값을 검색하는 함수
int searchitem(hashTable* H, int x) {
    int index = h(x); // 입력값의 해시 인덱스 계산
    hashTable* current = H[index].next; // 해당 인덱스의 첫 번째 노드부터 탐색 시작
    int count = 1;

    // 값을 찾을 때까지 연결 리스트 순회
    while (current != NULL) {
        if (current->number == x) {
            return count; // 값이 발견되면 위치 반환
        }
        current = current->next;
        count++;
    }
    return 0; // 값이 발견되지 않으면 0 반환
}

// 해시 테이블에서 값을 삭제하는 함수
int deleteitem(hashTable* H, int x) {
    int index = h(x); // 입력값의 해시 인덱스 계산
    hashTable* current = &H[index];
    hashTable* prev = NULL;
    int count = 1;

    // 연결 리스트를 순회하며 값을 찾으면 노드를 삭제
    while (current != NULL && current->next != NULL) {
        prev = current;
        current = current->next;

        if (current->number == x) {
            // 노드를 삭제
            if (prev != NULL) {
                prev->next = current->next;
            }
            else {
                H[index].next = current->next;
            }
            free(current); // 메모리 해제
            return count;
        }
        count++;
    }
    return 0; // 값이 발견되지 않으면 0 반환
}