哈夫曼编码实验报告材料

1、标准文案哈夫曼编码器实验报告学院：计算机学院班级：计科0801 班姓名：王宇宏学号： 04081027（ 27）大全一实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二实验环境Microsoft visual c+三、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码 / 译码系统。试为这样的信息收发站写一个哈夫曼编码的编码 / 译码器。四、需求分析（ 1）初始化

2、 ; 从终端输入字符集的大小 n，以及 n 个字符和 n 个权值建立哈夫曼树。（ 2）输出哈夫曼树，及各字符对应的编码。（ 3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。（ 4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。五、概要设计#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>/typedef int TElemType;

3、const int UINT_MAX=1000;char str50;typedef structint weight,K;int parent,lchild,rchild;HTNode,* HuffmanTree;typedef char *HuffmanCode;/-全局变量 -HuffmanTree HT;HuffmanCode HC;2int w50,i,j,n;char z50;int flag=0;int numb=0/ -求哈夫曼编码 -struct couchar data;int count;cou50;int min(HuffmanTree t,int i) / 函数 vo

4、id select()调用int j,flag;取 k 为不小于可能的值 , 即 k 为最大的权值 1000int k=UINT_MAX; /for(j=1;j<=i;j+)if(tj.weight<k&&tj.parent=0)k=tj.weight,flag=j;tflag.parent=1;return flag;-slect 函数 - -/void select(HuffmanTree t,int i,int &s1,int &s2) / s1 为最小的两个值中序号小的那个 int j;s1=min(t,i);s2=min(t,i);if(s

5、1>s2)j=s1;s1=s2;s2=j;-算法 6.12/void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w 存放 n 个字符的权值 ( 均>0), 构造哈夫曼树 HT,并求出 n 个字符的哈夫曼编码 HCint m,i,s1,s2,start; /unsigned c,f;int c,f; HuffmanTree p; char *cd; if(n<=1)return;/检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc(m+1)*siz

6、eof(HTNode); / 0 号单元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w)p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)p->parent=0;for(i=n+1;i<=m;+i) /建哈夫曼树/在 HT1i-1 中选择 parent 为 0 且 weight 最小的两个结点 , 其序号分别为 s1 和 s2select(HT,i-1,s1,s2);3HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HT

7、i.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/ 从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/ 分配 n 个字符编码的头指针向量 (0 不用 )cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间cdn-1='0' /编码结束符for(i=1;i<=n;i+) /逐个字符求哈夫曼编码start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/ 从叶

8、子到根逆向求编码 if(HTf.lchild=c) cd-start='0' else cd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);/ 为第 i 个字符编码分配空间strcpy(HCi,&cdstart); /从 cd 复制编码 ( 串) 到 HCfree(cd); /释放工作空间/-获 取 报 文 并 写 入 文 件-int InputCode()/cout<<"请输入你想要编码的字符"<<endl;FILE *tobetran;if(tobetra

9、n=fopen("tobetran.txt","w")=NULL)cout<<"不能打开文件 "<<endl;return 0;cout<<" 请输入你想要编码的字符"<<endl;gets(str);fputs(str,tobetran);cout<<" 获取报文成功 "<<endl;fclose(tobetran);return strlen(str);/-初始化哈夫曼链表 -void Initialization()

10、int a,k,flag,len;a=0;len=InputCode();for(i=0;i<len;i+)k=0;flag=1;coui-a.data=stri;coui-a.count=1;while(i>k)if(stri=strk)a+;4flag=0;k+;if(flag=0)break;if(flag)for(j=i+1;j<len;j+)if(stri=strj)+coui-a.count;n=len-a;for(i=0;i<n;i+) cout<<coui.data<<" " cout<<coui.

11、count<<endl;for(i=0;i<=n;i+)*(z+i)=coui.data;*(w+i)=coui.count;HuffmanCoding(HT,HC,w,n);/-打印编码-cout<<"字符对应的编码为 :"<<endl;for(i=1;i<=n;i+)puts(HCi);/-将哈夫曼编码写入文件-.cout<<"下面将哈夫曼编码写入文件"<<endl<<""<<endl;FILE *htmTree;char r='

12、; ','0'if(htmTree=fopen("htmTree.txt","w")=NULL)cout<<"can not open file"<<endl;return;fputs(z,htmTree);for(i=0;i<n+1;i+)fprintf(htmTree,"%6d",*(w+i);fputs(r,htmTree);for(i=1;i<=n;i+)fputs(HCi,htmTree);fputs(r,htmTree);fclose(htmT

