首页 > 代码库 > poj 1056 Trie树判断哈夫曼编码是否合法
poj 1056 Trie树判断哈夫曼编码是否合法
理解了Trie树然后就能1A 其实估计这个题随便做做就能A掉,可能不需要高级数据。
先贴吉林大学的代码模板
/*==================================================*| Trie树(k叉) | INIT: init(); | 注: tree[i][tk]>0时表示单词存在, 当然也可赋予它更多含义; \*==================================================*/ const int tk = 26, tb = 'a'; // tk叉; 起始字母为tb; int top, tree[N][tk + 1]; // N: 最大结点个数 top: 第一层有多少节点 void init(){ top = 1; memset(tree[0], 0, sizeof(tree[0])); } int sear(char*s){ // 失败返回0 for(int rt = 0; rt = tree[rt][*s - tb]; ) if(*(++s) == 0) return tree[rt][tk]; //插入单词结束的时候 有这一句 tree[rt][tk] = Rank; return 0; } void Insert(char*s, int Rank = 1){ int rt, nxt; for(rt = 0; *s; rt = nxt, ++s) { nxt = tree[rt][*s - tb]; if(0 == nxt) {//没被使用时插入 tree[rt][*s - tb] = nxt = top; memset(tree[top], 0, sizeof(tree[top])); top++; } } tree[rt][tk] = Rank;//1表示存在0表示不存在,也可以赋予其其他含义 } void delt(char*s){ // 只做标记, 假定s一定存在 int rt = 0; for( ; *s; ++s) rt = tree[rt][*s - tb];//tree的值本身指向下一个节点 tree[rt][tk]=0; } int prefix(char*s){ // 最长前缀 int rt = 0, lv; for(lv = 0; *s; ++s, ++lv) { rt = tree[rt][*s - tb]; if(rt == 0) break; } return lv; }
我把模板改掉然后A了poj1056
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int N = 2000+10; char str[N]; const int tk = 26, tb = '0'-5; // tk叉; 起始字母为tb; int top, tree[N][tk + 1]; // N: 最大结点个数 top: 第一层有多少节点 void init(){ top = 1; memset(tree[0], 0, sizeof(tree[0])); } int Insert(char*s, int Rank = -2){//-2表示一个单词的结尾 int rt, nxt; for(rt = 0; *s; rt = nxt, ++s) { nxt = tree[rt][*s - tb]; if(tree[rt][tk]<0)return -2; //这是我改的地方,原来的模板,在 tree[rt][tk] = Rank;表示结束(相当于空字符) //那么每走到一步查看是不是以前的单词到这里是结尾,如果是的话,说明这之前的都匹配了,当然就不合法 if(0 == nxt) {//没被使用时插入 tree[rt][*s - tb] = nxt = top; memset(tree[top], 0, sizeof(tree[top])); top++; } } tree[rt][tk] = Rank;//1表示存在0表示不存在,也可以赋予其其他含义 return 0; } int main() { int ans=0,cnt=1,flag=0; init(); while(~scanf("%s",str) && strcmp(str,"9")) { ans=flag=0; ans=Insert(str); if(ans<0)flag=1; while(scanf("%s",str) && strcmp(str,"9")) { ans=Insert(str); if(ans<0)flag=1; } if(flag){printf("Set %d is not immediately decodable\n",cnt++);} else { printf("Set %d is immediately decodable\n",cnt++); } init(); } }
其实我的代码这组数据就过不了
10
010
01
0000
9
题中好像没说已经按长度排过序了,但是测试数据肯定是排序过的
应该加上判断,如果*(s+1)==0 && nxt!=0,那么说明已经有比现在正在插入的长的字符串,当前正在插的字符串是已经插的前缀。。。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。