哈夫曼编解码 完整c程序代码

c语言实现哈夫曼算法以下是C语言实现哈夫曼算法的示例代码：```cinclude <>include <>include <>// 定义哈夫曼树节点结构体typedef struct HuffmanNode {char data; // 节点存储的数据int freq; // 节点出现的频率struct HuffmanNode left, right; // 左右子树指针} HuffmanNode;// 定义创建哈夫曼树函数HuffmanNode createNode(char data, int freq) { HuffmanNode node =(HuffmanNode)malloc(sizeof(HuffmanNode));node->data = data;node->freq = freq;node->left = node->right = NULL;return node;}// 定义比较函数，用于按照频率从小到大排序int compare(const void a, const void b) {return ((HuffmanNode)b)->freq - ((HuffmanNode)a)->freq; }// 定义构建哈夫曼树函数HuffmanNode buildHuffmanTree(char data[], int freq[], int size) { if (size == 1) {return createNode(data[0], freq[0]);} else {HuffmanNode nodes[size]; // 存储所有节点指针的数组for (int i = 0; i < size; i++) {nodes[i] = createNode(data[i], freq[i]);}qsort(nodes, size, sizeof(HuffmanNode), compare); // 按频率从小到大排序return mergeNodes(nodes, size); // 合并两个最小的节点，直到只剩下一个节点}}// 定义合并两个最小节点函数HuffmanNode mergeNodes(HuffmanNode nodes[], int size) {if (size == 0) return NULL; // 空节点返回NULL指针if (size == 1) return nodes[0]; // 只剩下一个节点直接返回该节点指针 HuffmanNode root = createNode('$', nodes[0]->freq + nodes[1]->freq); // 创建根节点，频率为左右子树频率之和root->left = mergeNodes(nodes+1, size-1); // 递归合并剩余节点，左子树指向左子树数组中除第一个节点外的所有节点指针，右子树指向右子树数组中除最后一个节点外的所有节点指针return root; // 返回根节点指针}```。

#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct{char data;int weight;int parent;int lchild;int rchild;}HTNode;HTNode ht[30];typedef struct{char cd[30];int start;}HCode;HCode hcd[30];void CreateHT( HTNode ht[] , int n ) {int i , k , lnode, rnode ;int min1 , min2 ;for ( i = 0 ; i < 2*n-1 ; i++ ){ht[i].parent = ht[i].lchild = ht[i].rchild = 0;}for ( i = n ; i < 2*n-1 ; i++ ){min1 = min2 = 32767;lnode = rnode = 0;for ( k=0 ; k <= i-1; k++)if ( ht[k].parent == 0) {if (ht[k].weight < min1){min2 = min1;min1 = ht[k].weight;rnode = lnode;lnode = k;}else if ( ht[k].weight < min2){min2 = ht[k].weight;rnode = k;}}ht[lnode].parent = i;ht[rnode].parent = i;ht[i].weight = ht[lnode].weight + ht[rnode].weight;ht[i].lchild = lnode;ht[i].rchild = rnode;}}void CreateHCode( HTNode ht[] , HCode hcd[] , int n ){int i , f , c;HCode hc;for( i = 0 ; i < n; i++){hc.start = n;c = i;f = ht[i].parent;while (f != 0){if( ht[f].lchild == c){hc.cd[hc.start--] = '0';}else{hc.cd[hc.start--] = '1';}c=f ;f=ht[f].parent;}hc.start++;hcd[i] = hc;}}void CodeInput(int n,HTNode ht[]){int i;char ch[30];scanf( "%s" , ch );for ( i=0 ; i<n ; i++ ){scanf( "%ld" , &ht[i].weight );}printf("######################################- \n"); }void CodeOutput( int n , HCode hcd[] ){int i , j ;printf (" 所有字符的哈弗曼编码为：");for ( i = 0 ; i < n ; i++ ){for( j=hcd[i].start ; j<=n ; j++ ){printf( "%lc" , hcd[i].cd[j] );}}printf("\n");for ( i=0 ; i<n ; i++ ){printf( " 序号%d : " , i );for( j = hcd[i].start ; j <= n ; j++ ){printf( "%lc" , hcd[i].cd[j] );}printf( "\n" );}}void save( int n ){int i ;FILE *fp;if( ( fp = fopen ( "c:\\data.txt" , "w" ) ) == NULL ) {printf( " can't open this file !!! " ) ;exit(0) ;}else{for ( i = 1 ; i <= n ; i++ ){fprintf( fp , " %ld ", ht[i].weight );}printf(" You have saved it successful !!!");}fclose (fp) ;}void main(){ int num ;char flag ='y';while( flag == 'y' || flag == 'Y' ){system( "cls" );printf(" ################################ \n");printf(" 欢迎使用哈夫曼编码系统\n ");printf(" ################################ \n");printf(" ######## 1. 生成哈夫曼树#########\n");printf(" ######### 2. 哈夫曼编码######### \n");printf(" ######### 3.哈夫曼权值存储######### \n");printf(" ######## 4. 退出########\n");printf(" ##############################\n");printf(" 请选择操作类型( 1 - 4 ) : " );scanf( " %d" , &num );printf("############################################ \n");switch(num){case 1 :int n , i ;printf(" 请输入要输入的字符数量n为: ");if((scanf(" %ld", &n ))&&(n!=0)){printf("\n 请输入%d 个字符和%d 个对应权值<先将所有字符输入再输对应权值> \n 在此输入: " , n , n );CodeInput( n , ht );CreateHT( ht , n );printf(" 对应的权值为：\n");for( i = 0 ; i < n ; i++ ){printf( " %d : %ld " , i , ht[i].weight );if((i+1) % 4 == 0){printf("\n");}}}printf("\n######################################- \n");break;case 2 :CreateHCode( ht , hcd , n );CodeOutput( n , hcd );printf("##############################################-");break;case 3 :save(n);printf("#######################################");break;case 4 :printf("############# **感谢使用本程序** ############### \n ");exit(1);printf("########################################");break;default :printf(" Error ! You must put the number between <1 -- 4> ");printf("\n#####################################\n");}printf(" \n 继续或退出(y or n) : ");getchar() ;flag=getchar();}}。

