Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

uva644--String

来源: huzhengnan 分享至:

字典树过的第一题,感觉得到自己在进步

//#define LOCAL
#include <stdio.h>
#include <string.h>

#define MAXN 20 + 10

char str[MAXN]; 

const int sonsum = 2;
struct Trie
{
	bool terminal;
	struct Trie* son[2];
};

Trie* newTrie();
bool Insert(Trie *, char *, int);

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	int i;
	int temp;
	int cases = 1;
	Trie* root = new Trie;
	char ch = '\0';
	bool flag;
	root->terminal = false;
 	for(i = 0; i < sonsum; i++)  
  		root->son[i] = NULL;  
	while(~scanf("%s", str))
	{
		// 算法主体
		if(~strcmp(str, "9"))
		{
			printf("Set %d is immediately decodable\n", cases);
			root = new Trie;
			root->terminal = false;
 			for(i = 0; i < sonsum; i++)  
  				root->son[i] = NULL;
			cases++;
			flag = false;
		}
		else
		{
			flag = Insert(root, str, strlen(str));
			if(flag)
			{
				ch = '\0';
				while(ch != '9')// 如果插入时经过了终止符||插入的字符串被完全覆盖 
					ch = getchar();
				getchar(); // 除掉回车符 
				root = new Trie;
				root->terminal = false;
 				for(i = 0; i < sonsum; i++)  
  					root->son[i] = NULL;
				printf("Set %d is not immediately decodable\n", cases);
				cases++;
				flag = false;
			}	
		}
		
	}
	return 0;
}


Trie *NewTrie()// Create a new node  
{  
    Trie *temp = new Trie;    
    temp->terminal = false;  
    for(int i = 0; i < sonsum; i++)  
        temp->son[i] = NULL;  
    return temp;  
}  

bool Insert(Trie *pnt,char *s, int len)// insert a new word to Trie tree  
{  
	bool flag = true;
    Trie *temp = pnt;
	
    for(int i = 0; i < len; i++)  
    {    
 		if(temp->terminal)
			return true;
    	if(temp->son[s[i] - '0'] == NULL)
		{
			temp->son[s[i] - '0'] = NewTrie();
			flag = false;
		} 
  		temp = temp->son[s[i] - '0'];
    }  
    temp->terminal = true;
	return flag;  
} 



Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
相关文章列表:
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史