综合实验报告格式--哈弗曼树--数据结构

华北科技学院 用哈夫曼编码实现文件压缩 实验报告 用哈夫曼编码实现文件压缩 实 验 报 告 课程名称课程名称 数据结构 B 实验学期实验学期 2014 至至 2014 学年学年 第第 1 学期学期 学生所在系部学生所在系部 计算机系 年级年级 2010 专业班级专业班级 网络 B10 3 学生姓名学生姓名 学号学号 任课教师任课教师 实验成绩实验成绩 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 一 实验题目 用哈夫曼编码实现文件压缩 二 实验目的 1 了解文件的概念 2 掌握线性链表的插入 删除等算法 3 掌握 Huffman 树的概念及构造方法 4 掌握二叉树的存储结构及遍历算法 5 利用 Huffman 树及 Huffman 编码 掌握实现文件压缩的一般原理 三 实验设备与环境 微型计算机 Windows 系列操作系统 Visual C 6 0 软件 四 实验内容 根据 ASCII 码文件中各 ASCII 字符出现的频率情况创建 Haffman 树 再将各字符对应的哈 夫曼编码写入文件中 实现文件压缩 五 概要设计 在文件存储时 一个整型的字符要占用一个字节的空间 对于某些不常用 的字符这样会造成空间的浪费 但如果用位来存储数据 可以将字符重新编码 使那些常用的字符存储空间相对短的 不常用的字符相对长些 可以节约空间 哈夫曼编码即是这样一个过程 用哈夫曼编码进行文件压缩 首先应对所用的字符进行哈夫曼变编码 在 这之前应先对所用字符进行权值统计 在编码哈夫曼树的时候 选取两个权值 最小的依次构造哈夫曼树 进行哈夫曼编码时 使哈夫曼树的左孩子上的分支 编码为 0 右孩子上的分支编码为 1 然后对文件进行压缩 压缩过程用到了文件的读写 六 详细设计 头文件的构造 头文件首先应用宏定义 对文件要用到的数据进行定义 然后定义了结构 体类型 将所要到字符的权值 数据 双亲编号与孩子编号放在结构体中 使 程序间的关系变得紧密 定义第二个结构体 其中包含结构体数组和树根的编 号 定义指针 使其指向第二个结构体 接着类型定义 定义了结构体 其中 包含字符原码值 哈夫曼编码值和哈夫曼编码值的长度 并将其取名为 HaffCode 将程序所用到的函数包含在头文件里 哈夫曼树的构造 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 在程序开头先对程序所用到的变量进行定义 包括指向结构体的指针 整 型变量 权值最小的结点的编号 第二小的结点的编号 权值最小的结点的权 值 第二小的结点的权值 接着为哈夫曼树分配空间 然后调用 asserF 函数对条件进行判断 看是否 满足构造哈夫曼树的条件 对含有 m 个字符的结点构造哈夫曼树时 将产生 2m 1 个结点 为了便于程序进行 先利用循环结构对每个结点里的左右孩子 及双亲编号进行初始化 然后将 m 个字符中的数据从 0 位开始依次存入各个结 点中 用 pht ht i ww w i 实现字符权值的存储 用 pht ht i info i 实现字 符数据的存储 剩下结点的权值全赋值为 1 构造哈夫曼树是这个程序的核心 也是文件是否能压缩成功的关键 从结 点中选择权值最小的结点的编号分别赋给 firstMinIndex 和 secondMinIndex 权 值也进行相应赋值 将两结点的权值相加后放到未放元素的结点处 m i 将这 两个权值最小的结点的双亲编号都替换为 m i 而 m i 处的左孩子放第一小的结 点的编号 右孩子放第二小的结点的编号 然后从产生的 m i 个结点中再找权 值最小的两个 重复上述操作 直到所有的结点构成一棵树 文件在对字符进 行哈夫曼编码时用到了位的运算 并且使用了递归的算法 统计权值 在统计权值时定义了两个数组 一个是字符型的数组 用于输入数据时的 使用 另一个是结构体类型的数组 其中包括字符域和权值域 用于统计权值 时使用 首先输入数据 并将数据存储在字符类型的数组中 然后从第一个字符开 始 使第一个数组中的数据与第二个数组中的字符进行比较 若相等 则字符 相应的权值加 1 若不相等 则将字符放入第二个数组中未放字符的数据域 权值加 1 直到将第一个数组中的所有字符遍历完为止 假设两数组分别为 s1 和 s2 s1 中含 3n 个字符 s2 中含 n 个字符 s2 定义如下所示 Struct tongji Char data Int w 主函数 程序在运行的时候运用了文件的读写 和大多数程序一样 这个程序在最 开始对所需的变量进行了定义 包括哈夫曼数组 输入文件名数组 输出文件 名数组 指向文件的指针等 首先根据条件判断文件是否已打开 若没有打开则输出 please enter your file address n 若打开则将 argv 赋给 inputFileName 和 outputFileName 然后计 算文件名的长度 将 rer 连接到 outputFileName 的后面 以此来区分程序运行 前后的文件 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 assertF 函数的流程图 由主函数传来 condition 和 errorMsg 的值 Condition 的值为真 F T 输出 errorMsg 的值 Abort 统计权值流程图 向 s1 中输入数据 当 i 3n S1 i s2 j d ata T F S2 j 1 data s1 i S2 j w S2 j 1 w I 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 哈夫曼树构造流程图 定义指针变量及整型变量 分配空间 分配成功 F T 当 I 2 m 1 为结点的左右孩子及双亲赋值 I m T F 将结点的权值域及数据域进行赋 值 将权值位标记为 1 i 当 i m 1 当 j m i 所指结点权值小于最小权值的 值且双亲域值为 1 F T 比第二最小 权值小 T F 将该结点的值赋 到 secondMin 相 应的位置 将该结点 的值赋到 minFirst 相应的位 置 J 输出 errorMsg 的值 将权值最小和第二小的双亲域赋值为 m i 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 打开文件流程图 Argc 1 F T 对 inputFileName 和 outputFileName 进行 赋值 将 rer 连接到 outputFileName 后 并使 inputFileName 和 outputFileName 成为完 整的字符串 打开文件成功 F T 输出 file path not found 输出 File open success 输出 please enter your file address 七 测试结果及分析 对结点 M i 的相应的各位置进行赋值 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 总结体会 经过一年的学习 终于可以接触一点儿比较正式的程序 感觉真的很好 相对以前的程序 这次的程序不但在理解上有点儿难度 在程序上的运行上和 以前也不同 这次是在 DOS 环境下运行的 而以前只是直接在程序里边进行运 行 刚开始觉得很不可思议 但后来发现程序只是被分开 然后再被组装到一 块儿 相对于以前的程序 更有利于多人同时编写 这个程序是对文件进行压 缩 和实际生活很接近 因此这个程序使我更加感觉到学好程序对生活帮助的 巨大作用 该程序的核心是对结点进行哈夫曼编码 这听起来或许有点难度 但通过 课上的学习 这个很容易做到 即利用循环 找权值最小的结点 构造新结点 将其构造成二叉树即可 然后进行二进制编码 并存储 这次的程序对于我最大的挑战 应该算是对于以前没有学的自学 从上小 学开始 一切的学习都是老师教哪儿就看哪儿 不教的就很少去理会 即使看 也只是粗略的很不详细的看 基本不会掌握很多有用的知识 可是这次实验用 到的文件的运行和位运算 都是以前很少涉及的 因此要看懂程序就得自己学 习 这和以前的学习有很大的不同 但更接近了大学的学习方式 很值得在以 后的学习中继续运用 这应该才是学习的目的 会自己学习而不是一味的靠别 人学习 刚看到程序 看到有好多不认识的函数 心里感到很烦 尤其看到打印出 来的那么多函数 当时真有点而泄气了 后来发现已经有好多同学开始着手综 合实验 就觉得若再不做可能就只能在仓促中做 这样一学期的学习岂不是要 再仓促中画上句号 这不是我想要的 因此无论如何也要把程序弄好 最初我在图书馆找了点儿对文件进行处理的程序 但是发现只有哈夫曼编 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 码 没有压缩 后来就放弃了 在网上看到的程序都只是在 C 里运行 有关 文件的运算很少 所以到后来就直接用了老师的代码 看程序之前 我先把有关文件的内容看了下 发现和文件有关的函数名和 以前学的函数在命名上很相似 而且都能见名知意 有了以前学习的基础 有 关文件这一章的内容看起来就简单多了 像这个是打开文件的 fopen inputFileName rb 一个语句 和字符串的复制和链接很相似 只不过这 个是先输入文件名 后面是文件的打开方式 fscanf keyFile d 这 一句是对文件进行字符的输入 语句格式为先输入文件名 然后字符类型 最 后是存放的地址 这些都是文件的基本操作 简单 方便 对结点进行哈夫曼编码时 在我所看过的程序里 编码的过程都是一样的 所说语句会有所不同 但思路都是一样的 均是对结点进行赋初值 为下面的 操作提供方便 然后对已有的字符结点赋值 构造哈夫曼树 这些虽然简单 却是很重要的东西 统计权值 我自己感觉是用两个数组进行统计的程序更容易接受 而且在 程序里加入这个函数 增加了程序的可运用性 可以自己进行文件的输入 再 运用函数统计权值 进而构造哈夫曼树 实现文件压缩 不必只拘泥于一个文 件 更能深刻体会文件压缩的过程 在看程序时 不但看了老师的程序 同时也看了些同学找得关于文件压缩 的程序 发现程序中对函数的运用有好多 以前我一直比较排斥用函数写程序 因为在看主程序时看到陌生的函数心里很反感 有时形参和实参所用的字符不 一致时还要分辨哪个字符代表哪儿个参数 看得多了就感觉都晕了 可是看过 一些比较长的程序后才发现 调用函数编写程序其实很简单 只要搞懂了每个 程序的作用是什么 对每个函数都了如指掌 在看程序时就会发现程序的脉络 很清晰 主函数就是将每个函数放到一起的一次运用 将函数要用到的变量定 义好后 再调用函数 就可以将一个有特殊功能的函数编写出来 以前曾听说 在开发软件编写程序时 都是先对程序分块 好多人一块儿编写 而对程序进 行划分 这需要有很丰富的编写程序的经验 这次我真正体会到了这句话的意 思 只有丰富的编写程序的经验 才能对程序进行正确有效的划分 才不至于 在分别编写程序时出现很多关系比较密切的程序被分开的现象 编程是一件需要长期实践以此来增长经验的过程 如果只是上课的时候学 一点儿书本上得知识就想把编程学好 这是远远不够的 还必须多看书 多动 手 在看别人的程序时 自己也要有自己的想法 并将其付诸行动才行 而课 外书则是必不可少的 在大学的这段时间应充分利用好课外时间 多读书 多 思考 开充实自己 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 八 教师评语 评定项目评定项目A AB BC CD D评定项目评定项目A AB BC CD D 算法正确界面美观 布局合理 程序结构合理操作熟练 语法 语义正确解析完整 实验结果正确文字流畅 教教 师师 评评 价价 报告规范题解正确 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 其他 评价教师签名 年 月 日 Code c文件 include ECBTree h include include include define LENGTH 128 define DEBUG 1 define REARPOS 80 char dotTxt txt char dotRer rer int getBinLen unsigned long inData void main int argc char argv long wList LENGTH HaffCode haffList LENGTH PHtTree myHtTree file data char inputFileName LENGTH outputFileName LENGTH FILE inputFile outputFile keyFile int fileNameLen 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 binary opeartion data char inData outputData unsignedlong curCode tmpBinData int curLen realLen curIndex int i int count unsigned long rearCode rear data consult int rearCodeLen open the files if argc keyFile not founded n return for i 0 i LENGTH 1 i fscanf keyFile d fscanf keyFile d myHtTree haffmanAlgorithm LENGTH wList step2 for i 0 irootIndex 0 x000000 0 haffList fprintf stdout haffCode List r n for i 0 i LENGTH 1 i fprintf stdout d haffList i haffCode fprintf stdout d r n haffList i haffCode fprintf stdout haffCode List Len r n for i 0 i LENGTH 1 i fprintf stdout d haffList i haffCodeLen fprintf stdout d r n haffList i haffCodeLen if DEBUG printf ntest start n starting setting curIndex curLen 0 rearCode haffList REARPOS haffCode rearCodeLen haffList REARPOS haffCodeLen while feof inputFile count 0 outputData 0 x01 while count 8 if curIndex curLen 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 1 get data if feof inputFile break inData fgetc inputFile if inData 1 else the rear output adjust for i 0 i 8 count i outputData rearCodeLen 1 i the consult below will make error happen outputData Should be a ascii file curCode haffList inData haffCode curLen haffList inData haffCodeLen realLen getBinLen curCode i curLen realLen curIndex 0 if i 0 outputData curLen curIndex 1 outputData 1 outputData char tmpBinData curIndex count 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 fputc outputData outputFile if DEBUG printf ntest ends n step3 end of code fclose inputFile fclose outputFile getchar return int getBinLen unsigned long inData int i 0 if inData 0 return 1 else while inData 0 inData 2 i return i ECBTree c 文件 include ECBTree h include include PHtTree haffmanAlgorithm int m EBTreeType w PHtTree pht int i j int firstMinIndex secondMinIndex int firstMinW secondMinW pht PHtTree malloc sizeof struct HtTree 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 assertF pht NULL in haffman algorithm mem apply failure n Initialize the tree array for i 0 iht i llinkIndex 1 pht ht i rlinkIndex 1 pht ht i parentIndex 1 if iht i ww w i pht ht i info char i else pht ht i ww 1 for i 0 i m 1 i new Inner Node Num m 1 firstMinW MAXCHAR firstMinIndex 1 secondMinW MAXCHAR secondMinIndex 1 for j 0 jht j wwht j parentIndex 1 trans minFirst info to minSecond info secondMinIndex firstMinIndex secondMinW firstMinW set new first min node firstMinIndex j firstMinW pht ht j ww else if pht ht j wwht j parentIndex 1 update second node info secondMinW pht ht j ww secondMinIndex j 华北科技学院 用哈夫曼编码实现文件压缩 实验报告 Construct a new node m i is current new node s index pht ht firstMinIndex parentIndex m i pht ht secondMinIndex parentIndex m i pht ht m i ww firstMinW secondMinW pht ht m i llinkIndex firstMinIndex pht ht m i rlinkIndex secondMinIndex pht rootIndex m i return pht Invoke preHaffListMake myHtTree myHtTree rootIndex 0 x00 0 myList void preHaffListMake PHtTree inTree int rootIn