C++实现哈夫曼编码完整代码（优选.)rd#include<iostream>#include<string>using namespace std;#include<math.h>typedef struct{//霍夫曼树的结构体char ch;double weight; //权值，此处为概率int parent,lchild,rchild;}htnode,*hfmtree;typedef char **hfmcode;/*****************************全局变量*****************************/ hfmtree HT;hfmcode HC;int n=0;//霍夫曼树叶节点个数int m=0;//霍夫曼树所有节点个数int *code_length;//用于记录每个消息字符的码长/*****************************霍夫曼编码模块*****************************/ //对输入的字符进行检验int Input_Char_Check(){ int flag=1; int j;for(int i=1;i<n&&flag;i++)for(j=i+1;j<=n;j++)if(HT[j].ch==HT[i].ch){flag=0;break;}}return flag;}//对输入的概率进行检测int Input_Weight_Check(){int flag=0; double sum=0.0;for(int i=1;i<=n;i++) {if(!(HT[i].weight>0&&HT[i].weight<1))//概率越界{ flag=1; return flag; }else{ sum+=HT[i].weight;continue; }}if(sum>1)//概率之和超过1{flag=2;}return flag;}void Select(int a,int *p1,int *p2) /*Select函数，选出HT树到a为止，权值最小和次小且parent为0的2个节点*/{int i,j,x,y;for(j=1;j<=a;++j){if(HT[j].parent==0){x=j; break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[x].weight&&HT[i].parent==0){x=i; //选出权值最小的节点}}for(j=1;j<=a;++j){if(HT[j].parent==0&&x!=j){y=j; break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i){y=i; //选出权值次小的节点}}if(x>y){*p1=y; *p2=x;}else{*p1=x; *p2=y;}}/*初始化n个叶子节点及其余节点*/void Init_htnode(){int i;char temp_ch;double temp_w;I: cout<<"请输入信源发出的消息字符个数：";cin>>n; if(sizeof(n)!=sizeof(int)||n<=1)//若输入的不是整数，则报错{cout<<"您输入的数据有误，程序终止!"<<endl;exit(0);}code_length=new int[n+1];for(i=1;i<=n;i++){code_length[i]=0;//初始化码长为0}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));printf("请输入字符信息,,字符对应的概率：");for(i=1;i<=n;++i) //初始化n个叶子结点{// printf("请输入第%d个字符信息：",i);cin>>temp_ch;// printf("请输入第%d个字符对应的概率：",i);cin>>temp_w;HT[i].ch=temp_ch;HT[i].weight=temp_w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;} int flag1=Input_Char_Check(); //检测输入的字符是否重复int flag2=Input_Weight_Check(); //检测输入的概率是否越界if(!flag1){cout<<"出现相同字符，输入错误，请重新输入!"<<endl;goto I;}if(flag2==1){cout<<"概率越界，输入错误，请重新输入!"<<endl;goto I;}if(flag2==2){cout<<"概率之和超过1，输入错误，请重新输入!"<<endl;goto I;}for( ;i<=m;++i) //初始化其余的结点{HT[i].ch='*'; //用*表示新生成根节点的字符域HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}} //建立霍夫曼树void Create_hfmtree(){int i;int p1,p2; //用于记录权值最小及次小节点的下标for(i=n+1;i<=m;++i) //建立霍夫曼树{Select(i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}}void Hfm_coding() //求出n个字符的霍夫曼编码HC 及码长{int i,start;int c; //当前字符下标int f; //当前字符的父节点下标char *cd;HC=(hfmcode)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i) //给n个字符编码{start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}else{cd[--start]='1';}code_length[i]+=1;}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);} //初始化/*功能：从终端读入字符集大小n，以及n个字符和n个权值，建立霍夫曼树，并将它存于文件hfmTree中。

