题目描述:
一个哈夫曼树,给出一个字符串以及编码,要求确定哈夫曼树
如果无解或者多解,输出MULTIPLE TABLES
解法:
同pku1261,那题我写了详细的报告,
http://www.cppblog.com/yzhw/archive/2011/01/11/138368.aspx代码:
1
# include <cstdio>
2
# include <cstring>
3
# include <stack>
4
using namespace std;
5
struct node
6

{
7
int count;
8
node *c[2];
9
node *pre;
10
char end;
11
node()
12
{
13
count=0;
14
c[0]=c[1]=pre=NULL;
15
end=0;
16
}
17
};
18
node *head=NULL,*ans[27],*res[27];
19
char str[1024],code[1024];
20
int count,total;
21
bool used[27],hasfind;
22
void clear(node *p=head)
23

{
24
if(!p) return;
25
clear(p->c[0]);
26
clear(p->c[1]);
27
delete p;
28
}
29
void init()
30

{
31
clear();
32
head=new node();
33
head->count=1;
34
memset(used,0,sizeof(used));
35
memset(ans,0,sizeof(ans));
36
count=2;
37
hasfind=false;
38
}
39
bool solve(int p1,int p2,node *p=head)
40

{
41
if(count>total||p->end) return 0;
42
else if(str[p1]=='\0'&&code[p2]=='\0')
43
{
44
if(!hasfind)
45
{
46
hasfind=true;
47
memcpy(res,ans,sizeof(ans));
48
return 0;
49
}
50
else return 1;
51
}
52
else if(str[p1]=='\0') return 0;
53
else if(str[p1]==' '&&ans[26]||str[p1]!=' '&&ans[str[p1]-'A'])
54
{
55
stack<int> s;
56
node *t=ans[str[p1]==' '?26:str[p1]-'A'];
57
while(t->pre)
58
{
59
s.push(t->pre->c[0]==t?0:1);
60
t=t->pre;
61
}
62
for(;code[p2]!='\0'&&!s.empty();p2++)
63
if(code[p2]==s.top()+48)
64
s.pop();
65
else return 0;
66
if(!s.empty()) return 0;
67
else return solve(p1+1,p2);
68
}
69
else
70
{
71
p->count++;
72
if(p->count==1)
73
{
74
p->end=str[p1];
75
ans[str[p1]==' '?26:str[p1]-'A']=p;
76
if(solve(p1+1,p2)) return 1;
77
p->end=0;
78
ans[str[p1]==' '?26:str[p1]-'A']=NULL;
79
}
80
if(code[p2]=='\0')
81
{
82
p->count--;
83
return 0;
84
}
85
if(p->count==1)
86
count++;
87
if(p->c[code[p2]-'0']==NULL)
88
{
89
p->c[code[p2]-'0']=new node();
90
p->c[code[p2]-'0']->pre=p;
91
}
92
if(solve(p1,p2+1,p->c[code[p2]-'0'])) return 1;
93
if(p->count==1)
94
count--;
95
p->count--;
96
return 0;
97
98
}
99
}
100
int main()
101

{
102
//freopen("ans.txt","w",stdout);
103
int test;
104
scanf("%d",&test);
105
getchar();
106
for(int t=1;t<=test;t++)
107
{
108
init();
109
gets(str);
110
gets(code);
111
total=0;
112
for(int i=0;str[i]!='\0';i++)
113
used[str[i]==' '?26:str[i]-'A']=true;
114
for(int i=0;i<27;i++)
115
total+=used[i];
116
printf("DATASET #%d\n",t);
117
if(solve(0,0)||!hasfind) printf("MULTIPLE TABLES\n");
118
else if(hasfind)
119
{
120
if(used[26])
121
{
122
printf(" = ");
123
stack<int> s;
124
while(res[26]->pre)
125
{
126
s.push(res[26]==res[26]->pre->c[0]?0:1);
127
res[26]=res[26]->pre;
128
}
129
while(!s.empty())
130
{
131
printf("%d",s.top());
132
s.pop();
133
}
134
printf("\n");
135
}
136
137
for(int i=0;i<26;i++)
138
if(used[i])
139
{
140
printf("%c = ",i+65);
141
stack<int> s;
142
while(res[i]->pre)
143
{
144
s.push(res[i]==res[i]->pre->c[0]?0:1);
145
res[i]=res[i]->pre;
146
}
147
while(!s.empty())
148
{
149
printf("%d",s.top());
150
s.pop();
151
}
152
printf("\n");
153
}
154
}
155
156
}
157
return 0;
158
}