下载文档原格式
一、课题名称：赫夫曼编码的应用二、课题来源：课程组自拟三、课题类型：综合型四、目的意义：1.学会编写实现树的各种操作的算法；2.掌握树的定义、存储结构；3.掌握哈夫曼树的建立和实现哈夫曼编码，解码及译码。
五、基本要求：对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。
(1)根据输入的一串电文字符，建立赫夫曼树，并输出显示赫夫曼树。
(2)对输入的一串电文字符实现赫夫曼编码，为每个字符生成它们的编码。
(3)实现赫夫曼编码的解码。
六、运行环境使用《数据结构》（严蔚敏，吴伟民，1997，C语言版）中给出的算法，将二叉树存放在连续空间里（静态链表），空间的每个结点内仍有左子树、右子树、双亲等指针。
使用VC++6.0软件实现。
七.课程设计步骤简介1 I：初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。
2 E：编码（Encoding）。
利用已建好的哈夫曼树对输入的字符进行编码。
3 D：译码（Decoding）。
利用已建好的哈夫曼树对输入的字符进行译码。
编码算法：（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值{w1,w2,……，wN}构成n棵二叉树的集合F={T1,T2,……，Tn}把它们保存到结构体数组HT『n』中,其中{Ti是按它们的ASCⅡ码值先后排序。
其中每棵二叉树Ti 中只有一个带权为Wi 的根结点的权值为其左、右子树上根结点的权值之和。
（2）在HT 『1..i 』中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。
. 译码算法：译码的过程是分解电文中字符串，从根出发，按字符'0',或'1'确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。
一、实验目的1. 理解霍夫曼编码的基本原理和算法流程。
2. 掌握霍夫曼编码的构建过程和编码方法。
3. 通过实验验证霍夫曼编码在数据压缩方面的效果。
4. 提高编程能力和数据结构应用能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理霍夫曼编码是一种基于字符出现频率进行编码的数据压缩方法。
其基本原理如下：1. 对字符进行统计，得到每个字符出现的频率。
2. 根据频率对字符进行排序，频率高的字符排在前面。
3. 构建霍夫曼树，将频率高的字符放在树的左侧，频率低的字符放在树的右侧。
4. 从树根到叶子节点，为每个字符分配一个二进制编码，频率高的字符用较短的编码表示，频率低的字符用较长的编码表示。
四、实验步骤1. 定义一个结构体HuffmanNode，用于存储字符及其频率。
2. 实现一个函数用于统计字符频率。
3. 实现一个函数用于构建霍夫曼树。
4. 实现一个函数用于生成霍夫曼编码。
5. 实现一个函数用于解码霍夫曼编码。
6. 编写主函数，进行实验验证。
五、实验过程1. 定义结构体HuffmanNode，用于存储字符及其频率。
```cppstruct HuffmanNode {char ch;int weight;HuffmanNode lchild, rchild;};```2. 实现一个函数用于统计字符频率。
```cppvoid StatFrequency(char str, int freq) {int length = strlen(str);for (int i = 0; i < 256; ++i) {freq[i] = 0;}for (int i = 0; i < length; ++i) {freq[(int)str[i]]++;}}```3. 实现一个函数用于构建霍夫曼树。
```cppHuffmanNode CreateHuffmanTree(int freq, int length) {HuffmanNode nodes = new HuffmanNode[length + 1];for (int i = 0; i < length; ++i) {nodes[i].ch = 'a' + i;nodes[i].weight = freq[i];nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = length; i < length + 1; ++i) {nodes[i].ch = '\0';nodes[i].weight = 0;nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = 0; i < length - 1; ++i) {HuffmanNode minNode1 = &nodes[0];HuffmanNode minNode2 = &nodes[1];for (int j = 0; j < length + 1; ++j) {if (nodes[j].weight < minNode1->weight) {minNode2 = minNode1;minNode1 = &nodes[j];} else if (nodes[j].weight < minNode2->weight && nodes[j].weight > minNode1->weight) {minNode2 = &nodes[j];}}nodes[i].weight = minNode1->weight + minNode2->weight;nodes[i].lchild = minNode1;nodes[i].rchild = minNode2;minNode1->parent = &nodes[i];minNode2->parent = &nodes[i];}return &nodes[length - 1];}```4. 实现一个函数用于生成霍夫曼编码。
实验报告课程名称：数据结构实验名称：赫夫曼编码及应用院（系）：计算机与通信工程学院专业班级：计算机科学与技术姓名：学号：指导教师：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个字符。
解码后的文本与原始文本完全一致，验证了哈夫曼编码的正确性。
五、讨论与总结哈夫曼编码作为一种高效的信息压缩算法，具有广泛的应用前景。
通过将出现频率较高的字符用较短的编码表示，哈夫曼编码可以在一定程度上减小信息的存储和传输成本。
然而，哈夫曼编码也存在一些局限性，例如对于出现频率相近的字符，编码长度可能会相差较大。
实验四哈夫曼树编码一、实验目的1、掌握哈夫曼树的一般算法；2、掌握用哈夫曼树对字符串进行编码；3、掌握通过哈夫曼树对字符编码进行译码得过程。
二、实验基本要求1、设计数据结构；2、设计编码算法；3、分析时间复杂度和空间复杂度三、程序实现此程序中包含六个函数：Select（）、HuffmanTree（）、BianMa（）、BianMa2（）、YiMa（）、Sum（），其功能及实现过程如下：#include <iostream.h>struct element//哈夫曼树结点类型{int weight;int lchild,rchild,parent;};struct Char//字符编码表信息{char node;int weight;char code[20];};void Select(element hT[],int &i1,int &i2,int k)//在hT[]中查找最小值及次小值{int min1=9999,min2=9999;i1=i2=0;for(int i=0;i<k;i++)if(hT[i].parent==-1)if(hT[i].weight<min1){min2=min1;i2=i1;min1=hT[i].weight;i1=i;}else if(hT[i].weight<min2){min2=hT[i].weight;i2=i;}}void HuffmanTree(element huffTree[],Char zifuma[],int n) //构建哈夫曼树{int i,k,i1,i2;for(i=0;i<2*n-1;i++) //初始化{huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(i=0;i<n;i++) //构造n棵只含有根结点的二叉树huffTree[i].weight=zifuma[i].weight;for(k=n;k<2*n-1;k++) //n-1次合并{Select(huffTree,i1,i2,k); //在huffTree中找权值最小的两个结点i1和i2huffTree[i1].parent=k; //将i1和i2合并，则i1和i2的双亲是khuffTree[i2].parent=k;huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}}void BianMa(element huffTree[],Char zifuma[],int n)//根据哈夫曼树编码{int i,m,k,j,l;char temp[20];if(n==1){ zifuma[0].code[0]='0';zifuma[0].code[1]=0;}else {for(i=0;i<n;i++){j=0;k=huffTree[i].parent;l=i;while(k!=-1){if(huffTree[k].lchild==l)temp[j++]='0';else temp[j++]='1';l=k;k=huffTree[k].parent;}k=j-1;for(m=0;m<j;m++)zifuma[i].code[m]=temp[k--];zifuma[i].code[m]=0;}}void BianMa2(Char zifuma[],char zifu[],char bianma[],int n)//根据编码表对字符串编码{int i,j,k,m;i=k=0;while(zifu[i]){for(j=0;j<n;j++)if(zifu[i]==zifuma[j].node){m=0;while(zifuma[j].code[m])bianma[k++]=zifuma[j].code[m++];}i++;}bianma[k]=0;}void YiMa(element huffTree[],Char zifuma[],char bianma[],char yima[],int n)//根据编号的码元译成字符串{int i,j,k;i=j=0;if(n==1)while(bianma[i++])yima[j++]=zifuma[0].node;else{while(bianma[i]){k=2*(n-1);while(!(huffTree[k].lchild==-1&&huffTree[k].rchild==-1))if(bianma[i++]=='0')k=huffTree[k].lchild;elsek=huffTree[k].rchild;yima[j++]=zifuma[k].node;}}yima[j]=0;}void Sum(char zifu[],Char bianma[],int &n)//计算字符串中字符种类的个数及其出现次数{i=j=0;while(zifu[i]){for(int k=0;k<j;k++)if(bianma[k].node==zifu[i]){bianma[k].weight++;break;}if(k==j){bianma[j].node=zifu[i];bianma[j++].weight=1;}i++;}n=j;}void main(){int n,i;char a[50],b[200],c[50];element huffTree[100];Char w[50];cout<<"请输入需要编码的字符串:\n";cin.getline(a,49);Sum(a,w,n);cout<<"该字符串中共有"<<n<<"类字符。
计算机学院信管专业数据结构课程设计题目：哈夫曼树的应用班级：姓名：学号：同组人姓名：起迄日期：课程设计地点:指导教师：完成日期：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）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4) 要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
(此文档为word格式，下载后您可任意编辑修改！) +数据结构课程设计题目：赫夫曼编码院、系：计算机科学与工程学院学科专业：计算机科学与技术学生：高经典学号：指导教师：梁晨2010年12月22日目录1课程设计的题目-----02课程设计的目的（设计要解决的问题）3概要设计（函数划分、总体设计）----14详细设计（算法、流程图、程序）-----25调试结果--6课程设计总结---- -337心得体会二课程设计的目的<1>巩固构造赫夫曼树的算法。
<2>设计实验用程序实现赫夫曼树的构造。
<3>熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。
三概要设计（函数划分、总体设计）<一>总体设计（1）输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。
（2）定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。
（3）开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把‚0‛接进链表是右孩子的把‚1‛接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。
（4）从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。
（5）用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告1·实验目的1·1 理解哈夫曼编码的基本原理1·2 掌握哈夫曼编码的算法实现方式1·3 熟悉哈夫曼编码在数据压缩中的应用2·实验背景2·1 哈夫曼编码的概念和作用2·2 哈夫曼编码的原理和算法2·3 哈夫曼编码在数据压缩中的应用3·实验环境3·1 硬件环境：计算机、CPU、内存等3·2 软件环境：编程语言、编译器等4·实验过程4·1 构建哈夫曼树4·1·1 哈夫曼树的构建原理4·1·2 哈夫曼树的构建算法4·2 哈夫曼编码4·2·1 哈夫曼编码的原理4·2·2 哈夫曼编码的算法4·3 实现数据压缩4·3·1 数据压缩的概念和作用4·3·2 哈夫曼编码在数据压缩中的应用方法5·实验结果5·1 构建的哈夫曼树示例图5·2 哈夫曼编码表5·3 数据压缩前后的文件大小对比5·4 数据解压缩的正确性验证6·实验分析6·1 哈夫曼编码的优点和应用场景分析6·2 数据压缩效果的评估和对比分析6·3 实验中遇到的问题和解决方法7·实验总结7·1 实验所获得的成果和收获7·2 实验中存在的不足和改进方向7·3 实验对于数据结构学习的启示和意义附件列表：1·实验所用的源代码文件2·实验中用到的测试数据文件注释：1·哈夫曼编码：一种用于数据压缩的编码方法，根据字符出现频率构建树形结构，实现高频字符用较短编码表示，低频字符用较长编码表示。
2·哈夫曼树：由哈夫曼编码算法构建的一种特殊的二叉树，用于表示字符编码的结构。
数据结构试验报告霍夫曼编码（DOC X页）数据结构实验报告(三)学院自动化学院学号姓名日期 2014-12-09实验目的1、掌握哈夫曼编码原理;2、熟练掌握哈夫曼树的生成方法;3、理解数据编码压缩和译码输出编码的实现;4、掌握二叉树的基本3操作。
实验内容利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(解码)。
对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼编/译码系统。
实验要求1) 初始化(Initialzation)。
利用下表给出的字符集和频度的=;实际统计数据建立哈夫曼树，并将它存于文件hfmTree中;字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 1547 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 12) 编码(EnCoding)。
利用已建好的哈夫曼树(若不在内存中，则从文件hfmTree中读入)，对以下报文进行编码，结果存入文件CodeFile中;报文内容:THIS PROGRAM IS MY FAVORITE3) 译码(Decoding)。
利用已建好的哈夫曼树，对文件CodeFile中编码后的报文进行解码，结果存入文件Textfile中;4) 输出(Output)。
输出字符集中每个字符的哈夫曼编码;输出原始报文，及其编码文件CodeFile和解码文件Textfile的内容。
扩展要求:将2)的编码结果以二进制形式存入CodeFile中，输出原始报文长度和编码后的报文长度。
1 需求分析(1) 将实验要求中的表格写在文件“HfmTree.txt”中，程序初始化时从该文件中读取字符及其频度，并据此建立Hfm树，生成编码表，打印出编码表; (2) 编码:用上一步生成的编码表，对报文进行编码，考虑到数据压缩性，这一步将编码结果以二进制文件进行存储，文件名为CodeFile; (3) 解码:从文件CodeFile中读入编码后的报文，利用建立好的Hfm树对其进行一一解码，输出解码结果，同时将结果存入Textfile.txt中; 2 概要设计因本次实验涉及许多字符串的操作，文件读写，并且除了霍夫曼树外，还用到了许多其他数据结构，而本次实验重点在霍夫曼树上，为了省去编写其他数据结构的时间，本次实验选用了C#语言和 .NetFrameWork 4.0来实现。
数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告一、实验背景1：引言在日常生活中，信息传输已经成为了一个非常重要的环节。
通过对信息进行编码，可以有效地减少信息传输的开销和存储空间。
哈夫曼编码是一种常见的无损数据压缩方法，广泛应用于图像、音频和视频等领域。
本实验旨在通过实现哈夫曼编码算法，深入理解其工作原理，并对其性能进行评估。
2：实验目的本实验旨在：a：了解哈夫曼编码算法的基本原理；b：实现哈夫曼编码算法，并将其应用于对文本进行压缩；c：评估哈夫曼编码算法在不同文本数据上的性能。
二、实验内容1：哈夫曼编码原理介绍2：哈夫曼编码的实现思路a：构建哈夫曼树b：哈夫曼编码表c：对文本进行编码和解码3：实验环境介绍a：硬件环境b：软件环境4：实验步骤详解a：构建哈夫曼树的实现方法b：哈夫曼编码表的实现方法c：文本编码和解码的实现方法5：实验数据与结果分析a：不同文本数据的压缩结果对比 b：压缩性能的评估指标6：实验心得与建议a：实验过程中遇到的问题b：改进与优化方向三、实验结果与分析1：实验数据a：不同文本数据的大小与内容b：压缩率等性能指标数据2：实验结果分析a：不同文本数据对压缩效果的影响b：压缩率与文本数据的关系c：哈夫曼编码的运行时间分析四、结论根据实验结果和分析，可以得出以下结论：1：哈夫曼编码算法能够有效地减少文本数据的存储空间。
2：不同文本数据的压缩率存在差异，与文本的特性有关。
3：哈夫曼编码算法的运行时间与文本数据的长度成正比关系。
附件：1：实验源代码2：实验数据和结果法律名词及注释：1：无损数据压缩：指通过编码和解码过程，在不导致数据信息损失的情况下减少数据量。
2：哈夫曼编码：一种变长编码方式，通过更少的编码长度来表示频率较高的字符，从而达到减少编码长度的目的。
实验课程名称数据结构课程设计专业班级学生姓名学号指导教师2012 至 2013 学年第一学期第 1 至 18 周目录一、概述 (3)1.1课程设计的背景 (3)1.2 赫夫曼树 (3)1.3 课程设计目的 (3)二、系统分析 (4)2.1 课程设计的主要内容 (4)2.2功能设计 (4)三、概要设计 (5)3.1 设计思想 (5)3.2 函数间的关系 (5)四、详细设计 (6)五、运行于测试 (9)六、总结与心得 (12)附录：程序代码 (13)试验题目：赫夫曼编码的应用一、概述1.1课程设计的背景当下，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络传送时间已越来越引起人们的重视，赫夫曼编码正是一种运用广泛且非常有效的数据压缩技术。
1.2 赫夫曼树赫夫曼编码就是利用赫夫曼树求得用于通信的二进制编码。
树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示为“0码”，指向右子树的分支表示为“1”码，取每条路径上的“0”和“1”的序列作为和各个叶子对应的字符的编码，这就是所谓的赫夫曼编码。
1.3 课程设计目的本试验就是通过先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。
二、系统分析2.1 课程设计的主要内容本实验要求完成发送端对等待传送数据的编码和接收端对传送来的数据的译码。
要实现五个功能：接受原始数据、编码、译码、输出编码、译码存档。
通过系统的提示要建立赫夫曼树并对载入的原文件进行编码，并保存到txtfile.tet文件中，同时输出到屏幕。
最后将建立的赫夫曼树用某种的存储方式存储后输出。
2.2功能设计（1）初始化（initialization）从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。
并将它存放于文件htmtree.tx 中。
（2）编码（encoding）利用已经建立好的赫夫曼树（如不在内存，则从文件hfmtree.txe中读入，对文件tobetree.txt中的正文进行编码。
然后将结果存在文件codefile.txt中。
（3）译码（decoding）利用已经建立好的赫夫曼树将文件codefile.txt中的代码进行译码，将结果存入文件textfile.txt中。
（4）输出译码（print）将文件codefile.txt以紧凑格式显示在终端上。
同时将字符型式写入到文件codeprint.txt中。
（5）显示赫夫曼树（treeprint）将已经在内存中的赫夫曼树以直观的方式显示在屏幕上，同时将此字符型的赫夫曼树写入文件treeprint.txt中。
三、概要设计3.1 设计思想赫夫曼树用邻接矩阵来作为存储结构，借助静态链表来实现遍历。
3.2 函数间的关系四、详细设计1．赫夫曼树的抽象数据类型定义ADT HuffmanCoding{数据对象 T：具有相同特征的数据元素的集合数据关系 R：满足最优二叉树的关系基本操作 P：Init （&t）操作结果：构造一个空赫夫曼树t。
Encode（）操作结果：利用赫夫曼树进行编码Decode（）操作结果：利用赫夫曼进行译码}2．主函数void mian（）{打印表头：while（选择选项不为0）{输入选项：switch(选择项){case 1：初始化；break；case 2：输入编码字符；break；case 3：编码字符；break；case 4：译码操作；break；case 5：输出译码；break；case 6：显示赫夫曼树；break；default ：输入错误，重新选择；}3．求赫夫曼编码if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j; //flag为标志符，为不小于可能的值t[flag].parent=1;4．新建赫夫曼树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*));//为赫夫曼代码分配空间5．将赫夫曼编码写入文件用fputs(HC[i],htmTree); fputs(r,htmTree);fclose(htmTree) 这些函数来实现编码写入文件;6．完成译码功能并将译码写入文件因为赫夫曼树建好后是左孩子结点旁标上0，右孩子结点上标上1 所以碰到1是用左孩子结点，2是用右孩子结点，可以用条件语句来实现。
if(i2=='0') m=HT[m].lchild;if(i2=='1') m=HT[m].rchild;fputs(outext,txtfile);//将译码写入文件五、运行于测试1.程序运行后，出现如下主界面：2.执行其它操作之前必须进行初始化，选择“1”执行，并输入结点数3.依次按提示输入字符集并输入相应的权值,输入后会自动写入根目录下htmTree.txt文件中。
4．输入要编码的字符，如下图：6．编码，对目录下tobetran.txt文件进行编码，编码完成后将写入目录下codefile.txt文件中。
7.译码，即对目录下codefile.txt文件中的字符进行译码，译码完成后，内容将会被写入到目录下txtfile.txt文件中。
8．输出译码，即将CodePrint.txt中的编码字符。
9．显示赫夫曼树：六、总结与心得通过两个学期对数据结构课程设计的学习，从中认识到怎样将知识迁移运用，深刻的知道了理论应用和实际相互间的密切联系，感受到了理论知识的重要，在今后的学习中一定会更加努力，认真，并且将理论与实践相结合。
在做这个课程设计论文的时候，我遇到过许多的问题，比如说，写程序以及调试程序时，有很多地方的错误都搞不懂，不过在同学的帮助下，我成功的调试出了程序，并运行出了结果，当时我感觉非常有成就感。
还有就是论文格式上，之前都没有学习过，不过通过老师讲解以及网上百度，最终我还是把它搞懂了，总之，觉得这门课程我收获了很多课堂外不能学到的东西。
非常让我受益匪浅！通过这门课程的学习，我也确实体会到了自己的知识还有很多不足之处和个人能力的十分有限，只有通过同学、老师间的密切配合才能完成一项不错的工作。
不过从中我也体会到了在学习中也有无限的乐趣，可以将现实生活中某一问题用程序编写出来并将以调试，得出结果。
在这里也要感谢老师和同学们对我的帮助，有你们的帮助，我才会学得更好。
附录：程序代码#include <iostream.h>#include <iomanip.h>#include <string.h>#include <malloc.h>#include <stdio.h>typedef int TElemType;const int UINT_MAX=999;typedef struct{int weight; //权值int parent,lchild,rchild; //父节点，左孩子结点，右孩子结点}HTNode,* HuffmanTree;typedef char **HuffmanCode;//-----------全局变量-----------------------HuffmanTree HT; //代表赫夫曼树HuffmanCode HC; //代表赫夫曼编码int *w,i,j,n;char *z;int flag=0;int numb=0;// -----------------求赫夫曼编码-----------------------void line(){cout<<"\n================================\n";}int min(HuffmanTree t,int i){ int j,flag;int k=UINT_MAX; // 取k为不小于可能的值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; //返回标识符} //------------------------------------------void select(HuffmanTree t,int i,int &s1,int &s2){ int j;s1=min(t,i);s2=min(t,i);if(s1>s2)// s1为最小的两个值中序号小的那个{j=s1;s1=s2;s2=j;}}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) { int m,i,s1,s2,start;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) // 建赫夫曼树{ select(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*));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));strcpy(HC[i],&cd[start]);}free(cd);}//--------------初始化赫夫曼链表---------------------------------void init(){ flag=1;int num;int num2;cout<<"赫夫曼链表初始化完成!!!"<<endl<<"================================\n"<<"请输入结点数："; cin>>num;n=num;line();w=(int*)malloc(n*sizeof(int));//weightz=(char*)malloc(n*sizeof(char));//wordcout<<"\n请依次输入"<<n<<"个字符(字符型)\n按Enter结束：<<endl;char temp[2];line();for(i=0;i<n;i++){ cout<<"第"<<i+1<<"个字符:"<<endl;gets(temp);*(z+i)=*temp;}line();for(i=0;i<=n-1;i++){ cout<<setw(6)<<*(z+i);}line();cout<<"\n请依次输入"<<n<<"个权值\n按Enter结束："<<endl;line();for(i=0;i<=n-1;i++){cout<<endl<<"第"<<i+1<<"个字符的权值:";cin>>num2;*(w+i)=num2;}//输入部分结束------------------------------------------HuffmanCoding(HT,HC,w,n);line();cout<<"字符对应的编码为:"<<endl;for(i=1;i<=n;i++){//cout<<"字符"<<*(z+i-1)<<"的编码";puts(HC[i]);}//--------------------------将赫夫曼编码写入文件---------line();//cout<<"下面将赫夫曼编码写入文件"<<endl<<"...................."<<endl;FILE *htmTree;char r[]={' ','\0'};if((htmTree=fopen("htmTree.txt","w"))==NULL){cout<<"文件打开失败"<<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;}//init//---------------------获取字符并写入文件---------------------------------void inputcode(){//cout<<"请输入你想要编码的字符"<<endl;FILE *virttran,*tobetran;char str[100];if((tobetran=fopen("tobetran.txt","w"))==NULL){cout<<"不能打开文件"<<endl;return;}cout<<"请输入你想要编码的字符"<<endl;gets(str);fputs(str,tobetran);cout<<"获取字符成功"<<endl;fclose(tobetran);}void encode() //完成译码功能{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)); //为tuan分配100个字节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);puts(HC[j]);if(j>n){cout<<"字符错误，无法编码!"<<endl;break;}}}}}cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);}void decode() //完成译码功能{cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl;FILE *codef,*txtfile;if((txtfile=fopen("Textfile.txt","w"))==NULL){cout<<"不能打开文件"<<endl;}if ((codef=fopen("codefile.txt","r"))==NULL){cout<<"不能打开文件"<<endl;}char *tbdc,*outext,i2;int io=0,i,m;unsigned long length=10000;tbdc=(char*)malloc(length*sizeof(char)); //分配空间fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char)); //分配空间m=2*n-1;for(i=0;*(tbdc+i)!='\0';i++) //进入循环{i2=*(tbdc+i);if(HT[m].lchild==0){*(outext+io)=*(z+m-1);io++;m=2*n-1;i--;}else if(i2=='0') m=HT[m].lchild;else if(i2=='1') m=HT[m].rchild;}*(outext+io)='\0';fputs(outext,txtfile);cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<endl;free(tbdc);free(outext);fclose(txtfile);fclose(codef);}void printcode() //打印代码{cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl<<"================================\n";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);line();cout<<"打印工作结束"<<endl<<endl;fclose(CodePrin);fclose(codefile);}//------------------------打印赫夫曼树的函数----------------------void coprint(HuffmanTree start,HuffmanTree HT){char t=' ';if(start!=HT){FILE * TreePrint;if((TreePrint=fopen("TreePrint.txt","a"))==NULL){cout<<"创建文件失败"<<endl;return;} numb++;//该变量为已被声明为全局变量coprint(HT+start->rchild,HT);if(start->lchild!=NULL&&start->rchild!=NULL) t='<';cout<<setw(5*numb)<<start->weight<<t<<endl;fprintf(TreePrint,"%d\n",start->weight);coprint(HT+start->lchild,HT);numb--;fclose(TreePrint);}}void printree(HuffmanTree HT,int w) //打印赫夫曼树{HuffmanTree p;p=HT+w;cout<<"下面打印赫夫曼树"<<endl; // 输出“打印赫夫曼树”语句line();coprint(p,HT);line();cout<<"打印工作结束"<<endl; //输出“打印工作结束”}void printhead(){cout<<"\n\t\t";cout<<"********************************************\n\t\t";cout<<" ★欢迎使用赫夫曼编、译码系统★\n\t\t";cout<<"********************************************\n\t\t";cout<<" 1.初始化赫夫曼链表\n\t\t";cout<<" 2.输入编码字符\n\t\t";cout<<" 3.编码\n\t\t";cout<<" 4.译码\n\t\t";cout<<" 5.输出译码\n\t\t";cout<<" 6.显示赫夫曼树\n\t\t";cout<<" 0.退出\n\t\t";cout<<" \n\t ";cout<<"********************************************\n";if(flag==0)cout<<"\n请先输入'1'初始化赫夫曼链表"<<endl<<"\n"; cout<<"请选择你要进行的操作:";}/*2．主程序*/void main(){ char choice;while(choice!='0'){ printhead();cin>>choice;switch(choice){case '1':init(); //按下i则进行初始化赫夫曼链表,break;case '2': //按下2编码字符inputcode();break;case '3': //按下3编码encode();break;case '4': //按下4译码decode();break;case '5': //按下5输出译码printcode();break;case '6': //按下6显示赫夫曼树printree(HT,2*n-1);break;case '0': //按下0退出break;default:cout<<"输入错误，请重新选择"<<endl;} }free(z); //释放z结点free(w); //释放w结点free(HT); //释放HT结点}实验完成情况：完成基本完成未完成。