#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct{char ch;int weight;int parent,lchild,rchild;}htnode,*hfmtree;typedef char **hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2){int i,j,x,y;for(j=1;j<=a;++j){if(HT[j].parent==0){x=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[x].weight&&HT[i].parent==0){x=i;}}for(j=1;j<=a;++j) {if(HT[j].parent==0&&x!=j){y=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i){y=i;}}if(x>y){*p1=y;*p2=x;}else{*p1=x;*p2=y;}}void hfmcoding(hfmtree &HT,hfmcode &HC,int n) {int i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1){return;}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));for(i=1;i<=n;++i){printf("请输入第%d字符信息和权值：",i);scanf("%c%d",&z,&w);while(getchar()!='\n'){continue;}HT[i].ch=z;HT[i].weight=w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i<=m;++i){HT[i].ch='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;++i){Select(HT,i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}HC=(hfmcode)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}else{cd[--start]='1';}}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}int main(){char code[100],h[100],hl[100];int n,i,j,k,l;ifstream input_file;ofstream output_file;char choice,str[100];hfmtree HT;hfmcode HC;cout<<"\n";while(choice!='Q'&&choice!='q'){cout<<" "<<"*************************赫夫曼编码/译码器*************************\n";cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";cout<<"请输入您要操作的步骤：";cin>>choice;if(choice=='I'||choice=='i'){cout<<"请输入字符个数：";cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;++i){cout<<HT[i].ch<<":"<<HC[i]<<endl;}output_file.open("hfmTree.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}for(i=1;i<=n;i++){output_file<<"("<<HT[i].ch<<HC[i]<<")";}output_file.close();cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"<<endl; }else if(choice=='E'||choice=='e'){printf("请输入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}output_file<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}for(i=0;i<strlen(str);i++){for(j=0;j<=n;++j){if(HT[j].ch==str[i]){output_file<<HC[j];break;}}}output_file.close();cout<<"\n";cout<<"编码完毕，并且已经存入CodeFile.txt文件！\n";input_file.open("CodeFile.txt");if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>code;cout<<"编码码值为："<<code<<endl;input_file.close();}else if(choice=='D'||choice=='d'){input_file.open("CodeFile.txt");if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}k=0;while(h[k]!='\0') {for(i=1;i<=n;i++){l=k;for(j=0;j<strlen(HC[i]);j++,l++){hl[j]=h[l];}hl[j]='\0';if(strcmp(HC[i],hl)==0){output_file<<HT[i].ch;k=k+strlen(HC[i]);break;}}}output_file.close();input_file.open("Textfile.txt");if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>h;cout<<h<<endl;input_file.close();cout<<"译码结束，字符已经存入Textfile.txt文件中！"<<endl;}else if(choice=='Q'||choice=='q') \{exit(0);}else{cout<<"您没有输入正确的步骤，请重新输入！"<<endl;}cout<<endl;}return 0;}。

