Huffman编码译码实现.docVIP

南阳理工学院 数据结构课程设计 哈夫曼编码和译码的实现 移动1班 李保 1115115607 2012/5/16 努力造就辉煌 编程成就梦想 ------------------------------------------------------------------------------------------------------ 目录 ------------------------------------------------------------------------------------------------------ 一,题目介绍.......................................3 二,需求分析.......................................4 三,系统设计................................. ......5 四，程序流程图.....................................9 五,代码.......................................... 10 六，总结..........................................28 七，参考书目......................................29 一、题目: 哈夫曼编码/译码的设计与实现 构建一棵哈夫曼树，并用哈夫曼树来实现编码各译码的功能 二、目的与要求 1、目的： 通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法C\C++语言来完成系统的设计； 突出C语言的函数特征（以多个函数实现每一个子功能）或者C++语言面向对象的编程思想； 画出功能模块图； 进行简单界面设计，能够实现友好的交互； 具有清晰的程序流程图和数据结构的详细定义； 熟练掌握C语言或者C++语言的各种操作。 创新要求： 在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等 二，需求分析 哈夫曼树，又称最优二叉树。上课时我了解了哈夫曼树的某些奇特而强大的功能 ，通过哈夫曼树构造的编码译码系统具有加密的特性，而且加密性非常好，在某些领域中应用非常广泛！ 而且哈夫曼树的还有很大的功能就是压缩性很好！压缩性能可以达到20%至80%！ 而且通信的数码拨号时，我通常会用到十进制、八进制、或者十六进制数等。而输入数字后，数据将以二进制数编码后进行远距离通信传送。电文传输过程中，为了提高通讯效率，通常会要求所传输的二进制数码尽可能的短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但是同时要求各数字编码之间互不为前缀，从而不出现误码。设计一个程序构建一个赫夫曼树输出最优传输码。 因此我们应该能把哈夫曼树应用到我们的生活中！ 三，系统设计 1,分别定义两个结构体， typedef struct { char data; int weight; int parent; int lchild; int rchild; }HuffNode;//定义哈夫曼树节点的相关信息 HuffNode结构 data weight parent lchild rchild /*哈夫曼编码存储结构*/ typedef struct { int cd[MAXNUM];//存放HUFFMAN编码的数组 int begin; }HuffCode; HuffCode结点结构 cd[] begin 3、程序所用各函数功能 （1）创建赫夫曼树 Int HuffmanCreate( HuffNode *ht ) 输入用线性表HuffNode *ht存储的n个只含根结点的二叉树，及其权值。函数将各个根结点的父节点及孩子都初始化为0，由Huffman树的特性可知,创建Huffman树的总的结点数为2*n-1. 然后用for循环,从输入的n个结点中找到最小值min1和次小值min2,用p1和p2记录min1和min2的下标.然后将min1和min2的权值相加做为新的哈夫曼树的结点值,并将新的结点的权值插入到n到2*n-1剩下的空间中.通过逐步循环便可创建一棵哈夫曼树. 给哈夫曼树中各个节点的编码 void HuffmanCode(HuffNode ht[],HuffCode hcd[],in