首页 > 代码库 > hdu1305Immediate Decodability(字典树)
hdu1305Immediate Decodability(字典树)
这题看是否
这题能A是侥幸,解决的办法是先存一下输入的字符串,进行排序。
Examples: Assume an alphabet that has symbols {A, B, C, D}
The following code is immediately decodable: A:01 B:10 C:0010 D:0000
but this one is not: A:01 B:10 C:010 D:0000 (Note that A is a prefix of C)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef struct Node
{
struct Node *next[2];
int flag;
}Node,*Tree;
int flag1;
void Creat(Tree &T)
{
T=(Node *)malloc(sizeof(Node));
T->flag=0;
for(int i=0;i<2;i++)
T->next[i]=NULL;
}
void insert(Tree &T,char *s)
{
Tree p=T;
int t;
int l=strlen(s);
for(int i=0;i<l;i++)
{
t=s[i]-‘0‘;
if(p->next[t]==NULL)
Creat(p->next[t]);
p=p->next[t];
if(p->flag>0)
flag1=0;
}
p->flag++;
}
void D(Tree p)
{
for(int i=0;i<2;i++)
{
if(p->next[i]!=NULL)
D(p->next[i]);
}
free(p);
}
int main()
{
char a[30];
int kk=0;
Tree T;
while(scanf("%s%*c",a)!=EOF)
{
Creat(T);
kk++;
flag1=1;
insert(T,a);
while(scanf("%s",a)!=EOF)
{
if(strcmp(a,"9")==0)
break;
insert(T,a);
}
if(flag1)
printf("Set %d is immediately decodable\n",kk);
else printf("Set %d is not immediately decodable\n",kk);
D(T);
}
return 0;
}