C++实现哈夫曼树

一、功能

1、根据输入的字符、字符出现频率构建哈夫曼树

2、翻译

①、字符->编码

②、编码->字符

③、报文->密码

④、破译密码

二、碰到的一些问题

1、如何读取空格?

①、读取含空格的字符串

1 while (1)
2             {
3                 getline(cin, message);
4                 if (message != "")
5                 {
6                     break;
7                 }
8             }

执行死循环,然后读取字符串,当字符串不为空时跳出死循环

②、读取单个空格字符

 1 while (1)
 2             {
 3                 string pankong = "";
 4                 getline(cin, pankong);
 5                 zf = pankong[0];
 6                 if (zf != '\0')
 7                 {
 8                     break;
 9                 }
10             }

2、好像其他并没有什么值得一提的问题

三、代码

1、主函数

 1 #include<iostream>
 2 #include"Huffman_Tree.h"
 3 #include<string>
 4 using namespace std;
 5 int main()
 6 {
 7     bool flag = true;
 8     char zf;
 9     string message;
10     Huffman huffman;
11     while (flag)
12     {
13         cout << "1、输出哈夫曼树的基本结构" << endl;//ok
14         cout << "2、输出字符所对应的哈夫曼编码" << endl;//ok
15         cout << "3、将报文翻译成密码" << endl;//ok
16         cout << "4、解译密码" << endl;//ok
17         cout << "5、退出" << endl;
18         cout << "请选择你想要进行的操作:";
19         int select;
20         cin >> select;
21         switch (select)
22         {
23         case 1:
24             cout << "哈夫曼树为: " << endl;
25             huffman.Print();
26             break;
27         case 2:
28             cout << "请输入字符: ";
29             while (1)
30             {
31                 string pankong = "";
32                 getline(cin, pankong);
33                 zf = pankong[0];
34                 if (zf != '\0')
35                 {
36                     break;
37                 }
38             }
39             cout << endl << "该字符所对应的哈夫曼编码为: " << huffman.Print_cypher(zf) << endl;
40             break;
41         case 3:
42             cout << "请输入需要翻译的报文: ";
43             while (1)
44             {
45                 getline(cin, message);
46                 if (message != "")
47                 {
48                     break;
49                 }
50             }
51             cout << endl << "翻译后的密码为: " << huffman.inverse_translate(message) << endl;
52             break;
53         case 4:
54             cout << "请输入你需要翻译的密码: ";
55             cin >> message;
56             cout<< "解码后的报文为: " << huffman.translate(message) << endl;
57             break;
58         case 5:
59             flag = false;
60             break;
61         default:
62             cout << "error!" << endl;
63         }
64         cout << "====================================" << endl;
65     }
66 }

