`
bcyy
  • 浏览: 1809821 次
文章分类
社区版块
存档分类
最新评论

hdu 1250 字典树+内存释放

 
阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1251
/*
第一次做字典树,找了一道比较简单的。
建树的时候用到了new动态分配内存,刚好学C++的时候老师讲到了这一点,动态内存有申请就要有释放。
但是在网上看了好多代码都没有清理内存。虽然能通过题目测试,但是却反映了一个编程态度的问题。
在此告诫自己,也希望大家都能端正自己的态度,不要为了AC而AC

*/

#include"iostream"
#include"cstring"
#include"cstdlib"
using namespace std;
//结点结构
struct Node
{
	int ncount;
	Node* Next[26];
};
Node* root;
//初始化结点
void Init(Node* t)
{
	memset(t->Next,NULL,sizeof(t->Next));
	t->ncount=0;
}
//插入新单词
void Insert(char* s)
{
	int i,k;
	Node* p=root;
	Node* newnode;
	for(i=0;i<strlen(s);i++){
		k=s[i]-'a';
		if(p->Next[k]==NULL){
			newnode=new Node;
			Init(newnode);
			p->Next[k]=newnode;
			p=newnode;
			p->ncount++;
		}
		else{
			p=p->Next[k];
			p->ncount++;
		}
	}
}
//搜索单词
int Search(char* s)
{
	int i,k;
	Node* p=root;
	for(i=0;i<strlen(s);i++){
		k=s[i]-'a';
		if(p->Next[k]==NULL)
			return 0;
		else
			p=p->Next[k];
	}
	return p->ncount;
}
//释放内存
void Freedom(Node* p)
{
	int i;
	for(i=0;i<26;i++){
		if(p->Next[i]!=NULL)
			Freedom(p->Next[i]);
	}
	delete p;
}
int main()
{
	char s[11];
	root=new Node;
	Init(root);
	while(gets(s),s[0]!='\0'){
		Insert(s);
	}
	while(gets(s)){
		int ans=Search(s);
		cout<<ans<<endl;
	}
	Freedom(root);
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics