DLL + hash 2개

기본 더블링크드리스트 와 2개 이상의 hash를 연결하는 코드.

이걸 자유자재로 구사해야 한다.

 

#include <stdio.h>
 
// 시험에서 주어짐 [[
void mystrcpy(char*dest, const char*src) {
    while ((*dest++ = *src++));
}
// 시험에서 주어짐 ]]
 
void printcount()
{
    printf("counthash\n");
    for (int i = 0; i < 100; ++i)    {
        if (realcnt[i])    {
            printf("[%d] : %d", i, realcnt[i]);
 
            //시작에는 더미가 있으니 시작 다음부터 loop
            for (Node* p = counthash[i]->countnext; p != 0; p = p->countnext)    {
                printf("[name:%s, cnt:%d] -> ", p->name, p->cnt);
            }
            printf("\n");
        }
    }
    printf("\n");
}
 
int bn;
int realcnt[101];
struct Node
{
    char name[11];
    int cnt;
    Node* nameprev;
    Node* namenext;
    Node* countprev;
    Node* countnext;
 
    Node* alloc(char _name[11], int _cnt, Node* _nameprev, Node* _namenext, Node* _countprev, Node* _countnext)    {
        mystrcpy(name, _name);
        cnt = _cnt;
        nameprev = _nameprev;
        namenext = _namenext;
        countprev = _countprev;
        countnext = _countnext;
 
        if (nameprev)    nameprev->namenext = this;
        if (namenext)    namenext->nameprev = this;
        if (countprev)    countprev->countnext = this;
        if (countnext)    countnext->countprev = this;
 
        return this;
    }
    void move(int _cnt)    {
        // 기존 링크드리스트에서 삭제    
        if (countprev)    countprev->countnext = countnext;
        if (countnext)    countnext->countprev = countprev;
        realcnt[cnt]--;
 
        cnt += _cnt;
 
        // 새 링크드리스트에서 추가
        countprev = counthash[cnt];
        countnext = counthash[cnt]->countnext;
        if (countprev)    countprev->countnext = this;
        if (countnext)    countnext->countprev = this;
        realcnt[cnt]++;
    }
}buf[50000], *namehash[20010], *counthash[101];
 
// 앞 3글자로 hashkey. 3글자 보다 작을경우 예외처리 필요
int getnamekey(char name[11])
{
    int a = name[0] - 'a';
    int b = name[1] - 'a';
    int c = name[2] - 'a';
 
    return (a * 26 * 26 + b * 26 + c);
}
 
int main()
{
    // 초기화할때는 namehash[i]로 리턴받음
    bn = 0;
    for (int i = 0; i < 20000; ++i)    namehash[i] = buf[bn++].alloc("", 0, 0, 0, 0, 0);
    for (int i = 0; i < 100; ++i)    counthash[i] = buf[bn++].alloc("", 0, 0, 0, 0, 0);
 
    char name[10][11] = { "chaewon", "minji", "chiney", "jenny", "suyeon", "vera", "danny", "yuri", "hyungji", "yuna" };
    
    int namekey = 0;
    int countkey = 0;
    for (int i = 0; i < 10; ++i)    {
        namekey = getnamekey(name[i]);
        countkey = 0;
 
        // 넣을때는 namehash[i]로 리턴받지 않음. 그래야 namehash[i]가 시작을 가르키고 있으니
        buf[bn++].alloc(name[i], 0, namehash[namekey], namehash[namekey]->namenext, counthash[countkey], counthash[countkey]->countnext);
        realcnt[countkey]++;
    }
    
    // 점수 변경
    char changename[10][11] = { "chaewon", "minji", "chiney", "chiney", "suyeon", "suyeon", "danny", "yuna", "hyungji", "yuna" };
    int changeval[10] = { 5, 6, 2, 3, 4, 5, 5, 6, 7, 1 };
 
    for (int i = 0; i < 10; ++i)    {
        namekey = getnamekey(changename[i]);
        for (Node* p = namehash[namekey]->namenext; p != 0; p = p->namenext)    {
            // hash에 따라 비교구문 추가
            p->move(changeval[i]);
        }
    }
 
}

 

링크드리스트 안에서 노드를 삭제할경우 여러개의 삭제가 필요하다면 아래처럼 한다.

더미가 있어야 한다. 더미가 없으면 아래의 삭제도 첫번째 노드가 안지워진다.

// 이렇게 지우면 제대로 못지운다. 연속으로 있을때 문제
// 원래 5->4->4->4->3->3->3->2->2->1
// 지운 5->4->4->4->3->3->3->2->1
for (Node* p = head->next; p != 0; p = p->next) {
    if (p->data == 2) p->del();
}
 
// 이렇게 해야 제대로 지운다.
// 원래 5->4->4->4->3->3->3->2->2->1
// 지운 5->4->4->4->3->3->3->1
Node* p = head;
while (p->next) {
    if (p->next->data == 2)    p->next->del();
    else p = p->next;
}