课程设 计
目 录
一、 概述 1、设计目的 2、设计任务 3 、所用软件环境 二、 需求分析 1、问题描述 2、基本要求 三、 设计过程 1、霍夫曼编码 2、费诺编码 3、游程编码 4、算术编码
一、 概述 1设计目的
1.1深刻理解信源编码的基本思想与目的；
1.2深刻理解并掌握霍夫曼编码译码、费诺编码译码、游程编码译码、算术编码译码的原理与方法；
1.3提高综合利用所学理论知识独立分析和解决问题的能力，提高编程能力。
2设计任务
2.1对任意的字符分别进行2元霍夫曼编码、2元费诺编码、游程编码和
算术编码，并进行相应的译码； 2.2注意编码效率的计算.
3 所用软件环境
Visual C++ 6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。Visual C++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。Visual C++6.0由Microsoft开发, 它不仅是一个C++ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C++6.0由许多组件组成，包括编辑器调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。这些组件通过一个名为
Developer Studio的组件集成为和谐的开发环境Microsoft的主力软件产品。Visual C++是一个功能强大的可视化软件开发工具。
二、 需求分析 1问题描述
1.1霍夫曼编码首先要解决的问题是给定一段字符串，如何建造霍夫曼树；怎样根据该树求每个字符的编码，并对该段字符串进行编码；怎么样将得到的编码进行译码；怎么样遍历输出树中的叶子节点。 1.2费诺编码,给定一段字符串，如何排序；分治法编码如何实现；如何计算频率并求编码效率。
1.3游程编码，如何统计输入的灰度值；灰度值如何编码；解码如何回溯；编码效率与之前两个的差异。
1.4算术编码，如何计算精度；如何找到某字符落在哪一个频率区间；反向解码的难点。
2基本要求
2.1霍夫曼编码要达到的要求：用户从键盘随机输入一串字符串，程序读入字符串，统计每个字符的频率，建造霍夫曼树，编码译码，并根据统计的字符频率求出根据公式求出编码效率。
2.2费诺编码要达到的要求：用户从键盘随机输入一串字符串，程序读入字符串，统计每个字符的频率，将频率按大小排序，用分治法编码，译码，求编码效率。
2.3游程编码要达到的要求：输入灰度值矩阵，进行编码译码，求出编码效率。
2.4算术编码要达到的要求：输入符号串，编码译码，计算精度。
三、 设计过程 1、霍夫曼编码 1.1算法思想
哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。
统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码
越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。
为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。按照上面的算法，则可按照下面图的构造过程生成huffman树。 Huffman树产生流程:
1.2模块划分
（1）主程序模块：
Int main() {
初始化； 输入数据； 执行功能；
显示结果； }
（2）各功能模块