下载文档原格式
哈夫曼编码译码实验报告哈夫曼编码译码实验报告一、引言哈夫曼编码是一种用来对数据进行压缩的算法，它能够根据数据的频率分布来分配不同长度的编码，从而实现对数据的高效压缩。
本次实验旨在通过实际操作，深入理解哈夫曼编码的原理和实现方式，并通过编码和解码过程来验证其有效性。
二、实验目的1. 掌握哈夫曼编码的原理和算法；2. 学会使用编程语言实现哈夫曼编码和解码；3. 验证哈夫曼编码在数据压缩中的实际效果。
三、实验过程1. 数据准备在实验开始前，首先需要准备一段文本数据作为实验材料。
为了更好地展示哈夫曼编码的效果，我们选择了一篇新闻报道作为实验文本。
这篇报道涵盖了多个领域的信息，包括科技、经济、体育等，具有一定的复杂性。
2. 哈夫曼编码实现根据哈夫曼编码的原理，我们首先需要统计文本中每个字符的频率。
为了方便处理，我们将每个字符与其频率构建成一个字符-频率的映射表。
然后，我们根据频率构建哈夫曼树，将频率较低的字符作为叶子节点，频率较高的字符作为内部节点。
最后，根据哈夫曼树构建编码表，将每个字符映射到对应的二进制编码。
3. 哈夫曼解码实现在哈夫曼解码过程中，我们需要根据编码表将二进制编码转换回字符。
为了实现高效解码，我们可以将编码表转换为一个二叉树，其中每个叶子节点对应一个字符。
通过遍历二叉树，我们可以根据输入的二进制编码逐步还原出原始文本。
4. 编码和解码效果验证为了验证哈夫曼编码的有效性，我们需要对编码和解码的结果进行比较。
通过计算编码后的二进制数据长度和原始文本长度的比值，我们可以得到压缩率，进一步评估哈夫曼编码的效果。
四、实验结果经过实验，我们得到了以下结果：1. 哈夫曼编码表根据实验文本统计得到的字符-频率映射表，我们构建了哈夫曼树，并生成了相应的编码表。
编码表中每个字符对应的编码长度不同，频率较高的字符编码长度较短，频率较低的字符编码长度较长。
2. 编码结果将实验文本使用哈夫曼编码进行压缩后，得到了一串二进制数据。
算法与数据结构课程设计哈夫曼编码和译码的设计与实现1。
问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼码的编/译码系统。
2。
基本要求a。
编/译码系统应具有以下功能:(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中.b。
测试数据（1）利用下面这道题中的数据调试程序.某系统在通信联络中只可能出现八种字符，其概率分别为0。
25，0.29,0。
07，0.08，0.14,0。
23，0。
03，0。
11，试设计哈夫曼编码。
（2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE".字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 13．需求分析3。
哈夫曼编码译码器课程设计1.哈夫曼编码是一种有效的数据压缩算法，通过将最常用的字符编码为较短的比特串，最大限度地减少了存储空间。
本文档介绍一个哈夫曼编码译码器的设计和实现，该译码器可以实现从原始文本到哈夫曼编码的转换，并且可以从哈夫曼编码还原出原始文本。
2. 设计和实现本译码器的开发采用Python语言，主要分为两部分：哈夫曼编码和译码两部分。
2.1 哈夫曼编码哈夫曼编码的过程主要分为两步：1.统计每个字符出现的频率，并生成一个频率表。
2.根据频率表生成哈夫曼树，并生成相应的编码表。
以下是用于生成哈夫曼编码的Python代码：import heapqfrom collections import defaultdictclass Node:def__init__(self, freq, char=None, left=None, right=None): self.freq = freqself.char = charself.left = leftself.right = rightdef__lt__(self, other):return self.freq < other.freqdef__eq__(self, other):return self.freq == other.freqdef build_tree(data):freq = defaultdict(int)for char in data:freq[char] +=1q = [Node(freq[char], char) for char in freq]heapq.heapify(q)while len(q) >1:left = heapq.heappop(q)right = heapq.heappop(q)parent = Node(left.freq + right.freq, left.char + right.char, l eft, right)heapq.heappush(q, parent)return q[0]def generate_codes(node, current_code='', codes={}):if node is None:returnif node.char is not None:codes[node.char] = current_codegenerate_codes(node.left, current_code +'0', codes)generate_codes(node.right, current_code +'1', codes)return codes通过调用build_tree()函数来生成哈夫曼树，并调用generate_codes()函数来生成编码表。
实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的HUFFMANN编码与解码，这里的字符集及其字符频数自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼码及译码结果。
二．实验原理首先规定构建哈夫曼树，然后进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。
首先定义一个结构体，这个结构体定义时尽可能的大，用来存放左右的变量，再定义一个地址空间，用于存放数组，数组中每个元素为之前定义的结构体。
输入n个字符及其权值。
构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1.首先将地址空间初始化，将ht[0…n-1]中所有的结点里的指针都设置为空，并且将权值设置为0.2.输入:读入n个叶子的权值存于向量的前n个分量中。
它们是初始森林中n个孤立的根结点上的权值。
3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。
每次合并分两步：①在当前森林ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。
②将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。
具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。
4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。
当用户输入字母时。
就在已经找好编码的编码结构体中去查找该字母。
查到该字母就打印所存的哈夫曼编码。
接着就是完成用户输入0、1代码时把代码转成字母的功能。
这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。
如果是1这就走向该结点的右结点，重复上面步骤。
数据结构设计性实验Huffman编码与译码学号姓名班级设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。
二．实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。
写出技术工作报告并附源程序。
三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。
2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。
实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符四．分析以及算法描述1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。
2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。
②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。
③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。
④重复②和③，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。
3)练习通过普通树来构造霍夫曼树。
哈夫曼编\译码的设计与实现一、简介1．设计目的：通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。
2．问题的描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。
系统应该具有如下的几个功能：接收原始数据、编码、译码、打印编码规则。
二、数据结构的设计：1.哈夫曼结点结构体：typedef struct HtNode{int weight;int parent, lchild, rchild;}HtNode;2.哈夫曼树结构体：typedef struct HtTree{struct HtNode ht[MAXNODE+1];int root;}HtTree, *PHtTree;三、功能（函数）设计：总体上划分为四个模块，具体功能描述如下：1．初始化功能模块：接收输入信息，并正确输出2．建立哈夫曼树的功能模块：按照构造哈夫曼树的算法构造哈夫曼树，将HuffNode数组中的各个位置的各个域都添上相关的值3．哈夫曼编码的功能模块：根据输入的相关字符信息进行哈夫曼编码，然后将结果存入，同时将字符与0、1代码串的一一对应关系打印到屏幕上。
4．译码的功能模块：接收需要译码的0、1代码串，按照哈夫曼编码规则将其翻译成字符集中的字符所组成的字符串形式，将翻译的结果在屏幕上输出四、界面设计：该界面操做简单，内容详细，便于程序使用者根据提示轻松上手。
简洁明朗是该界面最大的特点。
哈夫曼编/译码请逐个输入结点和结点的权值>>>按Enter键开始根据此提示界面进入程序使用阶段。
请输入结点个数：根据用户输入结点个数，动态输入并存储字符及权值然后输出字符与0、1代码串的对应关系。
进入以下界面，进行后续操作1----------------------------编码2----------------------------译码3----------------------------重新输入权值;0----------------------------退出用户键入“0”，即可出编码译码操作五、程序设计：1．函数功能说明及其程序流程图的描述：1>:main函数：控制整个程序的整个流程。
哈夫曼编码和译码的算法设计与实现实验名称哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作实验台号班级姓名实验结果一、实验目的1、掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编码译码器；3、掌握贪心算法的设计策略。
二、实验任务①从文件中读取数据，构建哈夫曼树；②利用哈夫曼树，对输入明文进行哈夫曼编码；③利用哈夫曼树，对输入编码译码为明文。
三、实验设计方案1、结构体设计Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标#define N 29 //26个小写字母，逗号，句号和空格字符.struct treenode{ //静态链表char c; //charint w; //weightint f; //fatherint l; //left child indexint r; //right child index};struct treenode htree[2*N-1];2、自定义函数设计①函数原型声明void input(); //读取文件字符、权值数据void huffman(); //建立huffman树void getcode(int i, char *str); //得到单个字符的huffman编码void encode(char ch); //将明文进行huffman编码void decode(char *str); //将huffman编码译为明文②读取文件字符、权值数据void input(){int i;char c;int f;freopen("in.txt","r",stdin);for(i=0;i<n;i++)< p="">{c=getchar(); //接收字符scanf("%d",&f); //接收权值getchar(); //接收回车ht[i].c=c;ht[i].w=f;ht[i].l=ht[i].f=ht[i].r=-1; //初始化父亲、左右孩子下标} freopen( "CON", "r", stdin);}③建立huffman树//使用贪心法建立huffman树,每次选择权值最小的根结点void huffman(){void huffman(){int j,k,n;input();j=0;k=N;for(n=N;n<2*N-1;n++){ //建立huffman树，共合并N-1次int r=0,s=0;ht[n].l=ht[n].f=ht[n].r=-1;while(r<2){ //选择两个最小的权值结点if((ht[k].w==0 || ht[k].w>ht[j].w) && j<n){< p="">s+=ht[j].w;if(r==0) ht[n].l = j; //修改父亲、孩子下标else ht[n].r=j;ht[j].f=n;j++;}else{s+=ht[k].w;if(r==0) ht[n].l = k; //修改父亲、孩子下标else ht[n].r=k;ht[k].f=n;k++;}r++;}ht[n].w=s; //修改权值}}④根据字符下标找到字符的huffman编码//根据字符所在的下标，从叶子结点往上搜索到根节点，然后逆置得到该字符的huffman编码void getcode(int i, char *str){ int n,j,l=0;for(n=i;ht[n].f!=-1;n=ht[n].f){ //沿着父亲往上搜索int m=ht[n].f;if(n==ht[m].l)str[l++]='0'; //左孩子记为0elsestr[l++]='1'; //右孩子记为1}for(j=0;j<=(l-1)/2;j++){ //将编码逆置char t;t=str[j];str[j]=str[l-1-j];str[l-1-j]=t;}str[l]=0; // str存放huffman编码，字符串结束标记}⑤读入明文生成huffman编码void encode(char ch){int i;char str[N];for(i=0;ht[i].c!=0;i++)if(ht[i].c==ch) //找字符下标break;if (ht[i].c!=0){getcode(i,str); //得到字符的huffman编码printf("%s",str);}}⑥将huffman编码串译码为明文void decode(char *str){while(*str!='\0'){int i;for(i=2*N-2;ht[i].l!=-1;){if(*str=='0')i=ht[i].l;elsei=ht[i].r;str++;}printf("%c",ht[i].c);}}3、主函数设计思路：主函数实现实验任务的基本流程。
实验二哈夫曼树及哈夫曼编码译码的实现实验二:哈夫曼树及哈夫曼编码译码的实现(验证性、4学时) 一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。
(1)掌握树的有关操作算法2)熟悉树的基本存储方法 ((3)学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构;输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。
三、实验环境硬件:(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境软件:(1)Windows XP中文操作系统 (2)Turbo C 3.0 四、算法描述及实验步骤1( 算法描述(1) 建立叶子结点——由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域;(2) 另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。
(3) 构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一个哈夫曼编码值;由于每个叶子结点的哈夫曼编码是从根就诶点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以先得到的分枝代码为说求编码的低位码而后得到的为高位码。
2( 算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3( 代码#include<stdio.h>#define maxvalue 10000//定义最大权值常量#define maxnodenumber 100//定义结点最大数目常量 typedef struct{int weight;int parent,lchild,rchild; }htnode;typedef htnode *huffmantree;//定义哈夫曼树类型 htnodeht[maxnodenumber]; //定义静态三叉链表存储区数组#define maxbit 10//定义哈夫曼编码的最大长度 typedef struct//定义保存一个叶子结点哈夫曼编码的结构 {int bit[maxbit];//哈夫曼编码域为一维数组int start;//开始位置域为整型}hcodetype;//定义哈夫曼编码类型hcodetype cd[maxnodenumber];//定义存放哈夫曼编码的数组cd void crthuffmantree(int n);//建立哈夫曼树void gethuffmancode(int n);//哈夫曼编码void main (){int nodenum;printf("inputnodenum:"); scanf("%d",&nodenum);crthuffmantree(nodenum); gethuffmancode(nodenum); }void crthuffmantree(int n)//该算法对n个叶子结点建立哈夫曼树，权重值由键盘逐个输入{int i,j,m1,m2,k1,k2;//定义局部变量for(i=0;i<2*n-1;i++)//数组ht初始化{ht[i].weight=0;//权重初始化为0ht[i].parent=-1;//3个指针域初始化为-1，即NULL ht[i].lchild=-1;ht[i].rchild=-1;}for (i=0;i<n;i++)//读入n个叶子结点的权重值scanf("%d",&ht[i].weight); for(i=0;i<n-1;i++)//控制n-1趟生成新结点构造哈夫曼树 {m1=maxvalue;//预置最小权值变量为最大权值 m2=maxvalue;//预置次小权值变量为最大权值 k1=0;k2=0;//预置最小和次小权值结点位置为下标0处for (j=0;j<n+i;j++)//控制一趟中找处最小权值的结点if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;//若第j个结点权小于当前最小的m1改为次小的m1=ht[j].weight;k1=j;//并记下新的当前最小权值及位置}elseif(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}//否则若小于当前次小的m2则更新m2及其位置ht[k1].parent=n+i;//修改最小权值结点的双亲为刚生成的新结点ht[k2].parent=n+i;//修改次小权值结点的双亲刚好生成的新结点ht[n+i].weight=ht[k1].weight+ht[k2].weight;//填新生成结点的权重值ht[n+i].lchild=k1;//新生成结点的左孩子指针指向k1ht[n+i].rchild=k2;//新生成结点的右孩子指针指向k2}}void gethuffmancode(int n) /*对具有n个叶子结点的哈夫曼树ht,求所有叶子结点的哈夫曼编码并输出*/{int i,j,c,p; /*定义局部变量*/for(i=0;i<n;i++) /*定义存放哈夫曼编码的数组cd*/ {c=i;j=maxbit; /*为求一个结点的哈夫曼编码初始化c和j*/ do{j--; /*j指向bit中存放编码位的正确位置*/ p=ht[c].parent; /*p指向c 的双亲结点*/if(ht[p].lchild==c) /*如果c是p的左孩子*/cd[i].bit[j]=0; /*编码位上赋0*/elsecd[i].bit[j]=1; /*否则c是p的右孩子，编码位上赋1*/ c=p; /*更新c为p,为求下一个编码位做准备*/ }while(ht[p].parent!=-1); /*当未到达根结点继续做do循环*/ cd[i].start=j; /*求完一个叶子结点的哈夫曼编码时，记下编码开始位置*/}for(i=0;i<n;i++) /*输出n个叶子结点的哈夫曼编码*/{for(j=cd[i].start;j<maxbit;j++) /*逐位输出一个编码*/printf("%d",cd[i].bit[j]);printf("\n"); /*输出完一个哈夫曼编码后换行*/ }}五、调试过程一次编译二次编译三次编译六、实验结果七、总结(1) 深刻体会构建哈夫曼树的整个过程，对整体有个总的理解; (2) 复习以前所学C语言的一些语法，例如:for循环，if循环，while循环 (3) 理解哈夫曼的编码过程，编码思想(4) 此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制，有待改进。
哈夫曼编码译码器实验报告实验名称：哈夫曼编码译码器实验一、实验目的：1.了解哈夫曼编码的原理和应用。
2.实现一个哈夫曼编码的编码和译码器。
3.掌握哈夫曼编码的编码和译码过程。
二、实验原理：哈夫曼编码是一种常用的可变长度编码，用于将字符映射到二进制编码。
根据字符出现的频率，建立一个哈夫曼树，出现频率高的字符编码短，出现频率低的字符编码长。
编码过程中，根据已建立的哈夫曼树，将字符替换为对应的二进制编码。
译码过程中，根据已建立的哈夫曼树，将二进制编码替换为对应的字符。
三、实验步骤：1.构建一个哈夫曼树，根据字符出现的频率排序。
频率高的字符在左子树，频率低的字符在右子树。
2.根据建立的哈夫曼树，生成字符对应的编码表，包括字符和对应的二进制编码。
3.输入一个字符串，根据编码表将字符串编码为二进制序列。
4.输入一个二进制序列，根据编码表将二进制序列译码为字符串。
5.比较编码前后字符串的内容，确保译码正确性。
四、实验结果：1.构建哈夫曼树：-字符出现频率：A(2)，B(5)，C(1)，D(3)，E(1) -构建的哈夫曼树如下：12/\/\69/\/\3345/\/\/\/\ABCDE2.生成编码表：-A:00-B:01-C:100-D:101-E:1103.编码过程：4.译码过程：5.比较编码前后字符串的内容，结果正确。
五、实验总结：通过本次实验，我了解了哈夫曼编码的原理和应用，并且实现了一个简单的哈夫曼编码的编码和译码器。
在实验过程中，我充分运用了数据结构中的树的知识，构建了一个哈夫曼树，并生成了编码表。
通过编码和译码过程，我进一步巩固了对树的遍历和节点查找的理解。
实验结果表明，本次哈夫曼编码的编码和译码过程正确无误。
在实验的过程中，我发现哈夫曼编码对于频率较高的字符具有较短的编码，从而实现了对字符串的高效压缩。
同时，哈夫曼编码还可以应用于数据传输和存储中，提高数据的传输效率和存储空间的利用率。
通过本次实验，我不仅掌握了哈夫曼编码的编码和译码过程，还深入了解了其实现原理和应用场景，加深了对数据结构和算法的理解和应用能力。
实验五哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发编写一个哈夫曼码的编/译码系统。
基本要求：（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。
（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat 中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。
（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件text中。
（4）打印编码规则：即字符与编码的一一对应关系。
（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。
二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：typedef struct{int weight;int parent;int lchild;int rchild;char inf;}HNodeType;2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。
由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。
哈夫曼编码译码器数据结构C语言哈夫曼编码译码器数据结构C语言文档1.引言本文档介绍了一个基于哈夫曼编码的译码器的设计和实现。
哈夫曼编码是一种无损压缩算法，通过对出现频率较高的符号进行较短的编码，来减小数据的存储或传输所需的空间。
2.哈夫曼编码原理在哈夫曼编码中，使用一颗二叉树，将出现频率较高的符号表示为树的较浅的节点，而出现频率较低的符号表示为树的较深的节点。
通过遍历整个二叉树，可以得到每个符号对应的哈夫曼编码。
2.1 创建哈夫曼树首先，根据每个符号的出现频率，创建一颗包含所有符号的节点的最小堆。
然后，根据最小堆的特性，每次从最小堆中选取两个出现频率最低的节点，并合并为一个新节点。
重复这个过程，直到最小堆中只剩下一个节点，即哈夫曼树的根节点。
2.2 哈夫曼编码通过遍历哈夫曼树，可以得到每个符号对应的哈夫曼编码。
在遍历的过程中，左孩子表示编码中的“0”，右孩子表示编码中的“1”。
每次左移一个位，表示向左遍历，每次右移一个位，表示向右遍历。
3.数据结构设计下面介绍了本文档中所使用的各种数据结构和相关函数的设计。
3.1 结构定义```cstruct Node {char symbol。
int frequency。
struct Node leftChild。
struct Node rightChild。
}。
```3.2 方法定义```c// 创建哈夫曼树struct Node createHuffmanTree(char symbols, int frequencies, int size）// 哈夫曼编码表void generateHuffmanTable(struct Node root, char huffmanTable, char currentCode）// 哈夫曼编码char encode(char data, char huffmanTable）// 哈夫曼译码char decode(char encodedData, struct Node root）```4.实现细节在这个章节中，我们将会具体讨论各个方法的实现细节和使用示例。
实验六-哈夫曼编码和译码的算法设计与实现一、实验目的1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。
二、预习与参考1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2、设计和编制哈夫曼编译码器。
[参考数据类型或变量]typedef ElemType char；typedef struct node{int w;int flag;ElemType c;struct node *plink,*llink,*rlink;char code[m];}Node;Node *num[n], *root;[参考子程序接口与功能描述]void SetTree( NODE *root )功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树，对输入的正文进行编码void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。
四、实验步骤1、设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2、设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3、设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4、将你的程序整理成功能模块存盘备用。
5、将写的程序如下：#include <stdio.h>#include <string.h>#include <math.h>#include <string>#define maxn 20 //最大结点数目#define inf 0xfffffff //无穷大typedef struct node{double w;int flag;int c;struct node *plink,*llink,*rlink; char code[maxn];int codelen;node() //初始化节点{flag=0;llink=NULL;plink=NULL;rlink=NULL;codelen=0;}}node;node *num[2*maxn-1];//指针数组int n;void SetTree(node *&root)//从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树{int i,m,j;scanf("%d",&n);//输入结点个数nfor(i=0;i<n;i++){num[i]=new node();num[i]->c=i;scanf("%lf",&num[i]->w);//输入结点的权值}m=n;double min1,min2;int pos1=0,pos2=0;for(i=0;i<m-1;i++){min1=inf;min2=inf;for(j=0;j<n;j++) //寻找权值最小的两个结点，保存在pos1和pos2中{if(num[j]->flag==0){if(num[j]->w<min1){min1=num[j]->w;pos2=pos1;pos1=j;}else if(num[j]->w<min2) {min2=num[j]->w;pos2=j;}}}num[pos1]->flag=1; //将pos1和pos2合并在新结点中，作为新节点的子节点num[pos2]->flag=1;num[n]=new node(); //新节点编号从n开始num[n]->c=-1;////添加代码，建立新结点n//// //建立新结点nnum[n]->w=num[pos1]->w+num[pos2]->w;num[n]->llink=num[pos1];num[n]->rlink=num[pos2];num[pos1]->plink=num[n];num[pos2]->plink=num[n];n++;}root=num[n-1];n=m;}void EnCode(node *root,int deep,char code[]) //利用已建好的哈夫曼树，对输入的文本进行编码{int i;if(root->c!=-1){for(i=0;i<deep;i++){root->code[i]=code[i];}root->codelen=deep;return;}code[deep]='0'; //左节点编码为0 EnCode(root->llink,deep+1,code);code[deep]='1'; //右节点编码为1 EnCode(root->rlink,deep+1,code);}void DeCode(node *root,char code[]) //利用已建好的哈夫曼树，对输入的代码进行译码int i;node *temproot=root;int len=strlen(code);int ans[maxn],anslen=0;for(i=0;i<len;i++){////添加代码，根据code[i]的值确定temproot的指向//// //根据code[i]的值确定temproot的指向if(code[i]=='0')temproot=temproot->llink;elsetemproot=temproot->rlink;if(temproot->c!=-1){ans[anslen++]=temproot->c; temproot=root;}if(temproot->llink==NULL && temproot->rlink==NULL){printf("你输入的数据不存在于该哈弗曼树中!\n");return;}}printf("输入数据的译码为：\n");for(i=0;i<anslen;i++){printf("%d",ans[i]);}printf("\n");}void print(){int i,j;for(i=0;i<n;i++){printf("%.2f:",num[i]->w);for(j=0;j<num[i]->codelen;j++) printf("%c",num[i]->code[j]);printf("\n");}}int main(){freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);node *root=NULL;root=new node();SetTree(root);char code[maxn*maxn];EnCode(root,0,code);print();printf("按上面的编码规则输入代码:\n");scanf("%s",code);DeCode(root,code);return 0;}五、测试输入80.6 0.2 0.05 0.05 0.03 0.03 0.030.01输出0.6：00.2：100.05：11000.05：11110.03：110100.03：110110.03：111010.01：11100六、实验报告要求1、阐述实验目的和实验内容;2、提交实验程序的功能模块;3、记录最终测试数据和测试结果。
算法与数据结构课程设计哈夫曼编码和译码的设计与实现1.问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼码的编/译码系统。
2.基本要求a.编/译码系统应具有以下功能：（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中。
b.测试数据（1）利用下面这道题中的数据调试程序。
某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
字符空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 13．需求分析3.1程序的基本功能本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。
哈夫曼编/译码系统的设计与实现一、实验项目简介：1．问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼编/译码系统。
2．一个完整的系统应具有以下功能：1）初始化（Initialzation）。
从数据文件 DataFile.data 中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）。
用已建好的哈夫曼树，对文件ToBeTran.data 中的文本进行编码形成报文，将报文写在文件 Code.txt 中；3）译码（Decoding）。
利用已建好的哈夫曼树，对文件CodeFile.data 中的代码进行解码形成原文，结果存入文件 Textfile.txt 中；4）输出（Output）。
输出 DataFile.data 中出现的字符以及各字符出现的频度（或概率）；输出 ToBeTran.data 及其报文 Code.txt；输出 CodeFile.data 及其原文 Textfile.txt；要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data 和 CodeFile.data 三个文件，以保证系统的通用性。
二、实验目的：理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对二叉树的构建、遍历等以及哈夫曼编码的应用有更深层次的理解。
实验步骤：实验分 2 次完成第 1 次：完成程序的主框架设计，进行调试，验证其正确性；（2学时）第 2 次：详细设计，进行调试，对运行结果进行分析，完成实验报告。
选择建树：
选择编码：
选择译码：
五、总结
通过本次课程设计，我对哈夫曼树及哈夫曼编码有了更深刻的理解。
同时对C，C++的编程以及算法的实现产生了比较大的兴趣，还学到了许多在处理程序时的技巧和方法，刚看见实验题目时我一点头绪都没有，通过看数据结构书知道了编码如何写代码，但是译码还不不太明白如何进行编写，后来通过网上的资料将自己的思路捋顺了。
在译码处，不单实现了从文件读入，同时也实现了从键盘读入。
另外，我认为调试功能是整个编写程序过程中很重要的一个环节。
通过这次实验我对调试有了更加深刻的理解，懂得怎么样去调试程序，如何发现错误，如何更高效的改正，通过对上面程序的编写让我积累了一些编程的经验，比如在你编写代码是首先你应在大脑内先构思好你的程序，并在纸上写下你的思路很实现步骤，而不是急于动手编写。
有些事没想好就急于容易出现一些逻辑上的错误，最后实现不了又必须重来。
其次是数据类型的处理，不能将字符型数据存其他类型的数据，计算机是不识别的，写程序是要严格规范自己对不同类型数据存储和使用，还有就是当一个数据不再被使用时或下次你要用它来存放其他数值时要记得提前赋空，以免数据出错。
还有就是在程序中如果你要重复某些步骤时你可以。
