Phone List(HDOJ-1671)(tire树)_PHP教程
程序员文章站
2022-04-09 17:21:43
...
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;i next[id]==NULL) { ok = false; q = &all_trie[k++]; for(int j=0;jnext[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;inext[i] = NULL; for(int i=0;i ;i++){>;i++){>
上一篇: [PHP源码阅读]count函数