哈夫曼编码译码系统实验报告-数据结构课程设计

v .. . ..安徽大学数据结构课程设计报告项目名称：哈弗曼编/译码系统的设计与实现姓名：鉏飞祥学号：E21414018专业：软件工程完成日期2016/7/4计算机科学与技术学院1 .需求分析1.1问题描述•问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

1.2基本要求(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能。

1.基本要求（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；2. 概要设计说明本程序中用到的所有抽象数据类型的定义。

主程序的流程以及各程序模块之间的层次(调用)关系。

(1)数据结构哈夫曼树的节点struct huff{int weight;int parent;int l;int r;};哈夫曼编码的存储struct huff *hufftree;(2)程序模块选择1到i-1中parent为0且权值最小的两个下标void Select(struct huff *HT, int n, int &s1, int &s2)构建哈夫曼树：void huffmancoding(struct huff *ht,int *w,int n)对原文进行编码：void code(char *c)根据报文找到原文：void decoding(char *zifu)3. 详细设计核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：根据每个字符权值不同，根据最优二叉树的构建方法，递归生成哈夫曼树，并且用数组存放哈夫曼树。

实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的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这就走向该结点的右结点，重复上面步骤。

《数据结构》课程设计实验报告题目哈夫曼编码/译码器学院数理与信息学院专业计算机科学与技术班级计科132学生姓名刘海澍 5周弘杰8徐铭瑶 3指导教师编写日期数据结构课程设计目录1 问题描述.................................................................错误!未定义书签。

2 问题分析.................................................................错误!未定义书签。

3 算法设计 (2)3.1抽象数据类型定义 (2)3.2模块划分 (3)4 详细设计 (4)4.1数据类型的定义 (4)4.2主要模块的算法描述 (4)4.3 流程图 (6)5 测试分析 (9)6 课程设计总结 (10)7 成员分工 (10)参考文献 (11)附录（源程序清单） (12)1.问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

1) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；2) 编码：利用建好的哈夫曼树生成哈夫曼编码；3) 输出编码；4）显示哈夫曼树；5）界面设计的优化；6) 设字符集及频度如下表：字符空格 A B C D E F频度4 9 23 2 17 15字符G H I J K频度1 2 3 3 42.问题分析（1）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht[60]存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cd[start]~cd[n]存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd[30]的数组用于存放当前叶子结点ht[i]的哈夫曼编码。

数据结构设计性实验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)第二章设计要求 (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。

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX系别：XXX专业：XXX班级：XXX学号：XXX指导教师：XXX XXX2012年6 月21日xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx学号xxx 姓名xxx主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。

对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。

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

（3）P：打印代码文件（Print）。

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

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

（4）T：打印哈夫曼树（Tree Printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。

3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012年6月21 日指导教师签名：课程负责人签名：2012年 6月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。

【仔细安排】之阳早格格创做简曲代码真止如下：#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中，并同时输出到屏幕上。

摘要；哈夫曼编码是根据字符的使用率的高低对字符进行不等长的编码，从而使使用率高的字符占用较少的空间，从而在传输的过程中大大提高了数据的空间传输效率。

本设计采用二叉链表的存储结构，建立哈夫曼树；用递归调用的方式对哈夫曼树的节点进行编码，生成与字符对应的哈夫曼编码。

本设计完全采用C++语言进行编程，并在XCode 6编译器上调试运行通过。

本程序使用中文界面，并有相应的提示信息，便于操作和程序运行。

关键词：哈夫曼树;哈夫曼编码;递归调用;二叉链表AbstractHuffman coding is based on the level of usage of characters ranging from long coding, so that high usage rate of the characters occupy less storage space , in the course of transmission has greatly enhanced the efficiency of data transmission space. This design build the Huffman tree by using Binary Tree storage structure, encoded Huffman tree nodes by recursive calling, and the characters generate the corresponding Huffman coding. The procedure completely write with C++ language and has Chinese explanatory note. What’s more, i t was debugged in XCode 6 debugger and run well. The whole procedure, with Chinese interface and the corresponding tips ,is convenient to run and easy to be operated.Keywords: Huffman Tree; Huffman code; Recursive call; Binary List目录摘要..................................................................................................................... 错误!未定义书签。

课程设计任务书课程名称数据结构课程设计课题赫夫曼编译码器专业班级网络工程***学生姓名***学号**指导老师审批任务书下达日期：2011 年6 月26 日任务完成日期：2011 年7 月15 日一、设计内容1）问题描述对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。

2）基本要求a.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。

b.编码，利用建好的huffman树生成huffman编码；c.输出编码；d.译码功能；二．设计要求：课程设计报告1)需求分析a.程序的功能。

1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。

2.编码，利用建好的huffman树生成huffman编码；3.输出编码；4.译码功能；b.输入输出的要求。

2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

i.void main()ii.void tohuffmancode(int n)//编码部分iii.void decode(char ch[],huftree tree[],int n)//译码iv.void huffman(huftree tree[],int *w,int n) //生成huffman树v.void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点vi.void huffmancode(huftree tree[],char code[],int n)//输出huffman编码其流程图如下：主函数main 调用其他函数：tohuffmancode(int n)decode(char ch[],huftree tree[],int n)huffman(huftree tree[],int *w,int n)select(huftree tree[],int k)huffmancode(huftree tree[],char code[],int n) 其主流程图如下：(3)主要模块程序流程图下面介绍三个主要的程序模块流程图：①函数流程图：流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。