哈夫曼编码与译码器-数据结构课程设计报告.doc

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器 院（系）：计算机学院 专 业：计算机科学与技术 班 级学 号：2012040101082 姓 名：尹伟和 指导教师：徐蕾  此页为任务书 目 录 1. 题目分析 1 1.1. 题目重述 1 1.1.1. 系统功能需求分析 1 2. 程序设计 2 2.1. 系统功能模块说明 2 2.1.1. 系统功能模块结构 2 2.1.2. 系统模块功能说明 3 2.2. 数据结构说明 3 2.2.1. 结构体定义说明 3 2.2.2. 哈夫曼树 4 2.2.3. 字符-哈夫曼编码对照表 4 2.3. 函数说明 4 3. 算法描述 6 3.1. 哈夫曼树的构建 6 3.2. 字符-哈夫曼编码对照表 6 3.3. 编码 6 3.4. 译码 7 4. 程序测试 8 4.1. 字符集输入 8 4.2. 编码测试 9 4.3. 译码测试 10 参考文献 12 附 录（程序清单） 13 题目分析 题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。 系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下： 读取用户输入的字符集和相应字符出现的频率； 根据用户输入构建哈夫曼树； 根据哈夫曼树构建字符-哈夫曼编码对照表； 根据字符-哈夫曼编码对照表对明文字符串进行编码； 根据哈夫曼树对二进制密文进行译码。  程序设计 系统功能模块说明 根据对系统的分析，哈夫曼编码与译码器系统共分为五个功能模块，分别为：用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码模块、译码模块。 系统功能模块结构 自底向上考虑各系统功能模块之间的依赖关系，译码模块依赖于哈夫曼树构造模块，编码模块依赖于字符-哈夫曼编码对照表构造模块，字符-哈夫曼编码对照表构造模块依赖于哈夫曼编码构造模块，哈夫曼编码构造模块依赖于用户输入获取模块。 系统功能结构框图如图2-1： 图21 哈夫曼编码与译码器系统功能结构框图 系统模块功能说明 用户输入获取模块 获取并保存用户从键盘上输入的字符集和相应字符出现的频率。 哈夫曼树构造模块 根据用户输入获取模块保存的字符数据，构造哈夫曼树。 字符-哈夫曼编码对照表构造模块 根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编码对照表。 编码模块 根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对用户提供的明文进行编码。 译码模块 根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的密文字符进行译码。 数据结构说明 在程序中主要用到了二叉树和链表等数据结构。 结构体定义说明 struct _NODE结构 结构体定义如下： typedef struct _NODE{ char word; int value; _NODE *left,*right; }Node,*LPNode; 结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树。 struct _CONTAINER结构 结构体定义如下： typedef struct _CONTAINER{ LPNode v; struct _CONTAINER *last,*next; }Container,*LPContainer; 结构体用途：用于在用户输入时保存字符信息，并构成双向链表。 struct _ CODENODE结构 结构体定义如下： typedef struct _CODENODE{ char word; char code[100]; struct _CODENODE *next; }CodeNode,*LPCodeNode; 结构体用途：作为单链表的结点结构，构成字符-哈夫曼编码对照表。 哈夫曼树 在本程序中，哈夫曼树是使用struct _NODE结构构建的二叉树，其满足树的叶子结点的带全路径和在所有可能组成的二叉树中最小。 字符-哈夫曼编码对照表 在本程序中，字符-哈夫曼编码对照表是一个单链表，用于保存字符与哈夫曼编码的对应关系。 函数说明 GetInput函数 该函数的功能是读取用户输入的字符集数据，并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。 createHuffmanTree函数 该函数的功能是根据用户输入构建哈夫曼树。 createCodeList函数 该函数的功能是根据