目录

哈夫曼编码（最优二叉树）

一、优势：缩短电文长度

二、思想：

三、过程：

四、图解实现过程：

五、总代码

哈夫曼编码（最优二叉树）

一、优势：缩短电文长度

二、思想：

获取每个字符出现的频率，用一个大小为[256]的数组保存（因为ASCII码是256个），最后作为每个字符的权重。权重越大，意味着出现频率越大，希望它的码长越短，这样总体电文最小。最后把这些字符（不重复部分）、权重依次放入结点中，把这些结点作为一个个元素，从小到大依次组成哈夫曼树。

三、过程：

先统计出字符出现的频率，作为其权重。

编码保存：把每个不重复的字符频率作为权重，用二叉树进行排序，二叉树上面的字符权重大(出现频率高)，编码的码长短，下面的字符权重小(出现频率低)，编码码长长。

编码：输入字符，遍历整个二叉树，对比是否和叶子结点相同，是则保存编码。（左0右1）

译码：输入二进制码，在二叉树中走一遍，走到叶子结点即为需要保存的编码。（左0右1）

（向左走为0，向右走为1）

四、图解实现过程：

五、总代码

//哈夫曼编码//优势：缩短电文长度//先统计出字符出现的频率，作为其权重。//编码保存：把每个不重复的字符作为权重，用二叉树进行排序，二叉树上面的字符权重高(出现频率高)，编码的码长短，//下面的字符权重小(出现频率低)，编码码长长//编码：输入字符，遍历整个二叉树，对比是否和叶子结点相同，是则保存编码//译码：输入二进制码，在二叉树中走一遍，走到叶子结点即为需要保存的编码。#include<iostream>#include<stdio.h>#include<malloc.h>#include<stdlib.h>using namespace std;#define MAXSIZE 100char str[MAXSIZE];//要编码保存的电文char str_en[MAXSIZE];//编码时输入的电文char str_de[MAXSIZE];//解码时输出的电文int code_de[MAXSIZE];//解码时存储int frequency[256] = { 0 };//统计各字符出现频率int flag_c[256] = { 0 };//只存储一次，判断是否第一次出现int length = 0;//数组总长度int LENGTH = 0;//叶子结点长度int sumFrequency = 0;//权重之和int index_s = 0;//字符串数组int code[64];//编码int index_c = -1;//编码数组int step = 0;//编码/译码步数（从哈夫曼树的根往后下走）int sumCode[4 * MAXSIZE];//总编码int flag_exit = 0;//退出符号int index = 0;//译码数组int decode_length;//译码数组长度//树元素typedef struct Tnode{char data;//存放数据int frequency;//权重(出现的频率）struct Tnode* lchild, * rchild;//左右孩子int code[64];//每个字符的哈夫曼码int code_length;//编码长度}Tnode;Tnode T[MAXSIZE];//存放各结点Tnode* hfmTree;//哈夫曼根结点Tnode* Pre;//存放前一个结点//输入字符串void Input(){cout << "请输入需要编码并保存编码的电文：\n";gets_s(str, 100);}//输入待编码数组void Encode_Input(){cout << "请输入需要编码的电文：\n";getchar();gets_s(str_en, MAXSIZE);}//输出编码后的数组void Encode_Output(){int i = 0;//下标for (i = 0; i <= index_c; i++){cout << sumCode[i];}cout << endl;}//输入待译码数组void Decode_Input(){int i = 0;char ch = ' ';step = 0;cout << "请输入需要译码的二进制码：\n";index = 0;getchar();//吸收空格//读取每位字符，挨个化整存入整形数组while (ch != '\n')//把每位字符保存到数组（换行退出）{ch = getchar();//读取一位字符if (ch != '\n')code_de[i++] = ch - 48;//字符化整}decode_length = i;//译码数组长度}//获取权重void GetFrequency(){int i = 0;//统计字符频率for (i = 0; i < strlen(str); i++){frequency[str[i]]++;//频率表中对应字符出现数值+1}}//创建树节点void CreateTnode(){int i = 0, count = 0;//添加字符和频率到树结构体数组中for (i = 0; i < strlen(str); i++){if (flag_c[str[i]] == 0)//首次出现{flag_c[str[i]] = 1;//标志出现过T[count].data = str[i];T[count].frequency = frequency[str[i]];T[count].lchild = NULL;T[count].rchild = NULL;sumFrequency += T[count].frequency;//计算叶子结点总权重count++;}}LENGTH = count;length = count;}//获取最小值/***********注：要整体替换，否则后面会出现混乱**********/Tnode Getmin(){int i, j, max = 0;Tnode temp;//选择排序(权重从高到低)（最后的一个最小）for (i = 0; i < length; i++){max = i;for (j = i; j < length; j++){if (T[j].frequency > T[max].frequency)max = j;}if (max != i){temp = T[i];//整体替换T[i] = T[max];T[max] = temp;}}return T[--length];//取出最后一个结点（最小权重）}//遍历void Traverse(Tnode* N){int i = 0;if (N != NULL){Traverse(N->lchild);if (N->lchild == NULL && N->rchild == NULL)//叶子结点{printf("%c结点权值：%d\t编码：", N->data, N->frequency);for (i = 0; i < N->code_length; i++){cout << N->code[i];}cout << endl;}Traverse(N->rchild);}}//初始化哈夫曼树void Init_hfmTree(){hfmTree = (Tnode*)malloc(sizeof(Tnode));//创建哈夫曼树hfmTree->lchild = NULL;hfmTree->rchild = NULL;Pre = hfmTree;//前一个结点}//创建哈夫曼树Tnode Create_hfmTree(){int len;Tnode* N = (Tnode*)malloc(sizeof(Tnode));while (N->frequency != sumFrequency){N = (Tnode*)malloc(sizeof(Tnode));N->lchild = (Tnode*)malloc(sizeof(Tnode));//左孩子N->rchild = (Tnode*)malloc(sizeof(Tnode));//右孩子if (length != -1)*N->lchild = Getmin();elseN->lchild = NULL;//地址设为空if (length != -1)*N->rchild = Getmin();elseN->rchild = NULL;//地址设为空N->data = '#';//表示空N->frequency = N->lchild->frequency + N->rchild->frequency;//求权重之和T[length++] = *N;//放入数组}return *N;}//结点编码（初始存档编码）void NodeEncode(Tnode* N){int i = 0;if (N != NULL){//向左走if (Pre->lchild == N){code[step++] = 0;//向左走}else if (Pre->rchild == N){code[step++] = 1;//向右走}Pre = N;//保存上一结点if (N->lchild != NULL && N->rchild != NULL)//未到达叶子结点{NodeEncode(N->lchild);step--;//向回走Pre = N;//保存上一结点NodeEncode(N->rchild);step--;//向回走}else//到达叶子结点{for (i = 0; i < step; i++)N->code[i] = code[i];//记录编码N->code_length = step;//记录码长}}}//编码void Encode(Tnode* N){int i = 0;if (flag_exit)return;if (N != NULL && str[index_s] != '\0')//到达叶子结点或者字符串到尾{if (N->lchild != NULL && N->rchild != NULL)//未到达叶子结点{Encode(N->lchild);Encode(N->rchild);}else//找到叶子结点{if (N->data == str_en[index_s])//是要找的叶子结点{flag_exit = 1;//退出标志for (i = 0; i < N->code_length; i++){sumCode[++index_c] = N->code[i];//编码存入}}}}}//译码void Decode(Tnode* N){int i = 0;if (N != NULL){if (N->lchild != NULL || N->rchild != NULL)//没有查找到叶子结点{if (code_de[index] == 0)//向左走{index++;step++;Decode(N->lchild);step--;//弹出来}else if (code_de[index] == 1)//向右走{index++;step++;Decode(N->rchild);step--;//弹出来}}else//查找到叶子结点{cout << N->data;//输出译码结果}}}int main(){int choice;int i;Input();//输入字符GetFrequency();//获取字符串//叶子结点的创建与排序CreateTnode();//创建树节点//哈夫曼树的初始化与创建Init_hfmTree();*hfmTree = Create_hfmTree();//结点编码step = 0;NodeEncode(hfmTree);while (1){system("cls");cout << "请选择需要的服务：\n";cout << "1、查找所有已保存的结点编码和权\n";cout << "2、整体编码\n";cout << "3、整体译码\n";cout << "0、退出\n";cout << "请选择您需要的服务：\n";cin >> choice;//选项switch (choice){//0、退出case 0:exit(0);break;//1、遍历所有叶子结点case 1:Traverse(hfmTree);//查找所有编码和权break;case 2:index_s = 0;Encode_Input();//编码输入//逐字符编码while (str_en[index_s] != '\0'){flag_exit = 0;Encode(hfmTree);index_s++;}Encode_Output();//编码输出break;//3、译码case 3://输入译码数组Decode_Input();index = 0;while (index < decode_length){//译码step = 0;Decode(hfmTree);//译码并输出}cout << endl;break;default:cout << "无此选项！" << endl;break;}system("pause");}return 0;}