//哈夫曼编码不唯一！！！！！//只有当哈夫曼树建好之后编码才固定！！！#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct{int weight;int parent,Lchild,Rchlid;}HamNode,*HamTree;typedef char* *HamCode;void select(HamTree *ht,int n,int *s1,int *s2) {int k= 0,temp= 0;for(int i=1;i<= n;i++)if( (*ht)[i].parent == 0){k=(*ht)[i].weight;break;}for(i=1;i<= n;i++){if( (*ht)[i].parent == 0){if( k>= (*ht)[i].weight ){k= (*ht)[i].weight;(*s1)= i;}}}for(i=1;i<= n ;i++)if( (*ht)[i].parent == 0){if(i==(*s1))continue;k=(*ht)[i].weight;break;}for(i=1;i<= n ;i++){if( (*ht)[i].parent == 0 && i!= (*s1)){if( k>= (*ht)[i].weight ){k= (*ht)[i].weight;(*s2)= i;}}}}void CrtTree(HamTree *ht, HamCode *hc,int *w,int n) {int m= 0,s1= 0,s2= 0,start= 0,c= 0,p= 0;char *cd= NULL;m=2*n-1;(*ht)=(HamTree)malloc( (m+1)* sizeof( HamNode)); for (int i=1;i<= n; i++){(*ht)[i].weight= w[i];(*ht)[i].parent= 0;(*ht)[i].Lchild= 0;(*ht)[i].Rchlid= 0;}for (i=n+1; i<=m ;i++){(*ht)[i].weight= 0;(*ht)[i].parent= 0;(*ht)[i].Lchild= 0;(*ht)[i].Rchlid= 0;}for(i=n+1 ;i<=m ;i++){select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2].parent=i;(*ht)[i].Lchild=s1;(*ht)[i].Rchlid=s2;(*ht)[i].weight= (*ht)[s1].weight+ (*ht)[s2].weight; }*hc= (HamCode)malloc((n+1)* sizeof(char * ));cd= (char *)malloc(n* sizeof(char));cd[n-1]= '\0';for (i= 1;i<=n ;i++ ){start= n-1;for(c= i,p=(*ht)[i].parent ;p!= 0 ;c= p,p= (*ht)[p].parent) if( (*ht)[p].Lchild== c)cd[--start]= '0';elsecd[--start]= '1';(*hc)[i]= (char *)malloc( (n-start)*sizeof(char) );strcpy( (*hc)[i], &cd[start]);}free(cd);}void visit( HamCode *hc ,int n){for(int i=1;i<=n ;i++){printf("\n%s", (*hc)[i]);}}#define N 7void main(){HamTree ht;HamCode hc;int w[N+1];printf("请输入权值:\n");for(int i=1;i<= N;i++){printf("请输入权值[%d]:\n",i);scanf("%d", &w[i]);}CrtTree(&ht, &hc,w,N);visit(&hc,N);}。

哈夫曼信源编码c语言程序代码哈夫曼编码的C语言实现编码原理程序步骤的分析：哈夫曼码是用概率匹配方法进行信源编码。

编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。

程序步骤：（见信息论课本p88页内容）（l）将信号源的符号按照出现概率递减的顺序排列。

（2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率（3）重排后的两个概率最小符号重复步骤(2)过程。

（4）不断继续上述过程，直到最后两个符号配以0和1为止（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。

根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。

哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。

每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。

