赫夫曼树编码译码器实践报告

数据结构课外实践报告项目名称：赫夫曼编码译码器所在班级：小组成员：指导教师：起止时间：10—16周·数据结构课外实践·2项目基本信息项目名称赫夫曼编码译码器项目简介此项目的主要功能有：1、统计权值；2、建赫夫曼树；3、对文件进行编码；4、对字符进行赫夫曼编码；5、进行赫夫曼译码；6、计算压缩比例；小组成员任务分工1、统计权值；主函数；2、建赫夫曼树；对字符进行编码；3、进行赫夫曼译码；4、对文件进行编码；计算压缩比例；5、实践报告；课外实践评定成绩记录指导教师意见系统完成情况：优良中差报告完成情况：优良中差答辩评定成绩团队整体成绩：成员成绩综合成绩·数据结构课外实践·3一、问题描述及分析1、统计字符种类及出现的频率；根据权值建立赫夫曼树；每个字符对应的译成0、1编码；把所输入的字符串压缩为0、1码；将0、1码译码为字符串；计算压缩比例2、问题分析：1）在建立赫夫曼树之前必须对所输入的字符进行统计，统计其个数（作为叶子结点个数）及出现的频率（作为权值）；2）然后编写Select函数选取权值最小的树作为左右子树构造一颗新的二叉树且置其根结点的权值为其左右子树之和，循环建立赫夫曼树；3）从叶子到根逆向求每个字符的赫夫曼编码，左分支为0，右分支为1；4）根据前面求出的赫夫曼树及其编码对字符串进行编码，并把0、1编码写进文件；5）把压缩的0、1码译码为字符串，并显示输出。6）赫夫曼编码的长度除以字符串的长度*8；二、功能模块及数据结构描述1、哈夫曼树和哈夫曼编码的储存结构定义typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组储存哈夫曼树typedefchar**HuffmanCode;//动态分配数组储存哈夫曼编码表#defineUINT_MAX1000//设定最大权值定义全局变量HT、HC等。2、统计字符种类及频率inttotal(){FILE*fp;inti,j;intqz[57]={0};//存放info中27个字符的权值数组…w=(int*)malloc(kind*sizeof(int));//为权值不为零的权值开辟空间zf=(char*)malloc((kind+1)*sizeof(char));//为权值不为零的字符开辟空间…}·数据结构课外实践·43、建立赫夫曼树voidHuffmanCoding(HuffmanTree&HT,intn)//建立赫夫曼树{FILE*fp;inti,j,m,s1,s2;HuffmanTreep;voidSelect(HuffmanTreeHT,intn,int&s1,int&s2)…}4、编码voidHuffmancoding(intn,HuffmanCode&HC){inti,start;char*cd;unsignedintc,f;//从叶子到根逆向求每个字符的赫夫曼编码…}5、对字符逐个编码voidCheckCoding(){FILE*fp;inti,j;…}6译码voidHuffmanTranslate(){//将CodeFile中的代码进行译码并存入TextfileFILE*fp1,*fp2;intkey;charc,ch;…}·数据结构课外实践·56、计算压缩比例voidratio(){floatlen1,len2=0;floatbili;len1=strlen(s);…}三、主要算法流程描述及部分核心算法1.开始1.输入文件2.统计字符的个数，及种类并输出3.建立赫夫曼树并输出编码对文件的字符进行逐个编码并输出输出计算压缩比例译码利用文件中的编码对文件进行译码是否继续结束·数据结构课外实践·62、部分核心算法1)统计个数及频率（权值）inttotal(){//输入要编码的正文FILE*fp;inti,j;intqz[57]={0};//存放info中27个字符的权值数组//把要统计的字符串写入文件if((fp=fopen(ToBeTra.txt,w+))==NULL)printf(ToBeTra.txtcan'tbecreated!\n);else{printf(pleaseinputatxt,itwillbesaveinthefileToBeTra.txt:\n);scanf(%s,&s);n=strlen(s);if(fputs(s,fp)!=NULL)printf(\nOK\n);}for(i=0;in;i++){//统计权值for(j=0;j57;j++)if(s[i]==info[j])qz[j]++;}for(j=0;j57;j++){//统计字符的种类if(qz[j]!=0)kind++;}w=(int*)malloc(kind*sizeof(int));//为权值不为零的权值开辟空间zf=(char*)malloc((kind+1)*sizeof(char));//为权值不为零的字符开辟空间·数据结构课外实践·7for(i=0,j=0;i57;i++)//为w,zf赋值if(qz[i]!=0){zf[j]=info[i];w[j]=qz[i];j++;}printf(输出要统计字符的种类：\n);printf(%d\n,kind);printf(输出字符及其权值：\n);for(i=0;ikind;i++)printf(%c%d\n,zf[i],w[i]);fclose(fp);return0;}2)Select函数voidSelect(HuffmanTreeHT,intn,int&s1,int&s2){for(inti=1;i=n;i++)//任取两个parent为0的节点赋值给s1和s2if(!HT[i].parent){s1=i;break;}for(i++;i=n;i++)if(!HT[i].parent){s2=i;break;}·数据结构课外实践·8if(HT[s1].weightHT[s2].weight){//s1记录权值小的下标s2记录次小的下标inttemp;temp=s1;s1=s2;s2=temp;}for(i=1;i=n;i++)//对数组进行遍历，寻找最小的两个节点if(!HT[i].parent){if(HT[i].weightHT[s1].weight){s2=s1;s1=i;}elseif(HT[i].weightHT[s2].weight&&i!=s1)s2=i;}}3)赫夫曼树及编码voidHuffmanCoding(HuffmanTree&HT,intn){//建立赫夫曼树FILE*fp;inti,j,m,s1,s2;HuffmanTreep;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)·数据结构课外实践·9{(*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i=m;i++,++p){(*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(i=n+1;i=m;i++){Select(HT,i-1,s1,s2);//选择两个权值小的结点HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//把赫夫曼树的构造过程写入文件fp=fopen(hfmTree.txt,w+);for(j=1;j=m;j++){if(fp!=NULL)fprintf(fp,%4d%8d%8d%8d%8d\n,j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);}printf(\nhfmTreehasbeensavedinthefilehfmTree.txt!\n);·数据结构课外实践·10fclose(fp);//赫夫曼树的构建过程printf(赫夫曼树的构建过程：\n);printf(\n结点weightparentlchildrchild);for(j=1;j=m;j++)printf(\n%4d%8d%8d%8d%8d\n,j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);}voidHuffmancoding(intn){inti,start;char*cd;unsignedintc,f;//从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)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';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}for(i=0;ikind;i++)printf(%c%s\n,zf[i],HC[i+1]);free(cd);}·数据结构课外实践·11inttotal(){//输入要编码的正文FILE*fp;inti,j;intqz[57]={0};//存放info中27个字符的权值数组//把要统计的字符串写入文件if((fp=fopen(ToBeTra.txt,w+))==NULL)printf(ToBeTra.txtcan'tbecreated!\n);else{printf(pleaseinputatxt,itwillbesaveinthefileToBeTra.txt:\n);scanf(%s,&s);n=strlen(s);if(fputs(s,fp)!=NULL)printf(\nOK\n);}for(i=0;in;i++){//统计权值for(j=0;j57;j++)if(s[i]==info[j])qz[j]++;}for(j=0;j57;j++){//统计字符的种类if(qz[j]!=0)kind++;}w=(int*)malloc(kind*sizeof(int));//为权值不为零的权值开辟空间zf=(char*)malloc((kind+1)*sizeof(char));//为权值不为零的字符开辟空间·数据结构课外实践·12for(i=0,j=0;i57;i++)//为w,zf赋值if(qz[i]!=0){zf[j]=info[i];w[j]=qz[i];j++;}printf(输出要统计字符的种类：\n);printf(%d\n,kind);printf(输出字符及其权值：\n);for(i=0;ikind;i++)printf(%c%d\n,zf[i],w[i]);fclose(fp);return0;}4）译码voidHuffmanTranslate(){//将CodeFile中的代码进行译码并存入TextfileFILE*fp1,*fp2;intkey;charc,ch;fp1=fopen(CodeFile.txt,r);fp2=fopen(TextFile.txt,w+);if(fp1==NULL||fp2==NULL)printf(nofiletotranslate!);else{c=fgetc(fp1);//从fp1中取一个字符·数据结构课外实践·13whil