首页 > 代码库 > 【POJ】1056 IMMEDIATE DECODABILITY

【POJ】1056 IMMEDIATE DECODABILITY

字典树水题。

 1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 typedef struct Trie { 6     bool v; 7     Trie *next[2]; 8 } Trie; 9 10 Trie *root;11 12 bool create(char str[]) {13     int i = 0, id;14     bool ret = false;15     Trie *p = root, *q;16 17     while (str[i]) {18         id = str[i] - 0;19         ++i;20         if (p->next[id] == NULL) {21             q = (Trie *)malloc(sizeof(Trie));22             q->v = false;23             q->next[0] = q->next[1] = NULL;24             p->next[id] = q;25             ret = true;26         } else {27             if (p->next[id]->v)28                 return false;29         }30         p = p->next[id];31     }32     p->v = true;33 34     return ret;35 }36 37 void del(Trie *t) {38     if (t == NULL)39         return ;40     del(t->next[0]);41     del(t->next[1]);42     free(t);43 }44 45 int main() {46     int t = 0;47     char buf[25];48     bool f = true;49     root = (Trie *)malloc(sizeof(Trie));50     root->next[0] = root->next[1] = NULL;51     while (scanf("%s", buf) != EOF) {52         if (buf[0] == 9) {53             ++t;54             if (f)55                 printf("Set %d is immediately decodable\n", t);56             else57                 printf("Set %d is not immediately decodable\n", t);58             f = true;59             del(root);60             root = (Trie *)malloc(sizeof(Trie));61             root->next[0] = root->next[1] = NULL;62         } else {63             if (f)64                 f = create(buf);65         }66     }67 68     return 0;69 }