2022年实验报告格式样例.docx

精品学习资源用哈夫曼编码实现文件压缩实 验 报 告课程名称数据结构 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.把握 Huffman 的概念及构造方法；4.把握二叉树的储备结构及遍历算法；Huffman 树及 Huffman 编码，把握实现文件压缩的一般原理；三、试验设备与环境：微型电脑· Windows 系列的操作系统· 四、试验内容：依据 ascii 码文件中各 ascii 字符显现的频率情形创建 Huffman 树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩；五、概要设计：此程序就是用 Microsoft Visual C+编写的；依据 ascii码文件中各 ascii字符显现的频率情形创建 Haffman 树，再将各字符对应的哈夫曼编码写入文件中；第一是对赫夫曼树进行定义， 然后编写各个子函数， 最终通过主函数对子函数的调用来实现程序的功能，其中用到了关于文本读入、选择权值最小的字符、赫夫曼编码、建立赫夫曼树等的子函数；通过读入的文本，对每个字符显现的次数进行统计，让后通过选择函数，选择权值最小的字符通过编码函数进行编码，然后把赫夫曼树的左右孩子分别赋值0、 1；用这两个数字来表示各个字符，求出各个字符的二进制编码并把字符的二进制码存入文本中，便实现了压缩功能；图见下页：欢迎下载精品学习资源主要结构图如下：主函数读取输出利用 c 中函数fopen 打 开 一个文档把 赫 夫 曼 树转 成 二 进 制数字输出压缩后的文件，输出每个字符的权重值，左右孩子节点以及对应的二进制编码计 算 读 取 文件 的 每 个 字符 的 权 值 及文件的长度把二进制编码输出，并运算文件依据各个字符的权值建立赫夫曼树把 压 缩 后 的文 件 存 入 一个 新 的 *.txt 文档中输出赫夫曼树六、具体设计：<1>赫夫曼树的结构体的定义， 其中包括权值、 父母、左右孩子及要编码的字符；欢迎下载精品学习资源用这个结构体定义个赫夫曼数组；定义如下：struct nodelong weight;/ 权值unsigned char ch;/字/符int parent,lchild,rchild;char code256;/编码的位数最多为 256 位int CodeLength;/编码长度hfmnode512;<2>读入文档，并运算其中显现的字符以及每个字符的权值，并统计文档中全部的字符个数：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 码值代替结点下标FileLength=0;while.feofifp/ 用来统计读入的文件长度以及每个显现字符的权值fread&c,1,1,ifp;/ 一个流中读取数据hfmnodec.weight+;FileLength+;<3>初始化赫夫曼树，运算赫夫曼树的节点数，把左右孩子，双亲指针都定义成 1:fori=0;i<256;i+ ifhfmnodei.weight.=0hfmnodei.ch=unsigned chari; n+;/叶子数hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1;欢迎下载精品学习资源m=2*n-1;/ 哈弗曼树结点总数j=0;fori=0;i<256;i+/ 去掉权值为 0 的结点ifhfmnodei.weight.=0hfmnodej=hfmnodei; j+;fori=n;i<m;i+/ 初始化根结点hfmnodei.lchild=hfmnodei.rchild=-1; hfmnodei.parent=-1;<4>写 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.weight<minmin=nodepi.weight; s1=i;return s1;<5>建立赫夫曼树： fori=n;i<m;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; / 编码<6>利用子函数 encode，对赫夫曼树进行编码 ,做孩子为 0，右孩子为 1： void encodestruct node *nodep,int n欢迎下载精品学习资源/从叶子向根求每个字符的哈弗曼编码int start;int i,f,c;char codes256;codesn-1='0'/ 编码终止符fori=0;i<n;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;<7>将各个字符的二进制码存入文本， 由于储备时依据 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<n;i+ifc=hfmnodei.ch break; /ch 必需也为 unsigned 型strcatcodes,hfmnodei.code; whilestrlencodes>=8fori=0;i<8;i+/ 将 codes的前 8 位 01 代码表示的字符存入 cifcodesi='1' c=c<<1|1;else c=c<<1;fwrite&c,1,1,ofp; / 将新的字符写入目标文件欢迎下载精品学习资源sumlength+; strcpycodes,codes+8;/更/新 codes的值欢迎下载精品学习资源iffilelength=FileLength break;/再将剩余的不足 8 位的 01 代码补全 8 位，连续写入ifstrlencodes>0strcatcodes,"00000000" fori=0;i<8;i+ifcodesi='1' c=c<<1|1;else c=c<<1;fwrite&c,1,1,ofp; sumlength+;fori=0;i<n;i+欢迎下载精品学习资源字节储备fwrite&hfmnodei.ch,1,1,ofp;c=hfmnodei.CodeLength;/编码最长为 256 位，因此只需用一个fwrite&c,1,1,ofp;/写入字符的编码ifhfmnodei.CodeLength%8.=0forj=hfmnodei.CodeLength%8;j<8;j+/ 把编码不足 8 位的欢迎下载精品学习资源在低位补 0,赋值给 C，再把 C 写入strcathfmnodei.code,"0"whilehfmnodei.code0.=0/ 开头存入编码，每 8 位二进制欢迎下载精品学习资源数存入一个字节c=0;forj=0;j<8;j+欢迎下载精品学习资源ifhfmnodei.codej='1' c=c<<1|1;else c=c<<1;欢迎下载精品学习资源位，连续存入编码strcpyhfmnodei.code,hfmnodei.code+8;/ 编码前移8count+; /编码占的字节数的总值fwrite&c,1,1,ofp;欢迎下载精品学习资源printf"n"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编程体会：欢迎下载