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] = '\0';//编码结束符 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] != '\0';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] = '\0'; 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"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩子" << "\t" << "右孩子" << endl; 204 for (int i = 1; i <= falg * 2 - 1; i++) 205 { 206 cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << 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"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl; 216 for (int i = 1; i <= falg; i++) 217 { 218 cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << 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 } |
五．运行截图：
