huffman(哈夫曼)树编码译码-课程设计报告

数据结构课程设计学院：信息科学与工程学院专业：计算机科学与技术班级：计卓1601学号：学生姓名：指导教师：年月日题目名称一、实验内容哈夫曼编码译码系统【问题描述】用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。2）编码。利用已建好的哈夫曼树对输入英文进行编码，编码结果存储在数组中。3）译码。利用已建好的哈夫曼树将数组中的代码进行译码，结果存入一个字符数组。4）输出编码。将编码结果显示在终端上，每行50个代码。5）输出哈夫曼树。将哈夫曼树以直观的方式（树或凹入表形式）显示出来。【实现提示】用户界面可以设计为“菜单”方式，再加上一个“退出”功能。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“退出”为止。参考教材P240-246【选做内容】将哈夫曼树保存到文件中，编码和译码的结果也分别存放在两个文本文件中。二、数据结构设计储存结构structHNodeType{//字符结构体类型intweight;//权intparent;//双亲位置intlchild;//左孩子intrchild;//右孩子charinf;//字符};structHcodeType{intbit[MaxBit];//存储编码intstart;//起始位置};三、算法设计1、在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1。求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的父节点回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位2、初始化为从键盘接受字符集大小n，以及n个字符和n个权值。3、建立哈夫曼编码为使用2中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中。voidCreat_Haffmantree(int&n){//建树并输出树n++;HNodeType*HaffNode=newHNodeType[2*n-1];inti,j;intm1,m2,x1,x2;for(i=0;i2*n-1;i++){//赋初值HaffNode[i].weight=0;HaffNode[i].parent=-1;HaffNode[i].lchild=-1;HaffNode[i].rchild=-1;HaffNode[i].inf='0';}for(i=0;in-1;i++){//输入字符及权值cout请输入字符:endl;cinHaffNode[i].inf;cout请输入该字符的权值:endl;cinHaffNode[i].weight;}HaffNode[n-1].inf='';//最后一个为空格HaffNode[n-1].weight=120;//空格权值for(i=0;in-1;i++){//构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j++){//找出最小和次小if(HaffNode[j].parent==-1&&HaffNode[j].weightm1){m2=m1;x2=x1;m1=HaffNode[j].weight;x1=j;}else{if(HaffNode[j].parent==-1&&HaffNode[j].weightm2){m2=HaffNode[j].weight;x2=j;}}}//合并Huffman树HaffNode[x1].parent=n+i;HaffNode[x2].parent=n+i;HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;HaffNode[n+i].lchild=x1;HaffNode[n+i].rchild=x2;HaffNode[n+i].inf='';}//输出树cout显示存储的哈弗曼树信息:endl;cout权值左孩子右孩子父节点endl;for(i=0;i2*n-1;i++){coutHaffNode[i].inf;coutsetiosflags(ios::right)setw(4)HaffNode[i].weight;coutsetiosflags(ios::right)setw(4)HaffNode[i].lchild;coutsetiosflags(ios::right)setw(4)HaffNode[i].rchild;coutsetiosflags(ios::right)setw(4)HaffNode[i].parentendl;}//写入文件fstreamoutfile1;outfile1.open(E:\\nodedata.dat,ios::out|ios::trunc|ios::binary);//建立进行写入的文件并清空之前数据if(!outfile1){//没有创建成功则显示相应信息coutnodedata.dat文件不能打开endl;abort();}for(i=0;i2*n-1;i++)//将内存中从HaffNode[i]地址开始的sizeof(HaffNode[i])的内容写入文件中outfile1.write((char*)&HaffNode[i],sizeof(HaffNode[i]));outfile1.close();//关闭文件delete[]HaffNode;}4、编码系统为从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code.dat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上。voidHaffCode(int&n){//哈夫曼编码HNodeType*HaffNode=newHNodeType[Maxnode];//存储树HcodeType*HaffCode=newHcodeType[Maxleaf];//存储编码HcodeTypecd;inti,j,c,p;fstreamin(E:\\nodedata.dat,ios::in|ios::binary);//打开文件in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));//从文件中读取树in.close();//关闭文件fstreamoutfile;outfile.open(E:\\codedata.dat,ios::out|ios::binary);//建立进行写入的文件for(i=0;in;i++){//进行编码并向数组中从右向左写入编码cd.start=n-1;c=i;p=HaffNode[c].parent;while(p!=-1){if(HaffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HaffNode[c].parent;}for(j=cd.start+1;jn;j++)//向结构体数组存储编码HaffCode[i].bit[j]=cd.bit[j];HaffCode[i].start=cd.start;}for(i=0;in;i++){//向文件中存取数据outfileHaffNode[i].inf;for(j=HaffCode[i].start+1;jn;j++)outfileHaffCode[i].bit[j];}cout字符信息--编码信息endl;for(i=0;in;i++){coutHaffNode[i].inf---;for(j=HaffCode[i].start+1;jn;j++)//输出编码coutHaffCode[i].bit[j];//编码信息01串coutendl;}outfile.close();//关闭文件cout请输入要编码的字符串,基本元素为（;for(i=0;in;i++)coutHaffNode[i].inf,;cout)endl;charinf[100];//定义输入字符存放数组getchar();gets(inf);//读取屏幕字符intf=strlen(inf);fstreamoutfile1;outfile1.open(E:\\code.dat,ios::out|ios::binary);//建立进行写入的文件if(!outfile1){coutcode.dat文件不能打开!endl;abort();}else{coutendl;cout字符串编码后为:\n;intnum=0;for(intx=0;xf;x++){//输出文本编码for(i=0;in;i++){if(inf[x]==HaffNode[i].inf){for(j=HaffCode[i].start+1;jn;j++){outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));coutHaffCode[i].bit[j];num++;if(num%50==0)coutendl;}}}}}coutendl;coutendl;cout编译后的代码串已经存入code.dat文件中!endl;coutendl;outfile1.close();delete[]HaffNode;delete[]HaffCode;}5、译码系统为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式，一种是直接输入，一种是从文件中读取。voiddecode(int&n){inti;HNodeType*HaffNode=newHNodeType[2*n-1];fstreaminfile1;infile1.open(E:\\nodedata.dat,ios::in|ios::binary);//打开文件if(!infile1){coutnodedata.dat文件不能打开endl;abort();}for(i=0;i2*n-1;i++)//从文件里读出Huffman树infile1.read((char*)&HaffNode[i],sizeof(HNodeType));infile1.close();//关闭inttempcode[100];//定义一个数组存放01串intnum=0;for(i=0;i100;i++)//数组初始化tempcode[i]=-1;HcodeType*Code=newHcodeType[n];cout请选择要做的操作：endl;cout4.输入01串解码endl;cout5.从文件中解码endl;charq;cinq;while(q!='4'&&q!='5'){cout输入错误请重新输入;cin