哈夫曼编码译码问题

哈夫曼编码和译码哈夫曼编码是一种用于数据压缩的编码方法，通过根据字符出现的频率对字符进行编码，以便能够用较少的位数来表示出现频率较高的字符。

编码过程中，根据频率最低的字符构建一棵哈夫曼树，将字符的编码表示为树的路径。

而哈夫曼译码则是将经过哈夫曼编码后的数据解码成原始数据的过程。

在给定的文本中，首先需要统计每个字符的出现频率。

然后使用这些频率构建哈夫曼树。

构建哈夫曼树的过程中使用最小堆数据结构，通过不断合并两个最小频率的字符节点来构建树。

合并两个节点的过程中，创建一个新的节点来作为它们的父节点，并将其频率设置为两个子节点频率之和。

在构建树的过程中，赋予左子节点编码为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]的哈夫曼编码。

三元哈夫曼编码例题讲解
三元哈夫曼编码是一种编码方式，其基本思想是对于出现频率高的字符采用较短的编码，对于出现频率低的字符采用较长的编码，从而提高整个编码的效率。

以下是三元哈夫曼编码的例题讲解：
1. 题目：假设一个文件中只包含三个字符a、b和c，它们在文件中出现的频率分别为20%、30%和50%。

请使用三元哈夫曼编码对这三个字符进行编码。

解答：首先，我们需要构建一个哈夫曼树。

在哈夫曼树中，频率越高的字符越靠近根节点，因此它们的编码长度也就越短。

对于本题中的三个字符a、b和c，它们的频率分别为20%、30%和50%，因此可以构建如下的哈夫曼树：
字符a的编码为000
字符b的编码为001
字符c的编码为01
2. 题目：假设一个文件中包含五个字符a、b、c、d和e，它们在文件中出现的频率分别为10%、20%、30%、25%和15%。

请使用三元哈夫曼编码对这五个字符进行编码。

解答：首先，我们需要构建一个哈夫曼树。

在哈夫曼树中，频率越高的字符越靠近根节点，因此它们的编码长度也就越短。

对于本题中的五个字符a、b、c、d和e，它们的频率分别为10%、20%、30%、25%和15%，因此可以构建如下的哈夫曼树：
字符a的编码为000
字符b的编码为001
字符c的编码为01
字符d的编码为10
字符e的编码为11
通过以上两个例题，我们可以看出三元哈夫曼编码的基本思想是对于出现频率高的字符采用较短的编码，对于出现频率低的字符采用较长的编码。

这种编码方式可以有效地提高整个编码的效率，从而达到压缩文件的目的。

题目：哈夫曼树编码译码院系：信息工程系专业：计算机科学与技术（网络方向）*名：***学号： **********指导教师：赵莹莹刘欣日期： 2013年7月3日桂林电子科技大学信息科技学院实训报告目录一、设计思想............................. 错误!未定义书签。

1.1建立哈夫曼树的思想................. 错误!未定义书签。

1.2建立哈夫曼编码表................... 错误!未定义书签。

1.3对文件进行编码 (2)1.4对文件进行解码 (2)二、算法流程图 (3)三、运行结果 (8)四、遇到的问题及解决 (10)五、心得体会............................. 错误!未定义书签。

一、设计思想要完成哈夫曼的编码和解码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码和解码。

1.1建立哈夫曼树的思想。

首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。

在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。

初始化树节点之后开始建立哈夫曼树。

先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。

依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。

对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。

即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。

1.2建立哈夫曼编码表。

哈夫曼编码译码一、【实验内容】【问题描述】利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.【基本要求】:一个完整的系统应以下功能:(1) I. 初始化(Initialization)。

从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中.(2) E. 编码(Encoding)。

利用已建立好的哈夫曼树(如不在内存，则从文件hfmTree中读入)，对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。

利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中.(4) P. 印文件代码(Print)。

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

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

(5) T. 印哈夫曼树(TreePrinting)。

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

测试数据:(1) 利用教科书例6-2中的数据调试程序。

