軟件课程设计-Huffman编码.docxVIP

计算机软件基础课程设计题目：Huffman编码学院：信息与通信工程学院专业：通信工程专业任务书一题目1Huffman编码（难度系数10）主要内容完成Huffman编码中各个子函数的全部功能。学会编写DLL函数。掌握C++编程环境的基本调试方法，熟练使用可视化C++编程工具。4、理解信源编码的软件实现过程，掌握数据压缩的基本原理。设计要求1、上交课程设计的书面材料，要求打印。包括课程设计任务书、主要内容，Huffman编码源程序，指定函数的流程图，回答问题的详尽解答等，对程序的功能进行客观评价，明确指出自己编写了哪些具体函数。2、上交Huffman编码电子版源程序。3、写出build_tree函数的流程图。4、回答下面问题。(1) 给定已压缩文件（见电子版），请用同伴的解码程序还原成*.doc格式，还原后，word文件的内容是什么？(2) 对于给定的待压缩文件，Huffman编码是否唯一？为什么？(3) Huffman编码是否能进行无限次数压缩，为什么？例如对于原始文件k.doc，第1次压缩成kdoc1.out，；然后把kdoc1.out看成待压缩文件，进行第2次压缩，生成压缩文件kdoc2.out；然后把kdoc2.out看成待压缩文件，进行第3次压缩，生成压缩文件kdoc3.out......。请画出原始文件和每次压缩后的ASCII码字符概率分布图。(4) 自己编写一个求素数函数，把它书写成一个动态链接库形式，并在主函数中调用它。尝试把自己编写的Huffman编码程序写成动态链接库和静态链接库形式（无需上交），并比较以下三种EXE文件的大小。A：调用静态链接库生成的EXE执行文件。B：调用动态链接库生成的EXE执行文件。C：直接调用函数生成的EXE执行文件。5：假设简单马尔可夫信源A={a, b, c}，某符号输出与它之前的1个字母相关，信源输出序列为：a, b, b, c, c, b, a, a, b, b, b, c, c, c, c, a, b, a, b, a, b, c, a, b, a, b总计26个字符，因为总计只有3个字母，所以未压缩时，每个字母由2bit组成，回答下列问题：未压缩时，求序列总计的编码长度。采用通常的Huffman编码（也叫0次序Huffman编码）压缩后，求序列总计的编码长度。若考虑某符号输出与它之前的1个字母相关，这在日常中是经常见到的，例如英语字母q之后出现字母u的概率接近于1，而其它字母出现的概率近似于0。若采用这种Huffman编码（也叫1次序Huffman编码）压缩后，求序列总计的编码长度。（提示：此时是否只有一棵Huffman树？）以上3种编码长度是否相同，为什么？主要仪器设备计算机一台，安装Windows XP 操作系统、Microsoft Visual C++ 6.0、MSDN Library。主要参考文献[1] 侯俊杰. 深入浅出MFC(第二版)[M]. 武汉：华中科技大学出版社, 2001.[2] 谭浩强. C程序设计（第二版）[M].北京：清华大学出版社, 1999..[3] 孟彩霞. 计算机软件基础[M]. 陕西：西安电子科技大学出版社, 2003.[4] 严蔚敏, 吴伟民. 数据结构[M]. 北京：清华大学出版社, 2005.课程设计进度计划（起止时间、工作内容）选做Huffman数据压缩题目的同学，2人1组，1人做编码，1人做解码，整个课程设计共20学时，具体进度如下：4 学时了解课题背景，选题，学习DLL，学习文件读写。4 学时读文件、初始化Huffman树，计算权重。4 学时构建Huffman树。4 学时根据Huffman树，生成代码。4 学时调试程序，答辩。课程设计开始日期2012-9-17课程设计完成日期2012-10-15课程设计实验室名称计算中心机房地点健翔桥校区摘要Huffman编码霍夫曼编码是可变字长编码的一种。它是由Huffman于1952年提出的一种编码方法，该方法完全依据字符出现概率来构造异字头平均长度最短的码字，称之为最佳编码。在数据通信中，需要将传送的文字转换成二进制的字符，用0、1码的不同排列来表示字符。如果采用等长编码，编码的长度取决于报文中不同字符的个数。如果报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不同的，如果让使用平频率高的用短码，使用频率低的用长码，就可以优化整个报文编码。关键字：Huffman编码最优二叉树数据压缩动态链接库目录1、Huffman算法 ---------------------------------------------------------------------------- 5 Huffman编