程序源代码如下;#include stdio.h#include malloc.h #include conio.h #include string.h #include stdlib.h #define HuffmanTree HF #define HuffmanCode HMC typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HF; typedef char **HMC; typedef struct { unsigned int s1; unsigned int s2; } MinCode; void Error(char *message); HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n); MinCode Select(HF HT,unsigned int n); void Error(char *message) { fprintf(stderr,“Error:%s\n",message); exit(1); } HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n) { unsigned int i,s1=0,s2=0; HF p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error("Code too small!"); m=2*n-1;HT=(HF)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;ii++,p++,w++) { p-weight=*w; p-parent=0; p-lchild=0; p-rchild=0; } for(;ii++,p++) { p-weight=0; p-parent=0; p-lchild=0; p-rchild=0; } for(i=n+1;ii++){ min=Select(HT,i-1); s1=min.s1; s2=min.s2;HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight; } printf("HT List:\n");printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n"); for(i=1;ii++) printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);HC=(HMC)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *)); cd[n-1]='\0'; for(i=1;ii++) { start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char *)); strcpy(HC[i],cd[start]); } free(cd); return HC; } void main() {MinCode Select(HF HT,unsigned int n); HF HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; printf("请输入节点个数n:"); scanf("%d", w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));w=0; printf("请输入权重:\n"); for(i=1;ii++) { printf("w[%d]=",i);scanf("%d",w[i]); } HC=HuffmanCoding(HT,HC,w,n); printf("HMC:\n");printf("Number\t\tWeight\t\tCode\n"); for(i=1;ii++)printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]); } MinCode Select(HF HT,unsigned int n) { unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code;s1=1;s2=1; for(i=1;ii++) if(HT[i].parent==0) { min=HT[i].weight; s1=i; break; } tempi=i++; for(;ii++) if(HT[i].weightminHT[i].parent==0){ min=HT[i].weight; s1=i; } for(i=tempi;ii++) if(HT[i].parent==0i!=s1){ secmin=HT[i].weight; s2=i; break; } for(i=1;ii++)if(HT[i].weightsecmini!=s1HT[i].parent==0) { secmin=HT[i].weight; s2=i; } if(s1s2){ temp=s1; s1=s2; s2=temp; } code.s1=s1; code.s2=s2; return code; } 运行结果如下：请输入节点个数n:5请输入权重:w=2 w=3 w=1 w=1 w=3 Number Weight Code 1 2 00 2 3 10 3 1 010 4 1 011 5 3 11 Press any key to continue编程感想及总结：正如事物均具有两面性，哈夫曼编码也具有优点和缺点，比如哈夫曼编码可以取得较好的荣誉压缩效果，使得输出码元概率均匀化。

哈夫曼编解码完整c程序代码Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。

2）要求：一个完整的huffman编解码系统应该具有以下功能：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。

编码（Encoding）。

利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

解码（Decoding）。

利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。

打印代码文件（Print）。

将文件CodeFile以紧凑的格式显示在终端上，每行50 个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

打印Huffman树（Tree Printing）。

将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。

