资源预览内容
第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
第9页 / 共31页
第10页 / 共31页
亲,该文档总共31页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
实 训 报 告题目:哈夫曼编码和译码系统院系:专业:姓名:学号:指导老师: 日期: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打开一篇英文文章,统计该文章中每个字符显现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码;问题补充:1. 从硬盘的一个文件里读出一段英语文章;2. 统计这篇文章中的每个字符显现的次数;3. 以字符显现字数作为权值,构建哈夫曼树,并将哈夫曼树的储备结构的初态和终态进行输出;4. 对每个字符进行编码并将所编码写入文件然后对所编码进行编译;3这个哈夫曼编码译码主要是以英文字母输入进行编码与编译,编码译码过程由系统自动完成, 人工操作部分就是电文的录入, 和编译出来时的读操作;二概要设计本程序主要用到了三个算法;(1) 哈夫曼树建立、编码在初始化 I 的过程中间,要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码;先将输入的字符和权值存放到一个结构体数组中,建立哈夫 曼树,将运算所得的哈夫曼编码储备到另一个结构体数组中;(2) 串的匹配在编码D 的过程中间, 要对已经编码过的代码译码, 可利用循环, 将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较(3) 哈夫曼遍历在印哈夫曼树 T 的中,由于哈夫曼树也是二叉树,所以就要利用二叉树的先序遍历将哈夫曼树输出;三具体设计及编码实现构造哈夫曼树的方法如下:初始化:每个字符就是一个结点,字符的频度就是结点的权;1、将结点按频度从小到大排序;2、选取频度最小的两个结点,以它们为儿子,构造出一个新的结点;新结点 的权值就是它两个儿子的权值之和; 构造之后, 从原先的结点序列里删除刚才选出的那两个结点,但同时将新生成的结点加进去;3、假如结点序列里只剩下一个结点,表示构造完毕,退出;否就回到第一步;编码:上面已经生成了树,接着就该对该树进行编码了;来到这里,基本上艰苦的已经完成了,对某个具体的字符串编码和解码就只是简洁的“查表 替换”的工作了;译码:译码也是个简洁的查表 - 替换过程;假如利用该种编码发送字符串,就它的“字符编码”对应表也必需发送过去,不然对方是不知道怎么解码的;对给出的一串编码,从左向右,将编码组合起来并查表,“一旦”找到有匹配的字符,就立刻将当前的编码替换为对应的字符;由于该编码是不会显现 ”某一个字符的编码是另一个字符编码的缀”这种情况的,也就是不会显现类似于 “A 00B0010” 这样的情形,所以译码出来的字符串是唯独的,而且就是原先进行编码的那一个;代码如下:( 1)求频率遍历过程:int Frequentchar *pchar *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 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;/将编码字符逆置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;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.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;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号