首页 > 代码库 > 【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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。