题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=397#problem/H

题意很明确,就是利用字典树查找,字典树看的半懂,自己模拟了一下,不对的地方可能比较多,希望指点。

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node//定义相应结构体
{
char number;
struct node *left,*right;
}nod;
nod root;
int sum=0;
void initroot()//初始化根节点
{
root.left=NULL;
root.right=NULL;
}
void f(nod *p,nod *q)
{
nod *t,*r,*g;
r=p;
g=q;
if(r!=NULL)
{
t=(*r).right;
r=(*r).left;
f(r,t);
}
if(g!=NULL)
{
t=(*g).left;
g=(*g).right;
f(t,g);
}
if(p==NULL&&q==NULL)
sum++;
}
void tree(char *word)//建树
{
int n=strlen(word),flag=0,i;
nod *p,*q,*r;
r=&(root);
p=root.left;
q=root.right;
for(i=0;i<n;i++)
{
if(word[i]==’0′)
{
if(p!=NULL)
{
r=p;
q=(*p).right;
p=(*p).left;
}
else
{
p=(nod*)malloc(sizeof(nod));
(*r).left=p;
r=p;
p->number=word[i];
p->left=NULL;
p->right=NULL;
q=p->right;
p=p->left;
flag=1;
}
}
if(word[i]==’1′)
{
if(q!=NULL)
{
r=q;
p=(*q).left;
q=(*q).right;
}
else
{
q=(nod*)malloc(sizeof(nod));
(*r).right=q;
r=q;
q->number=word[i];
q->left=NULL;
q->right=NULL;
p=q->left;
q=q->right;
flag=1;
}
}
}
}
int main()
{
char word[50];
int k=0,sd=0;
memset(word,0,sizeof(word));
while(scanf(“%s”,word)!=EOF)
{
if(word[0]==’9′)
{ sd++;
f(root.left,root.right);
if(k==sum)
printf(“Set %d is immediately decodable\n”,sd);
else
printf(“Set %d is not immediately decodable\n”,sd);
sum=0;
k=0;
initroot();
}
else{
k++;
tree(word);
}
memset(word,0,sizeof(word));
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation