数据结构(HuffmanTree)报告

哈夫曼树实验报告编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（哈夫曼树实验报告）的内容能够给您的工作和学习带来便利。

同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。

本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为哈夫曼树实验报告的全部内容。

实验报告实验名称Huffman编码专业班级计科三班姓名学号指导教师日期 2014.12。

20一、实验目的熟练掌握二叉树应用（Huffman编码）的基本算法实现。

二、实验内容●1．对输入的一串电文字符实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。

实现功能如下：♦Huffman树的建立♦Huffman编码的生成编码文件的译码三、实验要求l 设计思路：数据结构：#define n 100 //叶子结点数＃define m 2*n-1 // Huffman树中结点总数typedef struct {int weight; //权值int lchild ， rchild , parent； //左右孩子及双亲指针｝HTNode； //树中结点类型typedef HTNode HuffmanTree［m+1］；//0号单元不用主要实现函数:⏹统计字符串中字符的种类以及各类字符的个数的函数⏹构造Huffman树的函数⏹Huffman编码的函数⏹建立正文的编码文件的函数⏹代码文件的译码函数⏹主函数四、实验概要设计1)功能框图五。

使用说明1.运行环境：VC++ 6.02。

首先选择主控菜单中的操作１，即建表，然后进行其它操作．六．实验截图七 实验体会1、构建哈夫曼树的关键在于找最小树；在F 中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：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)1．1路径和路径长度 (1)1.2树的带权路径长度 (1)1．3哈夫曼树的定义 (1)第二章哈夫曼树的构造 (2)2.1哈夫曼树的构造 (2)第三章哈夫曼树的存储结构及哈夫曼算法的实现 (3)3.1哈夫曼树的存储结构 (3)3.2 哈夫曼算法的简要描述 (3)第四章哈夫曼树的应用 (5)4.1哈夫曼编码 (5)4.2求哈夫曼编码的算法 (5)4.21思想方法 (5)4.22字符集编码的存储结构及其算法描述 (6)4.3哈夫曼树和编码程序实现： (6)4.4程序运行结果： (9)心得体会 (10)参考文献 (10)第一章哈夫曼树的基本术语1．1路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

1.2结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

1.2树的带权路径长度树的带权路径长度(Weighted Path Length of Tree)：也称为树的代价，定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。

1．3哈夫曼树的定义在权为wl ，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。

[例]给定4个叶子结点a，b，c和d，分别带权7，5，2和4。

