哈夫曼编译码器闽江学院.docx

实验四 哈夫曼编/译码器【实验课程名称】数据结构【实验项目名称】哈夫曼编/译码器【实验目的】1掌握哈夫曼编码、译码的实现；2学会设计一个完整的编/译码系统【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】1. 初始化：（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存入文件hfmTree.txt中。. 编码：（Edcoding）。利用建好的哈夫曼树（如不在内存则从文件hamTree.txt中读入），对文件TobeTran.txt中的正文进行编码，然后将结果存入文件CodeFile.txt 中。3. 译码：（Decoding）。利用已建好的哈夫曼树将文件CodeFile.txt中的代码进行译码，结果存入文件TextFile.txt中。4. 打印代码文件（Print）。将文件CodeFile.txt以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。5. 打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据及实验结果】（1）利用教科书例6-2中的数据调试程序。（2）利用下表给出的字符集合频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【实验小结】1.要初步学会哈夫曼编码。2.文件的使用；3.队列的作用；4.树的输出；【源代码说明】1文件名：#include #include string#include huffman.husing namespace std;int main()HuffmanTree HT,HT2;HuffmanCode HC,HC2;char str56;int n=27;int w27;int ww27=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; int i; gets(str); n=strlen(str); for(i=0;in;i+)if(stri= )wi=ww0;elsewi=stri-64;for(i=0;in;i+)coutwiendl;/逐个输出字符串每个字符的频率（乘以100）Initialization(HT2,w,n);/初始化赫夫曼编码Edcoding(HC2,n);/赫夫曼编码Decoding(HT2,n);/赫夫曼译码Print(n);/输出赫夫曼凹入表Tree_printing(HT2,n);/输出赫夫曼树return 0;#include /输入输出头文件#include /文件操作头文件#include /文件包含的头文件using namespace std;typedef struct /节点结构体unsigned int weight;/数据域unsigned int parent,lchild,rchild;/双亲，孩子位置HTNode,*HuffmanTree;typedef char *HuffmanCode;void Initialization(HuffmanTree &HT,int *w,int n)/初始化赫夫曼表，进行赫夫曼表的创建FILE *fp;/文件指针if(fp=fopen(hfmTree.txt,w)=NULL)coutERROR!endl;int i,j;int min1,min2,min1_pos,min2_pos;HuffmanTree p;if(n1)return;HT=new HTNode2*n;for(p=HT+1,i=1;i=2*n;i+,w+,p+)if(iweight=*w;else p-weight=0;p-lchild=0;p-parent=0;p-rchild=0;for(i=n+1;i2*n;i+)min1=65535;/赋值于最大整数min2=65535;/赋值于最大整数for(p=HT+1,j=1;pparent&p-weightweight)/找最小数min2=min1;/将之前的最小数给次最小数min2_pos=min1_pos;/将之前的最小数的位置给次最小数的位置min1=p-weight;/将找到的最小数给之前的最小数min1_pos=j;else/找次最小数if(p-weight&!p-parent&p-weightweight;min2_pos=j;HTi.weight=HTmin1_pos.weight+HTmin2_pos.weight;/父亲的重量是两个数的重量的总和HTmin1_pos.parent=i;HTmin2_pos.parent=i;HTi.lchild=min1_posmin2_pos?min1_pos:min2_pos;/右孩子是两个位置的最大for(i=1;i2*n;i+)/输出赫夫曼表，并把它存入fp所指向的文件里coutHTi.weight HTi.parent HTi.lchild HTi.rchildendl;/输出赫夫曼表fprintf(fp,%d ,HTi.weight);fprintf(fp,%d ,HTi.parent);fprintf(fp,%d ,HTi.lchild);fprintf(fp,%dn,HTi.rchild);/写入文件fclose(fp);/关闭文件void Edcoding(HuffmanCode &HC,int n)/赫夫曼编码，并把编码写入文件中int i;FILE *fp1,*fp;/TobeTran.txtfp=fopen(hfmTree.txt,r);/打开文件HuffmanTree HT;HT=new HTNode 2*n;/开辟内存fp1=fopen(CodeFile.txt,w);/打开文件HC=new char*n;for(i=1;i2*n;i+)/将文件里存的信息输出到HTfscanf(fp,%d%d%d%d,&HTi.weight,&HTi.parent,&HTi.lchild,&HTi.rchild);fclose(fp);/关闭文件fp=fopen(CodeFile.txt,w);for(i=1;i2*n;i+)/输出内存中的赫夫曼表coutHTi.weight HTi.parent HTi.lchild HTi.rchildendl;int start;char *cd;int c,f;cd=new charn;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;/左边为0if(HTf.rchild=c)cd-start=1;/右边为1HCi=new charn-start;/开辟内存strcpy(HCi,&cdstart);/赋值编码coutHCiendl;/输出编码fprintf(fp1,%sn,HCi);fclose(fp);/关闭文件fclose(fp1);/关闭文件delete cd;/释放内存void Decoding(HuffmanTree HT,int n)/3. 译码，利用已建好的哈夫曼树将文件CodeFile.txt中的代码进行译码，结果存入文件TextFile.txt中。FILE *fp,*fp1;/文件指针int i,j,Num,Pos;char *cd;cd=new charn;fp1=fopen(TextFile.txt,w);/打开文件fp=fopen(CodeFile.txt,r);/打开文件for(i=1;i=n;i+)/从文件中读取到HT中Pos=2*n-1;fscanf(fp,%s,cd);for(j=0;jstrlen(cd);j+)if(cdj=1)Pos=HTPos.rchild;if(cdj=0)Pos=HTPos.lchild;Num=HTPos.weight;fprintf(fp1,%dn,Num);/存入文件中fclose(fp);/关闭文件fclose(fp1);/关闭文件void Print(int n)/打印代码文件（Print）将文件CodeFile.txt以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。FILE *fp;/文件指针char *cd;cd=new charn;/开辟内存int i=1;fp=fopen(CodeFile.txt,r);/打开文件for(int j=0;jn;j+)/从文件中读取到cdfscanf(fp,%s,cd);i+=(strlen(cd)+1);if(i50)/控制一行50个字符coutcd ;else if(i=50)i=1;coutcdendl;elsefor(int z=0;i+z=50;z+)coutcdz;i=1;coutendl;for(i+;cdz!=0;z+)coutcdz;cout ;i+;void Tree_printing(HuffmanTree HT,int n)/打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。int front=0,rear=0;int Q60;int p;int i=0,j=1;Qrear+=2*n-1;/借助栈进行层次遍历while (rear!=front)p=Qfront+;coutHTp.weight ;for(int z=1;z=i;z+)z*=2;i+;if(HTp.lchild)Qrear+=HTp.lchild;if(HTp.rchild)Qrear+=HTp.rchild;2操作说明：（1）利用教科书例6-2中的