2、头文件

  1 #pragma once
  2 #include<iostream>
  3 #include<string>
  4 using namespace std;
  5 
  6 #define N 27//字符个数
  7 
  8 bool zt[N*2-1];
  9 
 10 struct ElemType
 11 {
 12     int weight;//权值
 13     int parent = -1, lchild = -1, rchild = -1;//游标
 14     char character;//字符
 15     string cypher = "";
 16 };
 17 
 18 class Huffman
 19 {
 20 private:
 21     ElemType huffmanTree[N * 2 - 1];
 22     int number=N;//密码字符的个数
 23     void supArr();//完成表格
 24     int select();//选出最小权值并用状态数组标记
 25     int lookup(char a);//找字符在数组中的位置
 26     void code(char a);//制作a的密码
 27     void Make_cypher();//调用code制作N个字符的密码
 28 public:
 29     Huffman();//完成一系列初始化
 30     void Print();//打印表格
 31     string Print_cypher(char a);//打印a的密码
 32     string translate(string a);//翻译密码串a
 33     string inverse_translate(string a);//逆翻译密码串
 34 };
 35 string Huffman::inverse_translate(string a)
 36 {
 37     string tra;
 38     for (int i = 0; i < a.length(); i++)
 39     {
 40         int xb = lookup(a[i]);
 41         tra = tra + huffmanTree[xb].cypher;
 42     }
 43     return tra;
 44 }
 45 string Huffman::translate(string a)
 46 {
 47     string tra;//译文
 48     int xb = 2 * N - 2;
 49     for (int i = 0; i < a.length(); i++)
 50     {
 51         if (huffmanTree[xb].lchild != -1 && huffmanTree[xb].rchild != -1)
 52         {
 53             if (a[i] == '0')
 54             {
 55                 xb = huffmanTree[xb].lchild;
 56             }
 57             else
 58             {
 59                 xb = huffmanTree[xb].rchild;
 60             }
 61             if (huffmanTree[xb].lchild == -1)
 62             {
 63                 tra = tra + huffmanTree[xb].character;
 64                 xb = 2 * N - 2;
 65             }
 66         }
 67     }
 68     return tra;
 69 }
 70 string Huffman::Print_cypher(char a)
 71 {
 72     int xb=lookup(a);
 73     return huffmanTree[xb].cypher;
 74 }
 75 void Huffman::code(char a)
 76 {
 77     int xb = lookup(a);
 78     while(huffmanTree[xb].parent != -1)
 79     {
 80         if (huffmanTree[huffmanTree[xb].parent].lchild == xb)
 81         {
 82             huffmanTree[lookup(a)].cypher = "0" + huffmanTree[lookup(a)].cypher;
 83         }
 84         if (huffmanTree[huffmanTree[xb].parent].rchild == xb)
 85         {
 86             huffmanTree[lookup(a)].cypher = "1" + huffmanTree[lookup(a)].cypher;
 87         }
 88         xb = huffmanTree[xb].parent;
 89     }
 90 }
 91 void Huffman::Make_cypher()
 92 {
 93     for (int i = 0; i < N; i++)
 94     {
 95         code(huffmanTree[i].character);
 96     }
 97 }
 98 int Huffman::lookup(char a)
 99 {
100     for (int i = 0; i < N; i++)
101     {
102         if (huffmanTree[i].character == a)
103             return i;
104     }
105 }
106 void Huffman::Print()
107 {
108     cout << " " << "\t" << "weight" << "\t" << "parent" << "\t" << "lchild" << "\t" << "rchild" << "\t" << endl;
109     for (int i = 0; i < 2 * N - 1; i++)
110     {
111         cout << i << "\t" << huffmanTree[i].weight << "\t" << huffmanTree[i].parent << "\t" << huffmanTree[i].lchild << "\t" << huffmanTree[i].rchild << "\t" << endl;
112     }
113 }
114 void Huffman::supArr()//完成数组表
115 {
116     for (int i = N; i < 2 * N - 1; i++)
117     {
118         int xb1 = select();
119         int xb2 = select();
120         huffmanTree[i].weight = huffmanTree[xb1].weight + huffmanTree[xb2].weight;
121         huffmanTree[i].lchild = xb1; huffmanTree[i].rchild = xb2;
122         huffmanTree[xb1].parent = i; huffmanTree[xb2].parent = i;
123     }
124 }
125 int Huffman::select()//选出两个最小的权值
126 {
127     int min = 999;
128     int xb=6;
129     for (int i = 0; i < 2 * N - 1; i++)
130     {
131         if (huffmanTree[i].weight < min && zt[i] == false)
132         {
133             min = huffmanTree[i].weight;
134             xb = i;
135         }
136     }
137     zt[xb] = true;
138     return xb;
139 }
140 Huffman::Huffman()
141 {
142     for (int i = 0; i < 2 * N - 1; i++)
143     {
144         if (i < N)
145         {
146             cout << "请输入第" << i + 1 << "个字符:";
147             while (1)
148             {
149                 string pankong="";
150                 getline(cin, pankong);
151                 huffmanTree[i].character = pankong[0];
152                 if (huffmanTree[i].character!='\0')
153                 {
154                     break;
155                 }
156             }
157             /*if (i == 0)
158             {
159                 huffmanTree[i].character = ' ';
160             }
161             else
162             {
163                 cout << "请输入第" << i + 1 << "个字符:";
164                 cin >> huffmanTree[i].character;
165             }*/
166             cout << "请输入第" << i + 1 << "个字符的权值:";
167             cin >> huffmanTree[i].weight;
168         }
169         else
170         {
171             huffmanTree[i].weight = 999;//方便选出两个最小权值
172         }
173         zt[i] = false;//初始化
174     }
175     supArr();
176     Make_cypher();
177 }

 

上一篇:谓词演算的等价及蕴含公式(一)


下一篇:直线段的代码裁剪算法