pta 编程题14 Huffman Codes

其它pta数据结构编程题请参见：pta

题目

题目给出一组字母和每个字母的频数，因为哈夫曼编码不唯一，然后给出几组编码，因为哈夫曼编码不唯一，所以让你判断这些编码是否符合是哈夫曼编码的一种。

解题思路：

1、构造哈夫曼树，并求出总代价COST，即各个字母的频数乘以编码长度的和。

2、对于题目给出的每一组编码，判断是否符合哈夫曼编码，即这组编码是否为前缀码，同时代价cost是否等于计算出的哈夫曼树的代价COST。

判断一组编码是否为前缀码的方法:

将这些编码逐个的添加到哈夫曼树中，对于每一个编码字符串，字符串中的每一个字符也逐个扫描，如果是0则向左构造树，1则向右构造树。如果已扫描到某节点为叶子节点但字符串还未结束，或者字符串已扫描结束但还当前节点非空，那么就不是前缀码。

需要注意的点：

最小堆数组中的元素类型ElementType为HuffmanTree型。

  1 #include <iostream>
  2 #include <string>
  3 #include <map>
  4 using namespace std;
  5 
  6 /*----------哈夫曼树定义---------*/
  7 typedef struct HuffmanNode *HuffmanTree;
  8 struct HuffmanNode
  9 {
 10     int weight;
 11     HuffmanTree left, right;
 12 };
 13 /*----------最小堆定义-----------*/
 14 #define minData -1;
 15 typedef HuffmanTree ElementType;
 16 typedef struct HeapNode* minHeap;
 17 struct HeapNode
 18 {
 19     ElementType *data;
 20     int size;
 21 };
 22 /*----------最小堆相关操作--------*/
 23 minHeap buildHeap(int N);
 24 void percDown(minHeap H, int p);
 25 void insert(minHeap H, HuffmanTree x);
 26 HuffmanTree deleteMin(minHeap H);
 27 /*----------哈夫曼树相关操作------*/
 28 HuffmanTree huffman(int N);
 29 HuffmanTree initHuffmanNode(int weight);
 30 bool cmp(HuffmanTree a, HuffmanTree b);
 31 void getLength(HuffmanTree T, int& total, int length);
 32 /*----------其它操作--------------*/
 33 bool valid(int N, int total);
 34 HuffmanTree insertHuffman(HuffmanTree T, string s, int n, bool& judge);
 35 map<string, int> mapp;
 36 /*--------------------------------*/
 37 
 38 int main()
 39 {
 40     int N, M, i;
 41     cin >> N;
 42     HuffmanTree T = huffman(N); //构造哈夫曼树
 43     int total = 0; //总哈夫曼编码长度
 44     getLength(T, total, 0);
 45     cin >> M;
 46     for (i = 0; i < M; i++)
 47     {
 48         if (valid(N, total)) cout << "Yes" << endl;
 49         else cout << "No" << endl;
 50     }
 51     return 0;
 52 }
 53 
 54 HuffmanTree initHuffmanNode(int weight)
 55 {
 56     HuffmanTree T = new HuffmanNode;
 57     T->weight = weight;
 58     T->left = T->right = NULL;
 59     return T;
 60 }
 61 
 62 minHeap buildHeap(int N)
 63 {
 64     minHeap H = new HeapNode;
 65     H->data = new ElementType[N + 1];
 66     H->size = 0;
 67     H->data[0] = initHuffmanNode(-1);//哨兵
 68 
 69     string c;
 70     int i, t;
 71     for (i = 1; i <= N; i++)
 72     {
 73         cin >> c >> t;
 74         mapp[c] = t;
 75         H->data[i] = initHuffmanNode(t);
 76     }
 77     H->size = N;
 78 
 79     /* 调整堆中的元素 */
 80     for (i = H->size / 2; i > 0; i--)
 81         percDown(H, i);
 82     return H;
 83 }
 84 
 85 void percDown(minHeap H, int p)
 86 { /* 下滤：将H中以H->Data[p]为根的子堆调整为最小堆 */
 87     int parent, child;
 88     ElementType X = H->data[p];
 89     for (parent = p; parent * 2 <= H->size; parent = child)
 90     {
 91         child = parent * 2;
 92         if (child != H->size && cmp(H->data[child], H->data[child + 1]))
 93             child++;
 94         if (!cmp(X, H->data[child])) break;
 95         else
 96             H->data[parent] = H->data[child];
 97     }
 98     H->data[parent] = X;
 99 }
100 
101 void insert(minHeap H, HuffmanTree x)
102 {
103     int i;
104     for (i = ++H->size; cmp(H->data[i / 2], x); i /= 2)
105         H->data[i] = H->data[i / 2];
106     H->data[i] = x;
107 }
108 
109 HuffmanTree deleteMin(minHeap H)
110 {
111     HuffmanTree minItem = H->data[1];
112     ElementType x = H->data[H->size--];
113     int parent, child;
114     for (parent = 1; parent * 2 <= H->size; parent = child)
115     {
116         child = parent * 2;
117         if (child != H->size && cmp(H->data[child], H->data[child + 1]))
118             child++; //将两个子节点中较小的一个和x比较
119         if (!cmp(x, H->data[child])) break;
120         else
121             H->data[parent] = H->data[child];
122     }
123     H->data[parent] = x;
124     return minItem;
125 }
126 
127 HuffmanTree huffman(int N)
128 {
129     HuffmanTree T;
130     minHeap H = buildHeap(N);
131 
132     while (H->size > 1)
133     {
134         T = new HuffmanNode;
135         T->left = deleteMin(H);
136         T->right = deleteMin(H);
137         T->weight = T->left->weight + T->right->weight;
138         insert(H, T);
139     }
140     T = deleteMin(H);
141     return T;
142 }
143 
144 bool cmp(HuffmanTree a, HuffmanTree b)
145 {
146     return a->weight > b->weight;
147 }
148 
149 void getLength(HuffmanTree T, int& total, int length)
150 {
151     if (!T) return;
152     if (!T->left && !T->right) //叶子节点
153         total += length * T->weight;
154     getLength(T->left, total, length + 1);
155     getLength(T->right, total, length + 1);
156 }
157 
158 bool valid(int N, int total)
159 {
160     string c, s;
161     bool isValid = true;
162     int i, sum = 0;
163     HuffmanTree T = initHuffmanNode(0);
164     for (i = 0; i < N; i++)
165     {
166         cin >> c >> s;
167         sum += s.size() * mapp[c];
168         if (!isValid) continue;
169         if (s[0] == '0')
170             T->left = insertHuffman(T->left, s, 0, isValid);
171         else
172             T->right = insertHuffman(T->right, s, 0, isValid);
173     }
174     if (!isValid || sum != total) return false;
175     else return true;
176 }
177 
178 HuffmanTree insertHuffman(HuffmanTree T, string s, int n, bool& judge)
179 {
180     if (!T)
181         T = initHuffmanNode(0);
182     else
183     {
184 
185         if (n + 1 == s.size()) judge = false;//当前节点非空且为字符串最后一个字符
186         else if (!T->left && !T->right)//当前节点为叶子节点且字符串还未结束
187             judge = false;
188     }
189     if (n + 1 < s.size())
190     {
191         if (s[n + 1] == '0')
192             T->left = insertHuffman(T->left, s, n + 1, judge);
193         else
194             T->right = insertHuffman(T->right, s, n + 1, judge);
195     }
196     return T;
197 }