반응형
아래와 같이 triePool을 만들어두고 동적 할당이 아닌 정적 할당을 해주고
alloc 이라는 함수를 만들어 해당하는 배열의 인덱스의 주소를 넘기면 우리가 흔히 하는 new를 이용 할 수 있다.
그리고 delete 대신 trieIdx = 0을 통해 새로이 트라이 배열을 사용 할 수 있어 delete 효과를 볼 수 있다.
소스 코드 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <iostream> #define MAX_SIZE 26 struct Trie { Trie *next[MAX_SIZE]; bool isEnd; int cnt; }; Trie triePool[1000002]; int trieIdx; Trie *root; void init() { root = nullptr; trieIdx = 0; } Trie *alloc() { for (int i = 0; i < MAX_SIZE; i++) triePool[trieIdx].next[i] = nullptr; triePool[trieIdx].isEnd = triePool[trieIdx].cnt = 0; return &triePool[trieIdx++]; } void insert(int buffer_size, char *buf) { if(root == nullptr) root = alloc(); Trie *cur = root; int len = buffer_size; for (int i = 0; i < len; i++) { int ch = buf[i] - 'a'; if (cur->next[ch] == nullptr) cur->next[ch] = alloc(); cur = cur->next[ch]; cur->cnt++; } cur->isEnd = true; } int query(int buffer_size, char *buf) { if (root == nullptr) return 0; Trie *cur = root; int len = buffer_size; for (int i = 0; i < len; i++) { int ch = buf[i] - 'a'; if (cur->next[ch] == nullptr) return 0; cur = cur->next[ch]; } return cur->cnt; } | cs |
반응형
'Applied > 자료구조' 카테고리의 다른 글
Parent, Child, Sibling 구조의 Tree (0) | 2019.09.10 |
---|---|
해싱 기법 소스 코드(No STL) (0) | 2019.04.01 |
재귀가 아닌 반복문을 이용한 Trie (0) | 2018.03.07 |
힙(Heap) 자료구조 (4) | 2018.03.04 |
[STL] deque 구현 (2) | 2018.02.28 |