数据结构哈夫曼编码实验报告

实验报告实验课名称：数据结构实验实验名称：文件压缩问题班级：20132012学号：姓名：时间：2015-6-9一、问题描述哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。二、数据结构设计首先定义一个结构体：structhead{unsignedcharb;//记录字符longcount;//权重intparent,lch,rch;//定义双亲，左孩子，右孩子charbits[256];//存放哈夫曼编码的数组}header[512],tmp;//头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511三、算法设计输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman编码思想创建Huffman树由创建的Huffman树来决定字符对应的编码，进行文件的压缩解码压缩即根据Huffman树进行译码设计流程图如图1.1所示。图1.1设计流程图(1)压缩文件输入一个待压缩的文本文件名称(可带路径)如:D:\lu\lu.txt统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD如:D:\lu\lu.COD压缩文件内容=哈夫曼树的核心内容+编码序列for(inti=0;i256;i++){header[i].count=0;//初始化权重header[i].b=(unsignedchar)i;//初始化字符}ifstreaminfile(infilename,ios::in|ios::binary);while(infile.peek()!=EOF){infile.read((char*)&temp,sizeof(unsignedchar));//读入一个字符header[temp].count++;//统计对应结点字符权重flength++;//统计文件长度}infile.close();//关闭文件for(i=0;i256-1;i++)//对结点进行冒泡排序,权重大的放在上面，编码时效率高for(intj=0;j256-1-i;j++)if(header[j].countheader[j+1].count)统计字符，得出统计出字符的权值n建立哈夫曼树生成二进制文件对二进制文件进行解码根据哈夫曼树编码对编码进行压缩生成对应文件根据哈夫曼树解码生成哈夫曼树{tmp=header[j];header[j]=header[j+1];header[j+1]=tmp;}for(i=0;i256;i++)if(header[i].count==0)break;leafnum=i;//取得哈夫曼树中叶子结点数pointnum=2*leafnum-1;//取得哈夫曼树中总结点数目infile.open(infilename,ios::in|ios::binary);//打开待压缩的文件infile.clear();infile.seekg(0);ofstreamoutfile(outfilename,ios::out|ios::binary);//打开压缩后将生成的文件outfile.write((char*)&flength,sizeof(long));//写入原文件长度(2)哈夫曼编码for(i=0;ileafnum;i++){outfile.write((char*)&header[i].b,sizeof(unsignedchar));//写入字符header[i].count=strlen(header[i].bits);//不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度outfile.write((char*)&header[i].count,sizeof(unsignedchar));//写入长度的ASCII码if(header[i].count%8==0)bytelen=header[i].count/8;else{bytelen=header[i].count/8+1;strcat(header[i].bits,0000000);//在编码后面补0，使其最后凑满8的倍数，//超过无妨，可以用bytelen控制好写入字节的长度}for(intj=0;jbytelen;j++){temp=ctoa(header[i].bits);outfile.write((char*)&temp,sizeof(unsignedchar));strcpy(header[i].bits,header[i].bits+8);cout该文件的哈夫曼的编码为:endl;for(i=0;iflength;i++){coutheader[i].bitsendl;}}}//此循环结束后就完成了编码对照表的写入(3)解压文件输入一个待解压的压缩文件名称(可带路径)如:D:\lu\lu.COD从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码；生成(还原)文本文件。文件文件名称=压缩文件名+_new.txt如:D:\lu\lu_new.txtwhile(1){while(readlen(clength-8)&&strlen(buf)=256)//读满缓冲区{infile.read((char*)&temp,sizeof(temp));ctoa(temp,code);//将字节转为数组strcat(buf,code);readlen++;}//whilewhile(strlen(buf)=256)//处理缓冲区，直到少于256位，再读满它{for(i=0;istrlen(buf);i++){strcpy1(buf1,buf,i+1);//逐渐增多取，放入buf1，进行匹配if(strcmp1(buf1,header,n,temp)==1){outfile.write((char*)&temp,sizeof(unsignedchar));writelen++;strcpy(buf,buf+i+1);//缓冲区前移break;}}//forif(writelen=flength)break;//如果写入达到原文件长度，退出}//whileif(readlen=(clength-8)/*编码长度*/||writelen=flength)break;//如果写入或者读入编码完毕，退出}//退出此循环后，还有未解码完成的buf[]//对buf[]缓冲的善后处理while(writelenflength){for(i=0;istrlen(buf);i++){strcpy1(buf1,buf,i+1);if(strcmp1(buf1,header,n,temp)==1){outfile.write((char*)&temp,sizeof(unsignedchar));writelen++;strcpy(buf,buf+i+1);break;}}//for}infile.close();//关闭文件outfile.close();四、界面设计程序包含压缩功能，解压功能，输出功能，帮助，终止程序功能。五、运行测试与分析（1）运行程序，显示提示，如图1.2所示。图1.2启动界面（2）编码操作。图1.3在D盘中建立一个文本文档，并命名为123.txt图1.4文件压缩，输出哈弗曼编码界面图1.5在Ｄ盘中生成一个．COD的文档，并且名为12.COD:（3）解码操作。根据实验要求输出实验结果。如图1.4所示。图1.4数据结果输出界面(4)显示数据内容若用户想知道文本输入的内容，可输入“L”，然后界面提示输入文本文件的路径和文件名，完成输入后按回车键，界面会出现文本的内容。六、实验收获与思考在完成实验的过程中，使我明白了面向对象与面向对象的差别。在面向对象过程中，类的设计是至关重要的，类设计好了等于程序就成功了一半，所以这次的课程帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的不足。同时，也使我对数据结构与算法的知识有了一定的了解，帮我在大二学习数据结构与算法的课程中奠定了一定的基础，使我以后学习数据结构与算法的时候可以更加轻松。教师评分：教师签字：