哈夫曼实验报告(附代码).doc

哈弗曼编码/译码器 一、程序的功能分析 1．构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。 2．编码：利用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。 3．译码：将“密文”文件中的0、1代码序列进行译码。(读文件) 4．打印“密文”文件：将文件以紧凑格式显示在终端上，每行30个代码；同时，将此字符形式的编码文件保存。 5．打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。 二、基本要求分析 1、输入输出的要求 按提示内容从键盘输入命令，系统根据用户输入的需求在保证界面友好的前提下输出用户所需信息，并按要求保存文件，以便保存备份信息。 2、测试数据 （1）．令叶子结点个数N为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。 （2）．令叶子结点个数N为7，权值集合为{12,6,8,18,3,20,2}，字符集合为{A,B,C,D,E,F,G}，且字符集与权值集合一一对应。 （3）．请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。 三、概要设计 1.主模块的流程及各子模块的主要功能 主函数负责提供选项功能，循环调控整个系统。 创建模块实现接收字符、权值、构建哈夫曼树，并保存文件，此功能是后续功能的基础。 编码模块实现利用已编好的哈夫曼树对每个字符进行哈夫曼编码，即对每个字符译出其密文代码，并保存文件。 译码模块实现对用户输入的密文翻译成明文，即用户所需的字符串信息。 输出模块实现对已编好的哈夫曼树以凹入表的的形式输出。 2、模块之间的层次关系 四、详细设计 1.采用c语言定义的相关数据类型 （1）结点的类型定义描述如下： #define N 叶子结点的个数 typedef strcut {int weight; /*结点权值*/ int parent; int lchild; int rchild; }HNodeType; HNodeType HNode[2*N-1]; （2）编码的类型定义描述如下： #define MAXBIT 10 typedef struct {int bit[MAXBIT]; int start; }HCodeType; HCodeType HCode[N]; 2.各模块伪算法 （1）主函数 int main() { do: { 界面友好设计; cout各个选项功能内容; cinch; 容错处理; switch(ch) { case 1: ..... } }while(); return 0; } （2）系统初始化模块 void create() //系统初始化 { for(i=0;i2*N-1;i++) //数组HNode初始化 {}; 从键盘接收字符; for(i=0;iN;i++) { cout输入字符endl; cinHNode[i].data; } 接收权值; 构造哈夫曼树; for(i=0;iN-1;i++) { 找最小和次小两个权值； 将找出的两棵子树合并为一棵子数； } 将已建好的哈夫曼树存入文件hfmtree.txt中; 调用哈夫曼编码子函数； } void HaffmanCode() //对哈夫曼树进行编码 { 从hfmtree.txt文件中读出哈夫曼树的信息存入内存HNodeType a[2*N-1]； 求每个叶子结点的哈夫曼编码； for(i=0;iN;i++) { 从叶节点回溯，回溯到根结点（parent==-1）; 记录回溯路径； } 打印出每个字符对应的密文； 将密文信息存入文件codefile.dat中； } （3）编码模块 void HfmanCode() //对用户输入的字符串进行编码 { 提示输入信息； 接收用户输入的要编译的字符串； cins; //从文件中读取哈夫曼编码信息 infile.open (F:\\codefile.dat,ios::in|ios::binary); //读文件 for(i=0;iN;i++) //将文件中的数据读出放在temp[i]内 //从文件中读字节到指定的存储器区域。 infile.read ((char*)temp[i],sizeof(temp[