当前位置：文档之家 › 哈夫曼编译码器实验报告

哈夫曼编译码器实验报告

  • 格式：docx
  • 大小：159.33 KB
  • 文档页数：9

哈夫曼编码/译码器1. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站编写一个赫夫曼码的编/译码系统。

2.基本要求一个完整的系统应具有以下功能：(1) I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。

(2) E：编码（Encoding）。

利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3) D：译码（Decoding）。

利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

(4) P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T：印赫夫曼树（Tree printing）。

将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。

3.测试数据(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。

(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“4.实现提示(1) 编码结果以文本方式存储在文件Codefile中。

(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。

(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。

每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

5.编码实现// HFM.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include<iostream>using namespace std;#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream>typedef struct{ //赫夫曼树的结构体char ch;int weight; //权值int parent,lchild,rchild;}htnode,*hfmtree;typedef char **hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点{int i,j,x,y;for(j=1;j<=a;++j){if(HT[j].parent==0){x=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[x].weight&&HT[i].parent==0){x=i; //选出最小的节点}}for(j=1;j<=a;++j){if(HT[j].parent==0&&x!=j){y=j;break;}}for(i=j+1;i<=a;++i){if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i){y=i; //选出次小的节点}}if(x>y){*p1=y;*p2=x;}else{*p1=x;*p2=y;}}void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC{int i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1){return;}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));for(i=1;i<=n;++i) //初始化n个叶子结点{printf("请输入第%d字符信息和权值：",i);scanf("%c%d",&z,&w);while(getchar()!='\n'){continue;}HT[i].ch=z;HT[i].weight=w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i<=m;++i) //初始化其余的结点{HT[i].ch='0';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;++i) //建立赫夫曼树{Select(HT,i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}HC=(hfmcode)malloc((n+1)*sizeof(char *));cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;++i) //给n个字符编码{start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c){cd[--start]='0';}else{cd[--start]='1';}}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}int main(){char code[100],h[100],hl[100];int n,i,j,k,l;ifstream input_file; //文件输入输出流ofstream output_file;char choice,str[100];hfmtree HT;hfmcode HC;cout<<"\n";cout<<" "<<"计算机c103班"<<" "<<"108413"<<" "<<"XXX\n";while(choice!='Q'&&choice!='q') //当choice的值不为q且不为Q 时循环{cout<<" "<<"*************************赫夫曼编码/译码器*************************\n";cout<<" "<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exit\n";cout<<"请输入您要操作的步骤：";cin>>choice;if(choice=='I'||choice=='i') //初始化赫夫曼树{cout<<"请输入字符个数：";cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;++i){cout<<HT[i].ch<<":"<<HC[i]<<endl;}output_file.open("hfmTree.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}for(i=1;i<=n;i++){output_file<<"("<<HT[i].ch<<HC[i]<<")";}output_file.close();cout<<"赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!"<<endl;}else if(choice=='E'||choice=='e') //进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中{printf("请输入字符：");gets(str);output_file.open("ToBeTran.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}output_file<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}for(i=0;i<strlen(str);i++){for(j=0;j<=n;++j){if(HT[j].ch==str[i]){output_file<<HC[j];break;}}}output_file.close();cout<<"\n";cout<<"编码完毕，并且已经存入CodeFile.txt文件！\n";input_file.open("CodeFile.txt"); //从CodeFile.txt中读入编码，输出在终端if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>code;cout<<"编码码值为："<<code<<endl;input_file.close();}else if(choice=='D'||choice=='d') //读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中{input_file.open("CodeFile.txt");if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file){cout<<"can't oen file!"<<endl;return 1;}k=0;while(h[k]!='\0') //先用编码中的前几个和字符的编码相比较，然后往后移{for(i=1;i<=n;i++){l=k;for(j=0;j<strlen(HC[i]);j++,l++){hl[j]=h[l];}hl[j]='\0';if(strcmp(HC[i],hl)==0){output_file<<HT[i].ch;k=k+strlen(HC[i]);break;}}}output_file.close();input_file.open("Textfile.txt");if(!input_file){cout<<"can't oen file!"<<endl;return 1;}input_file>>h;cout<<h<<endl;input_file.close();cout<<"译码结束，字符已经存入Textfile.txt文件中！"<<endl;}else if(choice=='Q'||choice=='q') //退出程序{exit(0);}else //如果选了选项之外的就让用户重新选择{cout<<"您没有输入正确的步骤，请重新输入！"<<endl;}cout<<endl;}return 0;}6.调试分析编码译码退出。

合集下载

哈夫曼编码译码实验报告

哈夫曼编码译码实验报告

哈夫曼编码译码实验报告哈夫曼编码译码实验报告一、引言哈夫曼编码是一种用来对数据进行压缩的算法，它能够根据数据的频率分布来分配不同长度的编码，从而实现对数据的高效压缩。

本次实验旨在通过实际操作，深入理解哈夫曼编码的原理和实现方式，并通过编码和解码过程来验证其有效性。

二、实验目的1. 掌握哈夫曼编码的原理和算法；2. 学会使用编程语言实现哈夫曼编码和解码；3. 验证哈夫曼编码在数据压缩中的实际效果。

三、实验过程1. 数据准备在实验开始前，首先需要准备一段文本数据作为实验材料。

为了更好地展示哈夫曼编码的效果，我们选择了一篇新闻报道作为实验文本。

这篇报道涵盖了多个领域的信息，包括科技、经济、体育等，具有一定的复杂性。

2. 哈夫曼编码实现根据哈夫曼编码的原理，我们首先需要统计文本中每个字符的频率。

为了方便处理，我们将每个字符与其频率构建成一个字符-频率的映射表。

然后，我们根据频率构建哈夫曼树，将频率较低的字符作为叶子节点，频率较高的字符作为内部节点。

最后，根据哈夫曼树构建编码表，将每个字符映射到对应的二进制编码。

3. 哈夫曼解码实现在哈夫曼解码过程中，我们需要根据编码表将二进制编码转换回字符。

为了实现高效解码，我们可以将编码表转换为一个二叉树，其中每个叶子节点对应一个字符。

通过遍历二叉树，我们可以根据输入的二进制编码逐步还原出原始文本。

4. 编码和解码效果验证为了验证哈夫曼编码的有效性，我们需要对编码和解码的结果进行比较。

通过计算编码后的二进制数据长度和原始文本长度的比值，我们可以得到压缩率，进一步评估哈夫曼编码的效果。

四、实验结果经过实验，我们得到了以下结果：1. 哈夫曼编码表根据实验文本统计得到的字符-频率映射表，我们构建了哈夫曼树，并生成了相应的编码表。

编码表中每个字符对应的编码长度不同，频率较高的字符编码长度较短，频率较低的字符编码长度较长。

2. 编码结果将实验文本使用哈夫曼编码进行压缩后，得到了一串二进制数据。

哈夫曼实验报告实验目的(3篇)

哈夫曼实验报告实验目的(3篇)

5. 使用哈夫曼编码对实验数据进行压缩。
6. 对压缩数据进行解压缩，验证哈夫曼编码的正确性。
7. 分析实验结果，对比压缩前后数据的差异。
五、实验总结
通过本次实验，我们掌握了哈夫曼编码的原理和构造方法，学会了如何使用哈夫曼编码进行数据压缩和解压缩。实验结果表明，哈夫曼编码能够有效降低数据的冗余，提高数据压缩效果。同时，本次实验也加深了我们对数据结构中树形结构及其应用的理解，提高了算法设计和实现能力。在今后的学习和工作中，我们将继续探索哈夫曼编码及其应用，为相关领域的研究和发展贡献自己的力量。
二、实验内容
1. 理解哈夫曼编码的原理，掌握哈夫曼树的构造方法。
2. 编写程序实现哈夫曼树的构建、编码和解码过程。
3. 对给定的字符集进行哈夫曼编码，并分析编码后的结果。
4. 对编码后的数据进行解码，验证解码结果的正确性。
5. 比较哈夫曼编码与其他编码方法在数据压缩方面的性能。
三、实验原理
哈夫曼编码是一种基于字符频率的变长编码方法。在哈夫曼编码中，每个字符都被赋予一个唯一的编码，编码的长度与其在原始数据中的频率成反比。频率高的字符编码较短，频率低的字符编码较长。这样，哈夫曼编码在保证数据完整性的同时，实现了数据压缩的目的。
2. 能够编写程序实现哈夫曼编码和解码，提高编程能力。
3. 分析哈夫曼编码在不同场景下的压缩效果，为实际应用提供参考。
4. 了解哈夫曼编码在实际应用中的优势和局限性，为解决实际问题提供思路。
5. 培养实验操作能力，提高解决实际问题的能力。
通过本次实验，我们希望学员能够全面掌握哈夫曼编码的原理、构造方法及其在实际应用中的价值，为今后的学习和工作打下坚实的基础。
第2篇
一、实验目的
1. 理解哈夫曼编码的原理及其在数据压缩中的应用。
哈弗曼编译器实验报告

哈弗曼编译器实验报告

实习报告题目：哈弗曼编译码器班级：电信系通信工程0902班完成日期：2010.11一、需求分析1、编写哈弗曼编译码器，其主要功能有（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

（2）E：编码（Encoding）。

利用已建好的哈夫曼树），对从终端输入的正文进行编码，然后从终端输出。

（3）D：译码（Decoding )。

利用已建好的哈夫曼树将从终端输入的代码进行译码，结果从终端输出。

（4）P：印哈夫曼树（Print）。

将已编码的的哈夫曼树显示在终端上，同时将此字符形式的哈夫曼树。

2、测试数据：输入的字符={a， b， c， d， e}其对应的权值={5，29，7，8，14}二、概要设计1、二哈弗曼树的抽象数据类型定义为：ADT HuffmanTree{数据对象D:D是具有相同性质的数据元素的集合数据关系R：若D=Φ，则R= Φ，哈弗曼树为空若D≠Φ，则R= {H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱（2）若D-{root}≠Φ，则存在D-{root}={Dl，Dr}。

且Dl∩Dr=Φ（3）若Dl≠Φ，则Dl中存在唯一的数据元素Xl，<root, Xl>属于H，且存在Dl上的关系H1属于H。

若Dr≠Φ，则Dr中存在唯一的数据元素Xr，<root, X>属于H，且存在Dr上的关系Hr属于HH={<root, Xl>，<root, X>，Hl，Hr}；（4）（Dl，{Hl}）是一棵符合本定义的哈弗曼树，称为根的左子树。

（Dr，{Hr}）是一棵符合本定义的哈弗曼树，称为根的右子树。

基本操作：HuffmanCoding（&HT, &HC, &sum)操作结果：建立哈弗曼树并进行编码将编码存放在HC中，并返回字符的个数。

Encoding(HT, HC, sum)操作结果：利用已建立的哈弗曼树对字符进行编码Decoding(HuffmanTree HT,HuffmanCode HC,int sum)操作结果：对输入的密码进行翻译Print(HT, HC, sum)操作结果：打印建立好的哈弗曼树}ADT HuffmanTree三、详细设计（1）哈弗曼树每个节点的定义：typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;char elemt[20];}HTNode,*HuffmanTree;（2）定义指向哈弗曼树的指针，用于动态分配空间typedef char **HuffmanCode;（3）哈弗曼树的基本操作Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ //建立哈弗曼树，求出哈弗曼编码if (n<=1)return;m=2*n-1; //n 个叶子的HuffmanTree共有2n-1个结点HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=0; i<n; ++i,++p,++w)*p={*w,0,0,0};//给前n个单元初始化for(；i<=m; ++i,++p)*p ={0,0,0,0}; //从叶子之后的存储单元清零for(i=n+1;i<=m; ++i){ //建Huffman树(从n个叶子后开始存内结点) Select(HT, i-1, s1, s2);//选择parent为0且weight最小的两个结点，HT[s1].parent=i; HT[s2].parent=i; //给双亲分量赋值HT[i].lchild=s1; HT[i].rchild=s2; //给合并后的内结点赋孩子值HT[i].weight=HT[s1].weight+ HT[s2].weight;} //以上建立了哈弗曼树，以下求哈弗曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量（一维数组）cd=(char*) malloc(n*sizeof(char)); //分配求编码的临时最长空间cd[n-1]=“\0”; //编码结束符（从cd[0]~cd[n-1]为合法空间）for(i=1;i<=n;++i) //逐个字符求Huffman编码{start=n-1; //编码结束符位置for(c=i,f=HT[i].parent; f!=0; c=f, f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c) cd[--start]=“0”;else cd[--start]=“1”;HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间，并以数组形式存放各码串指针strcpy(HC[i],&cd[start]); //从cd复制编码串到HC所指空间}free(cd); //释放临时空间}//HuffmanCodingfor(i=0; i<n; ++i){start=n-1; //编码结束符位置for(c=i, f=HT[i].parent;f!=0;c=f, f=HT[f].parent) {If(HT[f].lchild==c) cd[--start]=“0”;else cd[--start]=“1”;} / /从叶子到根逆向求编码}// HuffmanCodingVoid Encoding(HuffmanTree HT,HuffmanCode HC,int sum) //利用已经建立的哈弗曼树对输入的字符进行哈弗曼编码{for(int i=0;a[i]!='\0';i++)//依次判断字符的对应的哈弗曼编码{for(int n=0;HT[n].elemt[0];n++)//查找a[i]在哈弗曼树中的位置{strcpy(p,HC[n]);p=p+strlen(HC[n]);break;//把编码复制接到code后}}i=0;printf("得到的编码是：\n");while(code[i]!='\0') //输出字符对应的哈弗曼编码{printf("%c",code[i++]);}}// EncodingVoid Decoding(HuffmanTree HT,HuffmanCode HC,int sum) //译码{while(code1[i]!='\0'){if(code1[i]=='0') b=HT[b].lchild;//当遇到0时指向哈弗曼树的左子树else if(code1[i]=='1') b=HT[b].rchild;//当遇到1时指向哈弗曼树的右子树}if(HT[b].lchild==0&&HT[b].rchild==0)//当左右子树均为空时表明已找到对应的字符{a1[n++]=HT[b].elemt[0];b=2*sum-2;//将对应的字符放在数组a1中并重新设置b的值继续翻译 }i++;}// DecodingVoid Print(HuffmanTree HT,HuffmanCode HC,int sum)//打印哈弗曼树{for(int i=0;i<2*sum-1;i++)//从首元素开始，逐个输入哈弗曼树的各项数据{printf("%d%c%d%d%d",i,HT[i].elemt[0],HT[i].parent,HT[i].lch ild,HT[i].rchild);}}// Print四、调试分析1、由于书上有详细的建立哈弗曼树的算法，编码，译码，打印哈弗曼树的算法比较简单，程序的模块比较简单，所以整体的思路比较清晰，但是在将算法，写为C语言的过程中，出现了很多的语法和逻辑上的错误，所以用了很多的时间调试，修改错误。

哈夫曼编码译码器实验报告

哈夫曼编码译码器实验报告

问题解析与解题方法问题分析：设计一个哈夫曼编码、译码系统。

对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。

（1）从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；（2）统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3）根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4）将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6）进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。

根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。

哈夫曼树的理论创建过程如下：一、构成初始集合对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。

二、选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、删除左右子树从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。

四、重复二和三两步，重复二和三两步，直到集合F中只有一棵二叉树为止。

因此，有如下分析：1.我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存它们；2.定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；3.自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；4.从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；5.使用文件读写操作哈夫曼编码和解码结果的写入；解题方法：结构体、数组、类的定义：1.定义结构体类型的signode 作为哈夫曼树的节点，定义结构体类型的hufnode 作为哈夫曼编码对照表的节点，定义HFM类实现对哈夫曼树的创建，利用其成员函数完成哈夫曼编码译码的工作。