(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”.。

字符 A B C D E F G H I J K L M频数 186 64 13 22 32 103 21 15 47 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 1二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.三、实验文档:哈夫曼编码/译码一、需求分析1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

实验九哈夫曼编码-译码器实验十哈夫曼编/译码器一、实验目的(1)掌握哈夫曼树的构造和应用(2)利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统二、实验内容[问题描述](设计性实验)哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

该技术一般可将数据文件压缩掉20,至90,，其压缩效率取决于被压缩文件的特征。

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

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

请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。

并实现以下报文的编码和译码:“this program is my favorite”。

[测试数据]某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示:[实现提示]如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法:参见ppt。

1、设计思想描述(1) 问题分析。

(2) 哈夫曼树中各结点的结构描述(提示:图示)。

(3) 哈夫曼树的存储结构描述(提示:分析采用顺序存储还是利用链式存储等)。

2、主要算法设计与实现[要求]1)、利用类模板来实现。

2)、类中各成员函数要求给出自行设计的算法步骤描述及主要设计思想。

3)、给出类中各成员函数算法设计实现。

4)、对自行设计的各算法进行评估(提示:时间复杂度、空间复杂度等)。

#include<iostream>#include<string>using namespace std;const int MAX = 1000;class HTree;class HTNode{friend class HTree;unsigned int weight;unsigned int parent, lchild, rchild; };class HuCode{friend class HTree;char *ch; //字符的编码char data;//被编码的字符};//动态分配数组存储哈夫曼编码表。

《数据结构》课程设计报告设计题目哈夫曼编码译码学院名称信息工程学院专业班级计算机科学与技术2班姓名学号摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。

它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。

本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。

在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。

与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。

在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。

关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffman coding is a encoding of variable length and a special transformation form of the binary tree. Its principle is: the code that be used more often will be changed into the code of shorter lengths, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter the character set which will be used to coding and their weights. Secondly, according to the fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class SuanFa,and class JieMian. At last, the computer will output Huffman coding on user interface.And then, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the character set one by one during the processs of decoding .And then, the cycle of the next character encoding will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.During the process of coding and decoding, we encounter many problems, such as the problem on arithmetic and grammar. However, we try our best to solve these problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；coding；decoding目录摘要 (I)ABSTRACT (II)1.绪论……………………………………………………………1.1设计目的 (1)1.2问题描述 (1)1.3设计思想 (1)2. 概要设计 (2)3.需求分析 (4)4.详细设计 (5)5.测试数据与实验结果 (10)6.课程设计总结 (14)参考文献 (15)附录（源程序代码） (16)绪论1.1设计目的学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。

数据结构哈夫曼编码与译码哈夫曼编码与译码是数据结构中的重要概念，它是一种可变长度编码的方法，用于压缩数据。

在本文中，我将详细介绍哈夫曼编码与译码的原理、步骤以及应用。

一、哈夫曼编码的原理哈夫曼编码是一种根据字符出现的频率来构建编码表的方法，使得频率较高的字符使用较短的编码，频率较低的字符使用较长的编码。

这样可以有效地减少数据的存储空间。

二、哈夫曼编码的步骤1. 统计字符频率：遍历待编码的文本，统计每个字符出现的频率。

2. 构建哈夫曼树：根据字符频率构建哈夫曼树。

首先将每个字符作为一个独立的树节点，然后合并频率最低的两个节点，生成一个新的节点，频率为这两个节点的频率之和。

重复此过程，直到所有节点都合并为一个根节点，得到哈夫曼树。

3. 生成编码表：从根节点开始遍历哈夫曼树，左子树路径为0，右子树路径为1，将路径上的0和1依次添加到对应字符的编码中，得到编码表。

4. 进行编码：根据编码表，将待编码的文本中的每个字符替换为对应的编码。

5. 完成编码：得到编码后的文本。

三、哈夫曼译码的步骤1. 根据编码表，将编码后的文本逐个字符地进行译码。

从根节点开始，根据字符是0还是1，选择左子树或右子树进行下一步操作。

2. 如果到达叶子节点，则找到对应的字符，并将该字符添加到译码结果中。

3. 重复上述步骤，直到译码结束，得到原始文本。

四、哈夫曼编码与译码的应用哈夫曼编码与译码广泛应用于数据压缩领域。

通过使用哈夫曼编码，可以大大减小数据的存储空间，提高数据传输的效率。

在图像、音频、视频等大数据文件的传输和存储中，哈夫曼编码被广泛使用。

总结：哈夫曼编码与译码是一种基于字符频率的编码方法，可以有效地压缩数据。