3) 测试数据: 用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符 A B C D E F G H I J K L M 频度1866413223210321154757153220 字符 N O P Q R S T U V W X Y Z 频度5763151485180238181161 完整代码如下：#include<stdio、h>#include<iostream>#include<string>#define N100int*w;char *c,stack[N],code[N][N];int s1,s2;typedef struct HuffmanTree{int weight;int parent;int lchild;int rchild;}HuffmanTree,*Huff;void menu(void); voidSelect(struct HuffmanTree HT[],int i); voidHuffmanTree(Huff &HT,int *w,int n);void visite(HuffHT,int i,int flag,int rear);void translatef(char*scource,char *save,int n);bool uncodef(FILE *fp1,FILE*fp2,Huff HT,int n);int inputHuff();void screanio(int n);void fileio(int n);int initHuff();void Print_tree(int n,Huff HT);void Convert_tree(Huff HT,unsigned charT[100][100],int tt[100][100],int s,int *i,int j);void decoding(int n);void coding(int n);void main(){intn=0;menu();Huff HT;char state;do{std::cout<<"input:\n";std::cin>>state;fflush(stdin); //读取状态switch(state){ caseI:n=inputHuff();HuffmanTree(HT,w,n);st d::cout<<"\nHuffmanTree 初始化完毕\n";break;caseC:coding(n);break; caseD:decoding(n);break;caseP:Print_tree(n,HT);break;caseQ:break;}}while(state!=Q);}void menu()//显示菜单函数{std::cout<<"===========HuffmanCoding===========\n"; std::cout<<"input \t\t do\n";std::cout<<"I\t\tInit_HUffTree\n"; //初始化huffmantreestd::cout<<"C \t\tCoding\n"; //对ToBeTran、txt文件中的字符进行编码到CodeFile、txt中std::cout<<"D \t\tUnCoding\n"; //对CodeFile、txt中的01序列进行解码到TextFile、txtstd::cout<<"P \t\tPrintTree\n"; //打印哈夫曼树std::cout<<"Q \t\tquit\n";std::cout<<"请初始化哈夫曼树再执行后面的操作\n";}int inputHuff()//输入各个字母及其权值{int i=1,n=0;int ww[28];char cc[28];while(1){std::cout<<"input the letter(input # to stop):";cc[i]=std::cin、get();fflush(stdin);if(cc[i]==#)break;std::cout<<"inputtheweight:";std::cin>>ww[i];fflush(stdin);n++;i++;}w=(int *)malloc(sizeof(int)*(n+1));c=(char*)malloc(sizeof(char)*(n+1));for(i=0;i<n+1;i++){w[i]=ww[i ];c[i]=cc[i];}return n;}void HuffmanTree(Huff &HT,int*w,int n)//初始化哈夫曼树{int m,i;m=n*2-1;HT=(struct HuffmanTree *)malloc(sizeof(structHuffmanTree)*(m+1));HT[0]、lchild=0;HT[0]、parent=0;HT[0]、rchild=0;HT[0]、weight=0;for(i=1;i<m;i++){HT[i]、weight=i<=n?w[i]:0;HT[i]、lchild=HT[i]、rchild=HT[i]、parent=0;}for(i=n+1;i<=m;i++){ Select(HT,i);HT[i]、lchild=s1;HT[i]、rchild=s2;HT[i]、weight=HT[s1]、weight+HT[s2]、weight;HT[s1]、parent=HT[s2]、parent=i;}}void Select(struct HuffmanTree HT[],int i) //在HT[1、、i-1]中选择parent为0且weight为最小的两个结点{ int j;for(j=1;j<i;j++){if(HT[j]、parent==0){s1=j;s2=j;goto flag;}}flag:for(j=s1+1;j<i;j++){if(HT[j]、parent==0){if(HT[s1]、weight >=HT[j]、weight){s2=s1;s1=j;}if(HT[s2]、weight>HT[j]、weight&&j!=s1)s2=j;if(s1==s2)s2=j;}}}void Print_tree(int n,Huff HT)//以凹入法的形式打印树{ unsigned char T[100][100];int tt[100][100]; int i,j,m=0; FILE *fp;Convert_tree(HT,T,tt,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint、txt","wb+"))==NULL)printf("Open file treeprint、txt error!\n");printf("\n以凹凸表形式打印已建好的赫夫曼树：\n");for(i=1;i<=2*n-1;i++){ for (j=0;T[i][j]!=0;j++){ if(T[i][j]== ){printf(" ");fputc(T[i][j],fp);} else{printf("%d",tt[i][j]);fprintf(fp,"%d\n\n\n",tt[i][j]);} } printf("\n"); } fclose(fp); printf("\n此字符形式的哈夫曼树已写入文件treeprint、txt中、\n\n"); printf("\n文件treeprint、txt的打开方式要为写字板，若打开方式为记事本，则无法显示凹凸表的形式\n"); } void Convert_tree(HuffHT,unsigned char T[100][100],int tt[100][100],int s,int*i,int j)//将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中{ int k,l; l=++(*i); for(k=0;k<s;k++)T[l][k]= ; T[l][k]=#; tt[l][k]=HT[j]、weight;if(HT[j]、lchild)Convert_tree(HT,T,tt,s+1,i,HT[j]、lchild); if(HT[j]、rchild)Convert_tree(HT,T,tt,s+1,i,HT[j]、rchild);T[l][++k]=\0; } void coding(int n)//对文件ToBeTran、txt编码到CodeFile、txt{ FILE*fp1;Huff HT;HuffmanTree(HT,w,n);visite(HT,2*n-1,2,0);fflush(stdin);translatef("ToBeTran、txt","CodeFile、txt",n);fp1=fopen("CodeFile、txt","r");printf("\n编码已写入文件treeprint、txt中、\n");fclose(fp1);}void decoding(int n)//对CodeFile、txt中的01序列进行解码到TextFile、txt{FILE *fp1,*fp2;HuffHT;HuffmanTree(HT,w,n);fp1=fopen("CodeFile、txt","r");fp2=fopen("TextFile、txt","w");while(uncodef(fp1,fp2,HT,2*n-1));printf("\n");printf("\n解码已写入文件TextFile、txt 中、\n");fclose(fp1);fclose(fp2);}void visite(Huff HT,int i,int flag,int rear)//通过递归调用visite()函数，得到各个字母的编码，存储于全局变量code[][]中{intj=0,k=0;if(flag==0){ stack[rear]=0;rear++;}elseif(flag==1){stack[rear]=1;rear++;}if(HT[i]、lchild==0){for(j=0;j<rear;j++){code[i][j]=stack[j];}code[ i][j]=#;rear--;return;}visite(HT,HT[i]、lchild,0,rear);visite(HT,HT[i]、rchild,1,rear);k=rear;for(j=0;j<k;j++){code[i][j]=stack[j ];}code[i][j]=#;rear--;return;}void translatef(char*scource,char *save,int n)//读取文件中的字母序列，并根据code[][]将其转换成01序列输出{FILE *fp1,*fp2;char p= ;int i=0,j=0,k=0;fp1=fopen(scource,"r");fp2=fopen(save,"w");p= fgetc(fp1);printf("\n得到的编码为:\n");while(p!=EOF){for(i=0;i<=n;i++){if(c[i]==p){for(j =0;j<N&&code[i][j]!=#;j++){fputc(code[i][j],fp2);putchar( code[i][j]);k++;if(k>=50){k=0;putchar(\n);}}}}p=fgetc(fp1 );}fclose(fp1);fclose(fp2);}bool uncodef(FILE *fp1,FILE *fp2,Huff HT,int n)//通过对树的访问，把文件中01序列转换成一个字母输出。

