下载文档原格式
合肥学院计算机科学与技术系一、问题分析和任务定义1、题目采用哈夫曼编码思想实现英文文本的压缩与解压缩，并提供压缩前后的占用空间比。
要求 1）压缩原文件规模不小于5K2) 提供解压缩文件后文件与原文件的相同性比较功能2、问题分析压缩过程 news.txt →news1.txt1、以读的形式打开需要压缩的一个英文本文件，把其中出现的所有字符按其在文本中出现的频率利用哈夫曼树进行编码。
2、以写的形式打开一个新的文本文件，把它作为英文文本压缩后的文本文件，扫描需要压缩的英英文本文件（ new.txt ）中所有字符，把其对应的编码通过转换后存入新的文本文件( new1.txt )中。
3、把需要压缩的英文文本（ new.txt ）中所出现的字符及其编码等原始文件的信息保存在新的文本文件中。
解压缩过程news1.txt →news2.txt1、以读的形式打开一个压缩文件 news1.txt，按其中保存的原始文件的信息还原哈夫曼树及字符编码。
2、以写的形式打开一个新的文本文件，作为解压后的英文文本 news2.txt ，逐个扫描压缩文件 news1.txt中的所有字符，把其中所有转换后的编码再转换回来并与哈夫曼树中存储的字符编码比较，把其对应的字符写入news2.txt 中。
一个字符在文本文件中存储时占一个字节，而其二进制编码若直接存入文本文件其所占的空间不会少于一个字节。
例如：假设字符E的编码为001，若把001直接存入文件只能用字符串的形式，其所占用的空间为三个字节。
达不到文件压缩的目的，所以必须对编码的存储空间进行转换。
3 编码转换在文本文件中字符之间是连续的，所以在文本文件中存储编码也是连续的。
可以把连续的不同字符的编码存入同一个字节，再把这一个字节的二进制码转换成一个字符，把转换后的字符存储在文本文件中。
二、数据结构的选择和概要设计：1 此程序采用的数据结构为顺序表。
哈夫曼树是二叉树的一种，二叉树的顺序存储结构中可以把结点间的关系放在其存储位置中，无需附加任何信息就能在这种结构中找到每个结点的双亲结点和孩子结点，这正是哈夫曼编码所需要的。
Mac命令行中的压缩和解压缩使用tar和zip命令在Mac命令行中，我们可以使用tar和zip命令进行文件的压缩和解压缩操作。
本文将详细介绍这两个命令的使用方法和常见参数。
一、tar命令的使用tar命令是在Unix和类Unix系统上广泛使用的归档工具，可以将多个文件或目录打包成一个文件。
下面是tar命令的基本用法：1. 打包文件或目录tar -cvf archive.tar file1 file2 ... # 将文件或目录打包成archive.tar 文件2. 查看打包文件的内容tar -tf archive.tar # 查看archive.tar文件中包含的文件列表3. 解压缩打包文件tar -xvf archive.tar # 解压缩archive.tar文件4. 打包并压缩文件tar -zcvf archive.tar.gz file1 file2 ... # 将文件或目录打包并使用gzip 进行压缩，生成archive.tar.gz文件5. 解压缩压缩文件tar -zxvf archive.tar.gz # 解压缩archive.tar.gz文件以上是tar命令的基本用法，此外，tar命令还有许多可选参数，以适应不同的使用场景。
例如，可以通过指定文件或目录的名称、排除特定文件或目录、设置压缩级别等来调整tar命令的行为。
二、zip命令的使用zip命令是Mac系统中用于创建和提取zip压缩文件的命令行工具。
它的用法与tar命令有所不同。
下面是zip命令的基本用法：1. 压缩文件或目录zip -r archive.zip file1 file2 ... # 将文件或目录压缩成archive.zip 文件2. 解压缩压缩文件unzip archive.zip # 解压缩archive.zip文件3. 查看压缩文件的内容unzip -l archive.zip # 查看archive.zip文件中包含的文件列表以上是zip命令的基本用法，与tar命令类似，zip命令也有许多可选参数供我们使用。
Mac命令行使用技巧压缩和解压文件Mac命令行使用技巧：压缩和解压文件在Mac操作系统中，命令行是一种非常强大的工具，它可以帮助我们完成各种任务，其中包括文件的压缩和解压。
本文将介绍一些Mac 命令行使用技巧，让您能够更加高效地进行文件的压缩和解压操作。
一、压缩文件1. 将文件压缩成zip格式：通过使用"zip"命令可以将指定的文件或文件夹压缩成zip格式。
以下是一个示例命令：```zip -r compressed.zip folder```上述命令将"folder"文件夹中的所有文件和子文件夹压缩成一个名为"compressed.zip"的zip文件。
2. 将文件压缩成tar.gz格式：有时候我们需要将文件以tar.gz格式进行压缩，可以使用下面的命令：```tar -zcvf compressed.tar.gz file上述命令将"file"压缩成一个名为"compressed.tar.gz"的文件。
3. 使用gzip压缩文件："Gzip"是一种常用的压缩格式，我们可以使用以下命令来将文件压缩成gzip格式：```gzip file```上述命令将"file"进行压缩，并生成一个名为"file.gz"的文件。
二、解压文件1. 解压zip文件：要解压缩一个zip文件，可以使用"unzip"命令。
以下是一个示例：```unzip compressed.zip```上述命令将"compressed.zip"文件解压到当前目录。
2. 解压tar.gz文件：要解压缩一个tar.gz文件，可以使用下面的命令：tar -zxvf compressed.tar.gz```上述命令将"compressed.tar.gz"文件解压到当前目录。
ZIP压缩算法详细分析及解压实例解释最近自己实现了一个ZIP压缩数据的解压程序，觉得有必要把ZIP压缩格式进行一下详细总结，数据压缩是一门通信原理和计算机科学都会涉及到的学科，在通信原理中，一般称为信源编码，在计算机科学里，一般称为数据压缩，两者本质上没啥区别，在数学家看来，都是映射。
一方面在进行通信的时候，有必要将待传输的数据进行压缩，以减少带宽需求；另一方面，计算机存储数据的时候，为了减少磁盘容量需求，也会将文件进行压缩，尽管现在的网络带宽越来越高，压缩已经不像90年代初那个时候那么迫切，但在很多场合下仍然需要，其中一个原因是压缩后的数据容量减小后，磁盘访问IO的时间也缩短，尽管压缩和解压缩过程会消耗CPU资源，但是CPU计算资源增长得很快，但是磁盘IO资源却变化得很慢，比如目前主流的SATA硬盘仍然是7200转，如果把磁盘的IO压力转化到CPU上，总体上能够提升系统运行速度。
压缩作为一种非常典型的技术，会应用到很多很多场合下，比如文件系统、数据库、消息传输、网页传输等等各类场合。
尽管压缩里面会涉及到很多术语和技术，但无需担心，博主尽量将其描述得通俗易懂。
另外，本文涉及的压缩算法非常主流并且十分精巧，理解了ZIP的压缩过程，对理解其它相关的压缩算法应该就比较容易了。
1、引子压缩可以分为无损压缩和有损压缩，有损，指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高，主要应用于视频、话音等数据的压缩，因为损失了一点信息，人是很难察觉的，或者说，也没必要那么清晰照样可以看可以听；无损压缩则用于文件等等必须完整还原信息的场合，ZIP自然就是一种无损压缩，在通信原理中介绍数据压缩的时候，往往是从信息论的角度出发，引出香农所定义的熵的概念，这方面的介绍实在太多，这里换一种思路，从最原始的思想出发，为了达到压缩的目的，需要怎么去设计算法。
而ZIP为我们提供了相当好的案例。
尽管我们不去探讨信息论里面那些复杂的概念，不过我们首先还是要从两位信息论大牛谈起。
Mac命令行实用技巧文件压缩和解压缩Mac命令行实用技巧：文件压缩和解压缩在Mac操作系统中，命令行界面是一个强大而实用的工具，可以让用户通过一些简洁的指令完成各种任务。
本文将介绍Mac命令行下的文件压缩和解压缩技巧，帮助您更高效地处理文件。
1. ZIP压缩和解压缩ZIP是一种常见的文件压缩格式，Mac系统内置了ZIP压缩和解压缩命令。
下面是一些常用的指令：- 压缩一个文件或文件夹：```zip -r compressed.zip folder```这个指令将会压缩名为"folder"的文件夹，并将压缩后的文件保存为"compressed.zip"。
- 解压缩一个ZIP文件：```unzip compressed.zip```运行这个指令将会将"compressed.zip"解压缩到当前目录。
2. GZIP压缩和解压缩GZIP是一种广泛使用的文件压缩格式，通常用于压缩大文件和日志文件。
Mac系统同样内置了GZIP压缩和解压缩命令。
以下是一些示例指令：- 压缩一个文件：```gzip file.txt```运行这个指令将会把名为"file.txt"的文件压缩成"gzip"格式，并生成一个名为"file.txt.gz"的压缩文件。
- 解压缩一个GZIP文件：```gunzip file.txt.gz```运行这个指令将会解压缩名为"file.txt.gz"的文件，生成一个名为"file.txt"的文本文件。
3. TAR打包和解包TAR是另一种常用的文件打包格式，通常和GZIP结合使用，用于将多个文件或文件夹打包成一个文件。
以下是一些常用的指令：- 打包一个文件或文件夹：```tar -cvf archive.tar folder```这个指令将会把名为"folder"的文件夹打包成一个名为"archive.tar"的文件。
Mac命令行文件压缩技巧使用tar和zip压缩和解压缩文件在Mac系统中，命令行终端是一个非常强大的工具，可以通过它来进行文件的压缩和解压缩操作。
本文将介绍如何使用命令行中的tar和zip命令来进行文件的压缩和解压缩，以及一些相关的技巧和注意事项。
一、使用tar命令进行文件压缩和解压缩tar命令是一个经典的文件打包工具，可以将多个文件或目录打包成一个单独的文件。
同时，它也支持对打包文件进行解压缩操作。
1. 压缩文件：要将一个文件或目录进行压缩，可以使用以下命令：tar -czvf 压缩文件名.tar.gz 要压缩的文件或目录这里，“-c”表示创建压缩文件，“-z”表示使用gzip算法进行压缩，“-v”表示显示压缩和解压缩的详细过程，“-f”表示指定压缩文件的文件名。
例如，要将目录“documents”压缩成一个文件名为“backup.tar.gz”的压缩文件，可以使用以下命令：tar -czvf backup.tar.gz documents2. 解压缩文件：要对一个tar压缩文件进行解压缩，可以使用以下命令：tar -xzvf 压缩文件名.tar.gz这里，“-x”表示解压缩操作。
例如，要对压缩文件“backup.tar.gz”进行解压缩，可以使用以下命令：tar -xzvf backup.tar.gz二、使用zip命令进行文件压缩和解压缩zip命令是Mac系统中自带的文件压缩和解压缩工具，它可以创建zip格式的压缩文件并支持解压缩操作。
1. 压缩文件：要将一个文件或目录进行压缩，可以使用以下命令：zip -r 压缩文件名.zip 要压缩的文件或目录这里，“-r”表示递归地对目录进行压缩。
例如，要将目录“documents”压缩成一个文件名为“backup.zip”的压缩文件，可以使用以下命令：zip -r backup.zip documents2. 解压缩文件：要对一个zip压缩文件进行解压缩，可以使用以下命令：unzip 压缩文件名.zip例如，要对压缩文件“backup.zip”进行解压缩，可以使用以下命令：unzip backup.zip三、其他技巧和注意事项1. 压缩多个文件：如果要同时压缩多个文件，可以将它们的文件名依次列在tar或zip 命令后面即可。
Linux常⽤命令：zip、unzip压缩和解压缩命令Linux常⽤命令: zip、unzip 压缩和解压缩命令
zip的⽤法
基本⽤法是：
zip [参数] [打包后的⽂件名] [打包的⽬录路径]
常⽤参数：
-a将⽂件转成ASCII模式
-F尝试修复损坏的压缩⽂件
-h显⽰帮助界⾯
-m将⽂件压缩之后，删除源⽂件
-n特定字符串不压缩具有特定字尾字符串的⽂件
-o将压缩⽂件内的所有⽂件的最新变动时间设为压缩时候的时间
-q安静模式，在压缩的时候不显⽰指令的执⾏过程
-r将指定的⽬录下的所有⼦⽬录以及⽂件⼀起处理
-S包含系统⽂件和隐含⽂件（S是⼤写）
例如：
将指定⽬录/tmp压缩成test.zip⽂件
zip -r test.zip tmb/
unzip的⽤法
基本⽤法是：
unzip [参数] [待解压缩⽂件]
在linux下解压zip⽂件，最简单的⽅式就是unzip命令直接跟上要解压的zip⽂件。
unzip [待解压缩⽂件]
常⽤参数：
-n解压缩时不要覆盖原有的⽂件；
-o不必先询问⽤户，unzip执⾏后覆盖原有的⽂件；
-P [密码]使⽤zip的密码选项；
-q执⾏时不显⽰任何信息；
-d [⽬录]指定⽂件解压缩后所要存储的⽬录；
例如：
将压缩⽂件text.zip在当前⽬录下解压缩。
unzip test.zip
将压缩⽂件test.zip在指定⽬录/tmp下解压缩，如果已有相同的⽂件存在，要求unzip命令覆盖原先的⽂件。
unzip -o test.zip -d tmp/。
Mac命令行实用小技巧文件压缩与解压缩技巧在进行文件管理、传输或备份时，文件的压缩和解压缩是常见的操作。
而在Mac系统中，命令行提供了许多实用的小技巧，使得文件压缩和解压缩更加高效和便捷。
本文将介绍一些Mac命令行实用小技巧，帮助读者掌握文件压缩和解压缩的方法。
一、压缩文件在Mac的命令行终端中，使用压缩命令可以对文件进行压缩。
下面介绍几种常用的压缩命令及其用法：1. gzip命令：gzip命令是Mac系统自带的文件压缩工具，通过该命令可以将文件压缩成.gz格式。
使用方法如下：```gzip [选项] 文件名```例如，将名为"file.txt"的文件压缩为"file.txt.gz"，命令如下：```gzip file.txt```2. zip命令：zip命令可以将文件和文件夹压缩成zip格式文件，非常适合用于多个文件的压缩。
使用方法如下：```zip [选项] 压缩文件名源文件/文件夹```例如，将名为"folder"的文件夹压缩为"folder.zip"，命令如下： ```zip -r folder.zip folder/```3. tar命令：tar命令是将多个文件打包成一个文件的命令，结合gzip可以将文件压缩成tar.gz格式。
使用方法如下：```tar [选项] 目标文件名源文件/文件夹```例如，将名为"folder"的文件夹压缩成"folder.tar.gz"，命令如下： ```tar -zcvf folder.tar.gz folder/```二、解压缩文件在Mac的命令行终端中，同样提供了多种解压缩命令来解压缩文件。
下面介绍几种常用的解压缩命令及其用法：1. gunzip命令：gunzip命令可以对.gz格式的文件进行解压缩。
使用方法如下：```gunzip 文件名.gz```例如，将名为"file.txt.gz"的文件解压缩为"file.txt"，命令如下：```gunzip file.txt.gz```2. unzip命令：unzip命令可以解压缩zip格式的文件。
题目：名称：英文文件的压缩和解压缩内容：采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。
要求：（1）压缩原文件的规模应不小于5K。
（2）提供解压缩后文件与原文件的相同性比较功能。
一、问题分析何任务定义通过阅读并理解这个题目，要求实现对一个大小不小于5KB的英文文件的压缩和解压缩功能。
为了完成这个功能，可以采用哈夫曼编码具体实现。
实现本程序需要解决一下几个问题：1、如何统计英文文件的字符种类数和各类字符的数目，并将各类字符作为哈夫曼树的叶子，数目作为它的权值。
2、如何利用上述的字符数目作为叶子权值建立哈夫曼树。
3、如何对于步骤2建立的哈夫曼树的叶子（字符）进行编码。
4、如何将已知的字符编码应用到英文文件。
5、如何对应经压缩的文件进行解压缩。
首先，给定一个英文文件，如图（1）：图（1）解压后的文件：然后再进行字符统计，可以利用ASCII码表的字符与数字一一对应的知识计算出每类字符的数目，把计算出的每类字符放到另一个数组中顺序存储。
利用上述统计出的每类字符及字符数目作为哈夫曼树（数组存储）的叶子结点，把上述数组顺序存储的字符及数目赋给哈夫曼数组前n位，每次选用权值最小和次最小的两个结点构建哈夫曼树，已经选用的就不再此操作了。
建立好哈夫曼树后就是对其叶子进行编码，因为哈夫曼树的结点的度数不是2就是0（叶子），此叶子就是要进行编码的对象，令其左边为0，右边为1，如图（2）0 1图（2）从每个叶子结点开始一直沿着哈夫曼树向上，直到根结点，循环此操作，将每个字符进行编码。
对每个字符编码后，就要对英文文件进行压缩了，再次从英文文件单个单个读出字符，将每个字符对应的编码向另一个文件中写入，此时是利用循环来将字符对应的编码一个个的写入到文件中。
直到文件结束，此时压缩成功。
并可以查看压缩的文件code.txt。
对于一个压缩的文件进行译码，译码的方法就是从压缩文件连续读出0或1，将连续读出的0或1从哈夫曼树的根结点开始一直向下，直到某个叶子结点，将此编码所对应的字符写入另一个文件中，然后在继续读入0或1，利用上述的办法循环写入字符，直到文件结束。
Mac命令行文件压缩和解压缩技巧在Mac系统中，我们经常需要对文件进行压缩和解压缩操作。
除了使用图形界面上的压缩工具，还可以通过命令行来完成这些任务。
本文将介绍一些Mac命令行下的文件压缩和解压缩技巧，帮助你更高效地进行文件管理。
1. 压缩文件在命令行中，使用"zip"命令可以将一个或多个文件压缩成一个Zip 文件。
以下是一个示例命令：```zip compressed.zip file1.txt file2.txt```上述命令将压缩"file1.txt"和"file2.txt"两个文件，并将它们保存为"compressed.zip"。
2. 压缩文件夹如果需要压缩整个文件夹，可以在上述命令中加入"-r"参数，表示递归压缩文件夹及其子文件夹。
示例命令如下：```zip -r compressed.zip folder```上述命令将压缩名为"folder"的文件夹及其子文件夹，并将它们保存为"compressed.zip"。
3. 解压缩文件解压缩命令与压缩命令相对应。
使用"unzip"命令可以解压缩一个已压缩的Zip文件。
以下是一个示例命令：```unzip compressed.zip```上述命令将解压缩名为"compressed.zip"的Zip文件，并将其中的文件还原到当前目录。
4. 查看压缩文件内容如果只需要查看压缩文件中的内容，而不解压缩它，可以使用"unzip -l"命令。
示例命令如下：```unzip -l compressed.zip```上述命令将列出名为"compressed.zip"的压缩文件中包含的文件及其属性。
5. 创建tar归档文件除了Zip格式，还可以使用tar命令创建归档文件，将多个文件或文件夹打包成一个文件。
合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称英文文件的压缩和解压缩学生姓名学号专业班级指导教师李红沈亦军2010 年 6 月题目：（采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比）（1）压缩原文件的规模应不小于5K。
（2）提供解压缩后文件与原文件的相同性比较功能。
一、问题分析和任务定义。
1.1问题分析本实验是利用哈夫曼编码思想，设计对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。
要解决以上问题，需从以下几个方面着手：（1）如何读入待压缩的文本文件，统计文本文件中各字符的频数及出现的字符个数；（2）如何构造huffman树，进行huffman编码，生成压缩文件（后缀名.txt（3）如何读入待解压的压缩文件名,并利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，生成解压文件（后缀名为.txt）；（4）如何提供压缩前后的占用空间之比1.2输入、输出数据的形式、值的范围，算法（程序）所能达到的功能本实验的数据主要是以字符型为主，还有一些自定义的整形和浮点型变量，该实验室对文件进行压缩和解压（被压缩文件容量要求大于>5KB），通过该算法程序可以大致上满足实验所要求的功能，即压缩原文件的规模不小于5KB，提供了压缩后的文件与原文件的压缩比例，也即提供了性能比较功能1.3 测试用的数据本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。
所测试的部分数据：图1.原文档二、数据结构的选择和概要设计为了完成实验所要求的任务，解决的问题及方法如下：1.文件的读取及统计字符出现的个数和频率（1）文件的读取void read_file_count(){char c;ifstream infile;infile.open("huffman.txt");//打开huffman.txt文件if(!infile)//检查文件是否打开。
{cout<<"不能打开 huffman.txt文件";//输出文件未打开的标志exit(0);}cout<<"读入的文件中的内容为："<<endl;while((c=infile.get())!=EOF)//EOF是文件结束的标志cout<<endl;}(2)计所出现的字符个数void char_add(char c){huff[count].data=c;huff[count++].count++;//个数增加}(3)计每个字符出现的频率：bool char_judge(char c){for(int i=1;i<=count;i++)if(huff[i].data==c){huff[i].count++;return true;}//如果出现过，出现的频数加1return false;}2.构造huffman树解决了上述问题，接下来要考虑的是怎样去构造huffman树的问题，进行huffman编码，对文件进行压缩。
为了构造huffman树，我将每个字符出现的频率赋予huffman树中叶子结点的权值，从而构造huffman树，也即先查找两个权值最小的结点，合并为新的结点，并将新的结点存入数组中，继续比较合并，最后形成huffman树。
3.huffman编码利用构造好的huffman树，进行编码：设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn}，以d1,d2,……,dn作为叶结点，以w1,w2,……,wn作为各叶子结点的权值构造一棵二叉树，规定HUFFMAN树中的左孩子结点为0，右孩子结点为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。
这样的代码总长度最短的不等长编码就为HUFFMAN编码。
4.文件压缩问题采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样就能对文件进行压缩。
在计算机存储中，是以二进制来存储的，本来每个字符将占据8位，而通过huffman编码后，一个字符在计算机存储中，将占据的位数少于8位，这样将大大减少存储空间，从而实现对文件的压缩。
5.读入压缩文件，并对其解压。
对如何读取压缩文件，采用的方法大致和开始相同，在此不赘述。
为解压，利用构造好的 huffman 树，再根据读取的huffman 编码文件，在huffman 树中查找叶子结点，查找到叶子结点，放入另一个文本文档中，并输出。
其具体查找过程是从根结点开始，根据读入的二进制编码（huffman1.txt 中）及生成的huffman 树，查找叶子结点，当读到的是“0”时，从左孩子结点继续查找，当读到“1”时，则从右孩子结点继续查找，直到找到叶子结点，其判断语句是看一个结点的左右孩子是否为空，如果是则是，叶子结点找到，输入文件（huffman2.txt ）中，如果不是则继续查找，直到所有编码全部读完。
6.计算压缩比例算法如下： void evaluating() { float y1;y1=bitecount/8/remcount*100;cout<<"压缩比例是："<<y1<<"%"<<endl;} 三、详细设计和编码核心算法---huffman 算法： （1）根据给定的n 个权值{w1,w2,……,wn}构成n 棵二叉树的集合F={T1，T2，……,Tn},其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均空。
（2）在F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（3）在F 中删除这两棵树，同时将所得到的二叉树加入F 中。
（4）重复（2）和（3），直到F 只含一棵树为止。
这棵树便是huffman 树。
huffman 树可用于构造代码总长度最短的编码方案。
为了详细说明这个问题，特以下面例子来说明:有四个叶子结点A ，B ，C ，D ，分别带权为9，4，5，2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL （树的带权路径长度）不同，要想由n 个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。
权值越大的结点离根越近的二叉树才是最优二叉树（huffman 树）。
按照上面的算法，则可按照下面图的构造过程生成huffman 树。
Huffman 树产生流程：以一例说明ABCDACDBACDBACDB图2.哈夫曼树产生流程 Huffman 编码流程：图3.huffman 编码流程 Huffman 解码流程：fp1>>inchar;if(inchar=='1ptr=huffman[ptr].rchild ptr=huffman[ptr].lchildif(huffman[ptr].lchild==0&&huffman[ptr].lchildfp2int rem,p;int count1=0; for(int y=1;y<=count;y++)rem=y;hcode[y].c=huff[y].data; p=huffman[y].parent;while(p!=0if(huffman[p].lchild==rem)hcode[y].bits[++count1]='0';hcode[y].bits[++count1]='1';图4.huffman解码流程四、上机调试开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就是huffman 编码是采用等长编码还是采用不等长问题，采用不等长编码要避免译码的二义性或多义性。
假设用0表示字符D，用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。
因此，若对某一个字符集进行不等长编码，则要求字符集合中任一个字符的编码都不能是其他字符编码的前缀。
符合此要求的编码叫做前缀编码。
显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。
为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。
因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。
基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些变量还没有声明的错误，对遗漏的变量进行了声明后，再次调试，发现一个比较大的问题，就是字符都能读入，但是不能进行编码，也即不能构造huffman树，最后经过检查发现原来是结点方面存在问题，最后加入sum=2*count-1;语句，问题得到解决。
（该语句的作用是：例如提供了3个权值不同的结点，现在要构造huffman树，那就需要5个结点。
）五、测试结果图5（与图6同为测试结果）图6（与图5同为测试结果）被编码（部分字符）：图7.被编码后的文档被解码（部分文件）：图8.被解码后的文档六、用户使用说明用户运行本程序前，首先要在起工程文件下建立一个名字为Huffman.txt文本文档，再运行本程序后，第一步，按任意键来读取建立的 Huffman.txt文本文档,再据程序中提示完成第二步操作，也即是讲压缩的文件以Huffman编码放入一个由用户自己建立的文本文档中，接着再根据提示完成第三步操作，即对要压缩的文件解压后放入由用户建立的任意名的文本文档中，由此完成操作。
七、参考文献[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。
[2] 郑莉等.c++语言程序设计(第三版)[M].北京：清华大学出版社，2003年12月八、附录#include<iostream>#include<fstream>#include<string>#include<iomanip>using namespace std;string remfile[600000]; //存放原文件字符的数组int remcount=0; //记录元素个数float bitecount=0; //记录二进制码的个数typedef struct { //存放读入字符的类int count; //字符出现的个数char data; //字符}huffchar;int count=1; //记录huff数组中字符实际出现的个数huffchar huff[1000]; //类的对象//文件读入部分和统计字符出现的频率bool char_judge(char c){ //判断字符出现的函数for(int i=1;i<=count;i++)if(huff[i].data==c){huff[i].count++;return true;} //如果出现过，出现的频数加1return false;}void char_add(char c){ //添加新出现的字符；huff[count].data=c;huff[count++].count++; //个数增加}//文件的读取void read_file_count(){char c;ifstream infile;infile.open("huffman.txt"); //打开huffman.txt文件if(!infile){ //检查文件是否打开。
