哈夫曼树的C语言详解

​
哈夫曼树的C语言详解
1）一些名词的解释：
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i – 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积
2）哈夫曼树的定义：
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。
3）构造过程：
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
4）算法实现：
构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：
如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
如果介于两个结点权重值之间，替换原来较大的结点；

 #include<iostream> #include<string.h> #define  MAX 10000  /* 请输入一段文字:this*program*is*my*favourite 字符和权值信息如下 字符：t  权值：2 字符：h  权值：1 字符：i  权值：3 字符：s  权值：2 字符：*  权值：4 字符：p  权值：1 字符：r  权值：3 字符：o  权值：2 字符：g  权值：1 字符：a  权值：2 字符：m  权值：2 字符：y  权值：1 字符：f  权值：1 字符：v  权值：1 字符：u  权值：1 字符：e  权值：1 ******************************** 字符编码为： t:1000 h:11010 i:001 s:1001 *:011 p:11011 r:010 o:1010 g:11100 a:1011 m:1100 y:11101 f:11110 v:11111 u:0000 e:0001 文字编码为： 100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001 ******************************** 译码： 请输入要译码的二进制字符串,输入'#'结束：100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001# 译码为: this*program*is*my*favourite 是否继续?(Y/N): */ using namespace std; typedef struct {     char letter, *code;     int weight;     int parent, lchild, rchild; }HTNode, *HuffmanTree; int n; char coding[100]; int Min(HuffmanTree &HT, int i) {     int j;     unsigned int k = MAX;     int flag;     for (j = 0; j <= i; ++j)     {         if (HT[j].weight < k && HT[j].parent == 0)//用父结点是否为0来判断此结点是否已经被选过           {             k = HT[j].weight;             flag = j;         }     }     HT[flag].parent = 1;//作个标记，说明已经被选择了，因为在Select函数中要选择权值小的两个结点       return flag; } void Select(HuffmanTree &HT, int i, int &s1, int &s2) {     //在HT[1...i]中选择parent为0且权值最小的两个结点，其序号分别为s1,s2       //s1 <= s2       s1 = Min(HT, i);     s2 = Min(HT, i); } void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[]) {     int m;     int i, s1, s2;     if (n <= 1)         return;     m = 2 * n - 1; //总共需要2n－1个节点     HT = new HTNode[m + 1];//开辟空间     for (i = 0; i<n; i++)     {         HT[i].code = '';         HT[i].parent = 0;         HT[i].lchild = 0;         HT[i].rchild = 0;         HT[i].letter = t[i];         HT[i].weight = w[i];     }     for (i = n; i <= m; i++)     {         HT[i].code = '';         HT[i].parent = 0;         HT[i].lchild = 0;         HT[i].rchild = 0;         HT[i].letter = ' ';         HT[i].weight = 0;     }     cout << "********************************" << endl;     for (i = n; i<m; i++)     {         Select(HT, i - 1, s1, s2);//在n个数中找出权值最小的两个          HT[s1].parent = i;         HT[s2].parent = i;//将他们两个的parent节点设置为i;          HT[i].lchild = s1;         HT[i].rchild = s2;//把这两个分别当作左右节点         HT[i].weight = HT[s1].weight + HT[s2].weight;//他们两个的双亲为他们两个的和；      } } void CreatHuffmanCode(HuffmanTree HT) {     int start, c, f;     int i;     char *cd = new char[n];     cd[n - 1] = '';     cout << "字符编码为：" << endl;     for (i = 0; i<n; i++)     {         start = n - 1;         c = i;         f = HT[i].parent;         while (f != 0){             --start;             if (HT[f].lchild == c){                 cd[start] = '0';             }             else{                 cd[start] = '1';             }             c = f;             f = HT[f].parent;         }         HT[i].code = new char[n - start];         strcpy(HT[i].code, &cd[start]);         cout << HT[i].letter << ":" << HT[i].code << endl;     }     delete cd; } void HuffmanTreeYima(HuffmanTree HT, char cod[], int b)           //译码 {     char sen[100];     char temp[50];     char voidstr[] = " ";       //空白字符串     int t = 0;     int s = 0;     int count = 0;     for (int i = 0; i<b; i++)     {         temp[t++] = cod[i];     //读取字符         temp[t] = '';        //有效字符串         for (int j = 0; j<n; j++){        //依次与所有字符编码开始匹配             if (!strcmp(HT[j].code, temp)){                //匹配成功                 sen[s] = HT[j].letter;    //将字符保存到sen中                 s++;                 count += t;                 strcpy(temp, voidstr);                //将TEMP置空                  t = 0;          //t置空                 break;             }         }     }     if (t == 0){     //t如果被置空了，表示都匹配出来了，打印译码         sen[s] = '';         cout << "译码为:" << endl;         cout << sen << endl;     }     else{                             //t如果没有被置空 ， 源码无法被完全匹配         cout << "二进制源码有错！从第" << count + 1 << "位开始" << endl;     } } int main() {     HuffmanTree HT;     char a[100], buff[1024], p;//a为存放字符 buff为输入的字符串 p为输入译码时的字符      int b[100];//存放权值信息      int i, j;     int symbol = 1, x, k; //译码时做判断用的变量       cout << "请输入一段文字:";     cin >> buff;     int len = strlen(buff);     for (i = 0; i<len; i++)     {         for (j = 0; j<n; j++)         {             if (a[j] == buff[i])             {                 b[j] = b[j] + 1;                 break;             }         }         if (j >= n)         {             a[n] = buff[i];             b[n] = 1;             n++;         }     }     cout << "字符和权值信息如下" << endl;     for (i = 0; i<n; i++)     {         cout << "字符：" << a[i] << "  权值：" << b[i] << endl;     }     CreateHuffmanTree(HT, a, b);     CreatHuffmanCode(HT);     cout << "文字编码为：n";     for (int i = 0; i < len; i++)     {         for (int j = 0; j < n; j++)         {             if (buff[i] == HT[j].letter)             {                 cout << HT[j].code;                 break;             }         }     }     cout <<endl<< "********************************" << endl;     cout << "译码：" << endl;     while (1)     {         cout << "请输入要译码的二进制字符串,输入'#'结束：";         x = 1;//判断是否有非法字符只能是0 1          k = 0;//作为循环变量来使coding【k】=输入的字符          symbol = 1;//判断是否输入结束          while (symbol){             cin >> p;             if (p != '1'&&p != '0'&&p != '#'){ //若存在其它字符，x设为0，表示输入的不是二进制                 x = 0;             }             coding[k] = p;             if (p == '#')                 symbol = 0;  //#号结束标志             k++;         }         if (x == 1){             HuffmanTreeYima(HT, coding, k - 1);        //进行译码         }         else{             cout << "有非法字符！" << endl;         }         cout << "是否继续?(Y/N):";         cin >> p;         if (p == 'y' || p == 'Y')             continue;         else             break;     }     return 0; } 

​

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)