基于C++的哈夫曼编码

luckone

发布日期: 2019-05-25 08:05:13 浏览量: 1571
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

1. 设计目的

在计算机科学中,数据结构是一般程序设计的基础。通过综合设计,使学生学会分析研究数据结构的特征,以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法,掌握算法的时间复杂度分析技术。另一方面,综合设计也是复杂程序设计的训练过程,要求学生编写的程序结构符合软件工程规范,培养他们的数据抽象能力、建模能力和算法设计能力,提高复杂问题的解决能力,为后续课程的学习和应用奠定基础。

2. 任务与要求

要求学生以5人一组,自由结合,从给定的综合设计题目中进行选择。本次设计题目是设计内容不固定的题目,这就要求学生自己先确定本组设计题目,然后确定具体内容和设计目标,从而为数据结构设计、数据建模和算法设计奠定基础。提交的资料包含综合设计报告纸质版、电子版及源程序电子版。

3. 哈夫曼编/译码器

3.1 系统(问题)描述

利用哈夫曼编码器进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。

3.2 系统需求

一个完整的系统应具有以下功能

  • I:初始化( Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件 hfmTree中

  • E:编码( Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。

  • D:译码( Decoding)。利用已建好的哈夫曼树将文件Code file中的代码进行译码,结果存入文件TextFile中。

  • P:印代码文件( Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码,同时将此字符形式的编码文件写入文件CodePrin中。

  • T:印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。

4. 实现

5. 总结

5.1 系统特点及创新

  • 初始化前加入删除原文件操作,可在建立新哈夫曼树之前删除原来保存在文件中的旧哈夫曼树,避免之后的编码解码冲突,也降低了操作的复杂性。

代码片段:

  1. case 'I': { //初始化系统
  2. system("CLS");
  3. remove("E:\\CodeFile.txt");
  4. remove("E:\\TextFile.txt");
  5. remove("E:\hfmTree.txt"); //删除上次生成的文件
  6. }
  • 将建好的哈夫曼树,编码结果都直接存入文件,便于之后的查看与再次使用。

  • 在结构体HTNode中增加一个数据域char ch,用于储存该节点所表示的字符值,便于之后的编码解码操作。

代码片段:

  1. typedef struct{
  2. char ch; //结点的值
  3. int weight; //结点的权值
  4. int parent,lchild,rchild; //双亲结点和孩子结点
  5. }HTNode,*HuffmanTree;
  • 灵活使用fread(),fwrite(),fgetc(),fputc(),fgets(),fputs()等文件内容读写函数,对于不同的数据类型和不同的操作要求采用最合适的函数实现。

代码片段:

  1. fread(&Ht[i],sizeof(HTNode),1,rfp); //从文件中读入数据并输出
  2. printf("%c %d %d %d %d\n",Ht[i].ch,Ht[i].weight,Ht[i].parent,Ht[i].lchild,Ht[i].rchild);
  3. //从文件中读入编码过后的文本并输出
  4. codefile=fopen("E:\\CodeFile.txt","r");
  5. fgets(code,codemax,codefile); printf("%s",code);
  6. if(HT[k].lchild==0){
  7. fputc(HT[k].ch,textfp); k=2*n-1; //每次译码从头开始
  8. }
  • 在Select()函数中,即在HT[1…i-1] 选择parent为0且weight最小的两个结点,使用一轮循环,找到两个最小值。

5.2 遇到的问题及解决思路

  • 解码算法设计:设接收二进制序列用字符串表示,从根结点出发,‘1’表示向左,‘0’表示向右深入,直到到达某个叶子结点时,输出叶子结点对应的符号;重复此过程,直到接收序列全部译出。

代码片段:

  1. while(b[j]!='\0'){
  2. if(b[j]=='0') k=HT[k].lchild; //分解字符串,从根出发,按字符0或1确定左右孩子直至叶子节点
  3. else k=HT[k].rchild;
  4. if(HT[k].lchild==0){
  5. fputc(HT[k].ch,textfp); k=2*n-1; //每次译码从头开始
  6. }
  • 文件内容读写格式复杂:在读写哈夫曼树结点信息时,采用fread()和fwrite()函数,每次读写一个单位大小的结构体结点信息。在写入译码文件时,采用fputc()函数,每次将一个译好的字符写入文件,在写入编码文件时,采用fputs()函数,将每个字符对应的一串编码整个写入编码文件,在读出编码文件和译码文件时,采用fgets()函数,将编码结果和译码结果整体读出并打印。

  • Select()函数使用一轮循环找到两个最小值:先保存数组前两个值,再将从第三个值开始直至最后与这两个值进行比较,如果大于这两个值,则继续下一值比较,若小于两个值,则将两个值中较大的一者替换为该值,并进行下一次比较,直至结束。

代码片段:

  1. if(k>3){
  2. w3=HT[j].weight; w1=HT[s1].weight;
  3. w2=HT[s2].weight;
  4. if((w3<w2)&&(w3<w1)){ //比较第三个结点与之前暂存的结点权值大小
  5. if(w2<=w1) s1=j;
  6. else s2=j;
  7. } //如果第三个结点小于前两个,则将较大者替换
  8. if((w3<w2)&&(w3>w1)) s2=j;
  9. if((w3<w1)&&(w3>w2)) s1=j;
  10. }
上传的附件 cloud_download 基于C++的哈夫曼编码.zip ( 197.21kb, 69次下载 )
error_outline 下载需要9点积分

发送私信

生活变得再糟糕,也不妨碍你变得更好

13
文章数
16
评论数
最近文章
eject