pku1223 DEHUFF 哈夫曼樹確定,PKU1261簡化版
題目描述:一個哈夫曼樹,給出一個字符串以及編碼,要求確定哈夫曼樹
如果無解或者多解,輸出MULTIPLE TABLES
解法:
同pku1261,那題我寫了詳細的報告,http://www.shnenglu.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
}

2

3

4

5

6



7

8

9

10

11

12



13

14

15

16

17

18

19

20

21

22

23



24

25

26

27

28

29

30



31

32

33

34

35

36

37

38

39

40



41

42

43



44

45



46

47

48

49

50

51

52

53

54



55

56

57

58



59

60

61

62

63

64

65

66

67

68

69

70



71

72

73



74

75

76

77

78

79

80

81



82

83

84

85

86

87

88



89

90

91

92

93

94

95

96

97

98

99

100

101



102

103

104

105

106

107



108

109

110

111

112

113

114

115

116

117

118

119



120

121



122

123

124

125



126

127

128

129

130



131

132

133

134

135

136

137

138

139



140

141

142

143



144

145

146

147

148



149

150

151

152

153

154

155

156

157

158

posted on 2011-01-16 14:01 yzhw 閱讀(238) 評論(0) 編輯 收藏 引用 所屬分類: search 、data struct