78 /*-----------创建工作---------------------------*/
79     int s1，s2;
80     for (int i = n + 1; i <= m; ++i)
81     {//通过n-1次的选择，删除，合并来构造哈夫曼树
82         Select(HT， i - 1， s1， s2);
83         /*cout << HT[s1].weight << " ， " << HT[s2].weight << endl;*/
84         /*将s1，s2的双亲域由0改为i
85         (相当于把这两个结点删除了，这两个结点不再参与Select()函数)*/
86         HT[s1].parent = i;
87         HT[s2].parent = i;
88         //s1，与s2分别作为i的左右孩子
89         HT[i].lchild = s1;
90         HT[i].rchild = s2;
91         //结点i的权值为s1，s2权值之和
92         HT[i].weight = HT[s1].weight + HT[s2].weight;
93     }
94 }
95
96 //从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
97 void CreatHuffmanCode(HuffmanTree HT， HuffmanCode &HC， int n)
98 {
99     HC = new char*[n + 1];//分配储存n个字符编码的编码表空间
100     char *cd = new char[n];//分配临时存储字符编码的动态空间
101     cd[n - 1] = '';//编码结束符
102     for (int i = 1; i <= n; i++)//逐个求字符编码
103     {
104         int start = n - 1;//start 开始指向后，即编码结束符位置
105         int c = i;
106         int f = HT[c].parent;//f指向结点c的双亲
107         while (f != 0)//从叶子结点开始回溯，直到根结点
108         {
109             --start;//回溯一次，start向前指向一个位置
110             if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子，则cd[start] = 0;
111             else cd[start] = '1';//否则c是f的右孩子，cd[start] = 1
112             c = f;
113             f = HT[f].parent;//继续向上回溯
114         }
115         HC[i] = new char[n - start];//为第i个字符编码分配空间
116         strcpy(HC[i]， &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
117     }
118     delete cd;
119 }
120
121 //哈夫曼译码
122 void TranCode(HuffmanTree HT，char a[]，char zf[]，char b[]，int n)
123 {
124     /*
125     HT是已经创建好的哈夫曼树
126     a[]用来传入二进制编码
127     b[]用来记录译出的字符
128     zf[]是与哈夫曼树的叶子对应的字符（叶子下标与字符下标对应）
129     n是字符个数，相当于zf[]数组得长度
130     */
131
132     int q = 2*n-1;//q初始化为根结点的下标
133     int k = 0;//记录存储译出字符数组的下标
134     int i = 0;
135     for (i = 0; a[i] != '';i++)
136     {//for循环结束条件是读入的字符是结束符（二进制编码）
137         //此代码块用来判断读入的二进制字符是0还是1
138         if (a[i] == '0')
139         {/*读入0，把根结点(HT[q])的左孩子的下标值赋给q
140          下次循环的时候把HT[q]的左孩子作为新的根结点*/
141             q = HT[q].lchild;
142         }
143         else if (a[i] == '1')
144         {
145             q = HT[q].rchild;
146         }
147         //此代码块用来判断HT[q]是否为叶子结点
148         if (HT[q].lchild == 0 && HT[q].rchild == 0)
149         {/*是叶子结点，说明已经译出一个字符
150         该字符的下标是找到的叶子结点的下标*/
151             b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]
152             q = 2 * n - 1;//初始化q为根结点的下标
153             //继续译下一个字符的时候从哈夫曼树的根结点开始
154         }
155     }
156     /*译码完成之后，用来记录译出字符的数组由于没有结束符输出的
157     时候回报错，故紧接着把一个结束符加到数组后*/
158     b[k] = '';
159 }
160 //菜单函数
161 void menu()
162 {
163     cout << endl;
164     cout << "       ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
165     cout << "       ┃      ★★★★★★★哈夫曼编码与译码★★★★★★★        ┃" << endl;
166     cout << "       ┃                   1.  创建哈夫曼树                       ┃" << endl;
167     cout << "       ┃                   2.  进行哈夫曼编码                     ┃" << endl;
168     cout << "       ┃                   3.  进行哈夫曼译码                     ┃" << endl;
169     cout << "       ┃                   4.  退出程序                           ┃" << endl;
170     cout << "       ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
171     cout << "                       <><注意：空格字符用'- '代替><>" << endl;
172     cout << endl;
173 }
174 void main()
175 {
176     int falg;//记录要编码的字符个数
177     char a[MAX_MA];//储存输入的二进制字符
178     char b[MAX_ZF];//存储译出的字符
179     char zf[MAX_ZF];//储存要编码的字符
180     HuffmanTree HT = NULL;//初始化树为空数
181     HuffmanCode HC = NULL;//初始化编码表为空表
182     menu();
183     while (true)
184     {
185         int num;
186         cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";
187             cin >> num;
188             switch (num)
189             {
190             case 1 :
191                 cout << "<><请输入字符个数><>:";
192                 cin >> falg;
193                 //动态申请falg个长度的字符数组，用来存储要编码的字符
194                 /*char *zf = new char[falg];*/
195                 cout << "<><请依次输入" << falg << "个字符:><>: ";
196                 for (int i = 1; i <= falg; i++)
197                     cin >> zf[i];
198                 cout << "<><请依次输入" << falg << "个字符的权值><>: ";
199                 CreateHuffmanTree(HT， falg);//调用创建哈夫曼树的函数
200                 cout << endl;
201                 cout << "<><创建哈夫曼成功！，下面是该哈夫曼树的参数输出><>：" << endl;
202                 cout << endl;
203                 cout << "结点i"<<" "<<"字符" << " " << "权值" << " " << "双亲" << " " << "左孩子" << " " << "右孩子" << endl;
204                 for (int i = 1; i <= falg * 2 - 1; i++)
205                 {
206                     cout << i << " "<<zf[i]<< " " << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
207                 }
208                 cout << endl;
209                 break;
210             case 2:
211                 CreatHuffmanCode(HT， HC， falg);//调用创建哈夫曼编码表的函数
212                 cout << endl;
213                 cout << "<><生成哈夫曼编码表成功！，下面是该编码表的输出><>：" << endl;
214                 cout << endl;
215                 cout << "结点i"<<" "<<"字符" << " " << "权值" << " " << "编码" << endl;
216                 for (int i = 1; i <= falg; i++)
217                 {
218                     cout << i << " "<<zf[i]<< " " << HT[i].weight << " " << HC[i] << endl;
219                 }
220                 cout << endl;
221                 break;
222             case 3:
223                 cout << "<><请输入想要翻译的一串二进制编码><>：";
224                 /*这样可以动态的直接输入一串二进制编码，
225                 因为这样输入时后系统会自动加一个结束符*/
226                 cin >> a;
227                 TranCode(HT， a， zf， b， falg);//调用译码的函数，
228                  /*这样可以直接把数组b输出，因为后有
229                  在数组b添加输出时遇到结束符会结束输出*/
230                 cout << endl;
231                 cout << "<><译码成功！翻译结果为><>：" << b << endl;
232                 cout << endl;
233                 break;
234             case 4:
235                 cout << endl;
236                 cout << "<><退出成功！><>" << endl;
237                 exit(0);
238             default:
239                 break;
240             }
241     }
242
243     //-abcdefghijklmnopqrstuvwxyz
244     //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
245     //000101010111101111001111110001100100101011110110
246
247 }
　　五．运行截图：