C + + implementation of Huffman coding and decoding: building Huffman tree, coding and decoding Huffman

Recently completed the course design of data structure, and was assigned the title of Huffman coding and decoding. Now share your achievements in this blog.

When I was designing, I referred to the algorithm and code of many teachers and predecessors on the Internet, and thanked them! Their achievements have given me a lot of inspiration and help. In addition, there are many imperfections in their finished products, and we welcome criticism and correction.

Subject: Huffman coding and decoding C + + code implementation

(1) Count the frequency of characters in a message (assuming that the message contains only uppercase and lowercase English letters, as well as commas and point numbers);
(2) The Huffman tree is established by taking the frequency of characters as the weight, Huffman coding is carried out, and the coding result of each character is output;
(3) Huffman coding the message;
(4) The Huffman code of the message is decoded and the content of the corresponding message is output.

  1 #include <stdlib.h>
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 #include <string.h>
  5 #include <ctype.h>
  6 #define MAX 999999 //A maximum
  7 #define NUM 10
  8 
  9 //Store every node of Huffman tree
 10 typedef struct Node {
 11     char ch;
 12     int weight; //Weight
 13     int parent;
 14     int lchild,rchild;
 15 }HFNode;
 16 //Store each character and its Huffman code
 17 typedef struct {
 18     char ch;
 19     char code[NUM];
 20 }HFCharCode;
 21 
 22 HFNode HT[28*2-1]; //Huffman tree structure
 23 HFCharCode HCD[28]; //Huffman coding structure
 24 int LeafNum; //Number of leaf nodes
 25 int NodeNum; //All nodes
 26 char EnterStr[MAX]; //Incoming message to be encoded
 27 char EnterCode[MAX]; //Input ciphertext to be decoded
 28 char RealStr[MAX]; //Message after ciphertext decoding
 29 int AllWeight[28]; //Store weights for all 28 characters
 30 
 31 void Statistics();
 32 void CreateHFTree();
 33     void SelectMin(int &min1, int &min2);
 34 void CreateHFCode();
 35     void ReverseStr(char *str);
 36 void EncodeStr();
 37 void DecodeHFCode();
 38 
 39 int main() {
 40     printf("****** Huffman coding and decoding ******\n\n");
 41     printf("*** Enter a string ***\n");
 42     scanf("%s", EnterStr);
 43     getchar();
 44     Statistics();
 45     CreateHFTree();
 46     CreateHFCode();
 47     EncodeStr();
 48     printf("\n*** Enter what you want to decode ***\n");
 49     scanf("%s", EnterCode);
 50     getchar();
 51     DecodeHFCode();
 52     return 0;
 53 }
 54 
 55 //Count the weight of each character
 56 void Statistics() {
 57     int len = strlen(EnterStr);
 58     for(int i = 0; i <= 27; i++)
 59         AllWeight[i] = 0;
 60     for(int j = 0; j <= len - 1; j++) {
 61         if(isalpha(EnterStr[j])) {
 62             EnterStr[j] = tolower(EnterStr[j]);
 63             AllWeight[EnterStr[j]-'a']++;
 64         }
 65         else if((int)EnterStr[j] == 44)
 66             AllWeight[26]++;
 67         else if((int)EnterStr[j] == 46)
 68             AllWeight[27]++;
 69         else {
 70             printf("\n Input does not meet the requirements!\n\n");
 71             exit(-1);
 72         }
 73     }
 74     int i = 0, j = 0;
 75     for( ; i <= 25; i++) {
 76         if(AllWeight[i] != 0) {
 77                 HT[j].weight  = AllWeight[i];
 78                 HT[j].ch = i+'a';
 79                 j++;
 80         }
 81     }
 82     if(AllWeight[i] != 0) {
 83             HT[j].weight = AllWeight[i];
 84             HT[j].ch = ',';
 85             j++;
 86             i++;
 87     }
 88     if(AllWeight[i] != 0) {
 89             HT[j].weight = AllWeight[i];
 90             HT[j].ch = '.';
 91     }
 92     printf("\n*** Print the weight of each character ***\n");
 93     int n = 0;
 94     for(int i = 0; i <= 27; i++) {
 95         if(AllWeight[i] != 0) {
 96             n++;
 97             if(i <= 25)
 98                 putchar('a'+i);
 99             else if(i == 26)
100                 printf(",");
101             else
102                 printf(".");
103             printf(": %d\n", AllWeight[i]);
104         }
105     }
106     LeafNum = n;
107     NodeNum = 2*LeafNum-1;
108 }
109 
110 //Structure Huffman tree
111 void CreateHFTree() {
112     int i;
113     for(i = 0; i <= LeafNum-1; i++) {
114         HT[i].parent = -1;
115         HT[i].lchild = -1;
116         HT[i].rchild = -1;
117         HT[i].weight = HT[i].weight;
118     }
119     for(; i <= NodeNum-1; i++) {
120         HT[i].parent = -1;
121         HT[i].lchild = -1;
122         HT[i].rchild = -1;
123         HT[i].weight = MAX;
124     }
125     int min1, min2;
126     for(i = LeafNum; i <= NodeNum-1; i++) {
127         SelectMin(min1, min2);
128         HT[min1].parent = i;
129         HT[min2].parent = i;
130         HT[i].lchild = min1;
131         HT[i].rchild = min2;
132         HT[i].weight = HT[min1].weight + HT[min2].weight;
133     }
134     // printf("\n*** Print Huffman tree ***\n");
135     // for(int i = 0; i <= NodeNum-1; i++) {
136     //     printf("Serial number:%d character:%c Weight:%d parents:%d Left child:%d Right child:%d\n", i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
137     // }
138 }
139     //Find the sequence number of two binary trees with the least weight
140     void SelectMin(int &min1, int &min2) {
141         int i = 0;
142         int temp;
143         int wetmin1, wetmin2;
144         while(HT[i].parent != -1) 
145             i++;
146         wetmin1 = HT[i].weight;
147         min1 = i;
148         i++;
149         while(HT[i].parent != -1) 
150             i++;
151         wetmin2 = HT[i].weight;
152         min2 = i;
153         i++;
154         if(wetmin1 > wetmin2) {
155             temp = wetmin2;
156             wetmin2 = wetmin1;
157             wetmin1 = temp;
158             temp = min2;
159             min2 = min1;
160             min1 = temp;
161         }
162         for(; i <= NodeNum-1; i++) {
163             if(HT[i].weight < wetmin1 && HT[i].parent == -1) {
164                 wetmin2 = wetmin1;
165                 wetmin1 = HT[i].weight;
166                 min2 = min1;
167                 min1 = i;
168             } else if(HT[i].weight < wetmin2 && HT[i].parent == -1) {
169                 wetmin2 = HT[i].weight;
170                 min2 = i;
171             }
172         }
173     }
174 
175 //Carry out Huffman coding
176 void CreateHFCode() {
177     int i, j, len; 
178     for(i = 0; i <= LeafNum-1; i++) {  
179         len = 0;  
180         j = i;
181         HCD[i].ch = HT[j].ch;
182         while(HT[j].parent != -1) {  //Not the root node
183             if(HT[HT[j].parent].lchild == j) {  //It's the left child of the parents' node
184                 HCD[i].code[len++] = '0'+0;  //Add character 0
185             }else  //It's the right child
186                 HCD[i].code[len++] = '0'+1;  //Add character 1
187             j = HT[j].parent;  //Traverse up
188         }
189         HCD[i].code[len] = '\0'; //End of string 
190         ReverseStr(HCD[i].code); 
191     }
192     printf("\n*** Print the encoding for each character ***\n");
193     for(int i = 0; i <= LeafNum-1; i++)
194         printf("%c: %s\n", HT[i].ch, HCD[i].code);
195 }
196     //Invert a string  
197     void ReverseStr(char *str) {  
198         int i, j;  
199         char c;  
200         for(i = 0, j = strlen(str)-1; i < j; i++, j--) {  
201             c = str[i];  
202             str[i] = str[j];  
203             str[j] = c;  
204         }
205     }
206 
207 //Huffman code
208 void EncodeStr() {
209     int len = strlen(EnterStr);
210     printf("\n*** Coding results ***\n");
211     for(int i = 0; i <= len-1; i++) {
212         for(int j = 0; j <= LeafNum-1; j++) {
213             if(EnterStr[i] == HCD[j].ch)
214                 printf("%s", HCD[j].code);
215         }
216     }
217     printf("\n");
218 }
219 
220 //huffman decoding 
221 void DecodeHFCode() {
222     int k = NodeNum-1; //Root node No, Start with the last one
223     int len = 0, i = 0;  
224     while(EnterCode[i]) {  
225         if(EnterCode[i] == '0'+0)  
226             k = HT[k].lchild;  
227         else if(EnterCode[i] == '0'+1)  
228             k = HT[k].rchild;  
229         else {
230             printf("\n error! Ciphertext can only contain 1 and 0!\n\n");
231             exit(-1);
232         }  
233         if(HT[k].lchild == -1 && HT[k].rchild == -1) {  
234             RealStr[len++] = HT[k].ch;
235             k = NodeNum-1;
236         }  
237         i++;  
238     }
239     RealStr[len] = '\0';
240     if(k == NodeNum-1) {     
241         printf("\n*** Decoding results ***\n%s\n\n", RealStr);
242         exit(0);
243     }
244     printf("\n error! Some ciphertext cannot be decrypted!\n\n");
245     exit(-1);  
246 }

Tags: C++ encoding

Posted on Mon, 04 May 2020 21:59:45 -0700 by welsh_sponger