13、ree);cout<<"已 将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl;/-编码函数 -5void Encoding()cout<<"下面对目录下文件tobetran.txt中的字符进行编码 "<<endl;FILE *tobetran,*codefile;if(tobetran=fopen("tobetran.txt","rb")=NULL)cout<<"不能打开文件 "<&l

14、t;endl;if(codefile=fopen("codefile.txt","wb")=NULL)cout<<"不能打开文件 "<<endl;char *tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)cout<<"不能打开文件 "<<endl;break;for(i=0;*(tran+i)!='0'i+)for(j=

15、0;j<=n;j+)if(*(z+j-1)=*(tran+i)fputs(HCj,codefile);if(j>n)字符错误，无法编码 !"<<endl;cout<<"break;编码工作完成 "<<endl<<" 编码写入目录下的 codefile.txtcout<<"中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);译码函数 -/-void Decoding()下 面

16、对 根目 录 下文 件 codefile.txtcout<<"中的字符进行译码"<<endl;FILE *codef,*txtfile;if(txtfile=fopen("txtfile.txt","w")=NULL)cout<<"不能打开文件 "<<endl;if (codef=fopen("codefile.txt","r")=NULL)cout<<"不能打开文件 "<<endl;

17、6char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!='0'i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;else if(i2='0'

18、;) i3=HTi3.lchild;else if(i2='1') i3=HTi3.rchild;*(work2+i4)='0'fputs(work2,txtfile);cout<<" 译 码完 成 "<<endl<<" 内 容写 入根目录下的文件 txtfile.txt中"<<endl<<endl;free(work);free(work2);fclose(txtfile);fclose(codef);打印编码的函数 -/-void Code_printing(

19、)下面打印根目录下文件 CodePrin.txt中编码字符 "<<endl;cout<<"FILE * CodePrin,* codefile;if(CodePrin=fopen("CodePrin.txt","w")=NULL)不能打开文件 "<<endl;cout<<"return;if(codefile=fopen("codefile.txt","r")=NULL)cout<<"不能打开文件 &quo

20、t;<<endl;return;char *work3;work3=(char*)malloc(51*sizeof(char);doif(fgets(work3,51,codefile)=NULL)cout<<"不能读取文件 "<<endl;break;fputs(work3,CodePrin);puts(work3);while(strlen(work3)=50);free(work3);cout<<"打印工作结束 "<<endl<<endl;7fclose(CodePrin);f

21、close(codefile);/-打印译码函数-void Code_printing1()中译码字符 "<<endl;cout<<"下面打印根目录下文件 txtfile.txtFILE * CodePrin1,* txtfile;if(CodePrin1=fopen("CodePrin1.txt","w")=NULL)cout<<"不能打开文件 "<<endl;return;if(txtfile=fopen("txtfile.txt","

22、;r")=NULL)cout<<"不能打开文件 "<<endl;return;char *work5;work5=(char*)malloc(51*sizeof(char);doif(fgets(work5,51,txtfile)=NULL)cout<<"不能读取文件 "<<endl;break;fputs(work5,CodePrin1);puts(work5);while(strlen(work5)=50);free(work5);cout<<"打印工作结束 "

23、<<endl<<endl;fclose(CodePrin1);fclose(txtfile);-打印哈夫曼树的函数 - -/void coprint(HuffmanTree start,HuffmanTree HT)if(start!=HT)FILE * TreePrint;if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<<"创建文件失败 "<<endl;return;numb+;/该变量为已被声明为全局变量coprint(HT+sta

24、rt->rchild,HT);cout<<setw(5*numb)<<start->weight<<endl;fprintf(TreePrint,"%dn",start->weight);coprint(HT+start->lchild,HT);numb-;fclose(TreePrint);void Tree_printing(HuffmanTree HT,int w)8HuffmanTree p;p=HT+w;cout<<"下面打印哈夫曼树 "<<endl;copri

25、nt(p,HT);cout<<"打印工作结束 "<<endl;/-主函数 -void main()char choice;while(choice!='q')cout<<"n*"<<endl;cout<<"欢迎使用哈夫曼编码解码系统"<<endl;cout<<"*"<<endl;cout<<"(1)要初始化哈夫曼链表请输入'i'"<<endl;cout<<"(2)要编码请输入 'e'"<<endl;cout<<"(3)要译码请输入 'd'"<<endl;cout<<"(4)要打印编码请输入 'p'"<<endl;cout<<"(5)要打印哈夫曼树请输入 't'"<<endl;cout<<"(6)要