通过统计字符频率、构建哈夫曼树、生成编码表等步骤，可以实现对数据的编码和译码。

哈夫曼编码在数据压缩领域有着广泛的应用，可以大大减小数据的存储空间，提高数据传输的效率。

算法与数据结构课程设计哈夫曼编码和译码的设计与实现1.问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。

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

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

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

2.基本要求a.编/译码系统应具有以下功能：（1）I：初始化（Initialization）。

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

（2）E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。

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

（4）P：印代码文件（Print）。

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

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

（5）T：印哈夫曼树（Tree printing）。

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

b.测试数据（1）利用下面这道题中的数据调试程序。

某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。

（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 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 13．需求分析3.1程序的基本功能本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。

题目一: 哈夫曼编码与译码一、任务设计一个运用哈夫曼算法的编码和译码系统, 反复地显示并解决以下项目, 直到选择退出为止。

规定：1) 将权值数据存放在数据文献(文献名为data.txt, 位于执行程序的当前目录中) ；2) 初始化：键盘输入字符集记录字符权值、自定义26个字符和26个权值、记录文献中一篇英文文章中26个字母, 建立哈夫曼树；3) 编码: 运用建好的哈夫曼树生成哈夫曼编码；4) 输出编码（一方面实现屏幕输出, 然后实现文献输出）；5）译码（键盘接受编码进行译码、文献读入编码进行译码）；6) 界面优化设计。

二、流程图三、代码分解 //头文献 #include<stdio.h> #include<string.h> #include<stdlib.h> #include <conio.h> #define N 1000 #define M 2*N-1 #define MAXcode 6000 //函数声明void count(CHar &ch,HTNode ht[]);void editHCode(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); //编码函数void printyima(HTNode ht[],HCode hcd[],int n,char bianma[]); //译码函数 void creatHT(HTNode ht[],int n);字符集记录符集记录权值 权值 至文献“哈夫曼树。

