Phone List(HDOJ-1671)（tire树）_php

正解是字典树，运用链表实现的一种数据结构，构建 方式和紫书上的二叉树差不多。因为这道题的内存给的比较紧，所以需要解决内存问题，但是如果递归释放内存会导致效率低下，解决方案是开一个内存池（数组），每次更新下标就可以重复利用了。

 #include #include #include #include using namespace std; int T,n,k; struct pa{     char s[15];     int len; }; bool cmp(pa a,pa b){     return a.len>b.len; } struct trie{     trie *next[15]; }; trie *root; trie all_trie[1000000]; bool built(char *s,int len) {     bool ok = true;     trie *p = root, *q;     for(int i=0;inext[id]==NULL) {             ok = false;             q = &all_trie[k++];             for(int j=0;j<10;j++) q->next[j] = NULL;             p->next[id] = q;             p = p->next[id];         }         else {             p = p->next[id];         }     }     return ok; } int main(){     scanf("%d",&T);     while(T--){         scanf("%d",&n);         pa s[10005];         k = 0;         bool ok = true;         root = &all_trie[k++];         for(int i=0;i<10;i++) root->next[i] = NULL;         for(int i=0;i

欢迎大家阅读《Phone List(HDOJ-1671)（tire树）_php》,跪求各位点评,若觉得好的话请收藏本文，by 搞代码

喜欢 (0)赏

[搞代码]

分享 (0)