사람의 정보를 저장하는 테이블에 대한 예제를 만들어 볼것이다.

Person.h

#ifndef __PERSON_H__
#define __PERSON_H__

#define STR_LEN 100

typedef struct _person
{
    int ssn;
    char name[STR_LEN];
    char add[STR_LEN];
} Person;

int GetSSN(Person *p);
void ShowPerInfo(Person *p);
Person *MakePersonInfo(int ssn, char *name, char *add);

#endif

Person.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Person.h"

int GetSSN(Person *p)
{
    return p->ssn;
}
void ShowPerInfo(Person *p)
{
    printf("ssn : %d \\n", p->ssn);
    printf("name : %s \\n", p->name);
    printf("add : %s \\n", p->add);
}

Person *MakePersonInfo(int ssn, char *name, char *add)
{
    Person *newPerson = (Person *)malloc(sizeof(Person));
    newPerson->ssn = ssn;
    strcpy(newPerson->name, name);
    strcpy(newPerson->add, add);
    return newPerson;
}

위의 코드는 사람에 대한 정보를 관리하는 예제이다.

Slot.h

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h"

typedef int Key;
typedef Person *Value;

typedef struct _slot
{
    Key key;
    Value val; 
} Slot;

#endif

충돌을 해결 하기 위한 테이블 예제에서 설명했던 Slot의 구조체

https://www.notion.so/1de5b0e978884fbe8c4beaa090721a9d

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

#include "Slot.h"

typedef Slot LData;

typedef struct _node
{
    LData data;
    struct _node *next;
} Node;

typedef struct _DLinkdeList
{
    Node *head;
    Node *cur;
    Node *before;
    int (*comp)(LData d1, LData d2);
    int numOfData;
} List;

void ListInit(List *list);
void LInsert(List *list, LData data);
int LFirst(List *list, LData *data);
int LNext(List *list, LData *data);
LData LRemove(List *list);
int LCount(List *list);

#endif

List를 사용하여 chaining을 구성한 코드이다.

https://www.notion.so/67b0fd5f9878477c9cba19f4e84a0b58

Table.h

#ifndef __TABLE_H__
#define __TABLE_H__

#include "Slot.h"
#include "DLinkedList.h"

#define MAX_LEN 100

typedef int HashFunc(int k);

typedef struct _table
{
    List tbl[MAX_LEN];
    HashFunc *hf;
} Table;

void TBLInit(Table *pt, HashFunc *f);
void TBLInsert(Table *pt, Key k, Value v);
Value TBLDelete(Table *pt, Key k);
Value TBLSearch(Table *pt, Key k);

#endif

Table.c

#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
#include "DLinkedList.h"

void TBLInit(Table *pt, HashFunc *f)
{
    pt->hf = f;
    for (int i = 0; i < MAX_LEN; i++)
    {
        ListInit(&(pt->tbl[i]));
    }
}
Value TBLSearch(Table *pt, Key k)
{
    int hv = pt->hf(k);
    Slot cSlot;

    if (LFirst(&(pt->tbl[hv]), &cSlot))
    {
        if (cSlot.key == k)
            return cSlot.val;
        else
        {
            while (LNext(&(pt->tbl[hv]), &cSlot))
            {
                if (cSlot.key == k)
                    return cSlot.val;
            }
            
        }
    }
    return NULL;
}
void TBLInsert(Table *pt, Key k, Value v)
{
    int hv = pt->hf(k);
    Slot ns = {k, v};
    if (TBLSearch(pt, k) != NULL)
    {
        return ;
    }
    LInsert(&(pt->tbl[hv]), ns);
}
Value TBLDelete(Table *pt, Key k)
{
    int hv = pt->hf(k);
    Slot cSlot;

    if (LFirst(&(pt->tbl[hv]), &cSlot))
    {
        if (cSlot.key == k)
        {
            LRemove(&(pt->tbl[hv]));
            return cSlot.val;
        }
        else
        {
            while (LNext(&(pt->tbl[hv]), &cSlot))
            {
                if (cSlot.key == k)
                {
                    LRemove(&(pt->tbl[hv]));
                    return cSlot.val;
                }
            }
        }
    }
    return NULL;
}