《2022年实验报告格式样例.docx》由会员分享,可在线阅读,更多相关《2022年实验报告格式样例.docx(14页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精品学习资源用哈夫曼编码实现文件压缩实 验 报 告课程名称数据结构 A试验学期 2021至 2021学年 第二学期同学所在系部治理学院年级 2021专业班级电商 B15同学任课老师成果评定:学号兰芸1、工作量:A , B ,C,D,F2、难易度:A ,B , C,D,F3、答辩情形:基本操作:A ,B , C,D,F代码懂得:A ,B , C,D,F4、报告标准度:A ,B , C, D,F5、学习态度:A ,B , C, D,F总评成果 : 欢迎下载精品学习资源一、 试验题目:哈夫曼编码实现文件压缩二、 试验目的:1. 明白文件的概念;2. 把握线性链表的插入 .删除等算法; 3.把握 Hu
2、ffman 的概念及构造方法;4.把握二叉树的储备结构及遍历算法;Huffman 树及 Huffman 编码,把握实现文件压缩的一般原理;三、试验设备与环境:微型电脑 Windows 系列的操作系统 四、试验内容:依据 ascii 码文件中各 ascii 字符显现的频率情形创建 Huffman 树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩;五、概要设计:此程序就是用 Microsoft Visual C+编写的;依据 ascii码文件中各 ascii字符显现的频率情形创建 Haffman 树,再将各字符对应的哈夫曼编码写入文件中;第一是对赫夫曼树进行定义, 然后编写各个子函数, 最终
3、通过主函数对子函数的调用来实现程序的功能,其中用到了关于文本读入、选择权值最小的字符、赫夫曼编码、建立赫夫曼树等的子函数;通过读入的文本,对每个字符显现的次数进行统计,让后通过选择函数,选择权值最小的字符通过编码函数进行编码,然后把赫夫曼树的左右孩子分别赋值0、 1;用这两个数字来表示各个字符,求出各个字符的二进制编码并把字符的二进制码存入文本中,便实现了压缩功能;图见下页:欢迎下载精品学习资源主要结构图如下:主函数读取输出利用 c 中函数fopen 打 开 一个文档把 赫 夫 曼 树转 成 二 进 制数字输出压缩后的文件,输出每个字符的权重值,左右孩子节点以及对应的二进制编码计 算 读 取
4、文件 的 每 个 字符 的 权 值 及文件的长度把二进制编码输出,并运算文件依据各个字符的权值建立赫夫曼树把 压 缩 后 的文 件 存 入 一个 新 的 *.txt 文档中输出赫夫曼树六、具体设计:赫夫曼树的结构体的定义, 其中包括权值、 父母、左右孩子及要编码的字符;欢迎下载精品学习资源用这个结构体定义个赫夫曼数组;定义如下:struct nodelong weight;/ 权值unsigned char ch;/字/符int parent,lchild,rchild;char code256;/编码的位数最多为 256 位int CodeLength;/编码长度hfmnode512;读入文
5、档,并运算其中显现的字符以及每个字符的权值,并统计文档中全部的字符个数:printf 请输入要压缩的文件名 :; scanf%s,infile; ifp=fopeninfile,rb; ififp=NULLprintf 文件名输入错误,文件不存在 .n; return;printf 请输入目标文件名 :; scanf%s,outfile; ofp=fopenoutfile,wb; ifofp=NULLprintf 文件名输入错误,文件不存在 .n; return;start1=clock; /开头计时 1/统计文件中字符的种类以及各类字符的个数/先用字符的 ASCII 码值代替结点下标File
6、Length=0;while.feofifp/ 用来统计读入的文件长度以及每个显现字符的权值fread&c,1,1,ifp;/ 一个流中读取数据hfmnodec.weight+;FileLength+;初始化赫夫曼树,运算赫夫曼树的节点数,把左右孩子,双亲指针都定义成 1:fori=0;i256;i+ ifhfmnodei.weight.=0hfmnodei.ch=unsigned chari; n+;/叶子数hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1;欢迎下载精品学习资源m=2*n-1;/ 哈弗曼树结点总数j=0;fori=0;i25
7、6;i+/ 去掉权值为 0 的结点ifhfmnodei.weight.=0hfmnodej=hfmnodei; j+;fori=n;im;i+/ 初始化根结点hfmnodei.lchild=hfmnodei.rchild=-1; hfmnodei.parent=-1;写 select函数,用来选择权值小的字符:int selectstruct node *nodep,int poseint i;int s1;long min=2147483647;/s初值为 long 型的最大值fori=0;i=pose;i+ifnodepi.parent.=-1 continue;ifnodepi.weig
8、htminmin=nodepi.weight; s1=i;return s1;建立赫夫曼树: fori=n;im;i+s1=selecthfmnode,i-1; hfmnodei.lchild=s1; hfmnodes1.parent=i; s2=selecthfmnode,i-1; hfmnodei.rchild=s2; hfmnodes2.parent=i;hfmnodei.weight=hfmnodes1.weight+hfmnodes2.weight; / 编码利用子函数 encode,对赫夫曼树进行编码 ,做孩子为 0,右孩子为 1: void encodestruct node *
9、nodep,int n欢迎下载精品学习资源/从叶子向根求每个字符的哈弗曼编码int start;int i,f,c;char codes256;codesn-1=0;/ 编码终止符fori=0;in;i+ / 逐个字符求哈弗曼编码start=n-1;forc=i,f=nodepi.parent;f.=-1;c=f,f=nodepf.parentstart-; ifnodepf.lchild=ccodesstart=0; else codesstart=1;strcpynodepi.code,&codesstart; nodepi.CodeLength=strlennodepi.code;将各个
10、字符的二进制码存入文本, 由于储备时依据 8 位一个字节进行的储备, 对于不足 8 为的用 0 补足 8 位,然后进行储备:fseekifp,0,SEEK_SET;/将 ifp 指针移到文件开头位置fwrite&FileLength,4,1,ofp;/ 将 FileLength 写入目标文件的前 4 个字欢迎下载精品学习资源节的位置字节位置fseekofp,8,SEEK_SET;/再将目标文件指针 ofp 移到距文件开头 8 个codes0=0;/将编码信息写入目标文件while.feofifp欢迎下载精品学习资源fread&c,1,1,ifp; filelength+; fori=0;i=8
11、fori=0;i8;i+/ 将 codes的前 8 位 01 代码表示的字符存入 cifcodesi=1 c=c1|1;else c=c0strcatcodes,00000000; fori=0;i8;i+ifcodesi=1 c=c1|1;else c=c1;fwrite&c,1,1,ofp; sumlength+;fori=0;in;i+欢迎下载精品学习资源字节储备fwrite&hfmnodei.ch,1,1,ofp;c=hfmnodei.CodeLength;/编码最长为 256 位,因此只需用一个fwrite&c,1,1,ofp;/写入字符的编码ifhfmnodei.CodeLengt
12、h%8.=0forj=hfmnodei.CodeLength%8;j8;j+/ 把编码不足 8 位的欢迎下载精品学习资源在低位补 0,赋值给 C,再把 C 写入strcathfmnodei.code,0;whilehfmnodei.code0.=0/ 开头存入编码,每 8 位二进制欢迎下载精品学习资源数存入一个字节c=0;forj=0;j8;j+欢迎下载精品学习资源ifhfmnodei.codej=1 c=c1|1;else c=c1;欢迎下载精品学习资源位,连续存入编码strcpyhfmnodei.code,hfmnodei.code+8;/ 编码前移8count+; /编码占的字节数的总值
13、fwrite&c,1,1,ofp;欢迎下载精品学习资源printfn;printf 源文件长度为: %ld 个字节n,FileLength; sumlength=sumlength+4+n*2+count; /运算压缩后文件的长度printf 压缩后文件长度为: %ld 个字节n,sumlength; rate=floatsumlength/floatFileLength;printf 压缩率百分比为: %4.2f%n,rate*100; fcloseifp;fcloseofp; return;七、测试结果及分析:试验结果:第一运行程序,跳出菜单页面:选择“压缩文件” ,输入要压缩的文件,并且输入一个要将压缩后的文件储备的txt文档, 会跳出选择是否查看压缩后的文件,选择“y”,进行查看:欢迎下载精品学习资源从输出的结果上看, 程序输出了每个叶子节点的权值,双亲,二进制编码,以及源文件长度和压缩后文件长度、压缩比等:结果分析:这个程序基本实现了对文本进行赫夫曼编码,但是存在一个缺陷,当文本不够长的时候, 压欢迎下载精品学习资源缩后要比源文件仍长, 而利用大的文件进行压缩就会表达出他的优越性,如下面的试验结果:1编程过程中遇到的难题:2编程体会:欢迎下载
限制150内