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

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现哈夫曼编码和译码器院（系）：计算机学院专业：计算机科学与技术班级：24010102学号：2012040101082姓名：尹伟和指导教师：徐蕾沈阳航空航天大学课程设计报告I此页为任务书沈阳航空航天大学课程设计报告II目录1.题目分析...................................................................................................................11.1.题目重述............................................................................................................11.1.1.系统功能需求分析.....................................................................................12.程序设计...................................................................................................................22.1.系统功能模块说明............................................................................................22.1.1.系统功能模块结构.....................................................................................22.1.2.系统模块功能说明.....................................................................................32.2.数据结构说明....................................................................................................32.2.1.结构体定义说明.........................................................................................32.2.2.哈夫曼树.....................................................................................................42.2.3.字符-哈夫曼编码对照表............................................................................42.3.函数说明............................................................................................................43.算法描述...................................................................................................................63.1.哈夫曼树的构建................................................................................................63.2.字符-哈夫曼编码对照表...................................................................................63.3.编码....................................................................................................................63.4.译码....................................................................................................................74.程序测试...................................................................................................................94.1.字符集输入........................................................................................................94.2.编码测试..........................................................................................................104.3.译码测试...........................................................................................................11参考文献........................................................................................................................13附录（程序清单）..................................................................................................14沈阳航空航天大学课程设计报告11.题目分析1.1.题目重述本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。1.1.1.系统功能需求分析通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下：1)读取用户输入的字符集和相应字符出现的频率；2)根据用户输入构建哈夫曼树；3)根据哈夫曼树构建字符-哈夫曼编码对照表；4)根据字符-哈夫曼编码对照表对明文字符串进行编码；5)根据哈夫曼树对二进制密文进行译码。沈阳航空航天大学课程设计报告22.程序设计2.1.系统功能模块说明根据对系统的分析，哈夫曼编码与译码器系统共分为五个功能模块，分别为：用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码模块、译码模块。2.1.1.系统功能模块结构自底向上考虑各系统功能模块之间的依赖关系，译码模块依赖于哈夫曼树构造模块，编码模块依赖于字符-哈夫曼编码对照表构造模块，字符-哈夫曼编码对照表构造模块依赖于哈夫曼编码构造模块，哈夫曼编码构造模块依赖于用户输入获取模块。系统功能结构框图如图2-1：哈夫曼编码和译码器系统用户输入获取模块字符-哈夫曼编码对照表构造模块译码模块编码模块哈夫曼树构造模块图2-1哈夫曼编码与译码器系统功能结构框图沈阳航空航天大学课程设计报告32.1.2.系统模块功能说明1)用户输入获取模块获取并保存用户从键盘上输入的字符集和相应字符出现的频率。2)哈夫曼树构造模块根据用户输入获取模块保存的字符数据，构造哈夫曼树。3)字符-哈夫曼编码对照表构造模块根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编码对照表。4)编码模块根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对用户提供的明文进行编码。5)译码模块根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的密文字符进行译码。2.2.数据结构说明在程序中主要用到了二叉树和链表等数据结构。2.2.1.结构体定义说明1)struct_NODE结构结构体定义如下：typedefstruct_NODE{charword;intvalue;_NODE*left,*right;}Node,*LPNode;结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树。2)struct_CONTAINER结构沈阳航空航天大学课程设计报告4结构体定义如下：typedefstruct_CONTAINER{LPNodev;struct_CONTAINER*last,*next;}Container,*LPContainer;结构体用途：用于在用户输入时保存字符信息，并构成双向链表。3)struct_CODENODE结构结构体定义如下：typedefstruct_CODENODE{charword;charcode[100];struct_CODENODE*next;}CodeNode,*LPCodeNode;结构体用途：作为单链表的结点结构，构成字符-哈夫曼编码对照表。2.2.2.哈夫曼树在本程序中，哈夫曼树是使用struct_NODE结构构建的二叉树，其满足树的叶子结点的带全路径和在所有可能组成的二叉树中最小。2.2.3.字符-哈夫曼编码对照表在本程序中，字符-哈夫曼编码对照表是一个单链表，用于保存字符与哈夫曼编码的对应关系。2.3.函数说明1)GetInput函数该函数的功能是读取用户输入的字符集数据，并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。2)createHuffmanTree函数该函数的功能是根据用户输入构建哈夫曼树。沈阳航空航天大学课程设计报告53)createCodeList函数该函数的功能是根据哈夫曼树构建与之对应的字符-哈夫曼编码对照表。4)code函数该函数用于实现编码功能。5)uncode函数该函数用于实现译码功能。沈阳航空航天大学课程设计报告63.算法描述3.1.哈夫曼树的构建在本程序中，GetInput函数首先将用户输入的每个字符信息储存到struct_NODE结构中看做是哈夫曼树的叶子结点，并将struct_NODE结构的地址储存到struct_CONTAINER结构中，按字符出现频率升序插入到双向链表中，然后调用createHuffmanTree函数构造哈夫曼树。在构造哈夫曼树的过程中，首先从双向链表中选取字符出现频率最小和第二小的结点，从中提取哈夫曼树的子树，将两个子树合并成一个子树，再将父节点的地址存入struct_CONTAINER结构中，并插入到双向链表中。重复此步骤直到链表中只剩下一个结点。这样该struct_CONTAINER结构中存储的struct_NODE类型的指针就指向要得到哈夫曼树的根节点了。3.2.字符-哈夫曼编码对照表用深度优先搜索的方法递归的遍历哈夫曼树，展开的过程中向调用的递归函数传递要访问的结点的哈夫曼编码。当访问叶子结点时，从结点中提取字符信息，并和其哈夫曼编码一同储存到struct_CODENODE结构中，然后将struct_CODENODE结构插入到单链表中。如此，当遍历完成时，字符-哈夫曼编码对照表便构造完成了。3.3.编码从源文件中读取一个字符，在字符-哈夫曼编码对照表中查找该