构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=4(c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

数据结构实验报告实验名称：哈夫曼树学生姓名：袁普班级：2013211125班班内序号：14号学号：2013210681日期：2014年12月实验目的和内容利用二叉树结构实现哈夫曼编/解码器。

基本要求：1、初始化(Init)：能够对输入的任意长度的字符串 s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5、打印(Print)：以直观的方式打印哈夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

7、可采用二进制编码方式（选作）测试数据：I love data Structure, I love Computer。

I will try my best to studydata Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode{int weight; //权值int parent; //父节点int lchild; //左孩子int rchild; //右孩子};struct HCode //实现编码的结构类型{char data; //被编码的字符char code[100]; //字符对应的哈夫曼编码};2.2 程序流程2.3 关键算法分析算法1：void Huffman::Count()[1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表[2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组，[3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n）[4] 代码逻辑：leaf=0; //初始化叶子节点个数int i,j=0;int s[128]={0}; 用于存储出现的字符for(i=0;str[i]!='\0';i++) 遍历输入的字符串s[(int)str[i]]++; 统计每个字符出现次数for(i=0;i<128;i++)if(s[i]!=0){data[j]=(char)i; 给编码表的字符赋值weight[j]=s[i]; 构建权值数组j++;}leaf=j; //叶子节点个数即字符个数for(i=0;i<leaf;i++)cout<<data[i]<<"的权值为："<<weight[i]<<endl;算法2：void Init();[1] 算法功能：构建哈弗曼树[2] 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。

数据结构实验报告题目：数据结构实验报告学院：工商管理学院班级：信息1001姓名：彭振宇学号：时间：2012/6/26实验三：树和二叉树的应用一．实验题目：树和二叉树的应用二．实验内容：哈夫曼编码设计三．实验目的：掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。

四．实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。

五．概要设计原理：1.选择parent为0且weight最小的两个结点。

其序号分别为s1和s22.建立赫夫曼树叶3.从叶子到根逆向求每个字符的赫夫曼编码4.输出构造的树5.输出得到的各权Huffman编码六．详细程序清单及注释说明：#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAXSIZE 30 //最大叶子数#define MAXCODE 10000 //编码最大长度#define OK 1#define ERROR 0#define OVERLOW -2//=============赫夫曼树和赫夫曼编码的存储表示=====typedef struct{unsigned int weight;unsigned int parent, lchild, rchild;}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表/*----------------算法描述----------------*/void Select(HuffmanTree HT, int n, int *s1, int *s2)//选择parent为0且weight最小的两个结点。

【仔细安排】之阳早格格创做简曲代码真止如下：#include<iostream>#include<fstream>#include<string>struct HuffmanNode //哈妇曼树的一个结面{int weight;int parent;int lchild,rchild;};class HuffmanTree //哈妇曼树{private:HuffmanNode *Node; //Node[]存搁哈妇曼树char *Info; //Info[]存搁源文用到的字符——源码，如'a','b','c','d','e'，此真质不妨搁进结面中，不但独设数组存搁 int LeafNum; //哈妇曼树的叶子个数，也是源码个数public:HuffmanTree();~HuffmanTree();void CreateHuffmanTree(); /*正在内存中修坐哈妇曼树，存搁正在Node[]中. 让用户从二种修坐哈妇曼树的要领中采用：1.从键盘读进源码字符集个数，每个字符，战每个字符的权沉，修坐哈妇曼树，并将哈妇曼树写进文献hfmTree中.2.从文献hfmTree中读进哈妇曼树疑息，修坐哈妇曼树*/void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder(); /*使用修坐佳的哈妇曼树（如果不正在内存，则从文献hfmTree中读进并修坐内存里的哈妇曼树），对于文献ToBeTran中的正文举止编码，并将码文写进文献CodeFile中.ToBeTran的真质不妨用记事本等步调编写爆收.*/void Decoder(); /*待译码的码文存搁正在文献CodeFile 中，使用修坐佳的哈妇曼树（如果不正在内存，则从文献hfmTree中读进并修坐内存里的哈妇曼树）将码文译码，得到的源文写进文献TextFile中，并共时输出到屏幕上.*/ void PrintCodeFile(); /*将码文文献CodeFile隐现正在屏幕上*/void PrintHuffmanTree(); /*将哈妇曼树以曲瞅的形式（凸进表示法，或者广义表，或者其余树形表示法）隐现正在屏幕上，共时写进文献TreePrintFile中*/void PrintHuffmanTree_aoru(int T,int layer=1); /*凸进表示法隐现哈妇曼树，由PrintHuffmanTree()调用*/};#include<string>#include<limits> //为使用整型最大值#include"HuffmanTree.h"using namespace std;//************************************************** ****HuffmanTree::HuffmanTree(){Node=NULL;}//************************************************** ****HuffmanTree::~HuffmanTree(){delete[]Node;}//******************************************************void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<"您要从文献中读进哈妇曼树(按1)，仍旧从键盘输进哈妇曼树(按2)？";cin>>Choose;if(Choose=='2') {//键盘输进修坐哈妇曼树CreateHuffmanTreeFromKeyboard();}//choose=='2'CreateHuffmanTreeFromFile();}}//************************************************** ****void HuffmanTree::CreateHuffmanTreeFromKeyboard(){int Num;cout<<"\n请输进源码字符集个数：";cin>>Num;if (Num<=1){cout<<"无法修坐少于2个叶子结面的哈妇曼树.\n\n"; return;}LeafNum=Num;Node=new HuffmanNode[2*Num-1];Info=new char[2*Num-1];for(int i=0;i<Num;i++) {//读进哈妇曼树的叶子结面疑息cout<<"请输进第"<<i+1<<"个字符值";getchar();Info[i]=getchar(); //源文的字符存进字符数组Info[]getchar();cout<<"请输进该字符的权值或者频度";cin>>Node[i].weight; //源文的字符权沉存进Node[].weight Node[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;}for(i=Num;i<2*Num-1;i++){//循环修坐哈妇曼树里里结面int pos1=-1,pos2=-1;int max1=32767,max2=32767;for(int j=0;j<i;j++)//正在根节面中选出权值最小的二个if(Node[j].parent==-1)//是可为根结面if(Node[j].weight<max1){max2=max1;max1=Node[j].weight;pos2=pos1;pos1=j;}elseif(Node[j].weight<max2){max2=Node[j].weight;pos2=j;}Node[pos1].parent=i;Node[pos2].parent=i;Node[i].lchild=pos1;Node[i].rchild=pos2;Node[i].parent=-1;Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //forcout<<"哈妇曼树已乐成构制完毕.\n";char ch;cout<<"是可要替换本去的哈妇曼树文献(Y/N):";cin>>ch;if (ch!='y'&&ch!='Y') return;else{ofstream fop;fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //挨启文献if(fop.fail()){cout<<"\n哈妇曼树文献挨启波折，无法将哈妇曼树写进hfmTree.dat文献.\n";return;}fop.write((char*)&Num,sizeof(Num)); //先写进哈妇曼树的叶子结面个数for(i=0;i<Num;i++){ //再写进源笔墨符集的所有字符（保存正在Info[]中）fop.write((char*)&Info[i],sizeof(Info[i]));flush(cout);}for(i=0;i<2*Num-1;i++){ //末尾写进哈妇曼树的各个结面（保存正在Node[]中）fop.write((char*)&Node[i],sizeof(Node[i]));flush(cout);}fop.close(); //关关文献cout<<"\n哈妇曼树已乐成写进hfmTree.dat文献.\n";}}//************************************************** ****void HuffmanTree::CreateHuffmanTreeFromFile(){ifstream fip;fip.open("hfmTree.dat",ios::binary|ios::in);if(fip.fail()){cout<<"哈妇曼树文献hfmTree.dat挨启波折，无法修坐哈妇曼树.\n";return;}fip.read((char*)&LeafNum,sizeof(LeafNum));{cout<<"哈妇曼树文献中的数据有误，叶子结面个数少于2个，无法修坐哈妇曼树.\n";fip.close();return;}Info=new char[LeafNum];Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i<LeafNum;i++)fip.read((char*)&Info[i],sizeof(Info[i]));for(i=0;i<2*LeafNum-1;i++)fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<"哈妇曼树已乐成构制完毕.\n";}//************************************************** ****void HuffmanTree::Encoder(){if(Node==NULL)CreateHuffmanTreeFromFile();{cout<<"内存无哈妇曼树.支配撤消.\n\n";return;}}//ifchar *SourceText; //字符串数组，用于存搁源文char Choose;cout<<"您要从文献中读进源文(按1)，仍旧从键盘输进源文(按2)？";cin>>Choose;if(Choose=='1'){ifstream fip1("ToBeTran.txt");if(fip1.fail()){cout<<"源文文献挨启波折!无法继承真止.\n";return;}char ch;int k=0;while(fip1.get(ch)) k++; //第一次读文献只统计文献中有几个字符，将字符数存进kfip1.close();SourceText=new char[k+1]; //申请存搁源文的字符数组空间ifstream fip2("ToBeTran.txt");//第二次读源文文献，把真质写进SourceText[]k=0;while(fip2.get(ch)) SourceText[k++]=ch;fip2.close();SourceText[k]='\0';cout<<"需编码的源文为：";cout<<SourceText<<endl;}else{ //从键盘输进源文string SourceBuff;cin.ignore();cout<<"请输进需要编码的源文(可输进任性少，按回车键中断):\n";getline(cin,SourceBuff,'\n');int k=0;while(SourceBuff[k]!='\0')k++;SourceText=new char[k+1];k=0;while(SourceBuff[k]!='\0'){SourceText[k]=SourceBuff[k];k++;}SourceText[k]='\0';cout<<"覆盖已有的编码本文献?（Y/N）"; char ch;cin>>ch;if(ch=='y'||ch=='Y'){ofstream fip2;fip2.open("ToBeTran.txt");if(!fip2){cerr<<"文献挨启波折！"<<endl;abort();}fip2<<SourceText<<endl;fip2.close();cout<<"需编码的源文已写进ToBeTran.txt中"<<endl;}}//启初编码ofstream fop("CodeFile.dat",ios::trunc); //挨启码文存搁文献char *code;code=new char[LeafNum]; //存搁一个源笔墨符的编码int k=0;while(SourceText[k]!='\0') //源文串中从第一个字符启初逐个编码{int star=0;char ch=SourceText[k];for(int i=0;i<LeafNum;i++)if(Info[i]==ch)//供出该笔墨天圆的单元编号break;int j=i;while(Node[j].parent!=-1){j=Node[j].parent;if(Info[Node[j].lchild]==Info[i]) code[star++]='0';else code[star++]='1';i=j;}code[star]='\0';for(i=0;i<star/2;i++){int j=code[i];code[i]=code[star-i-1];code[star-i-1]=j;}i=0; //将源文的目前字符的对于应编码写进码文文献while(code[i]!='\0'){fop<<code[i];i++;}k++; //源文串中的字符后移一个}fop.close();cout<<"已完毕编码，码文已写进文献CodeFile.dat中.\n\n"; }//************************************************** ****void HuffmanTree::Decoder(){if(Node==NULL){CreateHuffmanTreeFromFile();if (LeafNum<=1){cout<<"内存无哈妇曼树.支配撤消.\n\n"; return;}}//将码文从文献CodeFile.dat中读进 CodeStr[] ifstream fip1("CodeFile.dat");if(fip1.fail()){cout<<"不码文，无法译码.\n";return;}char* CodeStr;int k=0;char ch;while(fip1.get(ch)){k++;}fip1.close();CodeStr=new char[k+1];ifstream fip2("CodeFile.dat");k=0;while(fip2.get(ch)) CodeStr[k++]=ch;fip2.close();CodeStr[k]='\0';cout<<"经译码得到的源文为：";ofstream fop("TextFile.dat");int j=LeafNum*2-1-1; //j指背哈妇曼树的根int i=0; //码文从第一个标记启初，逆着哈妇曼树由根下止，按码文的目前标记决断下止到左孩子仍旧左孩子while(CodeStr[i]!='\0'){ //下止到哈妇曼树的叶子结面处，则译出叶子结面对于应的源笔墨符if(CodeStr[i]=='0') j=Node[j].lchild;else j=Node[j].rchild;if(Node[j].rchild==-1){cout<<Info[j];fop<<Info[j];j=LeafNum*2-1-1;}i++;}fop.close();cout<<"\n译码乐成且已存到文献TextFile.dat中.\n\n";}//************************************************** ****void HuffmanTree::PrintCodeFile(){char ch;int i=1;ifstream fip("CodeFile.dat");ofstream fop("CodePrin.dat");if(fip.fail()){cout<<"不码文文献，无法隐现码文文献真质.\n";return;}while(fip.get(ch)){cout<<ch;fop<<ch;if(i==50){cout<<endl;fop<<endl;i=0;}i++;}cout<<endl;fop<<endl;fip.close();fop.close();}//************************************************** ****void HuffmanTree::PrintHuffmanTree(){if(Node==NULL){CreateHuffmanTreeFromFile();if (LeafNum<=1){cout<<"内存无哈妇曼树.支配撤消.\n\n";return;}}ofstream fop("TreePrint.dat",ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;}//************************************************** ****void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer){for(int i=0;i<layer;i++) cout<<"___";cout<<Node[T].weight<<endl;if(Node[T].lchild!=-1)PrintHuffmanTree_aoru(Node[T].lchild,++layer);if(Node[T].rchild!=-1)PrintHuffmanTree_aoru(Node[T].rchild,layer--);}#include<string.h>#include<stdlib.h>using namespace std;int main(){HuffmanTree huftree;char Choose;while(1){cout<<"\n\n**********************欢迎使用哈妇曼编码/译码系统***********************"<<endl;cout<<"您不妨举止以下支配:"<<endl;cout<<"1 修坐哈妇曼树 3 译码(码文已正在文献CodeFile中) 5 隐现哈妇曼树"<<endl;cout<<"2 编码(源文已正在文献ToBeTran中，或者键盘输进) 4 隐现码文 6 退出 "<<endl;cout<<"请采用一个支配:";cin>>Choose;switch(Choose){huftree.CreateHuffmanTree();break;case '2':huftree.Encoder();break;case '3':huftree.Decoder();break;case '4':huftree.PrintCodeFile();break;case '5':huftree.PrintHuffmanTree();break;case '6':cout<<"\n*************************感动使用本系统!***********************\n\n";system("pause");return 0;}//switch}//while【用户脚册】加进哈弗曼树系统，出现以下界里：1修坐弗曼树2、编码（源文中读进，键盘输进）3、译码4、隐现码文 5、隐现哈弗曼树 6、退出用户根据该提示，采用前里数字，便能加进各个功能函数，真止函数功能.【运止截止】截图一：截图二：截图三：截图四：【心得体验】本真验是收集相关资料，而后自己减少功能函数的代码真止的.果此，正在完毕已完毕的功能函数之前还必须要小心阅读所给出代码，完全瞅察各个部分之前的通联，搞领会已给出战已完毕的代码功能之后，才根据算法，安排出该功能的函数代码.正在完毕真验时，有收新颖码也有忽视的场合，如正在源文献读进的时间，多出了一个值，得要减少下表减那个代码去去掉.另有便是正在译码的时间，由于变量定义的殽杂，正在编译的时间通过，但是真止时却出现意料不到的截止，正在自己小心瞅察、思索之前也还出找堕落误之处.厥后通过请教教授，正在战教授计划查看之后才知讲了过得之天圆，末尾改正过得.真验乐成完毕.【参照文献】数据结构取算法（课本）C++谈话前提。

数据结构哈夫曼树编码译码实验报告.【详细设计】具体代码实现如下：//HaffmanTree.h#include#include#includestruct HuffmanNode //哈夫曼树的一个结点{ int weight; int parent; int lchild,rchild; };class HuffmanTree //哈夫曼树{private: HuffmanNode *Node; //Node[]存放哈夫曼树char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放int LeafNum; //哈夫曼树的叶子个数，也是源码个数public: HuffmanTree(); ~HuffmanTree(); void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。

让用户从两种建立哈夫曼树的方法中选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中。

2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。

ToBeTran的内容可以用记事本等程序编辑产生。

*/ void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上。

数据结构哈夫曼编码实验报告【正文】1.实验目的本实验旨在研究哈夫曼编码的原理和实现方法，通过实验验证哈夫曼编码在数据压缩中的有效性，并分析其应用场景和优缺点。

2.实验原理2.1 哈夫曼编码哈夫曼编码是一种无损数据压缩算法，通过根据字符出现的频率构建一颗哈夫曼树，将频率较高的字符用较短的编码表示，频率较低的字符用较长的编码表示。

哈夫曼编码的编码表是唯一的，且能够实现前缀编码，即一个编码不是另一个编码的前缀。

2.2 构建哈夫曼树构建哈夫曼树的过程如下：1) 将每个字符及其频率作为一个节点，构建一个节点集合。

2) 每次从节点集合中选择出现频率最低的两个节点，构建一个新节点，并将这两个节点从集合中删除。

