給出N個單詞組成的熟詞表,以及壹篇全用小寫英文書寫的文章,請妳按最早出現的順序寫出所有不在熟詞表中的生詞。
在這道題中,我們可以用數組枚舉,用哈希,用字典樹,先把熟詞建壹棵樹,然後讀入文章進行比較,這種方法效率是比較高的。 給定N個互不相同的僅由壹個單詞構成的英文名,讓妳將他們按字典序從小到大輸出
用字典樹進行排序,采用數組的方式創建字典樹,這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。 #include<cstring>#include<iostream>#include<conio.h>usingnamespacestd;namespacetrie{template<classT,size_tCHILD_MAX>/*ParameterT:Typeofreserveddata.ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.*/structnod{Treserved;nod<T,CHILD_MAX>*child[CHILD_MAX];nod(){memset(this,0,sizeof*this);}~nod(){for(unsignedi=0;i<CHILD_MAX;i++)deletechild[i];}voidTraversal(char*str,unsignedindex){unsignedi;for(i=0;i<index;i++)cout<<str[i];cout<<'\t'<<reserved<<endl;for(i=0;i<CHILD_MAX;i++){if(child[i]){str[index]=i;child[i]->Traversal(str,index+1);}}return;}};template<classT,size_tCHILD_MAX=127>/*ParameterT:Typeofreserveddata.ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.*/classtrie{private:nod<T,CHILD_MAX>root;public:nod<T,CHILD_MAX>*AddStr(char*str);nod<T,CHILD_MAX>*FindStr(char*str);boolDeleteStr(char*str);voidTraversal(){charstr[100];root.Traversal(str,0);}};template<classT,size_tCHILD_MAX>nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::AddStr(char*str){nod<T,CHILD_MAX>*now=&root;do{if(now->child[*str]==NULL)now->child[*str]=newnod<T,CHILD_MAX>;now=now->child[*str];}while(*(++str)!='\0');returnnow;}template<classT,size_tCHILD_MAX>nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::FindStr(char*str){nod<T,CHILD_MAX>*now=&root;do{if(now->child[*str]==NULL)returnNULL;now=now->child[*str];}while(*(++str)!='\0');returnnow;}template<classT,size_tCHILD_MAX>booltrie<T,CHILD_MAX>::DeleteStr(char*str){nod<T,CHILD_MAX>**nods=newnod<T,CHILD_MAX>*[strlen(str)];intsnods=1;nod<T,CHILD_MAX>*now=&root;nods[0]=&root;do{if(now->child[*str]==NULL)returnfalse;nods[snods++]=now=now->child[*str];}while(*(++str)!='\0');snods--;while(snods>0){for(unsignedi=0;i<CHILD_MAX;i++)if(nods[snods]->child[i]!=NULL)returntrue;deletenods[snods];nods[--snods]->child[*(--str)]=NULL;}returntrue;}}intmain(){//TestProgramtrie::trie<int>tree;while(1){cout<<1foraddastring<<endl;cout<<2forfindastring<<endl;cout<<3fordeleteastring<<endl;cout<<4fortraversal<<endl;cout<<5forexit<<endl;charstr[100];switch(getch()){case'1':cin.getline(str,100);cout<<Thisstinghasexistedfor<<tree.AddStr(str)->reserved++<<times.<<endl;break;case'2':cin.getline(str,100);trie::nod<int,127>*find;find=tree.FindStr(str);if(!find)cout<<Nofound.<<endl;elsecout<<Thisstinghasexistedfor<<find->reserved<<times.<<endl;break;case'3':cin.getline(str,100);cout<<Theactionis<<(tree.DeleteStr(str)?Successful.:Unsuccessful.)<<endl;break;case'4':tree.Traversal();break;case'5':return0;}}return0;}