C++实现哈夫曼编码完整代码#include <iostream>#include <queue>#include <vector>#include <map>#include <string>using namespace std;class Node {public:char c; //表示字符int frequency; //表示该字符出现的次数或频率Node *left;Node *right;Node(char _c, int f, Node *l = NULL, Node *r = NULL):c(_c), frequency(f), left(l), right(r) { }bool operator<(const Node &node) const { //重载<运算法以至于在加入优先队列的时候决定如何处理结点位置return frequency > node.frequency;}};void initNode(priority_queue<Node> &q, int nodeNum) {char c;int frequency;for (int i = 0; i < nodeNum; i++) {cout << "输入字符和结点出现的次数: ";cin >> c >> frequency;Node node(c, frequency);q.push(node);}}void showNode(priority_queue<Node> q) {while (!q.empty()) {Node node = q.top(); q.pop();cout << node.c << ", " << node.frequency << endl;}}//构造哈夫曼树void huffmanTree(priority_queue<Node> &q) {while (q.size() != 1) {Node *left = new Node(q.top()); q.pop();Node *right = new Node(q.top()); q.pop();Node node('R', left->frequency + right->frequency, left, right);q.push(node);}}// 打印哈夫曼编码void huffmanCode(Node *root, string &prefix, map<char, string> &result) { string m_prefix = prefix;if (root->left == NULL)return;//处理左子树prefix += "0";//如果是叶子结点则输出,否则递归打印左子树if (root->left->left == NULL)result[root->left->c] = prefix;//cout << root->left->c << ": " << prefix << endl;elsehuffmanCode(root->left, prefix, result);//还原原来的路径,回溯prefix = m_prefix;//处理右子树prefix += "1";//如果是叶子结点，则输出, 否则递归打印右子树if (root->right->right == NULL)result[root->right->c] = prefix;//cout << root->right->c << ": " << prefix << endl;elsehuffmanCode(root->right, prefix, result);}void testResult(map<char, string> result) {//迭代map容器map<char, string>::const_iterator it = result.begin(); while (it != result.end()) {cout << it->first << ": " << it->second << endl;++it;}}int main() {priority_queue<Node> q;int nodeNum;//初始化字符信息cout << "请输入结点个数: ";cin >> nodeNum;initNode(q, nodeNum);//showNode(q);//构造哈夫曼树huffmanTree(q);//构造哈夫曼编码Node root = q.top();string prefix = "";map<char, string> result;huffmanCode(&root, prefix, result);//检验结果是否正确testResult(result);return 0;}。