t xt” 菜单1.从键盘输入字符集进行编码2.从文献读入字符集进行编码1.从键盘输入编码进行译码2.从文献读入编码进行译码0.返回上级菜单 0.返回上级菜单void CreateHCode (HTNode ht[],HCode hcd[],int n);void DispHCode(HTNode ht[],HCode hcd[],int n);void input_key(CHar &ch);void input_file(CHar &ch);void input_cw(HTNode ht[]);void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]);void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan();//结构体typedef struct{char data;int parent;int weight;int lchild;int rchild;}HTNode;typedef struct{char cd[N];int start;}HCode;typedef struct{char s[N];int num;}CHar;CHar ch;HTNode ht[M];HCode hcd[N];//主函数int main(){int xh;while(1){system("color 1f"); //操作菜单背景颜色 xh=caidan(); //调用菜单函数switch(xh) //switch语句 {case 1:system("cls");creat_cw();break;case 2:system("cls");creatHT(ht,n);break;case 3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case 4:system("cls");bianmayima();break;case 0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感谢使用本系统!\n\n\n\n\n\n\n \t\t\t");exit(0);default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}return 0;}//菜单函数int caidan() //菜单函数模块//{int xh;printf("\n\n\n");printf("\t\t 欢迎使用哈夫曼编码译码系统\n");printf("\t\t \n");printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*= =*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 1.建立字符权值=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 2.建立并输出哈夫曼树=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 3.生成并查看哈夫曼编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 4.编码与译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 0.退出系统=*\n"); printf("\t\t*= =*\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d", &xh);return xh; //返回从键盘接受的选项}void bianmayima(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码与译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");printf("\t\t*= 1.编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianmacaidan();break;case 2:system("cls");yimacaidan();break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void yimacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");yima1(ht,hcd,n,bianma);break;case 2:system("cls");yima2(ht,hcd,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void bianmacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入字符集编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入文章编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void creat_cw(){int xh2;while(1){printf("\n\n\n\n\n");printf("\t\t 建立字符权值\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.从键盘输入字符集进行记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.从文献读入字符集记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 3.自定义字符权值=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh2);switch(xh2) //switch语句{case 1:system("cls");input_key(ch);break;case 2:system("cls");input_file(ch);break;case 3:system("cls");input_cw(ht);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}//建立字符权值模块void input_key(CHar &ch){int i,j=0;char st[N];printf("请输入字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&st[i]);if(st[i]=='#'){st[i]='\0';break;}}strcpy(ch.s,st);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_file(CHar &ch){int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的字符集为:%s\n",ch.s);fclose(fp);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_cw(HTNode ht[]){int i,w,s,j;char a;printf("要输入的字符总个数是？:");scanf("%d",&s);n=s;printf("请输入字符及其权值:\n");for(i=0;i<s;i++){printf("请输入第%d个字母:",i+1);scanf("%s",&a);ht[i].data=a;printf("请输入其权值:");scanf("%d",&w);ht[i].weight=w;}FILE *fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文献打开失败");return;}printf("\n定义权值成功!\n\n");printf("各字符及其权值为:\n\n");fprintf(fp,"各字符及其权值为:\n");printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<i;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight); }printf("\n");printf("\n字符权值已输出至文献“data.txt”！");fclose(fp);printf("输入完毕, 按任意键返回！");getch();system("cls");return;}//记录字符权值函数void count(CHar &ch,HTNode ht[]){int i,j,m=0;char c[N];int sum[N]={0};for(i=0;ch.s[i]!='\0';i++){for(j=0;j<m;j++)if(ch.s[i]==c[j]||(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j])) break;if(j<m)sum[j]++;else{if(ch.s[i]>='A'&&ch.s[i]<='Z')c[j]=ch.s[i]+32;else c[j]=ch.s[i];sum[j]++;m++;}}for(i=0;i<m;i++){ht[i].data=c[i];ht[i].weight=sum[i];}n=m;FILE *fp;if((fp=fopen("data.txt","w"))==0) {printf("\n\t\t文献打开失败"); return;}printf("\n记录权值成功!\n\n"); printf("各字符及其权值为:\n\n"); fprintf(fp,"各字符及其权值为:\n"); printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<m;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);}printf("\n");printf("\n字符权值已输出至文献“data.txt”！");fclose(fp);}//构造哈夫曼树void creatHT(HTNode ht[],int n){FILE *fp;if((fp=fopen("哈夫曼树.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,j,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for (i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if (ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}else if(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf("建立huffman树成功!\n");printf("输出huffman树:\n");fprintf(fp,"输出huffman树:\n");printf("\t字符\t权值\t父节点\t 左子节点\t右子节点");fprintf(fp,"\t字符\t权值\t父节点\t 左子节点\t右子节点");for(j=1;j<i;j++){ printf("\n");fprintf(fp,"\n");printf("\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i]. lchild,ht[j].rchild);fprintf(fp,"\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,h t[i].lchild,ht[j].rchild);}printf("\n");printf("哈夫曼树已输出至文献“哈夫曼树.txt”！按任意键返回!");fclose(fp);getch();system("cls");return;}//生成哈夫曼编码void CreateHCode (HTNode ht[],HCode hcd[],int n){int i,f,c,j=0;HCode hc;for(i=0;i<n;i++){hc.start=n;c=i;hc.cd[hc.start--]='0';f=ht[i].parent;while(f!=-1){if (ht[f].lchild==c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;for(j=0;j<hc.start;j++)hc.cd[j]=' ';hcd[i]=hc;}}void DispHCode(HTNode ht[],HCode hcd[],int n) {FILE *fp;if((fp=fopen("哈夫曼编码.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,k;int sum=0,m=0,j;printf("输出字符哈夫曼编码:\n"); fputs("输出字符哈夫曼编码:\n",fp); for (i=0;i<n;i++){j=0;printf("%c:\t",ht[i].data);fprintf(fp,"\n%c:\t",ht[i].data);for (k=hcd[i].start;k<=n;k++){printf("%c",hcd[i].cd[k]);j++;fprintf(fp,"%c",hcd[i].cd[k]); }m+=ht[i].weight;sum+=ht[i].weight*j;printf("\n");}printf("\n哈夫曼编码已保存至文献“哈夫曼编码.txt!按任意键返回！”");fclose(fp);getch();system("cls");}//编码函数void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]){int i;char str[N];printf("请输入要编码的字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&str[i]);if(str[i]=='#'){str[i]='\0';break;}}strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");}void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}ch.num=strlen(ch.s);printf("\n读入成功!\n");printf("文献中的字符集为:\n%s",ch.s);fclose(fp);editHCode(ht,hcd,ch,n,bianma);system("cls");return;}//译码函数void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;char code[MAXcode];printf("请输入编码进行译码（以‘#’结束）:\n");for(i=0;i<MAXcode;i++){scanf("%c",&code[i]);if(code[i]=='#'){code[i]='\0';break;}}strcpy(bianma,code);printyima(ht,hcd,n,bianma);printf("\n译码完毕！按任意键返回!");getch();system("cls");return;}void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&bianma[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的编码是:%s\n",bianma);printyima(ht,hcd,n,bianma);printf("\n译码完毕！按任意键返回!");getch();system("cls");}四、调试结果主菜单建立字符权值选择2.从文献读入字符进行记录输入测试文献名“cs.txt”输出个字符权值建立哈夫曼树并输出至文献生成哈夫曼编码并保存至文献编码选择2.从文献读入字符集编码编码结果保存至文献译码选择2.从文献读入编码, 读入上一步的编码译码完毕, 返回！退出系统。

