信息论与编码实验.doc

《信息论与编码实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据库系统课程设计学生姓名：马进孝学号：班号：-02指导教师：黄鹰中国地质大学（武汉）信息工程学院2012/5/15年2月25日实验一Huffman编码（2学时）一、实验目的1．复习C++程序基本编写方法，熟悉VC编程环境。2．会用VC调试Huffman编码程序。二、实验内容1．复习C++代码基本语法（结构体、树等数据结构定义）2．根据Huffman编码源代码，学习算法实现流程，培养自己动手能力，在C++编译器下按步调试跟踪算法。三、实验仪器、设备1．计算机－系统最低配置256M内存、P4CPU。2．C

2、++编程软件－VisualC++7.0（MicrosoftVisualStudio2003）VisualC++8.0（MicrosoftVisualStudio2005）四、实验原理1．Huffman编码原理：①将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)②给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一

3、次缩减信源，用S1表示。③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。2．Huffman树的编码原理：步骤1：将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）步骤2：在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值

4、设为两棵子树频率值之和。步骤3：对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。五、实验步骤1．VC环境下，建一个C++控制台应用程序，并把源代码考到该程序目录下。2．项目文件中含有一个预编译头文件，一个主函数入口文件和Huffman编码算法文件。3．在入口文件中，输入任一个离散信源进行编码调试。4．设置好程序断点，仔细分析Huffman树每步的建立过程。5．输出离散信源中每个符号的Huffman编码，并与手工运算的结果进行比较。六、实验报告要求1．按照实验一附3中实验报告样式书写本次实验

5、报告。2．总结C++语言学习心得，并结合Huffman编码实验总结自己的得失，指出今后自己要练习改进之处。根据自己实验情况，对本实验写出建议。七、实验注意事项1．指针数据结构定义typedefstruct{unsignedlongweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//指向存放数组指针的数组即二维数组2．二叉树生成操作放在数组中（节点n和数组大小m关系为：m=2*n-1）。每次在树中找到

6、两颗最小子树，其函数为Select(HuffmanTreeHT,intn,int*s1,int*s2)，实际实现的是在数组中找到最小两个元素。另外注意C++的数组起始索引是0，Matlab起始索引是1；程序中为了方便从1开始索引数组，HT[0].weight的大小设为0xffffffffL。为了输出二进制Huffman码，程序最后对每个符号进行深度优先搜索，得到该符号的二进制字符，然后进行字符串拷贝，直到最后输出。3哈夫曼是一种编码手段。也就是说保证将来的编码是最小长度的，最终生成最小的哈夫曼编码树，又

7、称哈夫曼最小树。它的原理是将一段文本中出现的字符按出现的频率决定其编码。然后按其最终的编码生成一段明文。知道了这个原理，编码还是很简单的。首先，要实现字符的频度表。也就是说，这18个字符中出现次数最多的一个记作01，然后按其出现的频率，分别生成最小树就可以了！保证哈夫曼最小树的生成！至于树的生成，可以先生成一个双链表，分别表示左子树，数据，右子树。#include　　#include　　usingnamespacestd;　　typedefstructTreeNode

8、　　{　　charc;　　intw;　　intparent;　　intright;　　intleft;　　inttag;　　char*code;　　}Node;　　voidFind(Node*tree,intn,int&m1,int&m2)　　{　　m1=-1;　　while(tree[++m1].tag!=0);　　m2=m1;　　while(tree[++m2].tag!=0);　　for(inti=m2+1;i