用c语言实现哈夫曼编码哈夫曼编码是一种用于无损数据压缩的熵编码算法。

以下是一个简单的使用C语言实现哈夫曼编码的例子。

这个例子只实现了编码过程，没有实现解码过程。

c复制代码#include<stdio.h>#include<stdlib.h>#include<string.h>// 节点结构体typedef struct Node {char data;int freq;struct Node *left, *right;} Node;// 创建新节点Node* newNode(char data, int freq) {Node* node = (Node*) malloc(sizeof(Node));node->data = data;node->freq = freq;node->left = node->right = NULL;return node;}// 计算前缀和int getSum(Node* root) {if (!root) return0;return root->freq + getSum(root->left) + getSum(root->right);}// 创建哈夫曼树Node* createHuffmanTree(char data[], int freq[], int size) { if (size == 0) return NULL;Node *left = newNode(data[size-1], freq[size-1]);Node *right = createHuffmanTree(data, freq, size-1);Node *top = newNode(0, getSum(right));top->left = left;top->right = right;return top;}// 打印哈夫曼编码void printHuffmanCode(Node* root, int n, char code[]) {if (!root) return;if (root->data != 0) printf("%c: ", root->data);code[n] = root->data;printHuffmanCode(root->left, n+1, code);printHuffmanCode(root->right, n+1, code);}int main() {char data[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};int freq[] = {5, 9, 12, 13, 16, 45};int size = sizeof(data)/sizeof(data[0]);Node* root = createHuffmanTree(data, freq, size);char code[256] = {0}; // 存放哈夫曼编码，初始为空字符串，表示没有编码，对应字符的编码为空字符串。

以下是C语言实现哈夫曼树编码的示例代码：```c#include <stdio.h>#include <stdlib.h>// 定义结构体表示节点struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};// 创建新节点struct TreeNode* newNode(int val) {struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;}// 计算权值和int calculateWeightSum(struct TreeNode* root) {if (root == NULL) {return 0;}return root->val + calculateWeightSum(root->left) + calculateWeightSum(root->right);}// 构建哈夫曼树struct TreeNode* buildHuffmanTree(int** freq, int size) {// 创建频率数组int arr[size];for (int i = 0; i < size; i++) {arr[i] = freq[i][0];}// 构建哈夫曼树struct TreeNode* root = NULL;int index = 0;while (index < size) {int min1 = INT_MAX, min2 = INT_MAX;int min1Index = -1, min2Index = -1;for (int i = 0; i < size; i++) {if (arr[i] < min1 && arr[i] != 0) {min1 = arr[i];min1Index = i;}if (arr[i] < min2 && arr[i] != 0) {min2 = arr[i];min2Index = i;}}// 创建新节点作为左右子树，并加入频率数组中arr[min1Index] = 0;arr[min2Index] = 0;struct TreeNode* left = newNode(min1);struct TreeNode* right = newNode(min2);left->left = right;right->right = left;// 将左右子树作为新的根节点，并更新频率数组和根节点指针if (root == NULL) {root = left;} else {struct TreeNode* parent = root;while (parent->left != NULL) {parent = parent->left;}parent->left = left;left->parent = parent;while (parent->right != NULL) {parent = parent->right;}parent->right = right;right->parent = parent;}index += 2; // 跳过左右子树，继续寻找下一对最小的节点构建子树，直到遍历完所有节点为止。