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

寻123

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

这是一些要求，请求大神们帮忙解决，请求代码，谢谢

最佳答案

月排行榜 / 总排行榜

lumber2388779

2017-4-19 17:44:25

寻123 发表于 2017-4-19 17:30
尴尬 ， 尴尬  我就是百度了很久也不知道怎么下手才来求助的

先把创建插入删除二叉树的部分先实现出来，然后在修改成用英文字符和标点空格创建二叉树，再将二叉树通过多种遍历生成english_01.txt，一步步慢慢实现

跳转到最佳答案楼层

lumber2388779

至少你自己写一点代码什么的吧，如果都让别人想好写出来，那样锻炼不了你的编程能力和思维

寻123

lumber2388779 发表于 2017-4-19 15:23
至少你自己写一点代码什么的吧，如果都让别人想好写出来，那样锻炼不了你的编程能力和 ...

尴尬 ， 尴尬  我就是百度了很久也不知道怎么下手才来求助的  

lumber2388779

寻123 发表于 2017-4-19 17:30
尴尬 ， 尴尬  我就是百度了很久也不知道怎么下手才来求助的

先把创建插入删除二叉树的部分先实现出来，然后在修改成用英文字符和标点空格创建二叉树，再将二叉树通过多种遍历生成english_01.txt，一步步慢慢实现

寻123

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. 
    
76.                 printf("a=%d b=%d c=%d d=%d e=%d \n",f[0],f[1],f[2],f[3],f[4]);
    
77.                 printf("f=%d i=%d j=%d k=%d l=%d \n",f[5],f[6],f[7],f[8],f[9]);
    
78.                 printf("m=%d n=%d o=%d p=%d q=%d \n",f[10],f[11],f[12],f[13],f[14]);
    
79.                 printf("r=%d s=%d t=%d u=%d v=%d \n",f[15],f[16],f[17],f[18],f[19]);         
    
80.                 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);
    
81.                
    
82. }

复制代码

寻123

寻123 发表于 2017-4-26 09:46

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. using namespace std;
   
5. 
   
6. #define N 10         // 带编码字符的个数，即树中叶结点的最大个数
   
7. #define M (2*N-1)    // 树中总的结点数目
   
8. 
   
9. class HTNode{        // 树中结点的结构
   
10. public:
    
11.         unsigned int weight;
    
12.         unsigned int parent,lchild,rchild;
    
13. };                    
    
14. 
    
15. class HTCode{
    
16. public:
    
17.         char data;      // 待编码的字符
    
18.         int weight;     // 字符的权值
    
19.         char code[N];   // 字符的编码
    
20. };
    
21. void Init(HTCode hc[], int *n){
    
22.         // 初始化，读入待编码字符的个数n，从键盘输入n个字符和n个权值
    
23.         int i;
    
24.         printf("input n = ");
    
25.         scanf("%d",&(*n));
    
26.        
    
27.         printf("\ninput %d character\n",*n);
    
28.        
    
29.         fflush(stdin);
    
30.         for(i=1; i<=*n; ++i)
    
31.                 scanf("%c",&hc[i].data);
    
32.         printf("\ninput %d weight\n",*n);
    
33.        
    
34.         for(i=1; i<=*n; ++i)
    
35.                 scanf("%d",&(hc[i].weight) );
    
36.         fflush(stdin);
    
37. }//
    
38. 
    
39. void Select(HTNode ht[], int k, int *s1, int *s2){
    
40.         // ht[1...k]中选择parent为0，并且weight最小的两个结点，其序号由指针变量s1，s2指示
    
41.         int i;
    
42.         for(i=1; i<=k && ht[i].parent != 0; ++i){
    
43.                 ; ;
    
44.         }
    
45.         *s1 = i;
    
46.         for(i=1; i<=k; ++i){
    
47.                 if(ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
    
48.                         *s1 = i;
    
49.         }
    
50.         for(i=1; i<=k; ++i){
    
51.                 if(ht[i].parent==0 && i!=*s1)
    
52.                         break;
    
53.         }
    
54.         *s2 = i;
    
55.        
    
56.         for(i=1; i<=k; ++i){
    
57.                 if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
    
58.                         *s2 = i;
    
59.         }
    
60. }
    
61. void HuffmanCoding(HTNode ht[],HTCode hc[],int n){
    
62.         // 构造Huffman树ht，并求出n个字符的编码
    
63.         char cd[N];
    
64.         int i,j,m,c,f,s1,s2,start;
    
65.         m = 2*n-1;
    
66.         for(i=1; i<=m; ++i){
    
67.                 if(i <= n)
    
68.                         ht[i].weight = hc[i].weight;
    
69.                 else
    
70.                         ht[i].parent = 0;
    
71.                 ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
    
72.         }
    
73.         for(i=n+1; i<=m; ++i){
    
74.                 Select(ht, i-1, &s1, &s2);
    
75.                 ht[s1].parent = i;
    
76.                 ht[s2].parent = i;
    
77.                 ht[i].lchild = s1;
    
78.                 ht[i].rchild = s2;
    
79.                 ht[i].weight = ht[s1].weight+ht[s2].weight;
    
80.         }
    
81.         cd[n-1] = '\0';
    
82.         for(i=1; i<=n; ++i){
    
83.                 start = n-1;
    
84.                 for(c=i,f=ht[i].parent; f; c=f,f=ht[f].parent){
    
85.                         if(ht[f].lchild == c)
    
86.                                 cd[--start] = '0';
    
87.                         else
    
88.                                 cd[--start] = '1';
    
89.                 }
    
90.                 strcpy(hc[i].code, &cd[start]);
    
91.         }
    
92. }
    
93. int main()
    
94. {
    
95.         int i,m,n,w[N+1];
    
96.         HTNode ht[M+1];
    
97.         HTCode hc[N+1];
    
98.         Init(hc, &n);     // 初始化
    
99.         HuffmanCoding(ht,hc,n);   // 构造Huffman树，并形成字符的编码
    
100.         for(i=1; i<=n; ++i)  
     
101.                 printf("\n%c---%s",hc[i].data,hc[i].code);  
     
102.         printf("\n");
     
103.         return 0;
     
104. }
     
105. 
     
106. 你能教我将上面的读取到的字母的频率应用到下面的哈弗曼代码中吗？？  我不会将两个连接在一起

复制代码

liutuoyang

斯蒂芬斯蒂芬斯蒂芬

lumber2388779

寻123 发表于 2017-4-26 09:48

抱歉，最近比较忙，有空帮你看下