《2021年哈夫曼编码和译码系统》由会员分享，可在线阅读，更多相关《2021年哈夫曼编码和译码系统（31页珍藏版）》请在金锄头文库上搜索。
1、实 训 报 告题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导老师： 日期：30 / 28目录一.需求分析2二.概要设计（1） ） 建立哈夫曼树 、编码3（2） ） 字符匹配3（3） ） 哈夫曼树遍历3三.具体设计及编码实现3四.流程图（1） ） 总流程图15（2） ） 编码实现流程图16（3） ） 译码实现流程图17五.调试分析（ 1）运算权值18（ 1）生成哈夫曼树，建立编码表18（ 3）将输入字符编码19（ 4）输入新的字符串，进行译码19（ 5）输入新的二进制数将其译为字符20六.系统保护20七试验总结20八.源代码21一需求分析1问题描述：在传送电文时，人们总是期望传送时间尽可
2、能短，这就是 要求使电文代码长度尽可能短； 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本；但是，这要求在发送端通过一个编码系 统能够对待传输数据预先编码， 在接收端将传来的数据进行译码； 对于双工信道（即可以双向传输信息的信道） ，每段都需要一个完整的编 /译系统；所以为这样的信息收发站写一个哈夫曼的编译码系统；2打开一篇英文文章，统计该文章中每个字符显现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码；问题补充：1. 从硬盘的一个文件里读出一段英语文章；2. 统计这篇文章中的每个字符显现的次数；3. 以字符显现字数作为权值，构建哈
3、夫曼树，并将哈夫曼树的储备结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入文件然后对所编码进行编译；3这个哈夫曼编码译码主要是以英文字母输入进行编码与编译，编码译码过程由系统自动完成， 人工操作部分就是电文的录入， 和编译出来时的读操作；二概要设计本程序主要用到了三个算法；(1) 哈夫曼树建立、编码在初始化 I 的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码；先将输入的字符和权值存放到一个结构体数组中，建立哈夫 曼树，将运算所得的哈夫曼编码储备到另一个结构体数组中；(2) 串的匹配在编码D 的过程中间， 要对已经编码过的代码译码， 可利用循环， 将代码中的与哈夫曼
4、编码的长度相同的串与这个哈夫曼编码比较(3) 哈夫曼遍历在印哈夫曼树 T 的中，由于哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出；三具体设计及编码实现构造哈夫曼树的方法如下：初始化：每个字符就是一个结点，字符的频度就是结点的权；1、将结点按频度从小到大排序；2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点 的权值就是它两个儿子的权值之和； 构造之后， 从原先的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；3、假如结点序列里只剩下一个结点，表示构造完毕，退出；否就回到第一步；编码：上面已经生成了树，接着就该对该树进行编码了；来到这里，基本上
5、艰苦的已经完成了，对某个具体的字符串编码和解码就只是简洁的“查表 替换”的工作了；译码：译码也是个简洁的查表 - 替换过程；假如利用该种编码发送字符串，就它的“字符编码”对应表也必需发送过去，不然对方是不知道怎么解码的；对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，就立刻将当前的编码替换为对应的字符；由于该编码是不会显现 ”某一个字符的编码是另一个字符编码的缀”这种情况的，也就是不会显现类似于 “A 00B0010” 这样的情形，所以译码出来的字符串是唯独的，而且就是原先进行编码的那一个；代码如下：（ 1）求频率遍历过程：int Frequentchar *pch
6、ar *pt2=p;int i=0;ch0=*pt2;freq0=0;可以假定，对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码为 1；这样就可以通过 “树的遍历 ”的方式来生成字符 编码对比表；while*pt2.=0forint j=0;ji/ 遍历终止，该字符目前频度为1 ，跳至下一个字符i+;chi=*pt2;freqi=1;pt2+;coutendl统计权值： endl;forint j=0;j=i;j+cout 字符chj的权值为 freqjendl;return i+1;（2） ）预程序处理及结构体定义：#include #include using namespace
7、 std;struct HNodeint weight;int parent;int LChild;int RChild;struct HCode/哈夫曼编码表char data;char code100;class Huffmanprivate:HNode* HTree;HCode* HCodeTable;int SentenceLen;/编码前长度int CodeLen;/编码后长度protected:void SelectMinint&x,int&y,int start,int end; /从 1-i中选取权值最小的两个结点（ x,y 为游标）void Reversechar *,int
8、;/将编码字符逆置public:void Initint a,int n;void CreateTablechar b,int n;void Encodechar *c, char *s,int n;void Decodechar *s, char *d,int n;Huffman;（3） ）主函数 main ：void mainHuffman obj;char *sentence1=new char500;char *code01=new char1000;*code01=0;coutn请输入所需文章: endl; getssentence1;int n=Frequentsentence1;
9、char *sentence2=new char500;char *sentence3=new char500;forint i=0;i=499;i+*sentence3+i=0;char *code02=new char1000;*code02=0;cout*endl菜单:endl1. 建立编码表 nn2.编码nn3.编码新字符串 nn4.译码新编码串nn5.退出 n*endl;coutnnint w;请挑选菜单：n*w;switchwcase 1:obj.Initfreq,n;obj.CreateTablech,n;coutnn请挑选菜单： n*endl; break;case 2:obj
10、.Encodesentence1,code01,n;coutnn请挑选菜单： n*endl; break;case 3:getssentence2;coutendl请依据已编码字符再输入一句话：endl;getssentence2;obj.Encodesentence2,code02,n;coutnn请挑选菜单： n*endl; break;case 4:getscode01;coutendl请依据编码表输入一个编码后的编码串：endl; getscode01;obj.Decodecode01,sentence3,n;coutnn请挑选菜单： n*endl; break;case 5:tag=0;break;default:cout挑选错误，请重新挑选！endl; coutendl;break;（4） ）初始化并创建哈夫曼树：void Huffman:Initint a,int nint x=0,y=0;HTree= new HNode2*n-1;forint i=0;in;i+HTreei.weight=ai;/依据权重数组a 初始化哈夫曼树HTreei.LChild=-1;/初始化HTreei.RChild=-1;/初始化HTreei.parent=-1;/初始化fori=n; i2*n-1;i+/开头建哈夫曼树SelectMinx,y,0,i;