3) 将新节点加入节点集合。

4) 重复以上步骤，直到节点集合中只有一个节点，这个节点就是哈夫曼树的根节点。

2.3 编码过程根据哈夫曼树，对每个字符进行编码：1) 从根节点开始，根据左子树为0，右子树为1的规则，将编码依次加入编码表。

2) 对于每个字符，根据编码表获取其编码。

3) 将编码存储起来，得到最终的编码序列。

3.实验步骤3.1 数据读取与统计从输入文件中读取字符序列，并统计各个字符的频率。

3.2 构建哈夫曼树根据字符频率构建哈夫曼树。

3.3 构建编码表根据哈夫曼树，构建每个字符的编码表。

3.4 进行编码根据编码表，对输入的字符序列进行编码。

3.5 进行解码根据哈夫曼树，对编码后的序列进行解码。

4.实验结果与分析4.1 压缩率分析计算原始数据和压缩后数据的比值，分析压缩率。

4.2 编码效率分析测试编码过程所需时间，分析编码效率。

4.3 解码效率分析测试解码过程所需时间，分析解码效率。

4.4 应用场景分析分析哈夫曼编码在实际应用中的优势和适用场景。

5.结论通过本次实验，我们深入了解了哈夫曼编码的原理和实现方法，实践了哈夫曼编码的过程，并对其在数据压缩中的有效性进行了验证。

