搜索
《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构B实验学期2012至2013学年第一学期学生所在系部计算机学院年级2011专业班级信管B111学生姓名学号任课教师兰芸实验成绩一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows系列操作系统、VisualC++6.0软件四、实验内容：根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、概要设计：（1）构造Hufffman树的方法—Hufffman算法构造Huffman树步骤：I.根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj。II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。(3)解压根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。六、详细设计：压缩的代码#includestdio.h#includestring.h#includestdlib.h#includeconio.hstructhead{unsignedcharb;/*thecharactor*/longcount;/*thefrequency*/longparent,lch,rch;/*makeatree*/charbits[256];/*thehaffumancode*/}header[512],tmp;voidyasuo()/*压缩*/{charfilename[255],outputfile[255],buf[512];unsignedcharc;charwenjianming[255];longi,j,m,n,f;longmin1,pt1,flength;FILE*ifp,*ofp;printf(输入文件地址及文件名:);gets(filename);ifp=fopen(filename,rb);/*打开源文件*/while(ifp==NULL){printf(打开文件出错\n);printf(重新输入文件地址及文件名);gets(filename);ifp=fopen(filename,rb);}printf(输入压缩后的文件地址和文件名及后缀:);gets(wenjianming);ofp=fopen(wenjianming,wb);/*创建并打开目的文件*/while(ofp==NULL){printf(重新输入压缩后的文件地址和文件名及后缀:);ofp=fopen(wenjianming,wb);}flength=0;while(!feof(ifp))/*读取ifp文件*/{fread(&c,1,1,ifp);/*按位读取*/header[c].count++;flength++;}flength-1;header[c].count-1;/*读取文件结束*/for(i=0;i512;i++)/*构造哈弗曼树*/{if(header[i].count!=0)header[i].b=(unsignedchar)i;elseheader[i].b=0;header[i].parent=-1;header[i].lch=header[i].rch=-1;}for(i=0;i256;i++){for(j=i+1;j256;j++){if(header[i].countheader[j].count){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}for(i=0;i256;i++)if(header[i].count==0)break;n=i;m=2*n-1;for(i=n;im;i++){min1=999999999;for(j=0;ji;j++){if(header[j].parent!=-1)continue;if(min1header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count=header[pt1].count;header[pt1].parent=i;header[i].lch=pt1;min1=999999999;for(j=0;ji;j++){if(header[j].parent!=-1)continue;if(min1header[j].count){pt1=j;min1=header[j].count;continue;}}header[i].count+=header[pt1].count;header[i].rch=pt1;header[pt1].parent=i;}for(i=0;in;i++){f=i;header[i].bits[0]=0;while(header[f].parent!=-1){j=f;f=header[f].parent;if(header[f].lch==j){j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='0';}else{j=strlen(header[i].bits);memmove(header[i].bits+1,header[i].bits,j+1);header[i].bits[0]='1';}}}/*哈弗曼构造结束*/fseek(ifp,0,SEEK_SET);/*把文件指针指向文件的开头*/fwrite(&flength,sizeof(int),1,ofp);//把哈弗曼代码写入ofp文件fseek(ofp,8,SEEK_SET);buf[0]=0;f=0;pt1=8;while(!feof(ifp)){c=fgetc(ifp);//从流中读取一个字符，并增加文件指针的位置f++;for(i=0;in;i++){if(c==header[i].b)break;}strcat(buf,header[i].bits);//把header[i].bits所指字符串添加到buf结尾处j=strlen(buf);//计算字符串buf的长度c=0;while(j=8){for(i=0;i8;i++){if(buf[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);pt1++;strcpy(buf,buf+8);j=strlen(buf);}if(f==flength)break;}if(j0){strcat(buf,00000000);for(i=0;i8;i++){if(buf[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET);/*fseek用于二进制方式打开的文件,移动文件读写指针位置.第一个是文件流,第3个是指针零点位置,第2个是把指针移动到的地点.*/fwrite(&pt1,sizeof(long),1,ofp);/*是要输出数据的地址,每次写入的位数,数据项的个数，目标文件地址*/fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;in;i++){fwrite(&(header[i].b),1,1,ofp);c=strlen(header[i].bits);fwrite(&c,1,1,ofp);j=strlen(header[i].bits);if(j%8!=0)/*按八位读取*/{for(f=j%8;f8;f++)strcat(header[i].bits,0);}while(header[i].bits[0]!=0){c=0;for(j=0;j8;j++){if(header[i].bits[j]=='1')c=(c1)|1;elsec=c1;}strcpy(header[i].bits,header[i].bits+8);/*把从header[i].bits+8地址开始且含有NULL结束符的字符串赋值到以header[i].bits开始的地址空间*/fwrite(&c,1,1,ofp);}}fclose(ifp);fclose(ofp);printf(压缩成功\n);}voidmain()/*主函数*/{printf(输入a开始压缩\n);printf(输入b结束压缩\n);while(1){charc;c=getch();if(c=='a')yasuo();else{if(c=='b')return;}}}压缩的图解解压的代码#includestdio.h#includestring.h#includestdlib.h#includeconio.hstructhead{unsignedcharb;/*thecharactor*/longcount;/*thefrequency*/longparent,lch,rch;/*makeatree*/charbits[256];/*thehaffumancode*/}header[512],tmp;voidjieya()/*解压*/{charfilename[255],outputfile[255],buf[255],bx[255];unsignedcharc;charwenjianming[255];longi,j,m,n,f,p,l;longflength;FILE*ifp,*ofp;printf(要解压的文件：);gets(filename);ifp=fopen(filename,rb);/*打开源文件*/while(ifp==NULL){printf(打开文件出错\n);printf(重新输入文件地址及文件名);gets(filename);ifp=fopen(filename,rb);}printf(输入解压后的文件地址和文件名及后缀:);gets(wenjianming);ofp=fopen(wenjianming,wb);/*创建并打开目的文件*/while(ofp==NULL){ofp=fopen(d:\\123\\解压的文件.txt,wb);}fread(&flength,sizeof(long),1,ifp);fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);for(i=0;in;i++){fread(&header[i].b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c;header[i].count=p;header[i].bits[0]=0;if(p%80)m=p/8+1;elsem=p/8;for(j=0;jm;j++){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;lf;l--){strcat(header[i].bits,0);}strca