哈夫曼编码与解码实验报告.docx

数据结构课程设计报告 题目： 哈夫曼编码与解码 学生姓名： 侯清源 学 号： 1021111118 班 级： 102111111 指导教师： 张 军 2012年 6月 1日目录需求分析说明总体设计详细设计实现部分程序测试部分实验总结附图：开发环境和工程文件介绍1， 需求分析说明A，通信线路中实现信息的最大传送，利用变长编码的方式，可以有效充分利用带宽，实现信息传送前的压缩。B，在文件保存时，利用哈夫曼编码的方式，压缩文件。可以实现硬盘存储最大的信息量。C，实验目的：1，.学会使用哈夫曼进行对文本文件的编码与译码。2，通过对哈夫曼的编码与译码，能够理解通信领域中的数据传输的压缩原理。3，通过对哈夫曼的编码/译码器的研究与分析，能够彻底的理解软件设计的一般步骤和方法，灵活地运用各种数据结构进行操作，熟练地把所学地数据结构应用地软件开发当中，提高软件设计水平，增强程序设计能力。D，实现功能 压缩：实现对用户输入的字符串压缩，并在终端显示相应字符对应的 频率，编码，编码长度，平均编码长度，字符个数。 并显示字符串编码后的二进制文件。解压：实现对压缩后的二进制文件解压，还原为原来的字符串。并显示在终端。和用户输入的字符串比较。2， 总体设计2,1 开发环境介绍 编译器：gcc 4.6.3 编辑器：vim 7.0附插件：ctags、taglist、autocomplpop。 打开syntax enable、syntax on、set number。 操作系统：Ubuntu 12.04 LTS 硬件环境：Processor： Intel(R) Core i5-2430 CPU 2.40GHz Vendor:AcerTravelMate 4750G Business LaptopMemory:4G 2.2系统框架 系统结构流程 算法思想描述（文字和图）1， 首先，根据用户输入的字符串得到字符频率。根据频率得到频率数据，对该频率数组由栈顶到栈低由小到大排列，同时将从小到大顺序存入优先队列2， 构造哈弗曼树，过程如下：从栈中取出两个最小频率。按照左小右大的原则。构造哈弗曼树。同时生成父节点，即频率和。同时父节点入栈，重新按照由小到大的顺序排列。3， 重复2过程，直到栈为空。4， 编码解码的过程编码时，根据哈弗曼树，左0右1，建立mapchar,vector 容器，右边存储字符，右边存储编码。编码时，从根节点递归遍历算法编码，左节点编码时添加0，右节点编码添加1解码时，也是根据哈弗曼编码树，从根节点开始，如果碰到编码的首部是1，往右遍历；如果是0，往左遍历。直到叶子节点，遍历匹配字符成功，返回匹配的字符。同时回到根节点，重复该步骤，翻译下一个编码。3， 详细设计3.1，类模板设计 1，类模板设计资料：高永平老师给的资料：数据结构（STL框架）王晓东编著，陈道蓄主审2，主要是STL编程，并利用了vector map queue 等容器，使用了容器的迭代器iterator哈夫曼树类结构模板Hafftree类模板原型TemplateHufftree+ template Hufftree(InputIterator begin,InputIterator end);构造哈夫曼树+ Hufftree()析构函数+ template vector encode(InputIterator begin,InputIterator end);编码+ vector encode(DataType const& value);返回字符编码+ double encodelength(DataType const& value);返回字符编码长度+ template void decode(vector const& v,OutputIterator iter);对字符串解码-class Node;字符串节点类-class NodeOrder;排序时用的类-Node *tree;根节点- typedef mapDataType ,vector encodemap; encodemap encodetable;编码表 Node类成员：templateNode +Frequency freqeuency;权或频率 +Node *leftChild;左孩子指针 +union Node *rightChild;右孩子指针 DataType *data;字符域指针TemplateNodeOrder初始化的时候对节点排序3.2，类模板设计源代码（排版：QtCreator 4.7）Hufftree头文件/-/ 哈夫编码与解码 Haffman encoding & decoding /作者：Houstar Author By Houstar /-/#ifndef Huffman_H#define Huffman_H#include#include#includeusing namespace std;/*哈夫模板设计，需要参数：数据类型和频率*/templateclass Hufftree public: /*输入迭代器，区间固定至begin到end,生成哈夫树*/ template Hufftree(InputIterator begin,InputIterator end); /*析构函数，删除树*/ Hufftree() delete tree; /*哈夫编码，区间固定至begin到end*/ template vector encode(InputIterator begin,InputIterator end); /*返回单个字符的编码*/ vector encode(DataType const& value) return encodetablevalue; /*返回字符的编码长*/ double encodelength(DataType const& value) typename encodemap:iterator iter = encodetable.find(value); return iter-second.size(); /*哈夫解码,输入待解码的数组V，输出iter*/ template void decode(vector const& v,OutputIterator iter); private: class Node;/节点类 Node *tree;/指向树的指针 typedef mapDataType ,vector encodemap; encodemap encodetable;/存储哈夫编码后的表 class NodeOrder;templatestruct Hufftree:Node Frequency frequency;/字符出现的频率或权 Node* leftChild;/左边孩子指针 union Node* rightChild; /if leftChild!=NULL如果不是叶子节点 DataType* data; /if leftChild=NULL如果是叶子节点 ; /*节点的构造函数,通过给基类传值构造*/ Node(Frequency f,DataType d): frequency(f), leftChild(0), data(new DataType(d) /*构造函数，该函数用来求父节点（最小两个节点出列，同时构造父节点）入列*/ Node(Node* left,Node* right): frequency(left-frequency+right-frequency), leftChild(left), rightChild(right) /*析构函数*/ Node() if(leftChild) delete leftChild; delete rightChild; else delete data; /*该函数对哈夫树的各个节点进行0，1编码*/ void fill(mapDataType, vector & encodetable, vector& prefix) if (leftChild)/递归到叶子节点停止，叶子节点：左孩子为空 prefix.push_back(0);/尾部加0 leftChild-fill(encodetable, prefix);/递归调用该函数 prefix.back() =1;/传回最后一个数据 rightChild-fill(encodetable, prefix);/递归调用该函数 prefix.pop_back();/删除最后一个数据 else encodetable*data = prefix;/将字符对应的编码存入数组的一个元素中，下标由 /data确定，即data为keyword,prefix为01010的编码 ;/*根据权值或频率生成哈夫树*/templatetemplate/InputIterator为频率或权值表，是二元组数组。存储字符及频率Hufftree:Hufftree(InputIterator begin, InputIterator end): tree(0) priority_queueNode*, vector, NodeOrder pqueue;/构造了一个优先队列，并非FIFO /优先队列参数说明： /priority_queue /其中Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 /数据类型节点类。存储容器为vector，排序方式为按权从小到大 while (begin != end)/往优先队列添加权值二元组。 /*生成频率或权值的节点类，节点左边指向频率，右边指向字符*/ Node* dataNode = new Node(begin-second, begin-first);/l.r pqueue.push(dataNode); +begin; while (!pqueue.empty()/队列不为空 Node* top = pqueue.top();/队首出列 pqueue.pop();/清空队首 if (pqueue.empty()/队列为空 tree = top; else Node* top2 = pqueue.top();/队首出列 pqueue.pop(); pqueue.push(new Node(top, top2); vector bitvec;/存储二进制编码的数组 tree-fill(encodetable, bitvec);/对树的各个节点进行0，1编码/*该函数主要是节点进行排序，重载了（）运算符*/templatestruct Hufftree:NodeOrder bool operator()(Node* l,Node* r) if(r-frequency frequency)/如果右边频率小于左边 return true; if(l-frequency frequency)/如果左边频率小于右边 return false; if(!l-leftChild & r-leftChild)/b节点存在左孩子 return true; if(l-leftChild & !r-leftChild)/a节点存在左孩子 return false; if(l-leftChild & r-leftChild)/均存在左孩子 if(*this)(l-leftChild,r-leftChild) return true; if(*this)(r-leftChild,l-leftChild) return false; return (*this)(l-rightChild,r-rightChild); return *(l-data) data); ;template template/InputIterator为待编码的字符串vector Hufftree:encode(InputIterator begin, InputIterator end) vector result;/存储编码后的文件即010100111 while (begin != end)/从第一个字符扫描到最后一个字符 /*从字符编码表中寻找对应字符的编码，并转换为该字符编码*/ typename encodemap:iterator i = encodetable.find(*begin); /*将该字符编码插入已完成的文件00101后面.例如aabc.已经将aa编码为11碰到b， 编码为00.添加到编码文件尾部*/ result.insert(result.end(), i-second.begin(), i-second.end(); +begin; return result;template templatevoid Hufftree:decode(vector const& v,/01001码 OutputIterator iter/*源码*/) Node* node = tree;/指向根节点 for (vector:const_iterator i = v.begin(); i != v.end(); +i) /*对二进制码和节点对应的二进制码进行比较*/ node = *i? node-rightChild:node-leftChild; if (!node - leftChild)/比较到叶子节点则返回叶子节点对应的字符 *iter+ = *(node-data);/将对应字符加到文件中 node = tree;/重新回到根节点，翻译下一个二进制码 #endif /Huffman_H主函数文件haffman.cc#includehuffman.h#include #include #include #include #include #include #includeusing namespace std;map frequencies;double sum=0;ostream& operator(ostream& os, vector vec)/重载运算符 copy(vec.begin(), vec.end(), ostream_iterator(os, ); return os;map fresTable(string &s)/生成字符频率表 for(string:const_iterator iter=s.begin();iter!=s.end();iter+) frequencies*iter+; +sum; return frequencies;int main(int argc,char *argv) cout- Source File -endlsource; frequencies=fresTable(source); cout- Encode&decode Table -endlendl; Hufftreehufftree(frequencies.begin(),frequencies.end(); typedef typename map:iterator it; coutsetw(10)Chsetw(10)Fsetw(10)encodesetw(10)lensetw(10)fresetw(10)everysecond/sum; coutsetw(10)first setw(10)second setw(10)first) setw(10)first) setw(10)fre setw(10)first)first); coutsetw(20)Sumsetw(40)lenAveendl; coutsetw(20)sumsetw(40)lenAveendl; cout- Encoded File -endlendl; vector encoded = hufftree.encode(source.begin(), source.end(); cout encoded endl; cout-Decoded File -endlendl; string destination