鱼C论坛

 找回密码
 立即注册
查看: 3286|回复: 7

[已解决]哈弗曼树的在二进制编码中的应用

[复制链接]
发表于 2017-4-19 09:35:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
给定一篇英语短文(English.txt),编写程序实现如下功能:
1、        统计短文中个英文字符和标点、空格出现的频率;
2、        以这些字符出现的频率为叶子节点的权值,建立一棵哈夫曼树,即最优二叉树,程序输出编码方案;
3、        用该编码方案对短文编码,生成english_01.txt;
4、        对english_01.txt反编码,生成english_inverse.txt;

这是一些要求,请求大神们帮忙解决,请求代码,谢谢
最佳答案
2017-4-19 17:44:25
寻123 发表于 2017-4-19 17:30
尴尬 , 尴尬  我就是百度了很久也不知道怎么下手才来求助的

先把创建插入删除二叉树的部分先实现出来,然后在修改成用英文字符和标点空格创建二叉树,再将二叉树通过多种遍历生成english_01.txt,一步步慢慢实现
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-19 15:23:58 | 显示全部楼层
至少你自己写一点代码什么的吧,如果都让别人想好写出来,那样锻炼不了你的编程能力和思维
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-19 17:30:49 | 显示全部楼层
lumber2388779 发表于 2017-4-19 15:23
至少你自己写一点代码什么的吧,如果都让别人想好写出来,那样锻炼不了你的编程能力和 ...

尴尬 , 尴尬  我就是百度了很久也不知道怎么下手才来求助的  
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-19 17:44:25 | 显示全部楼层    本楼为最佳答案   
寻123 发表于 2017-4-19 17:30
尴尬 , 尴尬  我就是百度了很久也不知道怎么下手才来求助的

