以現在的生產力，是做不到一天一篇博客了。這題給我難得不行了，花了兩天時間在PAT上還有測試點1沒過，先寫上吧。記錄幾個做題中的難點：1、本來比較WPL那塊我是想用一個函數實現的，無奈我對傳字符串數組無可奈何；2、實在是水平還不夠，做題基本上都是要各種參考，當然以課件（網易雲課堂《數據結構》（陳越，何欽銘））中給的方法為主，可是呢，關於ElementType的類型我一直確定不下來，最後還是參考了園友糙哥（http://www.cnblogs.com/liangchao/p/4286598.html#3158189）的博客；3、關於如何判斷是否為前綴碼的方法，我是用的最暴力的一一對比，不知如何能更好的實現。好了，具體的題目及測試點1未過的代碼實現如下
1 /*
2 Name:
3 Copyright:
4 Author:
5 Date: 07/04/15 11:05
6 Description:
7 In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as {'a'=0, 'x'=10, 'u'=110, 'z'=111}, or in another way as {'a'=1, 'x'=01, 'u'=001, 'z'=000}, both compress the string into 14 bits. Another set of code can be given as {'a'=0, 'x'=11, 'u'=100, 'z'=101}, but {'a'=0, 'x'=01, 'u'=011, 'z'=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.
8
9 Input Specification:
10
11 Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:
12
13 c[1] f[1] c[2] f[2] ... c[N] f[N]
14 where c[i] is a character chosen from {'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (<=1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:
15
16 c[i] code[i]
17 where c[i] is the i-th character and code[i] is a string of '0's and '1's.
18
19 Output Specification:
20
21 For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not.
22
23 Sample Input:
24 7
25 A 1 B 1 C 1 D 3 E 3 F 6 G 6
26 4
27 A 00000
28 B 00001
29 C 0001
30 D 001
31 E 01
32 F 10
33 G 11
34 A 01010
35 B 01011
36 C 0100
37 D 011
38 E 10
39 F 11
40 G 00
41 A 000
42 B 001
43 C 010
44 D 011
45 E 100
46 F 101
47 G 110
48 A 00000
49 B 00001
50 C 0001
51 D 001
52 E 00
53 F 10
54 G 11
55 Sample Output:
56 Yes
57 Yes
58 No
59 No
60 */
61 #include <stdio.h>
62 #include <stdlib.h>
63 #include <string.h>
64
65 #define MinData 0
66
67 typedef struct TreeNode
68 {
69 int Weight;
70 struct TreeNode * Left, * Right;
71 }HuffmanTree, * pHuffmanTree;
72 typedef struct HeapStruct
73 {
74 pHuffmanTree Elements;
75 int Size;
76 int Capacity;
77 }MinHeap, * pMinHeap;
78
79 pMinHeap Create(int MaxSize);
80 void Insert(pMinHeap pH, HuffmanTree item);
81 pHuffmanTree Huffman(pMinHeap pH);
82 pHuffmanTree DeleteMin(pMinHeap pH);
83 int getWPL(pHuffmanTree pT, int layer, int WPL);
84
85 int main()
86 {
87 // freopen("in.txt", "r", stdin); // for test
88 int N, i; // get input
89 scanf("%d", &N);
90 int a[N];
91 char ch;
92 for(i = 0; i < N; i++)
93 {
94 getchar();
95 scanf("%c", &ch);
96 scanf("%d",&a[i]);
97 }
98
99 int WPL = 0; // build min-heap and Huffman tree
100 pMinHeap pH;
101 HuffmanTree T;
102 pH = Create(N);
103 for(i = 0; i < N; i++)
104 {
105 T.Weight = a[i];
106 T.Left = NULL;
107 T.Right = NULL;
108 Insert(pH, T);
109 }
110 pHuffmanTree pT;
111 pT = Huffman(pH);
112
113 WPL = getWPL(pT, 0, WPL); // compare WPL
114 int M, j, k;
115 scanf("%d", &M);
116 int w[M], flag[M];
117 char s[N][N + 2];
118 for(i = 0; i < M; i++)
119 {
120 w[i] = 0;
121 flag[i] = 0;
122 for(j = 0; j < N; j++)
123 {
124 getchar();
125 scanf("%c", &ch);
126 scanf("%s", s[j]);
127 w[i] += strlen(s[j]) * a[j];
128 }
129 if(w[i] == WPL)
130 {
131 flag[i] = 1;
132 for(j = 0; j < N; j++)
133 {
134 for(k = j + 1; k < N; k++)
135 {
136 if(strlen(s[j]) != strlen(s[k]))
137 {
138 if(strlen(s[j]) >strlen(s[k]))
139 if(strstr(s[j], s[k]) == s[j])
140 {
141 flag[i] = 0;
142 break;
143 }
144 else
145 if(strstr(s[k], s[j]) == s[k])
146 {
147 flag[i] = 0;
148 break;
149 }
150 }
151 }
152 }
153 }
154 }
155
156 for(i = 0; i < M; i++)
157 {
158 if(flag[i])
159 printf("Yes\n");
160 else
161 printf("No\n");
162 }
163 // fclose(stdin); // for test
164 return 0;
165 }
166
167 pMinHeap Create(int MaxSize)
168 {
169 pMinHeap pH = (pMinHeap)malloc(sizeof(MinHeap));
170 pH->Elements = (pHuffmanTree)malloc((MaxSize + 1) * sizeof(HuffmanTree));
171 pH->Size = 0;
172 pH->Capacity = MaxSize;
173 pH->Elements[0].Weight = MinData;
174
175 return pH;
176 }
177
178 void Insert(pMinHeap pH, HuffmanTree item)
179 {
180 int i;
181
182 i = ++pH->Size;
183 for(; pH->Elements[i / 2].Weight > item.Weight; i /= 2)
184 pH->Elements[i] = pH->Elements[i / 2];
185 pH->Elements[i] = item;
186 }
187
188 pHuffmanTree Huffman(pMinHeap pH)
189 {
190 int i;
191 pHuffmanTree pT;
192
193 for(i = 1; i < pH->Capacity; i++)
194 {
195 pT = (pHuffmanTree)malloc(sizeof(HuffmanTree));
196 pT->Left = DeleteMin(pH);
197 pT->Right = DeleteMin(pH);
198 pT->Weight = pT->Left->Weight + pT->Right->Weight;
199 Insert(pH, *pT);
200 }
201 pT = DeleteMin(pH);
202
203 return pT;
204 }
205
206 pHuffmanTree DeleteMin(pMinHeap pH)
207 {
208 int Parent, Child;
209 pHuffmanTree pMinItem;
210 HuffmanTree temp;
211
212 pMinItem = (pHuffmanTree)malloc(sizeof(HuffmanTree));
213 *pMinItem = pH->Elements[1];
214 temp = pH->Elements[pH->Size--];
215 for(Parent = 1; Parent * 2 <= pH->Size; Parent = Child)
216 {
217 Child = Parent * 2;
218 if((Child != pH->Size) && (pH->Elements[Child].Weight > pH->Elements[Child + 1].Weight))
219 Child++;
220 if(temp.Weight <= pH->Elements[Child].Weight)
221 break;
222 else
223 pH->Elements[Parent] = pH->Elements[Child];
224 }
225 pH->Elements[Parent] = temp;
226
227 return pMinItem;
228 }
229
230 int getWPL(pHuffmanTree pT, int layer, int WPL)
231 {
232 if(pT->Left == NULL && pT->Right == NULL)
233 WPL += layer * pT->Weight;
234 else
235 {
236 WPL = getWPL(pT->Left, layer + 1, WPL);
237 WPL = getWPL(pT->Right, layer + 1, WPL);
238 }
239
240 return WPL;
241 }