哈夫曼编码和译码运行与调试分析
哈夫曼编码和译码是一种常用的数据压缩算法，以下是其运行、调试和分析的步骤：
1. 运行：
- 首先，根据待压缩的数据，构建哈夫曼树。

- 根据哈夫曼树，生成编码表，即每个字符对应的二进制编码。

- 将待压缩数据按照编码表转换为二进制编码序列。

- 将二进制编码序列存储或传输，实现数据压缩。

2. 调试：
- 检查构建哈夫曼树的过程：确认权重和频率计算是否正确，检查树的构建过程是否存在错误。

- 核对编码表：确保每个字符的编码是否唯一且正确，检查编码表的生成过程是否存在错误。

- 验证压缩结果：按照编码表将压缩后的二进制编码序列还原为原始数据，与原始数据进行对比，确保压缩结果的正确性。

3. 分析：
- 计算压缩率：压缩率可以通过压缩前后数据的长度比值来计算，压缩率越高，表示算法的效果越好。

- 分析运行时间：可以根据输入数据的规模，通过调试工具或代码统计，对哈夫曼编码和译码的运行时间进行分析，评估其效率。

- 对比其他压缩算法：可以将哈夫曼编码与其他压缩算法进行对比，比如LZW算法或gzip 等，评估其压缩效果和性能。

以上是对哈夫曼编码和译码运行、调试和分析的一般步骤，具体实现还需根据算法的具体实现代码和环境进行适配。

题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导教师：日期：实训报告目录一.需求分析 (2)二.概要设计（1）建立哈夫曼树、编码 (3)（2）字符匹配 (3)（3）哈夫曼树遍历 (3)三.详细设计及编码实现 (3)四.流程图（1）总流程图 (15)（2）编码实现流程图 (16)（3）译码实现流程图 (17)五.调试分析（1）计算权值 (18)（1）生成哈夫曼树，建立编码表 (18)（3）将输入字符编码 (19)（4）输入新的字符串，进行译码 (19)（5）输入新的二进制数将其译为字符 (20)六. 系统维护 (20)七．实验总结 (20)八. 源代码 (21)一．需求分析《1》问题描述：在传送电文时，人们总是希望传送时间尽可能短，这就是要求使电文代码长度尽可能短。

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

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

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

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

《2》打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。

问题补充：1. 从硬盘的一个文件里读出一段英语文章。

2. 统计这篇文章中的每个字符出现的次数。

3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出。

4. 对每个字符进行编码并将所编码写入文件然后对所编码进行编译。

《3》这个哈夫曼编码译码主要是以英文字母输入进行编码与编译，编码译码过程由系统自动完成，人工操作部分就是电文的录入，和编译出来时的读操作。

二．概要设计本程序主要用到了三个算法。

(1)哈夫曼树建立、编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。

先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。

基于哈夫曼编码的编码译码问题基于哈夫曼编码的编码译码问题相关问题：1.哈夫曼编码是什么？如何进行编码和译码？2.哈夫曼编码的原理是什么？3.哈夫曼编码的应用领域有哪些？4.如何生成哈夫曼编码树？5.哈夫曼编码的时间复杂度是多少？6.哈夫曼树的构建方法有哪些？7.哈夫曼编码在数据压缩中的作用是什么？8.哈夫曼编码存在的局限性是什么？9.哈夫曼编码与其他编码方法的比较有哪些特点？10.如何解决哈夫曼编码中的冲突问题？解释说明：1.哈夫曼编码是一种基于字符频率的可变长度编码方法。

