[자료구조] HashTable c

#include <stdio.h>
#include <stdlib.h>
#include <string.h> //strlen

#pragma wanring (disable : 4996)

//연결리스트를 이용한 해시 구현

typedef struct node
{
    int value;  //값
    struct node* next;  //다음 노드의 주소를 저장
}node;

typedef struct hashTable
{
    node** head; //node포인터 배열의 주소를 저장하는 포인터
    int size; //해시 테이블의 사이즈
}hashTable;

//해싱을 위한 해시함수를 구현
//해싱 : 데이터의 타입과 관계없이 정수 값(배열의 인덱스)으로 계산하는 작업
int hashInt(int value, int size);
int hashString(char* str, int size);
void createHash(hashTable* p, int size);
void addKey(hashTable* p, int key);

int hashInt(int value, int size)
{
    return value % size;
}

int hashString(char* str, int size)
{
    int total = 0;
    for(int i = 0; i < strlen(str); i++)
    {
        total += str[i]; //문자의 아스키코드 값을 더해준다.
    }

    return total % size;
}

void createHash(hashTable* p, int size)
{
    /*
    p->head = (node**)malloc(sizeof(node*) * size); //포인터 변수 7개 생성
    for (int i = 0; i < size; i++)
        p->head[i] = NULL;
     */

    //메모리 할당 후 0으로 초기화
    // p->head = (node**)calloc(개수, 개당 사이즈); // 포인터 변수 7개 생성
    p->head = (node**)calloc(size, sizeof(node*)); //포인터 변수 7개 생성
    p->size = size;
}

void addKey(hashTable* p, int key)
{
    //key값을 해싱한 후, 얻어진 값은 hashValue라고 한다.
    int hashValue = hashInt(key, p->size);
    node* newNode;
    newNode = (node*)malloc(sizeof(node));
    newNode->value = key;
    newNode->next = NULL;

    if(p->head[hashValue] == NULL)
    {
        p->head[hashValue] = newNode;
        return;
    }

    // 맨 앞 추가
    newNode->next = p->head[hashValue];
    p->head[hashValue] = newNode;
}

void displayHashTable(hashTable* p)
{
    node* curNode;

    for(int i = 0; i < p->size; i ++)
    {
        curNode = p->head[i];
        printf("HashTable[%d] => ", i);
        while (curNode)
        {
            printf("%d ", curNode->value);
            curNode = curNode->next;
        }
        puts("");
    }
    /*
    curNode = p->head[0];
    while (curNode)
    {
        printf("%d ", curNode->value);
        curNode = curNode->next;
    }
    puts("");

    curNode = p->head[1];
    while (curNode)
    {
        printf("%d ", curNode->value);
        curNode = curNode->next;
    }
    puts("");

    curNode = p->head[2];
    while (curNode)
    {
        printf("%d ", curNode->value);
        curNode = curNode->next;
    }
    puts("");
     */
}

int main()
{
    hashTable ht; //구조체 변수 선언

    createHash(&ht, 7); //해시테이블변수, 해시 테이블의 크기

    // 해시테이블에서 저장되는 값을 key라 부른다.
    addKey(&ht, 77);
    addKey(&ht, 7);
    addKey(&ht, 36);
    addKey(&ht, 92);
    addKey(&ht, 15);
    addKey(&ht, 79);
    addKey(&ht, 83);

    displayHashTable(&ht);

    return 0;
}