哈夫曼编码实验报告(共13页).doc

精选优质文档-倾情为你奉上哈夫曼编码器实验报告 学院：计算机学院 班级：计科0801班 姓名：王宇宏 学号：（27） 一实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二实验环境 Microsoft visual c+三、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼编码的编码/译码器。四、需求分析（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。 （2）输出哈夫曼树，及各字符对应的编码。 （3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。 （4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。五、概要设计#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>/typedef int TElemType;const int UINT_MAX=1000;char str50;typedef struct int weight,K; int parent,lchild,rchild;HTNode,* HuffmanTree;typedef char *HuffmanCode;/-全局变量-HuffmanTree HT;HuffmanCode HC;int w50,i,j,n;char z50;int flag=0; int numb=0/ -求哈夫曼编码- struct cou char data; int count;cou50;int min(HuffmanTree t,int i) / 函数void select()调用 int j,flag; int k=UINT_MAX; / 取k为不小于可能的值,即k为最大的权值1000 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(s1>s2) j=s1; s1=s2; s2=j; / -算法6.12-void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) / w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC int 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)*sizeof(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和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.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) / 从叶子到根逆向求编码 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间/- 获取报文并写入文件-int InputCode() /cout<<"请输入你想要编码的字符"<<endl; FILE *tobetran; if(tobetran=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() 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+; flag=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.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=' ','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(htmTree); cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl;/-编码函数-void Encoding() cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl; FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL) cout<<"不能打开文件"<<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=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(HCj,codefile); if(j>n) cout<<"字符错误，无法编码!"<<endl; break; cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose(codefile); free(tran);/-译码函数-void Decoding() cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("txtfile.txt","w")=NULL) cout<<"不能打开文件"<<endl; if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; char *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') 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() cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl; FILE * CodePrin,* codefile; if(CodePrin=fopen("CodePrin.txt","w")=NULL) cout<<"不能打开文件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout<<"不能打开文件"<<endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout<<"不能读取文件"<<endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); cout<<"打印工作结束"<<endl<<endl; fclose(CodePrin); fclose(codefile);/- 打印译码函数-void Code_printing1() cout<<"下面打印根目录下文件txtfile.txt中译码字符"<<endl; FILE * CodePrin1,* txtfile; if(CodePrin1=fopen("CodePrin1.txt","w")=NULL) cout<<"不能打开文件"<<endl; return; if(txtfile=fopen("txtfile.txt","r")=NULL) cout<<"不能打开文件"<<endl; return; char *work5; work5=(char*)malloc(51*sizeof(char); do if(fgets(work5,51,txtfile)=NULL) cout<<"不能读取文件"<<endl; break; fputs(work5,CodePrin1); puts(work5); while(strlen(work5)=50); free(work5); cout<<"打印工作结束"<<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+start->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) HuffmanTree p; p=HT+w; cout<<"下面打印哈夫曼树"<<endl; coprint(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)要打印译码请输入'y'"<<endl; if(flag=0)cout<<"n请先初始化哈夫曼链表,输入'i'"<<endl; cin>>choice; switch(choice) case 'i': Initialization(); break; case 'e': Encoding(); break; case 'd': Decoding(); break; case 'p': Code_printing(); break; case 't': Tree_printing(HT,2*n-1); break; case 'y': Code_printing1(); break; default: cout<<"input error"<<endl; free(z); free(w); free(HT);运行结果：六、所遇问题及心得体会本次试验中所遇到的主要问题为哈弗曼编码的算法，以及整个变量的控制。通过学习课本上的基础编码方法，再加上老师所讲的内容，整理修改后得到这个编码系统。通过本次试验，掌握了树和哈夫曼树的基本操作，以及各个程序的算法。也复习了前面所学习的参数调用和控制变量范围。这次课程设计，在编辑中犯了不应有的错误，统计字符时忘记了应该怎样保存数据，对文件的操作也很生疏，在不断的分析后明确并改正了错误和疏漏，是程序有了更高的质量。总的来说，不仅是实验的结果，更重要的是过程和思考，是我学到了很多的知识，真的是受益匪浅。附主要算法流程图：功能结构图：哈夫曼编码译码器构造树编码译码打印编码打印译码打印哈夫曼构造哈夫曼树：哈夫曼编码：参考文献：【1】 严蔚敏.数据结构（C语言版），清华大学出版社【2】 谭浩强.C语言程序设计教程，高等教育出版社专心-专注-专业