先把创建插入删除二叉树的部分先实现出来,然后在修改成用英文字符和标点空格创建二叉树,再将二叉树通过多种遍历生成english_01.txt,一步步慢慢实现
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-26 09:46:25 | 显示全部楼层
lumber2388779 发表于 2017-4-19 17:44
先把创建插入删除二叉树的部分先实现出来,然后在修改成用英文字符和标点空格创建二叉树,再将二叉树通过 ...
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void main(){
  4.         int number=0,other=0,space=0;
  5.         char as[500],*ps;
  6.         int f[27];
  7.         FILE *fp;
  8.         if((fp=fopen("E:\\english.txt","r"))==NULL){
  9.                 printf("cannot open file.\n");
  10.                 exit(0);
  11. }
  12.         fgets(as,499,fp);
  13.         fclose(fp);
  14.         for(int i=0;i<28;i++){
  15.                 f[i]=0;
  16.         for( ps=as;*ps!='\0';ps++)
  17.                 if( *ps=='A'||*ps=='a')
  18.                         f[0]++;
  19.                 else if( *ps=='B'||*ps=='b')
  20.                         f[1]++;
  21.                 else if( *ps=='C'||*ps=='c')
  22.                         f[2]++;
  23.                 else if( *ps=='D'||*ps=='d')
  24.                         f[3]++;
  25.                 else if( *ps=='E'||*ps=='e')
  26.                         f[4]++;
  27.                 else if( *ps=='F'||*ps=='f')
  28.                         f[5]++;
  29.                 else if( *ps=='G'||*ps=='g')
  30.                         f[6]++;
  31.                 else if( *ps=='H'||*ps=='h')
  32.                         f[7]++;
  33.                 else if( *ps=='I'||*ps=='i')
  34.                         f[8]++;
  35.                 else if( *ps=='J'||*ps=='j')
  36.                         f[9]++;
  37.                 else if( *ps=='K'||*ps=='k')
  38.                         f[10]++;
  39.                 else if( *ps=='L'||*ps=='l')
  40.                         f[11]++;
  41.                 else if( *ps=='M'||*ps=='m')
  42.                         f[12]++;
  43.                 else if( *ps=='N'||*ps=='n')
  44.                         f[13]++;
  45.                 else if( *ps=='O'||*ps=='o')
  46.                         f[14]++;
  47.                 else if( *ps=='P'||*ps=='p')
  48.                         f[15]++;
  49.                 else if( *ps=='Q'||*ps=='q')
  50.                         f[16]++;
  51.                 else if( *ps=='R'||*ps=='r')
  52.                         f[17]++;
  53.                 else if( *ps=='S'||*ps=='s')
  54.                         f[18]++;
  55.                 else if( *ps=='T'||*ps=='t')
  56.                         f[19]++;
  57.                 else if( *ps=='U'||*ps=='u')
  58.                         f[20]++;
  59.                 else if( *ps=='V'||*ps=='v')
  60.                         f[21]++;
  61.                 else if( *ps=='W'||*ps=='w')
  62.                         f[22]++;
  63.                 else if( *ps=='X'||*ps=='x')
  64.                         f[23]++;
  65.                 else if( *ps=='Y'||*ps=='y')
  66.                         f[24]++;
  67.                 else if( *ps=='Z'||*ps=='z')
  68.                         f[25]++;
  69.                 else if( *ps<='9'&&*ps>='0')
  70.                         number++;
  71.                 else if(*ps==' ')
  72.                         space++;
  73.                 else other++;
  74.                 }

  75.                 printf("a=%d b=%d c=%d d=%d e=%d \n",f[0],f[1],f[2],f[3],f[4]);
  76.                 printf("f=%d i=%d j=%d k=%d l=%d \n",f[5],f[6],f[7],f[8],f[9]);
  77.                 printf("m=%d n=%d o=%d p=%d q=%d \n",f[10],f[11],f[12],f[13],f[14]);
  78.                 printf("r=%d s=%d t=%d u=%d v=%d \n",f[15],f[16],f[17],f[18],f[19]);         
  79.                 printf("w=%d x=%d y=%d z=%d number=%d space=%d other=%d \n",f[20],f[21],f[22],f[23],f[24],f[25],number,space,other);
  80.                
  81. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-26 09:48:09 | 显示全部楼层
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;

  5. #define N 10         // 带编码字符的个数,即树中叶结点的最大个数
  6. #define M (2*N-1)    // 树中总的结点数目

  7. class HTNode{        // 树中结点的结构
  8. public:
  9.         unsigned int weight;
  10.         unsigned int parent,lchild,rchild;
  11. };                    

  12. class HTCode{
  13. public:
  14.         char data;      // 待编码的字符
  15.         int weight;     // 字符的权值
  16.         char code[N];   // 字符的编码
  17. };
  18. void Init(HTCode hc[], int *n){
  19.         // 初始化,读入待编码字符的个数n,从键盘输入n个字符和n个权值
  20.         int i;
  21.         printf("input n = ");
  22.         scanf("%d",&(*n));
  23.        
  24.         printf("\ninput %d character\n",*n);
  25.        
  26.         fflush(stdin);
  27.         for(i=1; i<=*n; ++i)
  28.                 scanf("%c",&hc[i].data);
  29.         printf("\ninput %d weight\n",*n);
  30.        
  31.         for(i=1; i<=*n; ++i)
  32.                 scanf("%d",&(hc[i].weight) );
  33.         fflush(stdin);
  34. }//

  35. void Select(HTNode ht[], int k, int *s1, int *s2){
  36.         // ht[1...k]中选择parent为0,并且weight最小的两个结点,其序号由指针变量s1,s2指示
  37.         int i;
  38.         for(i=1; i<=k && ht[i].parent != 0; ++i){
  39.                 ; ;
  40.         }
  41.         *s1 = i;
  42.         for(i=1; i<=k; ++i){
  43.                 if(ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
  44.                         *s1 = i;
  45.         }
  46.         for(i=1; i<=k; ++i){
  47.                 if(ht[i].parent==0 && i!=*s1)
  48.                         break;
  49.         }
  50.         *s2 = i;
  51.        
  52.         for(i=1; i<=k; ++i){
  53.                 if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
  54.                         *s2 = i;
  55.         }
  56. }
  57. void HuffmanCoding(HTNode ht[],HTCode hc[],int n){
  58.         // 构造Huffman树ht,并求出n个字符的编码
  59.         char cd[N];
  60.         int i,j,m,c,f,s1,s2,start;
  61.         m = 2*n-1;
  62.         for(i=1; i<=m; ++i){
  63.                 if(i <= n)
  64.                         ht[i].weight = hc[i].weight;
  65.                 else
  66.                         ht[i].parent = 0;
  67.                 ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
  68.         }
  69.         for(i=n+1; i<=m; ++i){
  70.                 Select(ht, i-1, &s1, &s2);
  71.                 ht[s1].parent = i;
  72.                 ht[s2].parent = i;
  73.                 ht[i].lchild = s1;
  74.                 ht[i].rchild = s2;
  75.                 ht[i].weight = ht[s1].weight+ht[s2].weight;
  76.         }
  77.         cd[n-1] = '\0';
  78.         for(i=1; i<=n; ++i){
  79.                 start = n-1;
  80.                 for(c=i,f=ht[i].parent; f; c=f,f=ht[f].parent){
  81.                         if(ht[f].lchild == c)
  82.                                 cd[--start] = '0';
  83.                         else
  84.                                 cd[--start] = '1';
  85.                 }
  86.                 strcpy(hc[i].code, &cd[start]);
  87.         }
  88. }
  89. int main()
  90. {
  91.         int i,m,n,w[N+1];
  92.         HTNode ht[M+1];
  93.         HTCode hc[N+1];
  94.         Init(hc, &n);     // 初始化
  95.         HuffmanCoding(ht,hc,n);   // 构造Huffman树,并形成字符的编码
  96.         for(i=1; i<=n; ++i)  
  97.                 printf("\n%c---%s",hc[i].data,hc[i].code);  
  98.         printf("\n");
  99.         return 0;
  100. }

  101. 你能教我将上面的读取到的字母的频率应用到下面的哈弗曼代码中吗??  我不会将两个连接在一起
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-2 13:00:44 | 显示全部楼层
斯蒂芬斯蒂芬斯蒂芬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-2 15:38:55 From FishC Mobile | 显示全部楼层
寻123 发表于 2017-4-26 09:48

抱歉,最近比较忙,有空帮你看下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 00:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表