实验结果表明，哈夫曼编码能够实现较高的压缩率和较高的编解码效率。

【具体设计】之杨若古兰创作具体代码实现如下：#include<iostream>#include<fstream>#include<string>struct HuffmanNode //哈夫曼树的一个结点{int weight;int parent;int lchild,rchild;};class HuffmanTree //哈夫曼树{private:HuffmanNode *Node; //Node[]存放哈夫曼树char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放 int LeafNum; //哈夫曼树的叶子个数，也是源码个数public:HuffmanTree();~HuffmanTree();void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中. 让用户从两种建立哈夫曼树的方法当选择：1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，并将哈夫曼树写入文件hfmTree中.2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），对文件ToBeTran中的注释进行编码，并将码文写入文件CodeFile中.ToBeTran的内容可以用记事本等程序编辑发生.*/void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，得到的源文写入文件TextFile中，并同时输出到屏幕上.*/ void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/void PrintHuffmanTree(); /*将哈夫曼树以直观的方式（凹入暗示法，或广义表，或其他树形暗示法）显示在屏幕上，同时写入文件TreePrintFile中*/void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入暗示法显示哈夫曼树，由PrintHuffmanTree()调用*/};#include<string>#include<limits> //为使用整型最大值#include"HuffmanTree.h"using namespace std;//****************************************************** HuffmanTree::HuffmanTree(){Node=NULL;}//****************************************************** HuffmanTree::~HuffmanTree(){delete[]Node;}//****************************************************** void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";cin>>Choose;if(Choose=='2') {//键盘输入建立哈夫曼树CreateHuffmanTreeFromKeyboard();}//choose=='2'CreateHuffmanTreeFromFile();}}//****************************************************** void HuffmanTree::CreateHuffmanTreeFromKeyboard(){int Num;cout<<"\n请输入源码字符集个数：";cin>>Num;if (Num<=1){cout<<"没法建立少于2个叶子结点的哈夫曼树.\n\n"; return;}LeafNum=Num;Node=new HuffmanNode[2*Num-1];Info=new char[2*Num-1];for(int i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息cout<<"请输入第"<<i+1<<"个字符值";getchar();Info[i]=getchar(); //源文的字符存入字符数组Info[] getchar();cout<<"请输入该字符的权值或频度";cin>>Node[i].weight; //源文的字符权重存入Node[].weight Node[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;}for(i=Num;i<2*Num-1;i++){//轮回建立哈夫曼树内部结点int pos1=-1,pos2=-1;int max1=32767,max2=32767;for(int j=0;j<i;j++)//在根节点当选出权值最小的两个if(Node[j].parent==-1)//是否为根结点if(Node[j].weight<max1){max2=max1;max1=Node[j].weight;pos2=pos1;pos1=j;}elseif(Node[j].weight<max2){max2=Node[j].weight;pos2=j;}Node[pos1].parent=i;Node[pos2].parent=i;Node[i].lchild=pos1;Node[i].rchild=pos2;Node[i].parent=-1;Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //forcout<<"哈夫曼树已成功构造完成.\n";char ch;cout<<"是否要替换本来的哈夫曼树文件(Y/N):"; cin>>ch;if (ch!='y'&&ch!='Y') return;else{ofstream fop;fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件if(fop.fail()){cout<<"\n哈夫曼树文件打开失败，没法将哈夫曼树写入hfmTree.dat文件.\n";return;}fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数for(i=0;i<Num;i++){ //再写入源文字符集的所有字符（存储在Info[]中）fop.write((char*)&Info[i],sizeof(Info[i]));flush(cout);}for(i=0;i<2*Num-1;i++){ //最初写入哈夫曼树的各个结点（存储在Node[]中）fop.write((char*)&Node[i],sizeof(Node[i]));flush(cout);}fop.close(); //关闭文件cout<<"\n哈夫曼树已成功写入hfmTree.dat文件.\n";}}//****************************************************** void HuffmanTree::CreateHuffmanTreeFromFile(){ifstream fip;fip.open("hfmTree.dat",ios::binary|ios::in);if(fip.fail()){cout<<"哈夫曼树文件hfmTree.dat打开失败，没法建立哈夫曼树.\n";return;}fip.read((char*)&LeafNum,sizeof(LeafNum));if (LeafNum<=1){cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，没法建立哈夫曼树.\n";fip.close();return;}Info=new char[LeafNum];Node=new HuffmanNode[2*LeafNum-1];for(int i=0;i<LeafNum;i++)fip.read((char*)&Info[i],sizeof(Info[i]));for(i=0;i<2*LeafNum-1;i++)fip.read((char*)&Node[i],sizeof(Node[i]));fip.close();cout<<"哈夫曼树已成功构造完成.\n";}//****************************************************** void HuffmanTree::Encoder(){if(Node==NULL) CreateHuffmanTreeFromFile();if (LeafNum<=1){cout<<"内存无哈夫曼树.操纵撤消.\n\n";return;}}//ifchar *SourceText; //字符串数组，用于存放源文char Choose;cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";cin>>Choose;if(Choose=='1'){ifstream fip1("ToBeTran.txt");if(fip1.fail()){cout<<"源文文件打开失败!没法继续履行.\n";return;}char ch;int k=0;while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入kfip1.close();SourceText=new char[k+1]; //申请存放源文的字符数组空间ifstream fip2("ToBeTran.txt");//第二次读源文文件，把内容写入SourceText[]k=0;while(fip2.get(ch)) SourceText[k++]=ch;fip2.close();SourceText[k]='\0';cout<<"需编码的源文为：";cout<<SourceText<<endl;}else{ //从键盘输入源文string SourceBuff;cin.ignore();cout<<"请输入须要编码的源文(可输入任意长，按回车键结束):\n";getline(cin,SourceBuff,'\n');int k=0;while(SourceBuff[k]!='\0')k++;SourceText=new char[k+1];k=0;while(SourceBuff[k]!='\0'){SourceText[k]=SourceBuff[k];k++;}SourceText[k]='\0';cout<<"覆盖已有的编码原文件?（Y/N）";char ch;cin>>ch;if(ch=='y'||ch=='Y'){ofstream fip2;fip2.open("ToBeTran.txt");if(!fip2){cerr<<"文件打开失败！"<<endl;abort();}fip2<<SourceText<<endl;fip2.close();cout<<"需编码的源文已写入ToBeTran.txt中"<<endl;}}//开始编码ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件char *code;code=new char[LeafNum]; //存放一个源文字符的编码int k=0;while(SourceText[k]!='\0') //源文串中从第一个字符开始逐一编码{int star=0;char ch=SourceText[k];for(int i=0;i<LeafNum;i++)if(Info[i]==ch)//求出该文字所在的单元编号break;int j=i;while(Node[j].parent!=-1){j=Node[j].parent;if(Info[Node[j].lchild]==Info[i]) code[star++]='0';else code[star++]='1';i=j;}code[star]='\0';for(i=0;i<star/2;i++){int j=code[i];code[i]=code[star-i-1];code[star-i-1]=j;i=0; //将源文的当前字符的对应编码写入码文文件while(code[i]!='\0'){fop<<code[i];i++;}k++; //源文串中的字符后移一个}fop.close();cout<<"已完成编码，码文已写入文件CodeFile.dat中.\n\n"; }//****************************************************** void HuffmanTree::Decoder(){if(Node==NULL){CreateHuffmanTreeFromFile();if (LeafNum<=1){cout<<"内存无哈夫曼树.操纵撤消.\n\n";return;}//将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1("CodeFile.dat");if(fip1.fail()){cout<<"没有码文，没法译码.\n";return;}char* CodeStr;int k=0;char ch;while(fip1.get(ch)){k++;}fip1.close();CodeStr=new char[k+1];ifstream fip2("CodeFile.dat");k=0;while(fip2.get(ch)) CodeStr[k++]=ch;fip2.close();CodeStr[k]='\0';cout<<"经译码得到的源文为：";ofstream fop("TextFile.dat");int j=LeafNum*2-1-1; //j指向哈夫曼树的根int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子while(CodeStr[i]!='\0'){ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符if(CodeStr[i]=='0') j=Node[j].lchild;else j=Node[j].rchild;if(Node[j].rchild==-1){cout<<Info[j];fop<<Info[j];j=LeafNum*2-1-1;}i++;}fop.close();cout<<"\n译码成功且已存到文件TextFile.dat中.\n\n";}//****************************************************** void HuffmanTree::PrintCodeFile(){char ch;int i=1;ifstream fip("CodeFile.dat");ofstream fop("CodePrin.dat");if(fip.fail()){cout<<"没有码文文件，没法显示码文文件内容.\n"; return;}while(fip.get(ch)){cout<<ch;fop<<ch;if(i==50){cout<<endl;fop<<endl;i=0;}}cout<<endl;fop<<endl;fip.close();fop.close();}//****************************************************** void HuffmanTree::PrintHuffmanTree(){if(Node==NULL){CreateHuffmanTreeFromFile();if (LeafNum<=1){cout<<"内存无哈夫曼树.操纵撤消.\n\n";return;}}ofstream fop("TreePrint.dat",ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);}//****************************************************** void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer){for(int i=0;i<layer;i++) cout<<"___";cout<<Node[T].weight<<endl;if(Node[T].lchild!=-1)PrintHuffmanTree_aoru(Node[T].lchild,++layer);if(Node[T].rchild!=-1)PrintHuffmanTree_aoru(Node[T].rchild,layer--);}#include<string.h>#include<stdlib.h>using namespace std;int main(){HuffmanTree huftree;char Choose;while(1){cout<<"\n\n**********************欢迎使用哈夫曼编码/译码零碎***********************"<<endl;cout<<"您可以进行以下操纵:"<<endl;cout<<"1 建立哈夫曼树 3 译码(码文已在文件CodeFile中) 5 显示哈夫曼树"<<endl;cout<<"2 编码(源文已在文件ToBeTran中，或键盘输入) 4 显示码文 6 退出 "<<endl;cout<<"请选择一个操纵:";cin>>Choose;switch(Choose){case '1':huftree.CreateHuffmanTree();break;case '2':huftree.Encoder();break;case '3':huftree.Decoder();break;case '4':huftree.PrintCodeFile();break;case '5':huftree.PrintHuffmanTree();break;case '6':cout<<"\n*************************感谢使用本零碎!***********************\n\n";system("pause");return 0;}//switch}//while}//main【用户手册】进入哈弗曼树零碎，出现以下界面：1建立弗曼树2、编码（源文中读入，键盘输入）3、译码4、显示码文 5、显示哈弗曼树 6、退出用户根据该提示，选择前面数字，就能进入各个功能函数，实现函数功能.【运转结果】截图一：截图二：截图三：截图四：【心得体会】本实验是搜集相干材料，然后本人添加功能函数的代码实现的.是以，在完成未完成的功能函数之前还必必要仔细浏览所给出代码，全体观察各个部分之前的联系，搞清楚已给出和未完成的代码功能以后，才根据算法，设计出该功能的函数代码.在完成实验时，有发古代码也有纰漏的地方，如在源文件读入的时候，多出了一个值，得要添加下表减这个代码来去掉.还有就是在译码的时候，因为变量定义的混淆，在编译的时候通过，但履行时却出现料想不到的结果，在本人仔细观察、思考之前也还没找出错误的地方.后来通过请教老师，在和老师讨论检查以后才晓得了错误之所在，最初改正错误.实验成功完成.【参考文献】数据结构与算法（课本）C++说话基础。

