数据结构(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。

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