赫夫曼编码译码器.doc

该【赫夫曼编码译码器 】是由【泰山小桥流水】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【赫夫曼编码译码器 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。百度文库 -让每个人平等地提升自我数据结构课程设计实验题目:赫夫曼编码/译码器班级网络一班姓名学号指导老师成绩1百度文库 -让每个人平等地提升自我一、需求分析利用赫夫曼编码进行通信可以大大提高信道利用率, 缩短信息传输时间, 降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码, 在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编 /译码系统。试为这样的信息收发站编写一个赫夫曼码的编 /译码系统。二、:(1)I:初始化(Initialization)。从终端读入字符集大小 n,以及n个字符和 n个权值,建立赫夫曼树,并将它存于文件 hfmTree中。(2)E:编码(Encoding)。利用已建好的赫夫曼树(如不在内存,则从文件 hfmTree中读入),对文件 ToBeTran中的正文进行编码,然后将结果存入文件 CodeFile中。(3)D:译码(Decoding)。利用已建好的赫夫曼树将文件 CodeFile中的代码进行译码,结果存入文件 Textfile中。-2的数据调试程序:已知某系统在通信联络中只可能出现八种字符,其频率分别,,,,,,,,试设计赫夫曼编码。(2)用下表给出的字符集和频度的实际统计数据建立赫夫曼树,并实现以下报文的编码和译码:“THISPROGRAMEISMYFAVORITE”。(1)编码结果以文本方式存储在文件Codefile中。(2)用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择2百度文库 -让每个人平等地提升自我了“Q”为止。(3)在程序的一次执行过程中,第一次执行 I,D或C命令之后,赫夫曼树已经在内存了,不必再读入。每次执行中不一定执行 I命令,因为文件 hfmTree可能早已建好。三、概要设计程序主要分为五部分,哈夫曼节点的定义,哈夫曼编码的定义, Select函数选择出权值最小的节点, Initialization函数生成哈夫曼树,主函数。四、详细设计数据存储结构设计1)哈夫曼节点哈夫曼节点数据类型如下,包含字符,权值,父节点,左右孩子:typedefstruct{charch;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HfmTree;2)哈夫曼编码哈夫曼编码用二级指针存储,动态分配空间:typedefchar**HfmCode;算法的设计思想(1)Select函数voidSelect(HfmTreeHT,inta,int&s1,int&s2){arent!=0);s1=i;while(HT[++i].parent!=0);s2=i++;if(HT[s1].weight>HT[s2].weight){temp=s1;s1=s2;s2=temp;3百度文库 -让每个人平等地提升自我}for(;i<=a;i++){if(HT[i].parent==0)if(HT[i].weight<HT[s1].weight)s1=i;elseif(HT[i].weight<HT[s2].weight)s2=i;}}h=ch[i-1];HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}h='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}arent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].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';4百度文库 -让每个人平等地提升自我}else{cd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}}free(cd);cout<<" 生成成功!"<<endl<<endl;;cout<<"ID\tchar\t"<<"weight"<<"\t"<<"parent"<<"\t"<<"lchild"<<"\t"<<"rchild"<<"\t"<<endl;for(i=1;i<2*n;i++){cout<<i<<"\t"<<HT[i].ch<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<"\t"<<endl;}cout<<"char\t"<<"Code\t"<<endl;for(i=1;i<=n;i++){cout<<HT[i].ch<<"\t"<<HC[i]<<"\t"<<endl;}}程序#include<iostream>#include<fstream>#include<string>usingnamespacestd;typedefstruct{charch;unsignedintweight;5百度文库 -让每个人平等地提升自我unsignedintparent,lchild,rchild;}HTNode,*HfmTree;typedefchar**HfmCode;voidSelect(HfmTreeHT,inta,int&s1,int&s2){arent!=0);s1=i;while(HT[++i].parent!=0);s2=i++;if(HT[s1].weight>HT[s2].weight){temp=s1;s1=s2;s2=temp;}for(;i<=a;i++){if(HT[i].parent==0)if(HT[i].weight<HT[s1].weight) s1=i;elseif(HT[i].weight<HT[s2].weight)s2=i;}}voidInitialization(HfmTree&HT,HfmCode&HC,intn,stringch,int*w){inti,m,s1,s2,start,c,f;h=ch[i-1];HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;6百度文库 -让每个人平等地提升自我HT[i].rchild=0;}h='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}arent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].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);cout<<"生成成功!"<<endl<<endl;;cout<<"ID\tchar\t"<<"weight"<<"\t"<<"parent"<<"\t"<<"lchild"<<"\t"<<"rchild"<<"\t"<<endl;7百度文库 -让每个人平等地提升自我for(i=1;i<2*n;i++){cout<<i<<"\t"<<HT[i].ch<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<"\t"<<endl;}cout<<"char\t"<<"Code\t"<<endl;for(i=1;i<=n;i++){cout<<HT[i].ch<<"\t"<<HC[i]<<"\t"<<endl;}}intmain(){ifstreaminput_file;ofstreamoutput_file;charaction;stringtoBeTranSource,textFileSource;stringcharsIn,code;inti,j,c,n,w[100];HfmTreeHT;HfmCodeHC;while(action!='Q'){cout<<endl<<"**********************************************"<<endl;cout<<"*哈夫曼编码/译码器*"<<endl;cout<<"**"<<endl;cout<<"*/*"<<endl;cout<<"**"<<endl;cout<<"*Codebywhocaresu16/12/2010*"<<endl;cout<<"**********************************************"<<endl;cout<<endl<<"请输入操作码: ";8百度文库 -让每个人平等地提升自我cin>>action;action=toupper(action);switch(action){case'I':."<<endl;("");if(!output_file){system("cls");cout<<"Can'topenfile!"<<endl;return1;}output_file<<n;output_file<<charsIn<<"\n";for(i=0;i<n;i++){output_file<<w[i]<<"";}output_file<<"-------- 以下为具体编码信息 --------"<<endl;output_file<<"Char\tCode\t"<<endl;;for(i=1;i<=n;i++){output_file<<HT[i].ch<<"\t"<<HC[i]<<"\t"<<endl;}();cout<<"备份到成功! "<<endl;;break;case'E':h){cout<<HC[j];output_file<<HC[j];}}9百度文库 -让每个人平等地提升自我}();cout<<endl<<"------------ 编译完成--------------------"<<endl;;break;case'D':child==0){cout<<HT[c].ch;c=2*n-1;}if(code[i]=='0')c=HT[c].lchild;elsec=HT[c].rchild;}cout<<endl;cout<<"-------------------------------------------"<<endl;;break;case'C':system("cls");break;default:cout<<endl<<"操作码错误,重新输入! "<<endl;}}system("pause");return0;}五、:(1)利用教科书例 6-2的数据调试程序: ,,,,,,,10