数据结构课程设计实验报告哈夫曼树的应用计算机学院信管专业数据结构课程设计题目：哈夫曼树的应用班级：姓名：学号：同组人姓名：起迄日期：课程设计地点:指导教师：完成日期：2012年12月目录一、需求分析 (3)二、概要设计 (4)三、详细设计 (6)四、调试分析和测试结果 (7)五、心得体会和总结 (10)六、参考文献 (10)七、附录 (11)一、需求分析（一）实验要求要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。

这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。

问题是将输入的信息保存入文件和从文件输出。

这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。

综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。

（二）实验任务一个完整的系统应具有以下功能：功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。

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

功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。

（三）实验步骤分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：完成功能1；3）进一步要求：完成功能2和3。

有兴趣的同学可以自己扩充系统功能。

第1篇一、实验目的1. 理解哈夫曼树的基本概念和构造方法。

2. 掌握哈夫曼编码和译码的原理及实现过程。

3. 熟练运用哈夫曼树解决实际问题，提高数据压缩效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 构造哈夫曼树2. 哈夫曼编码3. 哈夫曼译码四、实验步骤1. 数据准备（1）创建一个包含字符及其权值的数组，例如：`{'a', 5, 'b', 9, 'c', 12, 'd', 13, 'e', 16, 'f', 45}`。