它通过将出现频率高的字符用较短的编码来表示，出现频率低的字符用较长的编码来表示，以达到数据压缩的目的。

编码过程中，首先统计字符出现频率，然后构建哈夫曼树，根据树的结构生成编码表，最后对原始数据进行编码。

译码过程中，根据生成的编码表和编码数据，逐位解码还原原始数据。

2.哈夫曼编码的原理是基于贪心算法，通过构建哈夫曼树，将出现频率高的字符放在树的上层，出现频率低的字符放在树的下层，以实现最优的编码效果。

在编码过程中，使用了前缀码的特性，即任何一个编码不能是另一个编码的前缀，从而保证了译码的唯一性。

3.哈夫曼编码广泛应用于数据压缩领域，可以对文本、图像、音频等数据进行压缩和解压缩。

此外，哈夫曼编码也用于数据传输中的差错检测和纠正，以及编码理论的研究等领域。

4.生成哈夫曼编码树的方法主要有两种：静态生成和动态生成。

静态生成是根据给定的字符频率进行构建，而动态生成是根据实际数据的字符频率进行构建。

5.哈夫曼编码的时间复杂度为O(nlogn)，其中n为字符的个数。

这是由于在构建哈夫曼树时需要进行n-1次合并操作，每次合并的时间复杂度为O(logn)。

6.哈夫曼树的构建方法主要有两种：霍夫曼算法和优先队列算法。

霍夫曼算法是经典的构建方法，通过反复选择权值最小的两个节点合并构建树，直到所有节点合并为一棵树。

优先队列算法则先将节点插入优先队列中，每次取权值最小的两个节点合并。

哈夫曼编\译码的设计与实现一、简介1．设计目的：通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。

2．问题的描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

系统应该具有如下的几个功能：接收原始数据、编码、译码、打印编码规则。

二、数据结构的设计：1.哈夫曼结点结构体：typedef struct HtNode{int weight;int parent, lchild, rchild;}HtNode;2.哈夫曼树结构体：typedef struct HtTree{struct HtNode ht[MAXNODE+1];int root;}HtTree, *PHtTree;三、功能（函数）设计：总体上划分为四个模块，具体功能描述如下：1．初始化功能模块：接收输入信息，并正确输出2．建立哈夫曼树的功能模块：按照构造哈夫曼树的算法构造哈夫曼树，将HuffNode数组中的各个位置的各个域都添上相关的值3．哈夫曼编码的功能模块：根据输入的相关字符信息进行哈夫曼编码，然后将结果存入，同时将字符与0、1代码串的一一对应关系打印到屏幕上。

4．译码的功能模块：接收需要译码的0、1代码串，按照哈夫曼编码规则将其翻译成字符集中的字符所组成的字符串形式，将翻译的结果在屏幕上输出四、界面设计：该界面操做简单，内容详细，便于程序使用者根据提示轻松上手。

简洁明朗是该界面最大的特点。

哈夫曼编/译码请逐个输入结点和结点的权值>>>按Enter键开始根据此提示界面进入程序使用阶段。

请输入结点个数：根据用户输入结点个数，动态输入并存储字符及权值然后输出字符与0、1代码串的对应关系。

进入以下界面，进行后续操作1----------------------------编码2----------------------------译码3----------------------------重新输入权值;0----------------------------退出用户键入“0”，即可出编码译码操作五、程序设计：1．函数功能说明及其程序流程图的描述：1>:main函数：控制整个程序的整个流程。

实验五哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

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

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

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

基本要求：（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。

（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat 中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。

（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件text中。

（4）打印编码规则：即字符与编码的一一对应关系。

（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。

二、数据结构设计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序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。

霍夫曼编码经典例题霍夫曼编码又称为哈夫曼编码，是一种编码方式，它可以将信息编码成不同的二进制序列，有效地减少信号的传输量，以提高通信的效率。

