Tree

  • Parent, Child 연결 정보를 구현 하기 위해 아래와 같은 코드 구현
  • 아래 경우, ID가 정수로 들어오는 경우다.
  • 한 Parent가 여러 Child를 갖을 수 있으므로 Child는 링크드리스트로 구현 (child_info는 hash table 같은 구조)
#include <iostream>
using namespace std;
#define MAXNODE 1000

struct NODE {
    int id;
    NODE* prev;

}a[10000];

int idx = 0;
int parent_info[MAXNODE];//parent info array
NODE* child_info[MAXNODE];//child info linked list (same as hash table)
//if you want set other info, make more global vars
char name[MAXNODE][32];
int age[MAXNODE];
int numberOfChild[MAXNODE];

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


void traversing_tree(int node) {
    cout << node << " ";
    for (NODE* pp = child_info[node]; pp != NULL; pp = pp->prev) {
        traversing_tree(pp -> id);//recursive
    }
}


int main() {
    int T; cin >> T;
    for (int test_case = 0; test_case < T; ++test_case) {
        //init
        idx = 0;
        for (int i = 0; i < MAXNODE; ++i) {
            parent_info[i] = -1;
            child_info[i] = nullptr;
            *name[i] = NULL;
            age[i] = NULL;
            numberOfChild[i] = NULL;
        }

        int N; cin >> N;
        int parent, child;
        for (int i = 0; i < N; ++i) {
            cin >> parent >> child;
            parent_info[child] = parent;
            NODE* p = myalloc();
            p->id = child;
            p->prev = child_info[parent];
            child_info[parent] = p;
        }

        traversing_tree(1);//traversing all node under #1

    }
    
    return 0;
}
  • 만일 ID가 정수가 아닌 경우, 정수로 변경해서 위의 코드를 사용하면 됨. 가령 문자열ID의 경우
  • 변경하는 방법 1: table에 문자열 : 정수로 해주면 되지만 매번 찾을때 시간이 오래걸림
  • 변경하는 방법 2: Hash table이용. getid_hash를 하나 더 만들어서 들어오는 문자열을 정수로 변경하여 위의 코드사용하면됨
  • 즉 hash테이블형 배열을 위의 코드까지 포함 2개 사용하는 셈
#include <iostream>
using namespace std;
#define MAXTABLE 1000
#define MAXNODE 1000

unsigned long myhash(const char *str) {
    unsigned long hash = 5381;
    int c;

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

    return hash % MAXTABLE;
}

///////////////////////////////////////For Name To ID////////////////////////////////////////
struct ID_NAME_NODE {
    int id;
    char name[7];
    ID_NAME_NODE* prev;
}b[1000];

int id_name_idx = 0;
int id = 0;
char id2name[MAXTABLE][10];

ID_NAME_NODE* myIDalloc() {
    return &b[id_name_idx++];
}

ID_NAME_NODE* id_hash_table[MAXTABLE];

int getid_hash(char* name) {
    int key = (int)myhash(name);

    for (ID_NAME_NODE* pp = id_hash_table[key]; pp != NULL; pp = pp->prev) {
        if (!strcmp(pp->name, name)) {
            return pp->id;
        }
    }

    //if is not in hash table, add it
    ID_NAME_NODE* p = myIDalloc();
    strcpy(id2name[id], name);   //to restore name from id later
    p->id = id++;//from global var
    strcpy(p->name, name);
    p->prev = id_hash_table[key];
    id_hash_table[key] = p;
    
    return p->id;
}

////////////////////////////////////////////////////////////////////////////////////////////
struct NODE {
    int id;
    NODE* prev;

}a[10000];

int idx = 0;
int parent_info[MAXNODE];//parent info array
NODE* child_info[MAXNODE];//child info linked list (same as hash table)
//if you want set other info, make more global vars


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


void traversing_tree(int node) {
    cout << *id2name[node] << " ";
    for (NODE* pp = child_info[node]; pp != NULL; pp = pp->prev) {
        traversing_tree(pp->id);//recursive
    }
}


//when NODE is not Integer
int main() {
    //change NODE ID to Integer

    /*solv 1
    Use a table, use idx number instead real name
    0 | AAAAA
    1 | BBBBBBB
    2 | CCCCCC
    But, when the number of Node increase, speed will be slow
    */

    /*solv 2
    Use Hash Table
    Much faster than solv1
    if there is searched id, return the id, or add new Node and return the id
    Hash table(0):
    Hash table(1): IIIII(8) DDDDDD(3)
    Hash table(2):
    Hash table(3): GGG(6) BBBBBBB(1)
    ...
    */
    int T; cin >> T;
    for (int test_case = 0; test_case < T; ++test_case) {
        //init for id hashing
        id = 0;
        id_name_idx = 0;
        for (int i = 0; i < MAXTABLE; ++i) {
            id_hash_table[i] = nullptr;
            *id2name[i] = NULL;
        }
        
        //init
        idx = 0;
        for (int i = 0; i < MAXNODE; ++i) {
            parent_info[i] = -1;
            child_info[i] = nullptr;
        }
        //init end

        int N; cin >> N;
        for (int i = 0; i < N; ++i) {
            char parentname[10], childname[10];
            int parent, child;
            cin >> parentname >> childname;
            
            //convert name to id
            parent = getid_hash(parentname);
            child = getid_hash(childname);

            cout << parent << " " << child<<endl;

            //same with before
            parent_info[child] = parent;
            NODE* p = myalloc();
            p->id = child;
            p->prev = child_info[parent];
            child_info[parent] = p;
        }

        traversing_tree(0);//traversing all node under #0

    }

    return 0;
}

 

Musicals, Travel, Photo, Coding