pta 编程题14 Huffman Codes-白红宇

pta 编程题14 Huffman Codes

阅读量：5037 次

发布时间：2019-06-12

本文共 5642 字，大约阅读时间需要 18 分钟。

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

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

解题思路：

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

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

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

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

需要注意的点：

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

1 #include 
     
        2 #include 
      
         3 #include 
         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
        
          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         else121             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         else172             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     else183     {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         else194             T->right = insertHuffman(T->right, s, n + 1, judge);195     }196     return T;197 }

转载于:https://www.cnblogs.com/lxc1910/p/8908288.html

你可能感兴趣的文章