《数据结构》课程设计报告。
设计题目：哈夫曼编/译码器。
2024年 12 月 30 日
哈夫曼编码是根据字符的使用率的高低对字符进行不等长的编码，从而使使用率高的字符占用较少的空间，从而在传输的过程中大大提高了数据的空间传输效率。本设计采用二叉链表的存储结构，建立哈夫曼树；用递归调用的方式对哈夫曼树的节点进行编码，生成与字符对应的哈夫曼编码。本设计完全采用c++语言进行编程，并在xcode 6编译器上调试运行通过。
本程序使用中文界面，并有相应的提示信息，便于操作和程序运行。
关键词：哈夫曼树；哈夫曼编码；递归调用；二叉链表。
huffman 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, it 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
1、问题描述：
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。
2、基本要求：
一个完整的系统应具有以下功能：
1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。
2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。
3）译码。利用已建好的哈夫曼树将文件中的**进行译码，结果存入文件中。
4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。
5）计算平均编码长度。
2.1 设计目标。
一个完整的系统应具有以下功能：
1）初始化（initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。输出哈夫曼树，及各字符对应的编码。
2）输入（input）。从终端读入需要编码的字符串s，将字符串s存入文件中。
3）编码（encode）与译码（decode）。
编码（encode）。利用已建好的哈夫曼树（如不在内存，则从文件 中读入），对文件中的正文进行编码，然后将结果存入文件中。
译码（decode）。利用已建好的哈夫曼树将文件中的**进行译码，结果存入文件textfile中。
输出编码文件（print）。将编码显示在终端上。同时将此字符形式的编码写入文件中。
4）打印哈夫曼树（tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件中。
5）计算编码平均长度。计算编码平均长度，并显示在屏幕上。
2.2 设计思想。
哈夫曼编码(huffman coding)是一种编码方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这种方法是由发展起来的。
例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。
二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
3.1程序结构。
3.2 初始化算法：
程序从文件中获取26个英文字母以及对应的权值。
3.3 编码算法：
1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值构成n棵二叉树的集合f=把它们保存到结构体数组ht[n]中，其中。
void huffmantree建立哈夫曼树。
void initialization初始化程序。
void printhuffman(element h,element hh, int n); 打印哈夫曼树。
void huffmancode生成哈夫曼编码。
void printcode打印哈夫曼编码。
void filecode文件输出哈夫曼编码。
void filehuffman(element h,element hh, int n); 文件输出哈夫曼树。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...