Hash 문제 1

#include <iostream>
using namespace std;

typedef enum
{
    NAME,
    NUMBER,
    BIRTHDAY,
    EMAIL,
    MEMO
} FIELD;


typedef struct
{
    int count;
    char str[20];
} RESULT;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
#define MAX_KEY 22
#define MAX_TABLE 60000


unsigned long myhash(const char* str) {

    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c) % MAX_TABLE;
    }

    return hash % MAX_TABLE;
}


void mystrcpy(char* a, char* b) {
    while (*b != '\0') {
        *a = *b;
        a++; b++;
    }
    *a = '\0';
}

int mystrcmp(char* a, char* b) {
    for (; *a && (*a == *b); a++, b++);
    return *a - *b;
}


int idx = 0;

struct NODE {
    char data[5][MAX_KEY + 1];//name,num,birth,email,memo
    NODE* prev[5];
    int nodeNum;
}a[MAX_TABLE];


NODE* myalloc() {
    return &a[idx++];
}

//5 tables 
NODE* hTable[5][MAX_TABLE];


void InitDB()
{
    idx = 0;
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < MAX_TABLE; ++j)
            hTable[i][j] = nullptr;

}


void Add(char* name, char* number, char* birthday, char* email, char* memo)
{
    NODE* newNode = myalloc();

    newNode->nodeNum = idx - 1;

    mystrcpy(newNode->data[0], name);
    mystrcpy(newNode->data[1], number);
    mystrcpy(newNode->data[2], birthday);
    mystrcpy(newNode->data[3], email);
    mystrcpy(newNode->data[4], memo);

    int key[5];
    key[0] = (int)myhash(name);
    key[1] = (int)myhash(number);
    key[2] = (int)myhash(birthday);
    key[3] = (int)myhash(email);
    key[4] = (int)myhash(memo);

    for (int i = 0; i < 5; ++i) {
        newNode->prev[i] = hTable[i][key[i]];
        hTable[i][key[i]] = newNode;
    }

}


int Delete(FIELD field, char* str)
{
    /*
    1)hash, singledLinkedList는 이전노드를 찾아가지 못하므로 이전 노드의 prev저장
      삭제할 데이터를 찾고, 그 이전 노드의 prev에 검색된 노드의 prev 대입
    */

    int deletecnt = 0;
    int h = (int)myhash(str);

    for (NODE* pp = hTable[field][h]; pp != nullptr; pp = pp->prev[field]) {
        if (!mystrcmp(str, pp->data[field])) {//found
            deletecnt++;
            int thisNodeNum = pp->nodeNum;

            //delete in 5 tables
            for (int i = 0; i < 5; ++i) {
                int k = (int)myhash(pp->data[i]);
                NODE** del = &hTable[i][k]; //해당 테이블의 처음 노드로 초기화

                for (NODE* kk = hTable[i][k]; kk != nullptr; kk = kk->prev[i]) {
                    if (kk->nodeNum == thisNodeNum) {
                        *del = kk->prev[i]; //검색된 노드의 prev를 이전 노드 prev에 저장
                        break;
                    }
                    del = &kk->prev[i];
                }
            }
        }
    }

    return deletecnt;
}


int Change(FIELD field, char* str, FIELD changefield, char* changestr)
{
    //change : field가 str인 애들의 changefield를 changestr로 바꿔라
    //field가 str인 애들을 지우고 (정보 카피)
    //그 정보에서 changefield가 changestr인 애들로 다시 ADD 

    int changecnt = 0;
    int h = (int)myhash(str);

    char thisData[5][MAX_KEY];

    for (NODE* pp = hTable[field][h]; pp != nullptr; pp = pp->prev[field]) {
        
        if (!mystrcmp(str, pp->data[field])) {//found            
            changecnt++;
            int thisNodeNum = pp->nodeNum;
                
            for (int i = 0; i < 5; ++i) {
                mystrcpy(thisData[i], pp->data[i]);
                int k = (int)myhash(pp->data[i]);
                NODE** del = &hTable[i][k]; //해당 테이블의 처음 노드로 초기화
                
                for (NODE* kk = hTable[i][k]; kk != nullptr; kk = kk->prev[i]) {
                    if (kk->nodeNum == thisNodeNum) {
                        *del = kk->prev[i];
                        break;
                    }
                    del = &kk->prev[i];
                }
            }

            mystrcpy(thisData[changefield], changestr);
            Add(thisData[0], thisData[1], thisData[2], thisData[3], thisData[4]);
        }//found end
    }
    return changecnt;
}


RESULT Search(FIELD field, char* str, FIELD ret_field)
{
    //cout << "##### Field가 "<<field<<" "<<str <<" 인 레코드를 찾아라"<< endl; 
    RESULT result;
    result.count = -1;

    
    int h = (int)myhash(str);
    int cnt = 0;

    for (NODE* pp = hTable[field][h]; pp != nullptr; pp = pp->prev[field]) {
        if (!mystrcmp(pp->data[field], str)) {
            cnt++;
            mystrcpy(result.str, pp->data[ret_field]);
        }
    }

    result.count = cnt;
    return result;
}

 

You may also like...