哈夫曼编码译码系统(树应用)

1、实验三 哈夫曼编码/译码系统（树应用）一、实验目的1. 帮助读者复习C+语言程序设计中的知识。2.哈夫曼树的建立，哈夫曼编码的生成，对编码信息的翻译的熟悉和运用。需求分析 利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。二、实验内容和要求问题要求利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信

2、息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。问题分析在本例中设置发送者和接受者两个功能，发送者的功能包括：输入待传送的字符信息；统计字符信息中出现的字符种类数和各字符出现的次数（频率）；根据字符的种类数和各自出现的次数建立哈夫曼树；利用以上哈夫曼树求出各字符的哈夫曼编码；将字符信息转换成对应的编码信息进行传送。接受者的功能包括：接收发送者传送来的编码信息；利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。本实验首先从文件中读取数据，然后分析数据对不同的元素依次存入一字符数组并统计其出现的次数并当做其权值，然后根据这些信息建立哈弗曼

3、树，并对各个字符进行哈弗曼编码然后根据各个字符的编码对所有输入的一组字符进行哈弗曼编码。译码是根据哈弗曼树和接收到的一组编码进行译码操作。译码也就是对哈弗曼树的遍历三、算法设计首先读入一组字符，然后统计这些字符中不同字符出现的次数，并当做其权值，然后根据不同字符及其权值建立哈弗曼树。建立哈弗曼树后即可得到这些不同字符的哈弗曼编码，然后即可根据这些哈弗曼编码对那组输入的一串字符进行哈弗曼编码。译码是根据一组编码翻译成一组字符的操作，其算法就是根据这一串编码来对哈弗曼树进行遍历，每遍历到一个叶子结点即输出一个字符，直至将编码操作完即可完成多编码的翻译操作。四、调试分析及数据测试输入编码五、测试结果

4、程序符合算法要求，能正确编码#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) /Se

5、lect函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i; /选出最小的节点for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&HTi.par

6、ent=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) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HCint 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) /初始化n个叶子结点printf("请

7、输入第%d字符信息和权值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i) /初始化其余的结点HTi.ch='0'HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i) /建立赫夫曼树Select(HT,i-1,&

8、amp;p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-star

9、t='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n"cout<<" "

10、<<"计算机科学与技术"<<" "<<"201200814212"<<" "<<"董方园n"while(choice!='Q'&&choice!='q') /当choice的值不为q且不为Q时循环cout<<" "<<"*赫夫曼编码/译码器*n"cout<<" "<<"I.

11、Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exitn"cout<<"请输入您要操作的步骤："cin>>choice;if(choice='I'|choice='i') /初始化赫夫曼树cout<<"请输入字符个数："cin&g

12、t;>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<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<<"("<<HTi.ch<

13、;<HCi<<")"output_file.close();cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"<<endl;else if(choice='E'|choice='e') /进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf("请输入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_fi

14、le)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(HTj

15、.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"cout<<"编码完毕，并且已经存入CodeFile.txt文件！n"input_file.open("CodeFile.txt"); /从CodeFile.txt中读入编码，输出在终端if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_file>>

16、code;cout<<"编码码值为："<<code<<endl;input_file.close();else if(choice='D'|choice='d') /读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中input_file.open("CodeFile.txt");if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_

17、file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;k=0;while(hk!='0') /先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l+)hlj=hl;hlj='0'if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("Textfile.txt");if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_file>&