首页 > 代码库 > hdu 1671 Phone List (Trie树)
hdu 1671 Phone List (Trie树)
简单的字典树应用，在建树的时候判断就行了。
需要注意的语法：
在使用malloc和free来处理动态内存的时候，仅仅是释放了这个对象所占的内存，而不会调用这个对象的析构函数；使用new和delete就可以既释放对象的内存的同时，调用这个对象的析构函数。所以建立trie时用new更方便一些。
注意要每组数据处理完后释放动态内存（适时释放动态内存是基本素养），否则会造成内存泄漏（提交后导致MLE）。还要注意有这么个知识点：
delete和free都是只把指针所指向的内存释放掉了，并没有把指针本身干掉。在free和delete之后，都需要把指向清理内存的指针置为空，即p=NULL，否则指针指向的内存空间虽然释放了，但是指针p的值还是记录的那块地址，该地址对应的内存是垃圾，p就成了“野指针”。同样会使人认为p是个合法的指针，如果程序较长，我们通常在使用一个指针前会检查p！=NULL，这样就起不到作用了。此时如果再释放p指向的空间，编译器就会报错，因为释放一个已经被释放过的空间是不合法的。而将其置为NULL之后再重复释放就不会产生问题，因为delete一个0指针是安全的。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=10000+10;int T,n;char ss[15];struct trie{ trie*next[10]; int v; trie() { for(int i=0; i<10; i++) { next[i]=NULL; } v=0; }};trie *root;bool build(char *s){ int len=strlen(s); trie *p=root,*q; for(int i=0; i<len; i++) { int id=s[i]-‘0‘; if(p->next[id]==NULL) { q=new trie; p->next[id]=q; p=p->next[id]; p->v=1; } else if(p->next[id]->v==-1) { return false; } else { p=p->next[id]; p->v++; } } if(p->v>1) return false; else { p->v=-1; return true; }}void fang(trie*r){ if(r==NULL) return; else { for(int i=0; i<10; i++) { if(r->next[i]) fang(r->next[i]); } } delete r; r=NULL; return;}int main(){ //freopen("in8.txt","r",stdin); scanf("%d",&T); while(T--) { root=new trie; scanf("%d",&n); bool ans=true; for(int i=0; i<n; i++) { scanf("%s",ss); if(ans==true) { ans=build(ss); } } if(ans) puts("YES"); else puts("NO"); fang(root); } return 0;}
hdu 1671 Phone List (Trie树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。