해시테이블 구현 / 선형 조사법

// 이 코드는 해시 테이블을 선형 조사법(Linear Probing)을 사용하여 구현한 프로그램입니다.
// 해싱은 해시 함수로부터 계산된 인덱스에 데이터를 삽입하며, 충돌이 발생할 경우 선형 탐색으로 해결합니다.
// 주요 기능:
// 1. 'i': 원소 삽입 - 해시 값에 따라 데이터를 저장하며 충돌 시 빈 슬롯을 탐색하여 저장합니다.
// 2. 's': 원소 검색 - 해시 값에 따라 데이터 위치를 검색하며 충돌 시 다음 슬롯을 탐색하여 확인합니다.
// 3. 'p': 해시 테이블 출력 - 해시 테이블의 모든 슬롯 값을 출력합니다.
// 해시 함수는 모듈러 연산(x % M)을 사용하여 데이터를 삽입할 초기 인덱스를 계산합니다.

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

// 이 코드는 해시 테이블을 선형 조사법(Linear Probing)을 사용하여 구현한 프로그램입니다.
// 해싱은 해시 함수로부터 계산된 인덱스에 데이터를 삽입하며, 충돌이 발생할 경우 선형 탐색으로 해결합니다.
// 주요 기능:
// 1. 'i': 원소 삽입 - 해시 값에 따라 데이터를 저장하며 충돌 시 빈 슬롯을 탐색하여 저장합니다.
// 2. 's': 원소 검색 - 해시 값에 따라 데이터 위치를 검색하며 충돌 시 다음 슬롯을 탐색하여 확인합니다.
// 3. 'p': 해시 테이블 출력 - 해시 테이블의 모든 슬롯 값을 출력합니다.
// 해시 함수는 모듈러 연산(x % M)을 사용하여 데이터를 삽입할 초기 인덱스를 계산합니다.


//typedef struct node {
//    int number;
//    struct node* next;
//} hashTable;
// 선형 조사법
int M, n;

int h(int x);
int insertitem(int* A, int x);
void printHashTable(int* A);
int searchitem(int* A, int x);

int main()
{

    int x;
    char c = 0;

    // 해시 테이블 크기 입력
    scanf("%d %d", &M, &n);
    // 해시 테이블 초기화
    int* A = (int*)malloc(sizeof(int) * M);

    for (int i = 0; i < M; i++)
        A[i] = 0;

    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", result);
            if (result != -1)
                printf(" %d\n", A[result]);
        }
        else if (c == 'p') {
            printHashTable(A);
        }
    }

    return 0;
}

int h(int x) {
    return x % M;
}

// 해시 테이블에 원소를 삽입하는 함수
int insertitem(int* A, int x) {

    int index = h(x);
    int cnt = 0;
    
    while (A[index] != 0)
    {
        index++;
        if (index == M)
            index = 0;
        printf("C");
    }
    A[index] = x;
    printf("%d\n", index);
}

// 해시 테이블의 내용을 출력하는 함수
void printHashTable(int* A) {
    for (int i = 0; i < M; i++) {
        printf(" %d", A[i]);
    }
    printf("\n");
}

// 해시 테이블에서 값을 검색하는 함수
int searchitem(int* A, int x) {
    int index = h(x);
    int s = -1;
    for (int i = 0; i < M; i++)
    {
        if (A[i] == x)
        {
            s = i;
            break;
        }
    }
    return s; // 값이 발견되지 않음
}

// 해시 테이블에서 값을 삭제하는 함수