课程设计报告--哈夫曼编码译码系统.doc

北京化工大学北方学院课程设计报告课程名称 数据结构课程设计 设计题目 哈夫曼编码/译码系统 专业、班级 软件工程0901 学 号 090203014 姓 名 李泽 指导教师 周建敏 设计时间 2012年9月10日2012年9月23日 2012年 10 月 12 日一、 引言（简要说明设计题目的目的、意义、内容、主要任务等） 随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：u 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；u 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；u 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；u 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、 正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严谨，符合各学科、专业的有关要求。）问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。（1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6） 进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。哈夫曼树的理论创建过程如下：一、构成初始集合对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 二、选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、删除左右子树从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，重复二和三两步，直到集合F中只有一棵二叉树为止。 因此，有如下分析：1. 我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存它们；2. 定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；3. 自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；4. 从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；5. 使用文件读写操作哈夫曼编码和解码结果的写入； 解题方法： 结构体、数组、类的定义：1. 定义结构体类型的signode 作为哈夫曼树的节点，定义结构体类型的hufnode 作为哈夫曼编码对照表的节点，定义HFM类实现对哈夫曼树的创建，利用其成员函数完成哈夫曼编码译码的工作。2. 定义signode 类型的全局数组SN256（为方便调用，之后的forest256，hufNode256均为全局数组）, 保存ASCII编码的字符，是否在文章中出现（bool类型）以及出现次数（int类型，权重），左右孩子节点位置，父节点位置信息；3. 为节省存储空间，定义signode * 类型的全局数组forest256, 模拟森林，在创建哈夫曼树的过程中保存出现字符的指针，模拟哈夫曼树选取和删除左右子树的过程；4. 定义hufnode 类型的全局数组hufNode256，在编码时最为哈夫曼编码对照表的节点，char 型c保存字符,int code100保存其哈夫曼编码；5. 定义HFM类，主要保存哈夫曼树的根节点指针，但其丰富的功能函数将实现哈夫曼编码译码的工作及其他功能；函数介绍：1. void init(signode * sig) 初始化数组SN；2. void compress()输出压缩对比情况的信息;3. void exchange()用两层for循环实现hufNodei节点的成员哈夫曼编码数组code前后元素的对换，因为在之前的编码过程中由于是从叶节点追溯至根节点，存入code数组的哈夫曼编码与哈夫曼编码的概念反向，故而要调整；4. signode * getroot()返回哈夫曼树的根节点指针；5. signode * HFM:creat()创建哈夫曼树，首先用三个for循环查看forest数组，找到权值最小的两个字符，以int型的min1,min2记录其下标，定义signode * 类型指针pp指向新生成signode节点，用指针操作使pp指向的节点的权值为min1,min2权值之和，pp做孩子指向forestmin1,右孩子指向forestmin2，min1,min2的父指针指向pp，然后将pp存入min1的位置，min2之后的每一个节点依次往前移一个位置，实现从forest数组中清除min1,min2并加入pp的操作；6. void HFM:hufcode()哈夫曼编码，用for循环控制查看hufNode 数组，其初始化已在creat（）的开始完成，对每一个字符实现编码，用while循环从叶节点开始，如果该节点是其父节点的左孩子就将codehufNodei.size+赋值0，否则赋为1，直至当前节点的父节点为空，while循环结束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf)将读入的文章以哈夫曼编码的形式存储，其中inf为读入文件的指针，outf为写入文件的指针,首先调用rewind(inf)函数将光标放置在文章开头，防止文件未关闭导致的错误，每读一个字符就用for循环在hufNode 数组中查找，因为hufNode 数组就是保存出现的字符的，故一定可以找到，然后再用fputc函数将code数组的内容写入文件，直至读入文件结束；8. void HFM:inorder(signode * sig)迭代法遍历树，遍历到叶节点时执行hufNodecount+.sig=sig语句实现hufNode 数组指向文章中出现的字符；9. int HFM:maxc() 计数变量，记录哈夫曼编码最大位数；10. void HFM:hufdecode(FILE* ipf,FILE* opf)解码，从哈夫曼编码到字符，输出到屏幕和指定的文件中；11. void input(FILE * f)初始读入文章，保存出现的字符记录修改其权重；数据结构选择与算法设计 数据结构选择：signode： struct signode /signode节点，哈夫曼树节点/ char c; /字符/ int weight; /权重/ bool b; /文章中是否出现/ signode * parent; signode * left; signode * right; signode() /初始化/ c=NULL; b=false; weight=0; parent=left=right=NULL; ; Cweightbparentleftright hufnode: struct hufnode /哈夫曼编码对照表节点/ signode * sig; int code100; /保存哈夫曼编码/ int size;bool b; hufnode()sig=NULL;size=0;b=true;Sig code100 size;HFM:class HFM /哈夫曼类/ private: signode * root; /哈夫曼树根/ signode * pt; /编码时做哨兵指针/ int alleaf; public: HFM(int all)root=pt=NULL;alleaf=all; /all是森林中树的个数/ HFM() signode * getroot()return root; signode * creat(); /创建哈夫曼树/ void hufcode(); /编码/ void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼编码存储文件/ void hufdecode(FILE* ipf,FILE* opf); /解码/ void inorder(signode * sig); int maxc(); /求取哈弗曼编码最大长度/;Root pt alleafcreat() hufcode() savewithhufcode(inf,outf) inorder(sig) getroot()hufdecode(ipf,opf) maxc()算法设计：init(SN)初始化SN数组input（f1）从f1读入字符 输出字符信息及权重 huffman.creat（）创建哈夫曼树 huffman.hufcode(); exchange(); huffman.savewithhufcode(f1,f2);哈夫曼编码并用该编码保存 文件输入数字选择compress（）1. 查看哈夫曼编码3.查看压缩率2.哈夫曼解码huffman.hufdecode(f2,f3)输入数字选择测试结果Doc窗口： 文件读写（部分）： 三、 结论（应当准确、完整、明确精练；也可以在结论或讨论中提出建议、设想、尚待解决问题等。） 初始的创建是哈夫曼编码译码系统成功的关键，我在创建的过程当中多次使用树的先根，配合中根遍历操作，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性； 通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应先写出算法，再写程序，一段一段调试；对于没有实现的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程序有错误，太难找 。感觉文件操作自己并不是很熟练，尽管在向显示器输出的时候并没有什么错误但是读写文件的时候就没那么顺利了，比如说当编写savewithhufcode函数时读文件，却总不执行，后来通过断点测试发现每次fgetc()返回值总为-1，于是我考虑是否是文件没有打开或者文件结束的缘故，后来想通了是之前打开的文件光标读操作结束后仍在结尾故每次总返回-1，故调用rewind函数将光标位置移动到文章开始。 用哈夫曼编码存储文件的时候还应注意数字0,1与字符0,1的不同，不应直接在fputc()函数中直接