（2）根据数组内容，使用C++编写程序，实现以下功能：- 将数组元素插入到最小堆中。

- 构建哈夫曼树。

2. 哈夫曼编码（1）遍历哈夫曼树，记录每个字符的编码。

（2）根据编码规则，将字符和编码存储在映射表中。

（3）将映射表输出到文件中。

3. 哈夫曼译码（1）从文件中读取编码序列。

（2）根据哈夫曼树，逐个解码字符。

（3）将解码后的字符输出到文件中。

五、实验结果1. 哈夫曼树```45/ \16 29/ \ / \13 3 12 4/ \ / / \d c b a f```2. 哈夫曼编码```a: 0b: 100c: 101d: 110e: 111f: 1```3. 编码前后的数据```原始数据：abcdef编码后数据：0100110110111011```六、实验分析1. 哈夫曼树通过构建哈夫曼树，可以将权值较小的字符分配较短的编码，权值较大的字符分配较长的编码，从而提高数据压缩效率。

2. 哈夫曼编码哈夫曼编码是一种前缀编码，可以保证解码过程不会产生歧义。

3. 哈夫曼译码通过哈夫曼树，可以快速地将编码序列解码为原始数据。

七、实验总结1. 通过本次实验，掌握了哈夫曼树的基本概念、构造方法、编码和译码原理。

《数据结构》实验报告利用Huffman编码对文件进行压缩解压学生:XXX学号:XXXXXXXX联系:XXXXXX@(一)基本信息1.实验题目利用Huffman编码对文件进行压缩解压2.完成人（姓名、学号）姓名：XXX 学号：XXXXXXXX3.报告日期2007年12月12日星期二(二)实习内容简要描述1.实习目标学会对树的基本操作学会对文件进行操作利用Huffman编码对文件压缩解压2.实习要求实现最小堆模板类利用最小堆构建Huffman树实现Huffman编码和解码根据用户从键盘输入的报文文本,输出各字符的Huffman编码以及报文的编码根据用户从键盘输入一串报文文本，输出各字符的Huffman编码输出报文的Huffman编码及长度根据输入的Huffman编码，解码输出利用Huffman编码和解码对二进制文件的压缩和解压(三)报告主要内容1.设计思路开发环境：Microsoft Visual C++ 2005设计思路：1.设计Pack类储存字符的权值2.设计MinHeap模板类构建最小堆3.设计ExtBinTree模板类为带权二叉树4.设计Compress模板类以实现文件的压缩解压2.主要数据结构1.MinHeap.h: 头文件,包含MinHeap模板类的类界面以及定义;2.HuffmanTree.h:头文件,包含ExtBinTree模板类以及Compress模板类的类的的类界面以及定义3.main.cpp:调用上述头文件实现相关操作3.主要代码结构主要代码结构为见附件中各文件的代码注释4.主要代码段分析主要代码段分析，见附件中的代码注释(四)实习结果1.基本数据源程序代码行数：约800行完成该实习投入的时间：二十四小时(不包括写实验报告的时间)与其他同学讨论交流情况:感谢刘畅同学对程序的测试2.测试数据设计1.对屏幕输入字符进行Huffman编码2.根据Huffman树非唯一性,虽然和课件上有些许不同,但是还是正确的3.输入字符串:CASTCASTSATATATASA4.输出编码:A:0 C:110 S:111 T:105.输入霍夫曼编码:01110101101106.输出译码:ASATCC7.8.对”实验05.PPT”的压缩操作9.使用0秒(不足一秒按0秒计算),压缩率为56.1755%10.对”实验05.ppt.hfm”(即刚才生成的压缩文件)的解压操作11.使用0秒(不足一秒按0秒计算),解压后文件无异常12.对一个18M的EXE安装包前后进行压缩和解压操作,分别用时10秒和9秒3.测试结果分析A)程序运行的系统资源配置操作系统：Microsoft Windows XP Professional SP2CPU: AMD Athlon 3600+ 2.0GRAM: 1024M DDRII开发环境：Microsoft Visual C++ 2005B)对TXT文档进行压缩和解压后,通过WinMerge检验和原文件无差异C)对MP3和EXE文件压缩和解压后仍能正常使用D)对于中文名字和带有空格的路径均能正确无误识别E)文件名只能小于16个字符(包括后缀名),否则解压会出错(只预留了16个字节用于储存文件名)F)相对于不用文件块读写的程序,效率提高了三倍以上G)具有动态进度条,可以显示当前压缩和解压的进度百分比(当然消耗了一些系统资源)H)出错处理不够充分,特别是cin部分,如果误输入可能会造成死循环(五)实习体会1.实习过程中遇到问题及解决过程A)一开始时候的程序运行很慢,,压缩一个4M左右的文件需要七八秒,后来改用文件块缓存字节来读写后,压缩一个4M的文件只需要两秒左右的时间.本来是只想写一个进度条而已的,后来发现如果只读一个字节就判断一次进度条的话会很消耗系统资源,后来干脆麻烦点用文件块来缓存.不过至于一次缓存多少字节才能达到最好的效果还未知,现在设置的是一次缓存40KB 的数据B)本来一个一个字节读的时候对最后一个字节的操作基本没费什么劲,但是在文件块读写的时候就不是那么清晰明了了,后来经过仔细Debug,才找到错误的所在.许多问题都是这样C)对于中文名和带空格路径,用C++的fstream就不支持,但是C中的FILE*就支持,不知道为什么.还有C++中的fstream的成员函数read返回值很奇怪,不知道如何获取成功读入的项数.改用C中的FILE*文件指针后就解决掉了D)由于这次实验的各个步骤是一环套一环的,在哪里出错很难找得出来,所以这次实验调试消耗的时间特别多.最郁闷的一次错误是发现在取得字符C的第N位函数中,居然把0x40写成了0x30.有时候文件解压出来不对,但是又不清楚是压缩时候错了,还是解压时候错了,然后就要两个函数都要检查一遍.2. 实习体会和收获这次实验最大的特点在于难找错,很锻炼自己的Debug能力(六)自评成绩分数：90 //功能做得较齐全,程序的效率也不错(七)参考文献MSDN还有某网站上树的遍历算法(八)源程序见同一文件夹内.。

