哈夫曼编码课程设计说明书.doc

目 录 一． 问题描述及分析………………………………………（03） 二． 数据结构描述………………………………………….（04） 三． 主要算法流程描述…………………………………….（05） 四． 使用说明及调试…………………………………….（15） 五． 特色及改进设想………………………………………（18） 六． 综合设计过程，做出总结…………………………..（19） 问题描述及分析 【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符 空格 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) 初始化(I)　　　2) 编码(E)　　　　3) 译码(D) ) 输出编码文件(P)　　) 退出(Q)、测试数据：用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：  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. 抽象数据类型定义为：ADT HuffmanTree{数据对象：D={ai| aiCharSet,i=1,2,……,n,? n≥0}数据关系：R={ ai-1, ai ai-1, aiD, ai-1ai ,i=2，3，……，n}基本操作P：HuffmanTree();?????? 构造函数~ HuffmanTree();???? 析构函数Initialization(int WeightNum);操作结果：构造哈夫曼树。Encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码Decoder();初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码Print()初始条件：编码文件已存在。操作结果：把已保存好的编码文件显示在屏幕2.本程序包含三个模块：1)主程序模块：void main(){??? 初始化；do{?? 接受命令；?? 处理命令；}while(“命令”=”退出”)}2)、建树模块――实现定义的抽象数据类型3)、编/译码模块――实现字符串的编/译码各模块之间的调用关系如下：??????????????????? 主程序模块???????????????????? ????????????????????建树模块????????????????? ???????????????????? ?????????????????? 编/译码模块程序名：HuffmanTree.h程序功能：赫夫曼树类的头文件(并用其来实现编/译码)#includeiostream#includefstream#includestringusing namespace std;struct HuffmanNode??????? //定义赫夫曼树各结点{?int weight;??????? //存放结点的权值，假设只考虑处理权值为整数的情况?int parent;??????? //记录结点父亲位置，-1表示为根结点，否则表示为非根结点?int lchild,rchild;?? //分别存放该结点的左、右孩子的所在单元的编号};class HuffmanTree???? //建立赫夫曼树类{private:?HuffmanNode *Nod