它是由美国的克劳德霍夫曼于二十世纪五十年代开发的，并在1952年申请专利，他的发明改变了数据压缩和计算机科学领域，并成为了现代通信技术中不可缺少的一环。

霍夫曼编码的主要特点是它可以有效地将信息压缩，这样可以节省传输的时间和量。

霍夫曼编码的功能体现在不同的信号被编码成不同的二进制序列，这样做可以有效地减少传输量。

下面将介绍一些关于霍夫曼编码经典例题的内容。

例1：以下给出使用霍夫曼编码表示字母A，B，C，D的情况。

A：0B：10C：110D：111例2：已知字母A，B，C，D出现的频率分别为5，15，40，40，求其对应的霍夫曼编码。

A：0B：10C：110D：111例3：若给出的字母为E，F，G，H，频率分别为10，20，30，40，求其对应的霍夫曼编码。

E：00F：01G：10H：11以上就是关于霍夫曼编码经典例题的内容，它的主要特点是能够有效地将信息压缩，减少传输量，以提高通信效率。

霍夫曼编码可用于语音信号的传输，它也可以用于有限量数据压缩，以及数据库中的存储等。

霍夫曼编码的实现并不复杂，它的原理是，根据信源符号出现的频率，将频率较高的符号分配短码，而频率较低的符号分配长码。

实际上，由于字母A，B，C和D的频率相同，因此，分配的编码也是相同的。

在霍夫曼编码的过程中，需要对字母和对应的编码进行保存，因此，需要一个字典来存储字母和对应的编码。

此外，还需要实现霍夫曼编码的压缩，以及解压缩的功能。

总之，霍夫曼编码是一种有效率的信息压缩和传输技术，应用范围极其广泛，可以大大提高数据的传输速率。

一、设计思想程序要求：利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。

将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。

实现方法：输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。

将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。

然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。

根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。

重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。

解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。

于是就得到了原先被加密的那串字符串。

二、算法流程图三、源代码// hafuman.cpp : 定义控制台应用程序的入口点。