【详细设计】具体代码实现如下://HaffmanTree、h#include<iostream>#include<fstream>#include<string>struct HuffmanNode //哈夫曼树的一个结点{int weight;int parent;int lchild,rchild;};class HuffmanTree //哈夫曼树{private:HuffmanNode *Node; //Node[]存放哈夫曼树char *Info; //Info[]存放源文用到的字符——源码,如'a','b','c','d','e',此内容可以放入结点中,不单独设数组存放int LeafNum; //哈夫曼树的叶子个数,也就是源码个数public:HuffmanTree();~HuffmanTree();void CreateHuffmanTree(); /*在内存中建立哈夫曼树,存放在Node[]中。

让用户从两种建立哈夫曼树的方法中选择:1、从键盘读入源码字符集个数,每个字符,与每个字符的权重,建立哈夫曼树,并将哈夫曼树写入文件hfmTree中。

2、从文件hfmTree中读入哈夫曼树信息,建立哈夫曼树*/void CreateHuffmanTreeFromKeyboard();void CreateHuffmanTreeFromFile();void Encoder(); /*使用建立好的哈夫曼树(如果不在内存,则从文件hfmTree中读入并建立内存里的哈夫曼树),对文件ToBeTran中的正文进行编码,并将码文写入文件CodeFile中。

ToBeTran的内容可以用记事本等程序编辑产生。

*/void Decoder(); /*待译码的码文存放在文件CodeFile中,使用建立好的哈夫曼树(如果不在内存,则从文件hfmTree中读入并建立内存里的哈夫曼树)将码文译码,得到的源文写入文件TextFile中,并同时输出到屏幕上。

《用哈夫曼编码实现文件压缩》实验报告课程名称《数据结构B》实验学期2014至2014 学年第 1 学期学生所在系部计算机系年级2010 专业班级网络B10-3学生姓名学号任课教师实验成绩用哈夫曼编码实现文件压缩1、了解文件的概念。

2、掌握线性链表的插入、删除等算法。

3、掌握Huffman树的概念及构造方法。

4、掌握二叉树的存储结构及遍历算法。

5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。

微型计算机、Windows 系列操作系统、Visual C++6.0软件根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。

在文件存储时，一个整型的字符要占用一个字节的空间，对于某些不常用的字符这样会造成空间的浪费，但如果用位来存储数据，可以将字符重新编码，使那些常用的字符存储空间相对短的，不常用的字符相对长些，可以节约空间。

哈夫曼编码即是这样一个过程。

用哈夫曼编码进行文件压缩，首先应对所用的字符进行哈夫曼变编码，在这之前应先对所用字符进行权值统计。

在编码哈夫曼树的时候，选取两个权值最小的依次构造哈夫曼树，进行哈夫曼编码时，使哈夫曼树的左孩子上的分支编码为0，右孩子上的分支编码为1。

然后对文件进行压缩。

压缩过程用到了文件的读写。

头文件的构造：头文件首先应用宏定义，对文件要用到的数据进行定义，然后定义了结构体类型，将所要到字符的权值，数据，双亲编号与孩子编号放在结构体中，使程序间的关系变得紧密。

定义第二个结构体，其中包含结构体数组和树根的编号。

定义指针，使其指向第二个结构体。

接着类型定义，定义了结构体，其中包含字符原码值，哈夫曼编码值和哈夫曼编码值的长度，并将其取名为HaffCode。

将程序所用到的函数包含在头文件里。

哈夫曼树的构造：在程序开头先对程序所用到的变量进行定义，包括指向结构体的指针，整型变量，权值最小的结点的编号，第二小的结点的编号，权值最小的结点的权值，第二小的结点的权值。

数据构造试验汇报――试验五简朴哈夫曼编/译码旳设计与实现本试验旳目旳是通过对简朴哈夫曼编/译码系统旳设计与实现来纯熟掌握树型构造在实际问题中旳应用。

此试验可以作为综合试验，阶段性试验时可以选择其中旳几种功能来设计和实现。

一、【问题描述】运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本。

不过，这规定在发送端通过一种编码系统看待传数据预先编码，在接受端将传来旳数据进行译码，此试验即设计这样旳一种简朴编/码系统。

系统应当具有如下旳几种功能：1、接受原始数据。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文献nodedata.dat中。

2、编码。

运用已建好旳哈夫曼树（如不在内存，则从文献nodedata.dat中读入），对文献中旳正文进行编码，然后将成果存入文献code.dat中。

3、译码。

运用已建好旳哈夫曼树将文献code.dat中旳代码进行译码，成果存入文献textfile.dat中。

4、打印编码规则。

即字符与编码旳一一对应关系。

二、【数据构造设计】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序列，因此先得到旳分支代码为所求编码旳低位码，后得到旳分支代码位所求编码旳高位码，因此设计如下数据类型：#define MAXBIT 10typedef struct{int bit[MAXBIT]；int start；}HcodeType；3、文献nodedata.dat、code.dat和textfile.dat。

哈夫曼树实验报告计算机科学与技术学院数据结构实验报告班级2０１４级计算机1班学号２０１4４１38021 姓名张建华成绩实验项目简单哈夫曼编/译码得设计与实现实验日期２016、1、5一、实验目得本实验得目得就是进一步理解哈夫曼树得逻辑结构与存储结构，进一步提高使用理论知识指导解决实际问题得能力。

二、实验问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间,降低传输成本。

但就是，这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来得数据进行译码,此实验即设计这样得一个简单编/码系统。

系统应该具有如下得几个功能：1、接收原始数据。

从终端读入字符集大小n,以及n个字符与n个权值，建立哈夫曼树,并将它存于文件hfm ｔree、dａt中。

２、编码。

利用已建好得哈夫曼树（如不在内存,则从文件hfmtree、daｔ中读入），对文件中得正文进行编码,然后将结果存入文件code中。

３、译码。

利用已建好得哈夫曼树将文件ｃoｄe中得代码进行译码,结果存入文件ｔeｘt中。

4、打印编码规则。

即字符与编码得一一对应关系。

５、打印哈夫曼树,将已在内存中得哈夫曼树以直观得方式显示在终端上。

三、实验步骤１、实验问题分析１、构造哈夫曼树时使用静态链表作为哈夫曼树得存储。

在构造哈夫曼树时,设计一个结构体数组ＨuｆfNode保存哈夫曼树中各结点得信息,根据二叉树得性质可知,具有ｎ个叶子结点得哈夫曼树共有2n-1个结点,所以数组HuffNｏdｅ得大小设置为２n －1,描述结点得数据类型为:Typedef strcｕt{Int ｗeight；/*结点权值＊／Ｉnｔ parent;Iｎｔ lchild;Ｉnt ｒchilｄ；}HNodｅＴｙpe;2、求哈夫曼编码时使用一维结构数组HｕｆfCode作为哈夫曼编码信息得存储。

求哈夫曼编码,实质上就就是在已建立得哈夫曼树中,从叶子结点开始,沿结点得双亲链域回退到根结点，没回退一步,就走过了哈夫曼树得一个分支,从而得到一位哈夫曼码值,由于一个字符得哈夫曼编码就是从根结点到相应叶子结点所经过得路径上各分支所组成得０、1序列,因此先得到得分支代码为所求编码得低位码,后得到得分支代码位所求编码得高位码,所以设计如下数据类型:#ｄefiｎe ＭAＸBIT 10Tｙpedef struct{Int bit[MAXBＩT];Ｉnｔｓtart;｝ＨCoｄｅType;3、文件ｈfｍtree、dat、code与text。

Huffman编码及译码实验报告姜流PB12210218问题的描述：对传输的电文统计出现的字符及次数并进行Huffman编码，生成Huffman树，编码形式为1,0两种数字，打印出比特流，再将比特流译码成字符。

问题的输入输出：1.用户从键盘输入任意长度的任意字符，打印出出现的不同字符及次数；2.根据不同字符的权重生成Huffmam树并先序打印出来；3.根据Huffman树进行编码，打印出来比特流；4.将比特流转换成电文字符打印出来；算法的描述：1.统计字符功能的算法：用p指向输入的字符串，另开两个数组，一个是ch[]，用来存放不同的字符，另一个是k[]用来存放各个不同字符的次数，对输入的字符串逐个字符依次比较，就可以完成字符统计功能。

2.生成Huffamn树算法：采用经典的生成算法，每次找两个权重最小的节点合并成一个节点，一直到最后没有节点，本次实验采用左孩子权重小于右孩子的规则进行生成。

3.Huffman编码算法：先序遍历生成的Huffman树，每次向左拐就将1压栈，向右拐就将0压栈，直到访问到叶子，将栈里的1，0字符copy到相应字符的编码，就然后进行出栈操作，直到访问完全部的节点。

4.Hufman译码算法：对输入的比特流进行逐个访问，若为1，在Huffman树上左拐，若为0，在Huffman树上右拐，一直到叶子，则叶子上的字符就是比特流对应的字符，然后再从根节点开始译码，直到比特流结束，即可译出所有的电文打印。

数据结构的描述：1.存放编码的栈：typedef struct{ char *base;char *top;int stacksize;}SqStack;2.Huffman树的节点：typedef struct{int weight,parent,lchild,rchild;}HTNode;3.Huffman树结构体：typedef struct{HTNode *Htree;int root;}HuffmanTree;5.双指针类型：存放每个字符对应编码#define HuffmanCode char **HuffmanCode HC=NULL;//初始时为空程序结构的描述：Status EmptyStack(SqStack s)；Status Increment(SqStack &s)；void InitStack(SqStack &s)；void push(SqStack &s,char e)；void pop(SqStack &s,char &e)；Status Getop(SqStack &s,char &e)；int StackLength(SqStack S)；//以上关于栈的通用函数void select(HTNode *HT,int k,int &s)；void CreateHuffman(HuffmanTree &T,int *w,int n)；void Coding(HuffmanTree T,int i,SqStack &S,char **HC)；void HuffmanCoding(HuffmanTree T,HuffmanCode &HC,int n)；void Decoding(HuffmanTree T,char *s)；void Print(HuffmanTree T)；int compare(char ch[],char cha,int &n)；void stat(char *s,char ch[],int k[],int &count)；//完成各功能的函数main{ //主函数中对各个子函数调用顺序stat(s,ch,k,count);//以上为字符统计功能CreateHuffman(T,w,n);Print(T);//以上为构造HuffmanTree,并打印HuffmanCoding(T,HC,n);//以上为将每个字符翻译成比特文p=s;//puts(s);while(*p){i=compare(ch,*p,n);//printf("%d\n",n);printf("%s",HC[n+1]);p++;}printf("\n");//以上为将电文翻译为比特文printf("input the bits\n");gets(s1);Decoding(T,s1);//译码}调试分析：1.字符统计功能：结果是对的2.生成Huffman树并打印：结果是与输入相符合的3.将各个字符编码,成为比特流：结果很正确4.将比特流译码成为电文：结果输入的字符时相同的调试中遇到的问题：在创建Huffman树时，一开始是用scanf，但是调试的时候却总是不正确，查阅scanf函数原型后发现scanf在读字符时把空格也认为是有效字符，因此空格不能作为间隔符，建议用getchar()，gets()等函数。