huffman编码及截断huffman编码、解码实习报告(word版)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：2020 年 5 月12 日一、实验目的掌握赫夫曼树和赫夫曼编码的基本思想和算法的程序实现。

二、实验内容及要求1、任务描述a.提取原始文件中的数据（包括中文、英文或其他字符），根据数据出现的频率为权重，b.构建Huffman编码表；c.根据Huffman编码表对原始文件进行加密，得到加密文件并保存到硬盘上；d.将加密文件进行解密，得到解码文件并保存点硬盘上；e.比对原始文件和解码文件的一致性，得出是否一致的结论。

2、主要数据类型与变量a.对Huffman树采用双亲孩子表示法，便于在加密与解密时的操作。

typedef struct Huffman* HuffmanTree;struct Huffman{unsigned int weight; //权值unsigned int p, l, r;//双亲，左右孩子};b．对文本中出现的所有字符用链表进行存储。

typedef struct statistics* List;struct statistics {char str; //存储此字符int Frequency; //出现的频率（次数）string FinalNum; //Huffman编码struct statistics* Next;};3、算法或程序模块对读取到的文本进行逐字符遍历，统计每个字符出现的次数，并记录在创建的链表中。

借助Huffman树结构，生成结构数组，先存储在文本中出现的所有字符以及它们出现的频率（即权值），当作树的叶子节点。

再根据叶子节点生成它们的双亲节点，同样存入Huffman树中。

在完成对Huffman树的创建与存储之后，根据树节点的双亲节点域以及孩子节点域，生成每个字符的Huffman编码，并存入该字符所在链表节点的FinalNum域。

哈夫曼编码的实验报告哈夫曼编码的实验报告一、引言信息的传输和存储是现代社会中不可或缺的一部分。

然而，随着信息量的不断增加，如何高效地表示和压缩信息成为了一个重要的问题。

在这个实验报告中，我们将探讨哈夫曼编码这一种高效的信息压缩算法。

二、哈夫曼编码的原理哈夫曼编码是一种变长编码方式，通过将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示，从而实现信息的压缩。

它的核心思想是利用统计特性，将出现频率较高的字符用较短的编码表示，从而减少整体编码长度。

三、实验过程1. 统计字符频率在实验中，我们首先需要统计待压缩的文本中各个字符的出现频率。

通过遍历文本，我们可以得到每个字符出现的次数。

2. 构建哈夫曼树根据字符频率，我们可以构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，其中每个叶子节点代表一个字符，并且叶子节点的权值与字符的频率相关。

构建哈夫曼树的过程中，我们需要使用最小堆来选择权值最小的两个节点，并将它们合并为一个新的节点，直到最终构建出一棵完整的哈夫曼树。

3. 生成编码表通过遍历哈夫曼树，我们可以得到每个字符对应的编码。

在遍历过程中，我们记录下每个字符的路径，左边走为0，右边走为1，从而生成编码表。

4. 进行编码和解码在得到编码表后，我们可以将原始文本进行编码，将每个字符替换为对应的编码。

编码后的文本长度将会大大减少。

为了验证编码的正确性，我们还需要进行解码，将编码后的文本还原为原始文本。

四、实验结果我们选取了一段英文文本作为实验数据，并进行了哈夫曼编码。

经过编码后，原始文本长度从1000个字符减少到了500个字符。

解码后的文本与原始文本完全一致，验证了哈夫曼编码的正确性。

五、讨论与总结哈夫曼编码作为一种高效的信息压缩算法，具有广泛的应用前景。

通过将出现频率较高的字符用较短的编码表示，哈夫曼编码可以在一定程度上减小信息的存储和传输成本。

然而，哈夫曼编码也存在一些局限性，例如对于出现频率相近的字符，编码长度可能会相差较大。

中北大学数据结构课程设计说明书学生姓名: 郝晨栋学号： 1021010933软件学院学院:软件开发与测试: 专业哈夫曼编码/目题: 译码器康珺教指导师2011年12月20日目录1 问题描述.............................................................. 错误！未定义书签。

2 需求分析.............................................................. 错误！未定义书签。

3 概要设计 (1)3．1抽象数据类型定义 (1)3．2总体框图以及功能描述 (2)4 详细设计 (2)4．1数据类型的定义 (2)4．2主要模块的算法描述 (3)5 测试分析................................................................................................46 课程设计总结 (6)附录（源程序清单） (7)- 1 -1 问题描述1.设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

(1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)；(2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树;(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。

2 需求分析编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。

比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。

比如需传送的电文为“A B A C C D A”假设将A,B,C,D分别编码为00、01、10、11.则上述电文遍为00010010101100，总长度为14位。

数据结构课程设计设计题目：哈夫曼树编码译码目录第一章需求分析1第二章设计要求1第三章概要设计2（1）其主要流程图如图1-1所示。

3（2）设计包含的几个方面4第四章详细设计4（1）①哈夫曼树的存储结构描述为：4（2）哈弗曼编码5（3）哈弗曼译码7（4）主函数8（5）显示部分源程序：8第五章调试结果10第六章心得体会12第七章12附录：12第一章需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。

哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。

第二章设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。

若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。

... ... 哈夫曼编码器实验报告学院：计算机学院班级：计科0801班：王宇宏学号：04081027（27）一．实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二．实验环境Microsoft visual c++三、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

四、需求分析（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。

（2）输出哈夫曼树，及各字符对应的编码。

（3）编码：利用建好的哈夫曼树，对输入的待发送电文进行编码。

同时输入原文及编码串。

（4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。

同时输入编码串及原文。

五、概要设计#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>//typedef int TElemType;const int UINT_MAX=1000;char str[50];typedef struct{int weight,K;int parent,lchild,rchild;}HTNode,* HuffmanTree;typedef char **HuffmanCode;//-----------全局变量-----------------------HuffmanTree HT;HuffmanCode HC;int w[50],i,j,n;char z[50];int flag=0;int numb=0// -----------------求哈夫曼编码-----------------------struct cou{char data;int count;}cou[50];int min(HuffmanTree t,int i){ // 函数void select()调用int j,flag;int k=UINT_MAX; // 取k为不小于可能的值,即k为最大的权值1000 for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;return flag;}//--------------------slect函数----------------------void select(HuffmanTree t,int i,int &s1,int &s2){ // s1为最小的两个值中序号小的那个int j;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}// --------------算法6.12--------------------------void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ // w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HCint m,i,s1,s2,start;//unsigned c,f;int c,f;HuffmanTree p;char *cd;if(n<=1)return;//检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)p->parent=0;for(i=n+1;i<=m;++i) // 建哈夫曼树{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=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个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间cd[n-1]='\0'; // 编码结束符for(i=1;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';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC }free(cd); // 释放工作空间}//--------------------- 获取报文并写入文件---------------------------------int InputCode(){//cout<<"请输入你想要编码的字符"<<endl;FILE *tobetran;if((tobetran=fopen("tobetran.txt","w"))==NULL){cout<<"不能打开文件"<<endl;return 0;}cout<<"请输入你想要编码的字符"<<endl;gets(str);fputs(str,tobetran);cout<<"获取报文成功"<<endl;fclose(tobetran);return strlen(str);}//--------------初始化哈夫曼链表--------------------------------- void Initialization(){ int a,k,flag,len;a=0;len=InputCode();for(i=0;i<len;i++){k=0;flag=1;cou[i-a].data=str[i];cou[i-a].count=1;while(i>k){if(str[i]==str[k]){a++;flag=0;}k++;if(flag==0)break;}if(flag){for(j=i+1;j<len;j++){if(str[i]==str[j])++cou[i-a].count;}}}n=len-a;for(i=0;i<n;i++){ cout<<cou[i].data<<" ";cout<<cou[i].count<<endl;}for(i=0;i<=n;i++){*(z+i)=cou[i].data;*(w+i)=cou[i].count;}HuffmanCoding(HT,HC,w,n);//------------------------ 打印编码-------------------------------------------cout<<"字符对应的编码为:"<<endl;for(i=1;i<=n;i++){puts(HC[i]);}//-------------------------- 将哈夫曼编码写入文件------------------------cout<<"下面将哈夫曼编码写入文件"<<endl<<"...................."<<endl;FILE *htmTree;char r[]={' ','\0'};if((htmTree=fopen("htmTree.txt","w"))==NULL){cout<<"can not open file"<<endl;return;}fputs(z,htmTree);for(i=0;i<n+1;i++){fprintf(htmTree,"%6d",*(w+i));fputs(r,htmTree);}for(i=1;i<=n;i++){fputs(HC[i],htmTree);fputs(r,htmTree);}fclose(htmTree);cout<<"已将字符与对应编码写入根目录下文件htmTree.txt中"<<endl<<endl;}//---------------------编码函数---------------------------------void Encoding(){cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl; FILE *tobetran,*codefile;if((tobetran=fopen("tobetran.txt","rb"))==NULL){cout<<"不能打开文件"<<endl;}if((codefile=fopen("codefile.txt","wb"))==NULL){cout<<"不能打开文件"<<endl;}char *tran;i=99;tran=(char*)malloc(100*sizeof(char));while(i==99){if(fgets(tran,100,tobetran)==NULL){cout<<"不能打开文件"<<endl;break;}for(i=0;*(tran+i)!='\0';i++){for(j=0;j<=n;j++){if(*(z+j-1)==*(tran+i)){fputs(HC[j],codefile);if(j>n){cout<<"字符错误，无法编码!"<<endl; break;}}}}}cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);}//-----------------译码函数---------------------------------void Decoding(){cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;FILE *codef,*txtfile;if((txtfile=fopen("txtfile.txt","w"))==NULL){cout<<"不能打开文件"<<endl;}if ((codef=fopen("codefile.txt","r"))==NULL){cout<<"不能打开文件"<<endl;}char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000;work=(char*)malloc(length*sizeof(char));fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char));i3=2*n-1;for(i=0;*(work+i-1)!='\0';i++){i2=*(work+i);if(HT[i3].lchild==0){*(work2+i4)=*(z+i3-1);i4++;i3=2*n-1;i--;}else if(i2=='0') i3=HT[i3].lchild;else if(i2=='1') i3=HT[i3].rchild;}*(work2+i4)='\0';fputs(work2,txtfile);cout<<"译码完成"<<endl<<"容写入根目录下的文件txtfile.txt中"<<endl<<endl;free(work);free(work2);fclose(txtfile);fclose(codef);}//-----------------------打印编码的函数----------------------void Code_printing(){cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl; FILE * CodePrin,* codefile;if((CodePrin=fopen("CodePrin.txt","w"))==NULL){cout<<"不能打开文件"<<endl;return;}if((codefile=fopen("codefile.txt","r"))==NULL){cout<<"不能打开文件"<<endl;return;}char *work3;work3=(char*)malloc(51*sizeof(char));do{if(fgets(work3,51,codefile)==NULL){cout<<"不能读取文件"<<endl;break;}fputs(work3,CodePrin);puts(work3);}while(strlen(work3)==50);free(work3);cout<<"打印工作结束"<<endl<<endl;fclose(CodePrin);fclose(codefile);}//------------------------------- 打印译码函数---------------------------------------------void Code_printing1(){cout<<"下面打印根目录下文件txtfile.txt中译码字符"<<endl;FILE * CodePrin1,* txtfile;if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL){cout<<"不能打开文件"<<endl;return;}if((txtfile=fopen("txtfile.txt","r"))==NULL){cout<<"不能打开文件"<<endl;return;}char *work5;work5=(char*)malloc(51*sizeof(char));do{if(fgets(work5,51,txtfile)==NULL){cout<<"不能读取文件"<<endl;break;}fputs(work5,CodePrin1);puts(work5);}while(strlen(work5)==50);free(work5);cout<<"打印工作结束"<<endl<<endl;fclose(CodePrin1);fclose(txtfile);}//------------------------打印哈夫曼树的函数----------------------- void coprint(HuffmanTree start,HuffmanTree HT){if(start!=HT){FILE * TreePrint;if((TreePrint=fopen("TreePrint.txt","a"))==NULL){cout<<"创建文件失败"<<endl;return;}numb++;//该变量为已被声明为全局变量coprint(HT+start->rchild,HT);cout<<setw(5*numb)<<start->weight<<endl;fprintf(TreePrint,"%d\n",start->weight);coprint(HT+start->lchild,HT);numb--;fclose(TreePrint);}}void Tree_printing(HuffmanTree HT,int w){HuffmanTree p;p=HT+w;cout<<"下面打印哈夫曼树"<<endl;coprint(p,HT);cout<<"打印工作结束"<<endl;}//------------------------主函数------------------------------------void main(){char choice;while(choice!='q'){ cout<<"\n******************************"<<endl;cout<<" 欢迎使用哈夫曼编码解码系统"<<endl;cout<<"******************************"<<endl;cout<<"(1)要初始化哈夫曼链表请输入'i'"<<endl; cout<<"(2)要编码请输入'e'"<<endl;cout<<"(3)要译码请输入'd'"<<endl;cout<<"(4)要打印编码请输入'p'"<<endl;cout<<"(5)要打印哈夫曼树请输入't'"<<endl;cout<<"(6)要打印译码请输入'y'"<<endl;if(flag==0)cout<<"\n请先初始化哈夫曼链表,输入'i'"<<endl;cin>>choice;switch(choice){case 'i':Initialization();break;case 'e':Encoding();break;case 'd':Decoding();break;case 'p':Code_printing();break;case 't':Tree_printing(HT,2*n-1);break;case 'y':Code_printing1();break;default:cout<<"input error"<<endl;}}free(z);free(w);free(HT);}运行结果：六、所遇问题及心得体会本次试验中所遇到的主要问题为哈弗曼编码的算法，以及整个变量的控制。

1.初始化：从文件（程序运行时，由用户输入）读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，将它存于文件中。

2.编码：利用已建好的哈夫曼树（如不在内存，则从文件中读入）对文件字符集中的每一个进行编码，将结果放在中。

3.译码：利用已建好的哈夫曼树将中的代码进行译码，结果保存在中。

4.印代码文件。

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

同时将结果保存在中。

二.概要设计：1.哈夫曼树的抽象数据类型定义：ADT haffman{ 数据对象：D={ai|ai为charnode型的结点，i=1，2，3，……n，n>0}数据关系：R={<ai,><ai,>|ai是D上的元素}} ADT haffman2.编码集结构体的抽象数据类型的定义：ADT code{ 数据对象：D1={ai| ai是charlink型的结点，i=1，2，……n，n>0}D2={bi|bi是codelink型的结点，i=1，2，……n，n>0}数据关系： R1={<ai,>|ai是D1上的元素}R2={<bi,>|bi是D2上的元素}} ADT code3.程序分为四个部分：1）读入字符集以及相应频度，建立哈夫曼树。

2）根据哈夫曼树得到每一个字符的哈夫曼编码。

3）读入要编码的字符串，根据哈夫曼树和编码集求出字符串的哈夫曼编码。

4）根据哈夫曼编码和哈夫曼树得到字符串。

三.详细设计：h >> hufW[ ii ].wt;}(); .eight<< setw( 8 ) << hufT[ tOut ].parent<< setw( 8 ) << hufT[ tOut ].lChild<< setw( 8 ) << hufT[ tOut ].rChild << endl;}hufTreeOutPut << "-- end HT --------------------------- " << endl << endl << "-- HC ------------------------------- " << endl;for( int cOut = 1 ; cOut <= hufNum ; cOut++ ){hufTreeOutPut << " " << hufC[ cOut ].ch << " ---->> " << hufC[ cOut ].hufCh << endl;}hufTreeOutPut << "-- convert -- ok -------------------- " << endl;(); t;p->parent = p->lChild = p->rChild = 0; i-1 ]选择parent 为 0 且weight 最小的两个结点，其序号分别为 s1 和 s2arent = i; arent = i; Child = s1; Child = s2; eight =HT[ s1 ].weight + HT[ s2 ].weight; arent ; f != 0 ; c = f , f =HT[ f ].parent ) Child == c ) { cd[ --start ] = '0'; }else { cd[ --start ] = '1'; }}HC[ i ].ch = w[ i-1 ].ch ; ufCh = ( char* ) malloc ( ( n - start ) * sizeof( char ) ); ufCh , &cd[ start ] ); arent != 0 ) continue;else{sm1 = HT[ m ].weight;s1=m;break;}}for( int j = m+1 ; j <= i ; j++ ) arent != 0 ) continue;else{if( sm1 > HT[ j ].weight ){sm1 = HT[ j ].weight;s1 = j;}}}for( m = 1 ; m <= i ; m++ ) arent != 0 ) continue;else{sm2 = HT[ m ].weight;s2=m;if( s2 == s1 ) continue;else break;}}for( int k = m+1 ; k <= i ; k++ ) arent != 0 ) continue;else{if( (HT[ k ].weight < sm2) && ( k != s1 ) ) eight;s2 = k;}}}} ufCh == ' 'fOut << HC[ sub ].hufCh;}else if( inBuf == '\n' ){continue;}else{ufCh == 'A'. 以下的字符雷同sub = inBuf - 63;fOut << HC[ sub ].hufCh;}}HT[p]就为 HT 的根.Child != 0 ) Child; ufCh , cd ) == 0 ){fOut << HC[ iHC ].ch;break; Child; Child != 0 ) Child; ufCh , cd ) == 0 ){fOut << HC[ iHC ].ch;break; Child; ufCh , cd ) == 0 ){fOut << HC[ iHC ].ch;break; ufCh , cd ) == 0 ){fOut << HC[ iHC ].ch;break; 试分析1.本次作业在打印树形结构的时候有点遗憾，其他的都应该做的完美的了。

目录一、概述 (1)二、系统分析 (1)三、概要设计 (2)四、详细设计 (4)4.1 赫夫曼树的建立 (4)4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 (5)4.1.2 统计字符串中字符的种类以及各类字符的个数 (7)4.1.3构造赫夫曼树 (8)4.2赫夫曼编码 (10)4.2.1赫夫曼编码算法 (10)4.2.2建立正文的编码文件 (11)4.3代码文件的译码 (12)五、运行与测试 (14)六、总结与心得 (14)参考文献 (15)附录 (15)一、概述本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出电文字符串。

在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

二、系统分析赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。

若将此对应到二叉树上，W i 为叶节点的权，L i 为根节点到叶节点的路径长度。

那么，∑W i L i 恰好为二叉树上带权路径长度。

因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树，此构造过程成为赫夫曼编码。

根据设计要求和分析，要实现设计，必须实现以下方面的功能：（1）赫夫曼树的建立；（2）赫夫曼编码的生成；（3）编码文件的译码；三、概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

实习报告题目：哈夫曼编/译码器班级：计算机四班24021004学号：2402100402姓名：张青赛完成日期：2011年6月10日一、设计题目哈夫曼编码/译码器二、需求分析Ⅰ、运行环境：Microsoft Visual C++Ⅱ、程序执行的命令包括1 初始化：输入一串字符（正文），计算不同字符(包括空格)的数目以及每种字符出现的频率(以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。

2 编码：利用求出的哈夫曼编码，对该正文（字符串）进行码，并输出。

3 译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。

4 结束5 测试数据：E : 12 H : 2 M : 3 K : 7三、设计目的：1. 掌握建立哈夫曼树和哈夫曼编码的方法。

2. 掌握哈夫曼编码的实际应用方法。

四、设计内容利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

五设计说明：1 算法设计思想：确定哈夫曼树和哈夫曼编码的存储表示，在数组中存放结点的各类信息，设计构造哈夫曼树的程序creathuffmantree、求出n个字母的哈夫曼编码程序huffmancode和哈夫曼的译码程序huffmandecode。

利用译码程序进行译码并输出，main()中调用各个函数，实现整个过程。

2．二叉树的抽象数据类型定义为：ADT BinaryTree{数据对象D:D是具有相同特性的数据元素的集合数据关系R:若D为空,则BinaryTree称为空二叉树；若D不为空,则BinaryTree满足二元关系；基本操作P：InitBiTree(&T);操作结果：构造空二叉树T。