Phone List(HDOJ-1671)（tire樹）

Phone List(HDOJ-1671)（tire樹）

正解是字典樹，運用鏈表實現的一種數據結構，構建 方式和紫書上的二叉樹差不多。因為這道題的內存給的比較緊，所以需要解決內存問題，但是如果遞歸釋放內存會導致效率低下，解決方案是開一個內存池（數組），每次更新下標就可以重復利用了。

#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