精华内容
下载资源
问答
  • 主要为大家详细介绍了C++实现哈夫曼树编码解码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 构造过程:...

    哈夫曼(Haffman)树(最优树)

    定义:

    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    构造过程:

    以 1,7,3,4,9,8为例:

    第一步:排序,1,3,4,7,8,9

    第二步:选出最小的两个数,1,3(哈夫曼树是从下往上排列的),用一个树杈连接上两个最小的数,在顶点处计算出这两个数字的和 并写在上面。

    第三步:然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列。

    第四步:如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了;如果这两个数的和比较大不是下一步的两个最小数的其中一个那么,就并列生长。

    注意:(由于并未规定左右子树,所以哈夫曼树不唯一,同一层上的结点,位置是可以互换的)

     

     

    哈夫曼树的数据结构:

     1 //haffman 树的结构
     2 typedef struct
     3 {
     4     //叶子结点权值
     5     float weight;
     6     //指向双亲,和孩子结点的指针
     7     unsigned int parent;
     8     unsigned int lChild;
     9     unsigned int rChild;
    10 } Node, *HuffmanTree;
    11 
    12 //动态分配数组,存储哈夫曼编码
    13 typedef char *HuffmanCode;

    选择两个权值最小的结点:

     1 //选择两个parent为0,且weight最小的结点s1和s2的方法实现
     2 //n 为叶子结点的总数,s1和 s2两个指针参数指向要选取出来的两个权值最小的结点
     3 void select(HuffmanTree *huffmanTree, int n, int *s1, int *s2)
     4 {
     5     //标记 i
     6     int i = 0;
     7     //记录最小权值
     8     int min;
     9     //遍历全部结点,找出单节点
    10     for(i = 1; i <= n; i++)
    11     {
    12         //如果此结点的父亲没有,那么把结点号赋值给 min,跳出循环
    13         if((*huffmanTree)[i].parent == 0)
    14         {
    15             min = i;
    16             break;
    17         }
    18     }
    19     //继续遍历全部结点,找出权值最小的单节点
    20     for(i = 1; i <= n; i++)
    21     {
    22         //如果此结点的父亲为空,则进入 if
    23         if((*huffmanTree)[i].parent == 0)
    24         {
    25             //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
    26             if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
    27             {
    28                 min = i;
    29             }
    30         }
    31     }
    32     //找到了最小权值的结点,s1指向
    33     *s1 = min;
    34     //遍历全部结点
    35     for(i = 1; i <= n; i++)
    36     {
    37         //找出下一个单节点,且没有被 s1指向,那么i 赋值给 min,跳出循环
    38         if((*huffmanTree)[i].parent == 0 && i != (*s1))
    39         {
    40             min = i;
    41             break;
    42         }
    43     }
    44     //继续遍历全部结点,找到权值最小的那一个
    45     for(i = 1; i <= n; i++)
    46     {
    47         if((*huffmanTree)[i].parent == 0 && i != (*s1))
    48         {
    49             //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
    50             if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
    51             {
    52                 min = i;
    53             }
    54         }
    55     }
    56     //s2指针指向第二个权值最小的叶子结点
    57     *s2 = min;
    58 }

    构造哈夫曼树:

     1 //创建哈夫曼树并求哈夫曼编码的算法如下,w数组存放已知的n个权值
     2 void createHuffmanTree(HuffmanTree *huffmanTree, float w[], int n)
     3 {
     4     //m 为哈夫曼树总共的结点数,n 为叶子结点数
     5     int m = 2 * n - 1;
     6     //s1 和 s2 为两个当前结点里,要选取的最小权值的结点
     7     int s1;
     8     int s2;
     9     //标记
    10     int i;
    11     // 创建哈夫曼树的结点所需的空间,m+1,代表其中包含一个头结点
    12     *huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node));
    13     //1--n号存放叶子结点,初始化叶子结点,结构数组来初始化每个叶子结点,初始的时候看做一个个单个结点的二叉树
    14     for(i = 1; i <= n; i++)
    15     {
    16 
    17         //其中叶子结点的权值是 w【n】数组来保存
    18         (*huffmanTree)[i].weight = w[i];
    19         //初始化叶子结点(单个结点二叉树)的孩子和双亲,单个结点,也就是没有孩子和双亲,==0
    20         (*huffmanTree)[i].lChild = 0;
    21         (*huffmanTree)[i].parent = 0;
    22         (*huffmanTree)[i].rChild = 0;
    23     }// end of for
    24     //非叶子结点的初始化
    25     for(i = n + 1; i <= m; i++)
    26     {
    27         (*huffmanTree)[i].weight = 0;
    28         (*huffmanTree)[i].lChild = 0;
    29         (*huffmanTree)[i].parent = 0;
    30         (*huffmanTree)[i].rChild = 0;
    31     }
    32 
    33     printf("\n HuffmanTree: \n");
    34     //创建非叶子结点,建哈夫曼树
    35     for(i = n + 1; i <= m; i++)
    36     {
    37     
    38       select(huffmanTree,i-1,&s1,&s2);
    39       (*huffmanTree)[s1].parent=i;
    40       (*huffmanTree)[s2].parent=i;
    41       (*huffmanTree)[i].lChild=s1;
    42       (*huffmanTree)[i].rChild=s2;    
    43       (*huffmanTree)[i].weight=(*huffmanTree)[s1].weight+(*huffmanTree)[s2].weight;
    44       printf("%f (%f, %f)\n", (*huffmanTree)[i].weight, (*huffmanTree)[s1].weight, (*huffmanTree)[s2].weight);
    45     }
    46     printf("\n");
    47 }

    求每个节点的哈弗曼编码:

     1 //哈夫曼树建立完毕,从 n 个叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码
     2 void creatHuffmanCode(HuffmanTree *huffmanTree, HuffmanCode *huffmanCode, int n)
     3 {
     4     //指示biaoji
     5     int i;
     6     //编码的起始指针
     7     int start;
     8     //指向当前结点的父节点
     9     int p;
    10     //遍历 n 个叶子结点的指示标记 c
    11     unsigned int c;
    12     //分配n个编码的头指针
    13     huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
    14     //分配求当前编码的工作空间
    15     char *cd = (char *)malloc(n * sizeof(char));
    16     //从右向左逐位存放编码,首先存放编码结束符
    17     cd[n - 1] = '\0';
    18     //求n个叶子结点对应的哈夫曼编码
    19     for(i = 1; i <= n; i++)
    20     {
    21         //初始化编码起始指针
    22         start = n - 1;
    23         //从叶子到根结点求编码
    24         for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
    25         {
    26             if( (*huffmanTree)[p].lChild == c)
    27             {
    28                 //从右到左的顺序编码入数组内
    29                 cd[--start] = '0';  //左分支标0
    30             }
    31             else
    32             {
    33                 cd[--start] = '1';  //右分支标1
    34             }
    35         }// end of for
    36         //为第i个编码分配空间
    37         huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
    38         strcpy(huffmanCode[i], &cd[start]);
    39     }
    40 
    41     free(cd);
    42     //打印编码序列
    43     for(i = 1; i <= n; i++)
    44     {
    45         printf("HuffmanCode of %d is %s\n", i, huffmanCode[i]);
    46     }
    47 
    48     printf("\n");
    49 }

    输入一串数据(数据为1—9之间从小到大连续的数),编译成哈夫曼编码:

     1 HuffmanCode *creatHuffmanCode1(HuffmanTree *huffmanTree,char *Huffman, int n,int data[],float num){
     2     //该函数通过改写creatHuffmanCode函数,来实现译码(即是通过匹配即添加字符串的方式来实现) 
     3     HuffmanCode *huffmanCode;
     4     huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
     5     int i;
     6     int start;
     7     int p;
     8     unsigned int c;
     9     char *cd = (char *)malloc(n * sizeof(char));
    10     cd[n - 1] = '\0';
    11     for(i = 1; i <= n; i++)
    12     {
    13         start = n - 1;
    14         for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
    15         {
    16             if( (*huffmanTree)[p].lChild == c)
    17             {
    18                 cd[--start] = '0';
    19             }
    20             else
    21             {
    22                 cd[--start] = '1';
    23             }
    24         }
    25         huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
    26         strcpy(huffmanCode[i], &cd[start]);
    27     }
    28     free(cd);
    29     //打印编码序列
    30     int num1=int(num);
    31     int l=0;
    32     char s[10]="";
    33     itoa(n,s,10);
    34     huffmanCode[0] = (char *)malloc((10) * sizeof(char));
    35     strcpy(huffmanCode[0],s);
    36     for(int i=1;i<=num1;i++){
    37         int z=data[i];    
    38         strcat(Huffman,huffmanCode[z]);
    39     }
    40     printf("HuffmanCode of this String is %s\n",Huffman);
    41     printf("\n");
    42     return huffmanCode;
    43 }
    44 
    45 
    46 HuffmanCode *dataToHuffmanCode(char *Huffman, int data[]){
    47     //data数组是原数据(0—9),Huffman存放编译后的 Huffman编码 
    48     HuffmanTree huffmanTree;
    49     int k=1;
    50     int q=0;
    51     while(data[k]!=-99){
    52         k++;
    53     }
    54     float num=float(k-1);
    55     float val[10];
    56     for(int j=1;j<10;j++){
    57         int i=1;
    58         int n=0;
    59         while(data[i]!=-99){
    60             if(data[i]==j){
    61                 n++;
    62             }
    63             i++;
    64         }    
    65         val[j]=n/num;
    66     }
    67     for(int i=1;i<10;i++){
    68         if(val[i]!=0){
    69             q++;                //q为叶子结点数 
    70         }
    71     }
    72     float *val2; 
    73     val2 = (float *)malloc((q+1) * sizeof(float));
    74     int m=1;
    75     for(int i=1;i<10;i++){
    76         if(val[i]!=0){
    77             val2[m]=val[i];
    78         }
    79         m++;                   //val2[]储存不同元素的权值 
    80     }
    81     createHuffmanTree(&huffmanTree,val2,q);
    82     HuffmanCode *huffmanCode=creatHuffmanCode1(&huffmanTree,Huffman,q,data,num);//调用上面的 creatHuffmanCode1函数 
    83     return huffmanCode;
    84 }

    将一串哈夫曼编码,还原成原来的数据(此时哈弗曼树已经构造完成):

     1 void HuffmanCodeTodata(char *Huffman, int data[],HuffmanCode *huffmanCode){
     2     //huffmanCode为已经构造好的一颗Huffman树,Huffman存放已经编译好的 Huffman编码 ,data数组存放解码后的原数据(0—9) 
     3     
     4     printf("Huffman:%s\n",Huffman);
     5     printf("1:%s\n",huffmanCode[1]);
     6     printf("2:%s\n",huffmanCode[2]);
     7     printf("3:%s\n",huffmanCode[3]);
     8     printf("4:%s\n",huffmanCode[4]);
     9     //这几行是显示功能,和实现无关 
    10     
    11     int num=atoi(huffmanCode[0]);
    12     char Huffman1[100]="";
    13     int k1=0;
    14     int k2=0;
    15     int x=1;
    16     int y=1;
    17     while(Huffman[k1]=='1'||Huffman[k1]=='0'){    
    18         Huffman1[k2]=Huffman[k1];
    19         for(int i=1;i<=num;i++){
    20             if(strcmp(huffmanCode[i],Huffman1)==0){
    21                 k2=-1;
    22                 data[x]=i;
    23                 x++;
    24                 //strcpy(Huffman1,"");
    25                 memset(Huffman1,0,sizeof(Huffman1));
    26                 break;
    27             }
    28         }
    29         k1++;
    30         k2++;
    31     }
    32     data[x]=-99;
    33     for(int i=1;i<100;i++){
    34         if(data[i]!=-99){
    35             printf("%d",data[i]);
    36         }
    37         else{
    38             break;
    39         }
    40     }
    41 }

    输入一个文本,统计文本中各字符串的数目,计算相应的权重,使用该权重构建哈夫曼编码,使用该编码编译原文件

    (即是在编码的基础上加上文件操作):

     1 void fileHuff(){
     2     FILE *in;
     3     char Huffman2[1000]="";
     4     int data[100];
     5     char file[10];
     6     int k = 1;
     7     printf("输入读取的文件名:(输入aaa.txt)");
     8     scanf("%s",file);
     9     if((in=fopen(file,"r+"))==NULL){
    10         printf("无法打开此文件!\n");
    11         exit(0);
    12     }
    13     while(!feof(in)){
    14         fscanf(in,"%d",&data[k++]);
    15     }    
    16     for(int i=1;i<k;i++){
    17         printf("\n%d\n",data[i]);
    18     }
    19     data[k]=-99;    
    20     dataToHuffmanCode(Huffman2,data);
    21     fprintf(in,"\n");
    22     fprintf(in,"解码后的码为:\n");
    23     fprintf(in,"%s",Huffman2);
    24     fflush(in);
    25     fclose(in);
    26 }

    主函数:

     1 int main()
     2 {
     3     HuffmanTree HT;
     4     HuffmanCode HC;
     5     char Huffman[1000]="";
     6     char Huffman1[1000]="";
     7     HuffmanCode *huffmanCode;
     8     int i, n;
     9     float *w, wei;
    10     int choice;
    11     for (;;)
    12     {
    13         printf("\n           哈夫曼编码 \n");
    14         printf("             1.哈夫曼编码实现\n");
    15         printf("             2.输入一串数据(数据为1—9之间从小到大连续的数),编译成哈夫曼编码\n");
    16         printf("             3.将一串哈夫曼编码,还原成原来的数据\n");
    17         printf("             4.输入一个文本,统计文本中各字符串的数目,计算相应的权重,使用该权重构建哈夫曼编码,使用该编码编译原文件\n");
    18         printf("             5.退出系统\n");
    19         printf("请选择:");
    20         scanf("%d", &choice);
    21         switch (choice)
    22         {
    23         case 1:
    24             printf("\n 需要创建的文件有多少个码元 = " );
    25             scanf("%d", &n);
    26             w = (float *)malloc((n + 1) * sizeof(float));
    27             printf("\ninput the %d element's weight:\n", n);
    28             for(i = 1; i <= n; i++)
    29             {
    30                 printf("%d: ", i);
    31                 fflush(stdin);
    32                 scanf("%f", &wei);
    33                 w[i] = wei;
    34             }
    35             createHuffmanTree(&HT, w, n);
    36             creatHuffmanCode(&HT, &HC, n);
    37             break;
    38         case 2:
    39             printf("\n输入数据为:(以-99结束)");
    40             int data[100];
    41             for(int i=1;i<100;i++){
    42                 scanf("%d",&data[i]);
    43                 if(data[i]==-99){
    44                     break;
    45                 }
    46             }
    47             huffmanCode=dataToHuffmanCode(Huffman,data);
    48             break;
    49         case 3:
    50             int data1[100];
    51             printf("\n哈夫曼编码解码后为:\n");
    52             HuffmanCodeTodata(Huffman,data1,huffmanCode);
    53             break;
    54         case 4:
    55             printf("\n需要实现将aaa.txt文件放在桌面上!\n");
    56             fileHuff();
    57             break;
    58         case 5:
    59             printf("请退出系统!\n");
    60             exit(0);
    61             break;
    62         }
    63     }
    64     return 1;
    65 }

     

    转载于:https://www.cnblogs.com/OrdinaryMan/p/10048547.html

    展开全文
  • 最近完成了数据结构课程设计,被分到的题目是《哈夫曼编码解码》,现在在这篇博文里分享一下自己的成果。  我在设计时,在网上参考了很多老师和前辈的算法和代码,向他们表示感谢!他们的成果给了我很多启示和...

      最近完成了数据结构课程设计,被分到的题目是《哈夫曼编码和解码》,现在在这篇博文里分享一下自己的成果。

      我在设计时,在网上参考了很多老师和前辈的算法和代码,向他们表示感谢!他们的成果给了我很多启示和帮助。另外,自己的成品中也还有很多不完善的地方,欢迎批评指正。

    课题:哈夫曼编码与解码 C++代码实现

    (1)统计某电文中字符出现的频率(假设电文中只含有大小写英文字母,以及逗号和点号);
    (2)把字符出现的频率作为权值建立哈夫曼树,进行哈夫曼编码,并输出每个字符的编码结果;
    (3)对电文进行哈夫曼编码;
    (4)把电文的哈夫曼编码进行译码,输出对应电文的内容。

      1 #include <stdlib.h>
      2 #include <stdio.h>
      3 #include <malloc.h>
      4 #include <string.h>
      5 #include <ctype.h>
      6 #define MAX 999999 //一个极大值
      7 #define NUM 10
      8 
      9 //存储哈夫曼树每个结点
     10 typedef struct Node {
     11     char ch;
     12     int weight; //权值
     13     int parent;
     14     int lchild,rchild;
     15 }HFNode;
     16 //存储每个字符及其哈夫曼编码
     17 typedef struct {
     18     char ch;
     19     char code[NUM];
     20 }HFCharCode;
     21 
     22 HFNode HT[28*2-1]; //哈夫曼树结构体
     23 HFCharCode HCD[28]; //哈夫曼编码结构体
     24 int LeafNum; //叶子结点数
     25 int NodeNum; //所有结点数
     26 char EnterStr[MAX]; //输入的待编码电文
     27 char EnterCode[MAX]; //输入的待解码密文
     28 char RealStr[MAX]; //密文解码后的电文
     29 int AllWeight[28]; //存储所有28个字符的权值
     30 
     31 void Statistics();
     32 void CreateHFTree();
     33     void SelectMin(int &min1, int &min2);
     34 void CreateHFCode();
     35     void ReverseStr(char *str);
     36 void EncodeStr();
     37 void DecodeHFCode();
     38 
     39 int main() {
     40     printf("****** 哈夫曼编码与解码 ******\n\n");
     41     printf("*** 输入一串字符串 ***\n");
     42     scanf("%s", EnterStr);
     43     getchar();
     44     Statistics();
     45     CreateHFTree();
     46     CreateHFCode();
     47     EncodeStr();
     48     printf("\n*** 输入想解码的内容 ***\n");
     49     scanf("%s", EnterCode);
     50     getchar();
     51     DecodeHFCode();
     52     return 0;
     53 }
     54 
     55 //统计每个字符权值
     56 void Statistics() {
     57     int len = strlen(EnterStr);
     58     for(int i = 0; i <= 27; i++)
     59         AllWeight[i] = 0;
     60     for(int j = 0; j <= len - 1; j++) {
     61         if(isalpha(EnterStr[j])) {
     62             EnterStr[j] = tolower(EnterStr[j]);
     63             AllWeight[EnterStr[j]-'a']++;
     64         }
     65         else if((int)EnterStr[j] == 44)
     66             AllWeight[26]++;
     67         else if((int)EnterStr[j] == 46)
     68             AllWeight[27]++;
     69         else {
     70             printf("\n输入不符合要求!\n\n");
     71             exit(-1);
     72         }
     73     }
     74     int i = 0, j = 0;
     75     for( ; i <= 25; i++) {
     76         if(AllWeight[i] != 0) {
     77                 HT[j].weight  = AllWeight[i];
     78                 HT[j].ch = i+'a';
     79                 j++;
     80         }
     81     }
     82     if(AllWeight[i] != 0) {
     83             HT[j].weight = AllWeight[i];
     84             HT[j].ch = ',';
     85             j++;
     86             i++;
     87     }
     88     if(AllWeight[i] != 0) {
     89             HT[j].weight = AllWeight[i];
     90             HT[j].ch = '.';
     91     }
     92     printf("\n*** 打印每个字符的权值 ***\n");
     93     int n = 0;
     94     for(int i = 0; i <= 27; i++) {
     95         if(AllWeight[i] != 0) {
     96             n++;
     97             if(i <= 25)
     98                 putchar('a'+i);
     99             else if(i == 26)
    100                 printf(",");
    101             else
    102                 printf(".");
    103             printf(": %d\n", AllWeight[i]);
    104         }
    105     }
    106     LeafNum = n;
    107     NodeNum = 2*LeafNum-1;
    108 }
    109 
    110 //构造哈夫曼树
    111 void CreateHFTree() {
    112     int i;
    113     for(i = 0; i <= LeafNum-1; i++) {
    114         HT[i].parent = -1;
    115         HT[i].lchild = -1;
    116         HT[i].rchild = -1;
    117         HT[i].weight = HT[i].weight;
    118     }
    119     for(; i <= NodeNum-1; i++) {
    120         HT[i].parent = -1;
    121         HT[i].lchild = -1;
    122         HT[i].rchild = -1;
    123         HT[i].weight = MAX;
    124     }
    125     int min1, min2;
    126     for(i = LeafNum; i <= NodeNum-1; i++) {
    127         SelectMin(min1, min2);
    128         HT[min1].parent = i;
    129         HT[min2].parent = i;
    130         HT[i].lchild = min1;
    131         HT[i].rchild = min2;
    132         HT[i].weight = HT[min1].weight + HT[min2].weight;
    133     }
    134     // printf("\n*** 打印哈夫曼树 ***\n");
    135     // for(int i = 0; i <= NodeNum-1; i++) {
    136     //     printf("序号:%d 字符:%c 权值:%d 双亲:%d 左孩:%d 右孩:%d\n", i, HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
    137     // }
    138 }
    139     //找到两个权值最小的二叉树的序号
    140     void SelectMin(int &min1, int &min2) {
    141         int i = 0;
    142         int temp;
    143         int wetmin1, wetmin2;
    144         while(HT[i].parent != -1) 
    145             i++;
    146         wetmin1 = HT[i].weight;
    147         min1 = i;
    148         i++;
    149         while(HT[i].parent != -1) 
    150             i++;
    151         wetmin2 = HT[i].weight;
    152         min2 = i;
    153         i++;
    154         if(wetmin1 > wetmin2) {
    155             temp = wetmin2;
    156             wetmin2 = wetmin1;
    157             wetmin1 = temp;
    158             temp = min2;
    159             min2 = min1;
    160             min1 = temp;
    161         }
    162         for(; i <= NodeNum-1; i++) {
    163             if(HT[i].weight < wetmin1 && HT[i].parent == -1) {
    164                 wetmin2 = wetmin1;
    165                 wetmin1 = HT[i].weight;
    166                 min2 = min1;
    167                 min1 = i;
    168             } else if(HT[i].weight < wetmin2 && HT[i].parent == -1) {
    169                 wetmin2 = HT[i].weight;
    170                 min2 = i;
    171             }
    172         }
    173     }
    174 
    175 //进行哈夫曼编码
    176 void CreateHFCode() {
    177     int i, j, len; 
    178     for(i = 0; i <= LeafNum-1; i++) {  
    179         len = 0;  
    180         j = i;
    181         HCD[i].ch = HT[j].ch;
    182         while(HT[j].parent != -1) {  //不是根节点
    183             if(HT[HT[j].parent].lchild == j) {  //是双亲结点的左孩子
    184                 HCD[i].code[len++] = '0'+0;  //加上字符0
    185             }else  //是右孩子
    186                 HCD[i].code[len++] = '0'+1;  //加上字符1
    187             j = HT[j].parent;  //往上遍历
    188         }
    189         HCD[i].code[len] = '\0'; //字符串末尾 
    190         ReverseStr(HCD[i].code); 
    191     }
    192     printf("\n*** 打印每个字符的编码 ***\n");
    193     for(int i = 0; i <= LeafNum-1; i++)
    194         printf("%c: %s\n", HT[i].ch, HCD[i].code);
    195 }
    196     //将一个字符串反转  
    197     void ReverseStr(char *str) {  
    198         int i, j;  
    199         char c;  
    200         for(i = 0, j = strlen(str)-1; i < j; i++, j--) {  
    201             c = str[i];  
    202             str[i] = str[j];  
    203             str[j] = c;  
    204         }
    205     }
    206 
    207 //哈夫曼编码
    208 void EncodeStr() {
    209     int len = strlen(EnterStr);
    210     printf("\n*** 编码结果 ***\n");
    211     for(int i = 0; i <= len-1; i++) {
    212         for(int j = 0; j <= LeafNum-1; j++) {
    213             if(EnterStr[i] == HCD[j].ch)
    214                 printf("%s", HCD[j].code);
    215         }
    216     }
    217     printf("\n");
    218 }
    219 
    220 //哈夫曼解码
    221 void DecodeHFCode() {
    222     int k = NodeNum-1; //根结点序号, 开始时一定在最后一个
    223     int len = 0, i = 0;  
    224     while(EnterCode[i]) {  
    225         if(EnterCode[i] == '0'+0)  
    226             k = HT[k].lchild;  
    227         else if(EnterCode[i] == '0'+1)  
    228             k = HT[k].rchild;  
    229         else {
    230             printf("\n错误! 密文中仅能含有1和0!\n\n");
    231             exit(-1);
    232         }  
    233         if(HT[k].lchild == -1 && HT[k].rchild == -1) {  
    234             RealStr[len++] = HT[k].ch;
    235             k = NodeNum-1;
    236         }  
    237         i++;  
    238     }
    239     RealStr[len] = '\0';
    240     if(k == NodeNum-1) {     
    241         printf("\n*** 解码结果 ***\n%s\n\n", RealStr);
    242         exit(0);
    243     }
    244     printf("\n错误! 部分密文无法解密!\n\n");
    245     exit(-1);  
    246 }

     

    转载于:https://www.cnblogs.com/deepcho/p/huffman-tree-node-code-decode-encode-cpp.html

    展开全文
  • 有讲到了哈夫曼树的原理及哈夫曼编码解码的过程。原理讲解直接移步上述链接,就不再画蛇添足。作为巩固随手练习一道题: 给定一篇文章,统计里面的各个字符出现的频次,并构建哈夫曼树,实现哈夫曼编码和解码的过程...

    今天在复习哈夫曼树的时候,发现了一个不错的B站视频,讲解的非常清晰直观。地址传送门。有讲到了哈夫曼树的原理及哈夫曼编码解码的过程。原理讲解直接移步上述链接,就不再画蛇添足。作为巩固随手练习一道题:

    给定一篇文章,统计里面的各个字符出现的频次,并构建哈夫曼树,实现哈夫曼编码和解码的过程。并且计算哈夫曼编码和定长编码的空间节省了多少?
    输入的文本:

    each year, the american heart association (aha), in conjunction with the centers for disease control and prevention, the national institutes of health, and other government agencies, brings together the most up-to-date statistics on heart disease, stroke, other vascular diseases, and their risk factors and presents them in its heart disease and stroke statistical update. the statistical update is a valuable resource for researchers, clinicians, healthcare policy makers, media professionals, the lay public, and many others who seek the best national data available on disease morbidity and mortality and the risks, quality of care, medical procedures and operations, and costs associated with the management of these diseases in a single document. indeed, since 1999, the statistical update has been cited more than 8700 times in the literature (including citations of all annual versions). in 2009 alone, the various statistical updates were cited 1600 times (data from isi web of science). in recent years, the statistical update has undergone some major changes with the addition of new chapters and major updates across multiple areas. for this year s edition, the statistics committee, which produces the document for the aha, updated all of the current chapters with the most recent nationally representative data and inclusion of relevant articles from the literature over the past year and added a new chapter detailing how family history and genetics play a role in cardiovascular disease (cvd) risk. also, the 2011 statistical update is a major source for monitoring both cardiovascular health and disease in the population, with a focus on progress toward achievement of the aha s 2020 impact goals. below are a few highlights from this year s update. mortality data are presented according to the underlying cause of death. any-mention mortality means that the condition was nominally selected as the underlying cause or was otherwise mentioned on the death certificate. for many deaths classified as attributable to cvd, selection of the single most likely underlying cause can be difficult when several major comorbidities are present, as is often the case in the elderly population. it is useful, therefore, to know the extent of mortality due to a given cause regardless of whether it is the underlying cause or a contributing cause (ie, its any-mention status). the number of deaths in 2007 with any mention of specific causes of death was tabulated by the nhlbi from the nchs public-use electronic files on mortality. the first set of statistics for each disease in this update includes the number of deaths for which the disease is the underlying cause. two exceptions are chapter 7 (high blood pressure) and chapter 9 (heart failure). high bp, or hypertension, increases the mortality risks of cvd and other diseases, and hf should be selected as an underlying cause only when the true underlying cause is not known. in this update, hypertension and hf death rates are presented in 2 ways: (1) as nominally classified as the underlying cause and (2) as any-mention mortality. national and state mortality data presented according to the underlying cause of death were computed from the mortality tables of the nchs world wide web site, the health data interactive data system of the nchs, or the cdc compressed mortality file. any-mention numbers of deaths were tabulated from the electronic mortality files of the nchs world wide web site and from health data interactive.
    

    step1:统计文章中每个字符出现的次数,并保存在map中
    step2:将map中的每一项转化为一个单节点树,构成深林
    step3:构建霍夫曼树
    step4:获得每个字符的编码,保存在map中
    step5:编码文章的字符,并将编码的结果输出
    step6:依据编码的文档,加上霍夫曼树的信息,解码文档输出

    在这里插入图片描述

    #include<iostream>
    #include<fstream>
    #include<unordered_map>
    #include<algorithm>
    
    using namespace std;
    
    struct TreeNode {
    	int count;
    	char charcate;
    	TreeNode* left;
    	TreeNode* right;
    	TreeNode(int n, char c) { 
    		count = n; charcate = c; 
    		left = nullptr; right = nullptr;
    	}
    };
    
    bool compare(TreeNode* s1, TreeNode* s2) {
    	return s1->count < s2->count;
    }
    
    class Solution {
    private:
    	unordered_map<char, string> codingMap;
    public:
    	//step1:统计文章中每个字符出现的次数,并保存在map中
    	unordered_map<char, int> countC(string& s) {
    		ifstream ifs;
    		ifs.open(s);
    		_ASSERT(ifs.is_open());
    		ifs >> noskipws;
    		char temp;
    		unordered_map<char, int> data;
    		while (!ifs.eof()) {
    			ifs >> temp;
    			if (data.find(temp) == data.end())
    				data[temp] = 1;
    			else
    				data[temp]++;
    		}
    		ifs.close();
    		return data;
    	}
    
    	//step2:将map中的每一项转化为一个单节点树,构成深林
    	vector<TreeNode*> mapToNode(unordered_map<char, int>& data) {
    		vector<TreeNode*> out;
    		for (auto ptr = data.begin(); ptr != data.end(); ptr++) {
    			TreeNode* temp = new TreeNode(ptr->second, ptr->first);
    			out.push_back(temp);
    		}
    		return out;
    	}
    
    	//step3:构建霍夫曼树
    	TreeNode* creatTree(vector<TreeNode*>& Node) {
    		while (Node.size() > 1) {
    			sort(Node.begin(), Node.end(), compare);
    			TreeNode* left = Node[0];
    			TreeNode* right = Node[1];
    			Node.erase(Node.begin());
    			Node.erase(Node.begin());
    			TreeNode* new_Node = new TreeNode(left->count + right->count, '#');
    			new_Node->left = left;
    			new_Node->right = right;
    			Node.push_back(new_Node);
    		}
    		return Node[0];
    	}
    
    	//step4:获得每个字符的编码,保存在map中
    	void codeString(TreeNode* root, string code) {
    		if (root == nullptr) return;
    		if (root->left == nullptr&&root->right == nullptr) {
    			codingMap[root->charcate] = code;
    			return;
    		}
    
    		codeString(root->left, code + "0");
    		codeString(root->right, code + "1");
    	}
    
    	//step5:编码文章的字符,并将编码的结果输出
    	void coding(string& input, string& output) {
    		ifstream ifs;
    		ifs.open(input);
    		_ASSERT(ifs.is_open());
    		ifs >> noskipws;
    		char temp;
    
    		ofstream ofs;
    		ofs.open(output);
    		_ASSERT(ofs.is_open());
    		while (!ifs.eof()) {
    			ifs >> temp;
    			string codeCharacte = codingMap[temp];
    			for (auto single : codeCharacte)
    				ofs << single;
    		}
    		ofs.close();
    	}
    
    	//step6:依据编码的文档,加上霍夫曼树的信息,解码文档输出
    	void encoding(string& input_path, string& output_path, TreeNode* root) {
    		ifstream ifs;
    		ifs.open(input_path);
    		_ASSERT(ifs.is_open());
    		ifs >> noskipws;
    		char temp;
    
    		ofstream ofs;
    		ofs.open(output_path);
    		_ASSERT(ofs.is_open());
    		TreeNode* ptr = root;
    		while (!ifs.eof()) {
    			ifs >> temp;
    			if (temp == '0' && ptr->left != nullptr)
    				ptr = ptr->left;
    			else if (temp == '1' && ptr->right != nullptr)
    				ptr = ptr->right;
    			else {
    				ofs << ptr->charcate;
    				if (temp == '0') ptr = root->left;
    				if (temp == '1') ptr = root->right;
    			}
    		}
    	}
    };
    
    int main() {
    	Solution sol;
    	string input_path = "C:\\Users\\426-4\\Desktop\\artic_input.txt";
    	//step1:统计文章中每个字符出现的次数,并保存在map中
    	unordered_map<char, int> map = sol.countC(input_path);
    	//step2:将map中的每一项转化为一个单节点树,构成深林
    	vector<TreeNode*> node = sol.mapToNode(map);
    	//step3:构建霍夫曼树
    	TreeNode* root = sol.creatTree(node);
    	//step4:获得每个字符的编码,保存在map中
    	sol.codeString(root, "");
    	//step5:编码文章的字符,并将编码的结果输出
    	string coding_path = "C:\\Users\\426-4\\Desktop\\artic_coding.txt";
    	sol.coding(input_path, coding_path);
    	//step6:依据编码的文档,加上霍夫曼树的信息,解码文档输出
    	string encoding_path = "C:\\Users\\426-4\\Desktop\\artic_encoding.txt";
    	sol.encoding(coding_path, encoding_path, root);
    	return 0;
    }
    
    展开全文
  • C语言 哈夫曼树编码解码
  • 哈夫曼树与哈夫曼编码以及解码

    多人点赞 2020-07-22 16:23:13
    哈夫曼树即是带权路径最小的二叉树 可以看出,哈夫曼树的特点是 1.权值越大的叶子节点靠根节点越近,越小的越远; 2.只有度为0(叶子节点)和度为2(分支节点)的节点,不存在度为一的节点;(这一特点很重要) ...

    先来一张图,看看程序的效果OvO
    怎么样,484很心动??
    放心,我是不会告诉你我把完整代码都放在最后面了d

    咳咳,回归正题=_=

    接下来是正文

    哈夫曼树即是带权路径最小的二叉树

    可以看出,哈夫曼树的特点是
    1.权值越大的叶子节点靠根节点越近,越小的越远;
    2.只有度为0(叶子节点)和度为2(分支节点)的节点,不存在度为一的节点;(这一特点很重要)
    构建哈夫曼树可以分为三个步骤,选取,合并,删除与加入

    首先选取权值最小的节点2和3,再将它们的权值加起来作为其父节点的权值,最后将合并后的新节点加入原来的集合中。
    重复该操作即可得到哈夫曼树。

    下面的代码是哈夫曼树的构建部分的代码,全部的代码我会在最后面给出来。

    struct Element {
    	int weight;
    	int parent, Lchild, Rchild;
    };
    
    void Select(Element hufftree[], int &i1, int &i2)
    {
    	int min1 = 10000, min2 = 10000, i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min1 > hufftree[i].weight&& hufftree[i].parent == -1)
    		{
    			min1 = hufftree[i].weight;
    			i1 = i;
    		}
    		i++;
    	}
    	i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min2 > hufftree[i].weight&& hufftree[i].parent == -1 && i != i1)
    		{
    			min2 = hufftree[i].weight;
    			i2 = i;
    		}
    		i++;
    	}
    }
    void HuffManTree(Element hufftree[], int n,int w[])//哈夫曼树的创建函数
    {
    	int i1 = 0, i2 = 0;
    	for (int i = 0; i < n; i++)
    	{
    		hufftree[i].weight = w[i];
    	}
    	cout << endl;
    	for (int i = n; i < 2 * n - 1; i++)
    	{
    		Select(hufftree, i1, i2);
    		hufftree[i].weight = hufftree[i1].weight + hufftree[i2].weight;
    		hufftree[i].Lchild = i1; hufftree[i].Rchild = i2;
    		hufftree[i1].parent = i; hufftree[i2].parent = i;
    	}
    }
    

    哈夫曼树的一个重要用途是将叶子节点所包含的信息用二进制编码来表示,也就是编码,并且可以给出的二进制编码来得到里面包含的信息,也就是解码。

    关于编码

    通过该图可以了解到,所谓编码,就是节点位于左边,则编码为0,右边则为1

    void makecode(int q[][10],int road[], Element huffTree[],int n)//编码函数
    {
    	int bianma[10] ;//储存字符的编码
    	int parent = 0, current = 0;
    	memset(bianma,0,sizeof(bianma));
    	int x= 0;//bianma字符串数组的指针
    	for (int i = 0; i < n; i++)
    	{
    		current= i;  //current保存当前节点下标
    		parent = huffTree[current].parent;
    		while (parent!=-1)
    		{
    			if (huffTree[parent].Lchild == current)//当前节点为其双亲的左孩子,编码为0
    			{
    				bianma[x] = 0;
    				road[i]++;
    			}
    			else if (huffTree[parent].Rchild == current)//当前节点为其双亲的右孩子,编码为1
    			{
    				bianma[x] = 1;
    				road[i]++;
    			}
    			x++;
    			current = parent;
    			parent = huffTree[parent].parent;//向上寻找双亲节点
    		}
    		for (int y = 0; y < x; y++)
    		{
    			q[i][y] = bianma[x - y -1];
    		}
    		x = 0;
    	}
    	cout << "编码成功!"<<endl;
    }
    

    而解码便是通过编码表来对给出的二进制编码进行解码,但是给出的编码不一定全是正确的,因此解码函数应该还要拥有报错功能,即指出那部分的编码有误。考虑到篇幅和理解上的问题,这里解码函数不单独列出来了。

    了解了构建,编码,解码过程下面就是具体的代码了(由于把编码和解码函数都加在了里面所以代码会有点长)
    该程序的主要功能是:输入一段字符串后,输给出字符串中不同字符出现的次数,即所对应的权值,哈夫曼树表,不同字符对应的编码,以及其到根节点的路径长度,再输入二进制编码,即可得到对应的解码。

    #include<iostream>
    #include<string.h>
    #include<iomanip>
    using namespace std;
    
    const int SIZE = 100;
    
    struct Element {
    	int weight;
    	int parent, Lchild, Rchild;
    };
    
    void Select(Element hufftree[], int &i1, int &i2)
    {
    	int min1 = 10000, min2 = 10000, i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min1 > hufftree[i].weight&& hufftree[i].parent == -1)
    		{
    			min1 = hufftree[i].weight;
    			i1 = i;
    		}
    		i++;
    	}
    	i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min2 > hufftree[i].weight&& hufftree[i].parent == -1 && i != i1)
    		{
    			min2 = hufftree[i].weight;
    			i2 = i;
    		}
    		i++;
    	}
    }
    void HuffManTree(Element hufftree[], int n,int w[])//哈夫曼树的创建函数
    {
    	int i1 = 0, i2 = 0;
    	for (int i = 0; i < n; i++)
    	{
    		hufftree[i].weight = w[i];
    	}
    	cout << endl;
    	for (int i = n; i < 2 * n - 1; i++)
    	{
    		Select(hufftree, i1, i2);
    		hufftree[i].weight = hufftree[i1].weight + hufftree[i2].weight;
    		hufftree[i].Lchild = i1; hufftree[i].Rchild = i2;
    		hufftree[i1].parent = i; hufftree[i2].parent = i;
    	}
    }
    int findelementNum(char code[], char p[],int w[])//找出字符串中的不同字符,并计算其权重
    {
    	if (strlen(code) == 0)return 0;
    	int num = 1;//记录code中不同的字符个数
    	p[0] = code[0];
    	w[0]++;
    	for (int i = 1; i < strlen(code); i++)
    	{
    		for (int j = 0; j < num; j++)
    		{
    			if (code[i] == p[j])//code[i]已经出现过,则其权值加1,并退出内循环
    			{
    				w[j]++; 
    				break;
    			}
    			if (j == num - 1)//code[i]未出现过,则录入p中,其权值变为1
    			{
    				p[num] = code[i];
    				w[num]++;
    				num++;
    				break;
    			}
    		}
    	}
    	return num;
    }
    
    void makecode(int q[][10],int road[], Element huffTree[],int n)//编码函数
    {
    	int bianma[10] ;//储存字符的编码
    	int parent = 0, current = 0;
    	memset(bianma,0,sizeof(bianma));
    	int x= 0;//bianma字符串数组的指针
    	for (int i = 0; i < n; i++)
    	{
    		current= i;  //current保存当前节点下标
    		parent = huffTree[current].parent;
    		while (parent!=-1)
    		{
    			if (huffTree[parent].Lchild == current)//当前节点为其双亲的左孩子,编码为0
    			{
    				bianma[x] = 0;
    				road[i]++;
    			}
    			else if (huffTree[parent].Rchild == current)//当前节点为其双亲的右孩子,编码为1
    			{
    				bianma[x] = 1;
    				road[i]++;
    			}
    			x++;
    			current = parent;
    			parent = huffTree[parent].parent;//向上寻找双亲节点
    		}
    		for (int y = 0; y < x; y++)
    		{
    			q[i][y] = bianma[x - y -1];
    		}
    		x = 0;
    	}
    	cout << "编码成功!"<<endl;
    }
    
    void decode(int code2[],Element Hufftree[],char p[],int n)//解码函数
    {
    	int i = 0, j = 2 * n - 2, x = 0, count = 0;//j为根节点下标
    	while (code2[i] == 1||code2[i]==0)
    	{
    		if (code2[i] == 1)
    		{
    			count++;
    			x = Hufftree[j].Rchild;
    			j = x;//更新根节点
    			if (Hufftree[x].Rchild == -1)//当前节点没有右孩子,说明他为叶子节点(原因是哈夫曼树的特点是只存在度为0和度为2的节点),即找到对应解码
    			{
    				cout << p[x];
    				j = 2 * n - 2;
    				count = 0;
    			}
    			else if (code2[i + 1] == -1 && Hufftree[x].Rchild != -1)//给出的二进制编码已经结束但是却未能找到对应解码,说明这段编码有误
    			{
    				cout << "(第" << i - count+1 << "到第" << i << "号编码有误)";
    				j = 2 * n - 2;
    				count = 0;
    			}
    			
    		}
    		else if (code2[i] == 0)
    		{
    			count++;
    			x = Hufftree[j].Lchild;
    			j = x;
    			if (Hufftree[x].Rchild == -1)
    			{
    				cout << p[x];
    				j = 2 * n - 2;
    				count = 0;
    			}
    			else if (code2[i + 1] == -1 && Hufftree[x].Rchild != -1)
    			{
    				cout << "(第" << i - count+1 << "到第" << i << "号编码有误)";
    				j = 2 * n - 2;
    				count = 0;
    			}
    		}
    		i++;
    	}
    }
    
    void print(int q[][10],char p[],int n)
    {
    	int j = 0;
    	for (int i = 0; i < n; i++)
    	{
    		cout <<p[i] <<":";
    		while (q[i][j] != -1)
    		{
    			cout << q[i][j];
    			j++;
    		}
    		j = 0;
    		cout << endl;
    	}
    }
    int main()
    {
    	Element huffTree[SIZE];
    	int n;//叶子节点的个数
    	int w[SIZE] ;//储存叶子节点的权重
    	int road[SIZE];//储存叶子节点到根节点的路径长度
    	int q[SIZE][10] ;//储存不同字符的编码
    	char code[50];//待编码的字符串
    	char p[27] = { -1 };//储存字符串中不同的字符
    
    	memset(huffTree, -1, sizeof(huffTree));
    	memset(w, 0, sizeof(w));
    	memset(road, 0, sizeof(road));
    	memset(q, -1, sizeof(q));
    
    	
    	cout << "请输入待编码的字符串:";
    	cin >> code;
    	n = findelementNum(code, p, w);
    	cout << "叶子节点个数为:"<<n<<endl;
    	cout << "各叶子节点的权重为:";
    	for (int i = 0; i < n; i++)
    	{
    		cout <<p[i]<<":"<< w[i] << "   ";
    	}
    	HuffManTree(huffTree, n, w);
    	for (int i = 0; i < 2 * n - 1; i++)
    	{
    		cout << setiosflags(ios::left) << setw(4) << i;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].parent;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].Lchild;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].Rchild;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].weight<<endl;
    	}
    	makecode(q,road, huffTree, n);
    	print(q,p, n);
    	cout << "各叶子节点的路径为:" << endl;
    	for (int i = 0; i < n; i++)
    	{
    		cout<<p[i]<<":"<< road[i]<<" ";
    	}
    	cout << endl;
    	int code2[SIZE],t,I=0;
    	memset(code2, -1, sizeof(code2));
    	cout << "请输入待解码编码(以-1截止):";
    	cin >> t;
    	while (t != -1)
    	{
    		code2[I] = t;
    		cin >> t;
    		I++;
    	}
    	decode(code2, huffTree, p, n);
    }
    

    都看到这了还不点个赞吗QvQ

    展开全文
  • 哈夫曼树如果不清楚是什么概念的话可以看一下百度百科的介绍,这里的哈夫曼树节点存储的是char字符 Node节点数据结构: public class Node implements Comparable<Node>{ //需要改写compareTo方法,实现权重...
  • 哈夫曼树及哈夫曼编码解码

    千次阅读 2018-11-02 23:07:35
    哈夫曼树,又称最优树,是带权路径最小的树。 基本概念: 节点间的路径长度:两个节点间所包含的边的数目。 树的路径长度:从根到树中任意节点的路径长度之和。 权:将节点赋予一定的量值,该量值成为权。 树的带权...
  • 根据哈夫曼树进行对字符编码(从根节点出发,往左走为0,往右走为1进行编码);解码过程输入哈夫曼树和压缩码,输出为字符。 package Tree; import java.util.ArrayList; import java.util.Collections; import ...
  • Java哈夫曼编码实验--哈夫曼树的建立,编码与解码建树,造树,编码,解码一、哈夫曼树编码介绍1、哈夫曼树:(1)定义:假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 354
精华内容 141
关键字:

哈夫曼树编码解码