信息论和编码实验.doc

数据库系统课程设计 学生姓名： 马 进 孝 学 号： 班 号： -02 指导教师： 黄 鹰 中国地质大学（武汉）信息工程学院 2012/5/15年 2 月 25 日  实验一 Huffman 编码（2 学时） 一、实验目的 1．复习C++程序基本编写方法，熟悉VC 编程环境。 2．会用VC 调试Huffman 编码程序。 二、实验内容 1．复习C++代码基本语法（结构体、树等数据结构定义） 2．根据Huffman 编码源代码，学习算法实现流程，培养自己动手能力，在 C++编译器下按步调试跟踪算法。 三、实验仪器、设备 1．计算机－系统最低配置 256M 内存、P4 CPU。 2．C++ 编程软件－ Visual C++ 7.0 （Microsoft Visual Studio 2003） Visual C++ 8.0 （Microsoft Visual Studio 2005） 四、实验原理 1． Huffman 编码原理： ①将信源符号按概率从大到小的顺序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) ②给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这 两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率， 结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源， 用S1表示。 ③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含 (n－2)个符号的缩减信源S2。 ④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概 率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各 信源符号所对应的码字。 2．Huffman 树的编码原理： 步骤1： 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只 有根节点） 步骤2： 在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作 为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率值 之和。 步骤3：对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。 五、实验步骤 1．VC 环境下，建一个C++控制台应用程序，并把源代码考到该程序目录 下。 2．项目文件中含有一个预编译头文件，一个主函数入口文件和Huffman 编 码算法文件。 3．在入口文件中，输入任一个离散信源进行编码调试。 4．设置好程序断点，仔细分析Huffman 树每步的建立过程。 5．输出离散信源中每个符号的Huffman 编码，并与手工运算的结果进行比 较。 六、实验报告要求 1． 按照实验一附 3 中实验报告样式书写本次实验报告。 2． 总结 C++语言学习心得，并结合Huffman 编码实验总结自己的得失， 指出今后自己要练习改进之处。根据自己实验情况，对本实验写出建议。 七、实验注意事项 1．指针数据结构定义 typedef struct { unsigned long weight; int parent, lchild, rchild; } HTNode, *HuffmanTree; typedef char** HuffmanCode; // 指向存放数组指针的数组即二维数组 2．二叉树生成操作放在数组中（节点n 和数组大小m 关系为：m=2*n-1）。 每次在树中找到两颗最小子树，其函数为Select(HuffmanTree HT, int n, int *s1, int *s2)，实际实现的是在数组中找到最小两个元素。另外注意C++的数组起始索引 是0，Matlab 起始索引是1；程序中为了方便从1 开始索引数组，HT[0].weight 的大小设为0xffffffffL。为了输出二进制Huffman 码，程序最后对每个符号进行 深度优先搜索，得到该符号的二进制字符，然后进行字符串拷贝，直到最后输出。 3哈夫曼是一种编码手段。也就是说保证将来的编码是最小长度的，最终生成最小的哈夫曼编码树，又称哈夫曼最小树。 它的原理是将一段文本中出现的字符按出现的频率决定其编码。然后按其最终的 编码生成一段明文。知道了这个原理，编码还是很简单的。 首先，要实现字符的频度表。也就是说，这18个字符中出现次数最多的一个记作 01，然后按其出现的频率，分别生成最小树就可以了！保证哈夫曼最小树的生成！ 至于树的生成，可以先生成一个双链表，分别表示左子树，数据，右子树。 #includeiostream 　　#includestring 　　using namespace std; 　　typedef struct TreeNode 　　{ 　　char c; 　　int w; 　　int parent; 　　int right;