//#include "stdafx.h"#include "stdlib.h"#include "string.h"#include "stdio.h"#define n 100 //叶节点的个数小等于n#define m 2*n-1 //总结点的个数为m=2*n-1int num; //定义一个全局变量用于存放字符种类个数typedef struct //结构体用于存放树节点包括节点的父节点、左子、右子以及权值{ int weight;int parent,lchild,rchild;}HTNode;typedef HTNode HafumanTree[m+1]; //重命名HTNodetypedef struct //结构体由于存放每个字符的密文和长度{char ch;char bits[10];int len;}CodeNode;typedef CodeNode HafumanCode[n+1]; //重命名CodeNodeint _tmain(int argc, _TCHAR* argv[]){int quan[27]; //声明一个数组用以存放26字符的权值char getstr[300],str[27];//声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符char *s; //声明一个char型指针用于指向字符HafumanTree HT; //声明m+1个树节点HafumanCode HC; //声明n+1个codeint jisuanquan(char *s,int quan[],char str[]); //声明需要调用的函数void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]);void Hafumanencode(HafumanTree HT,HafumanCode HC);void coding(HafumanCode HC,char *str);char *decode(HafumanCode HC);printf("请输入要加密的字符串：\n");gets(getstr); //获得输入的字符串num=jisuanquan(getstr,quan,str); //统计字符串中含有字符种类个数//printf("%d\n",num);gjhafumantree(HT,HC,quan,str); //根据字符权值构建哈夫曼树Hafumanencode(HT,HC); //根据哈夫曼树确定每个字符的code coding(HC,getstr); //将字符串译码存入文件夹s=decode(HC); //将暗文解码printf("解密为：\n");printf("%s\n",s);system("pause");return 0;}//函数int jisuanquan(char *s,int quan[],char str[]) //计算字符串中字符权值{char *p;int i,j,k,quantemp[27];for(i=1;i<27;i++) //将所有字符的权值赋成0 {quantemp[i]=0;}for(p=s;*p!='\0';p++) //判断字符串是否结束{if(*p>='A'&&*p<='Z') //判断字符是否为26字母{k=*p-64; //看是26个字符中的哪个字符quantemp[k]++; //字符权值加1}}j=0;for(i=1,j=0;i<27;i++){if(quantemp[i]!=0){j++; //用于统计字符种类个数str[j]=i+64; //str按字母表顺序存储出现过的字符quan[j]=quantemp[i];}}return j;}void select(HafumanTree HT,int k,int *s1,int*s2) //选择权值最小的两个{int i,j;int min1=9999; //声明一个int类型的数值min1，赋个较大的输给它for(i=1;i<=k;i++) //选择权值最小的一个节点（且该节点无父节点）{if((HT[i].weight<min1)&&(HT[i].parent==0)){j=i;min1=HT[i].weight;}}*s1=j;min1=9999;for(i=1;i<=k;i++){if((HT[i].weight<min1)&&(HT[i].parent==0)&&(i!=*s1))//选择权值最小的一个节点（且该节点无父节点）{j=i;min1=HT[i].weight;}}*s2=j;}void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]) //构建哈夫曼树{int i,s1,s2;for(i=1;i<2*num-1;i++) //将所有的节点赋空{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++) //将num个字符的权值赋给num叶节点{HT[i].weight=quan[i];}for(i=1;i<=num;i++) //将num个字符赋给codenode{HC[i].ch=str[i];}i=1;while(i<=num){ printf("===%c===%d===\n",HC[i].ch,quan[i]);i++;} //输出每个字符的及其权值for(i=num+1;i<=2*num-1;i++){select(HT,i-1,&s1,&s2); //选择两个权值最小的叶节点HT[s1].parent=i;HT[s2].parent=i; //两个节点指向同一父节点HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//父节点的权值为子节点相加（父节点继续放入选择区）}}void Hafumanencode(HafumanTree HT,HafumanCode HC){int c,p,i;char cd[n]; //临时数组用于记录字符在哈夫曼树的位置int start;cd[num]='\0'; //给cd赋个结束符for(i=1;i<=num;i++){start=num;c=i;while((p=HT[c].parent)>0) //根据节点是其父节点的左右子来记录它的位置{cd[--start]=(HT[p].lchild==c)?'0':'1';c=p; //将父节点转为子节点}strcpy(HC[i].bits,&cd[start]); //将得到的0、1字串存入结构体HCprintf("%c:%s\n",HC[i].ch,HC[i].bits);HC[i].len=num-start; //求每个字符0、1编码长度}}void coding(HafumanCode HC,char *str) //根据哈夫曼树确定每个字符的0、1代码code{int i,j;FILE *fp; //声明一个文件夹指针fp=fopen("codefile.txt","w"); //打开文件夹codefileprintf("密文为：\n");while(*str) //字符串未结束时{for(i=1;i<=num;i++){if(HC[i].ch==*str) //判断字符是否在Codenode中存在{for(j=0;j<HC[i].len;j++) //将codenode中该字符的1、0代码存入文件夹{fputc(HC[i].bits[j],fp);}printf("%s",HC[i].bits);break;}}str++; //字符后移}printf("\n");fclose(fp);}char *decode(HafumanCode HC){FILE *fp;char tempstr[9999];char *p;static char cd[n+1]; //char型数组用于存放从文件夹中读取的1、0代码int i,j,k=0,jsjs;fp=fopen("codefile.txt","r");while(!feof(fp)) //当文件夹读取没有结束{jsjs=0; //判读一个字符是否译码结束for(i=0;(i<num)&&(jsjs==0)&&(!feof(fp));i++) //当一个字符未译完并且文件未读取结束{ cd[i]=' ';cd[i+1]='\0'; //让cd[]赋成空格cd[i]=fgetc(fp); //读取文件夹中的一个字符for(j=1;j<=num;j++){ if(strcmp(HC[j].bits,cd)==0) //看cd[]的字符串是否等于Codenode中的某个密文{tempstr[k]=HC[j].ch;jsjs=1;printf("=%s=",HC[j].bits);k++;break;}//将译出的字符赋给临时字符串tempstr[],标记一个字符译码结束jsjs赋1，跳出循环}}}tempstr[k]='\0'; //赋给临时字符串一个结束标志p=tempstr; //char型指针指向临时字符串return p;}四、运行结果图5 哈夫曼编码与译码运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：●当我写完程序，输入一段字符串让程序进行译码和解码是出现了一个问题，译出的结果不是想要的结果，但结果又有一定规律，就是结果中的字符都在明文中出现过，可是字符数量明显比明文中的要少很多。