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

沈阳航空沈阳航空航天大学航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：实现哈夫曼编码和译码器实现哈夫曼编码和译码器 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号：82 姓 名：尹伟和 指导教师：徐蕾 沈阳航空航天大学课程设计报告 I 此页为任务书 沈阳航空航天大学课程设计报告 II 目目 录录 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 沈阳航空航天大学课程设计报告 1 1. 题目分析 1.1. 题目重述题目重述 本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码 器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进 行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使 明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码， 使二进制密文变为字符明文。 1.1.1. 系统功能需求分析系统功能需求分析 通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需 求如下： 1) 读取用户输入的字符集和相应字符出现的频率； 2) 根据用户输入构建哈夫曼树； 3) 根据哈夫曼树构建字符-哈夫曼编码对照表； 4) 根据字符-哈夫曼编码对照表对明文字符串进行编码； 5) 根据哈夫曼树对二进制密文进行译码。 沈阳航空航天大学课程设计报告 2 程序设计 2.1. 系统功能模块说明系统功能模块说明 根据对系统的分析，哈夫曼编码与译码器系统共分为五个功能模块，分别为： 用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码 模块、译码模块。 2.1.1. 系统功能模块结构系统功能模块结构 自底向上考虑各系统功能模块之间的依赖关系，译码模块依赖于哈夫曼树构 造模块，编码模块依赖于字符-哈夫曼编码对照表构造模块，字符-哈夫曼编码对 照表构造模块依赖于哈夫曼编码构造模块，哈夫曼编码构造模块依赖于用户输入 获取模块。 系统功能结构框图如图 2-1： 哈夫曼编码和译码器系统 用户输入获取模块 字符-哈夫曼编码对照表构造模块 译码模块 编码模块 哈夫曼树构造模块 图 2-1 哈夫曼编码与译码器系统功能结构框图 沈阳航空航天大学课程设计报告 3 系统模块功能说明系统模块功能说明 1) 用户输入获取模块 获取并保存用户从键盘上输入的字符集和相应字符出现的频率。 2) 哈夫曼树构造模块 根据用户输入获取模块保存的字符数据，构造哈夫曼树。 3) 字符-哈夫曼编码对照表构造模块 根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编码对照表。 4) 编码模块 根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对 用户提供的明文进行编码。 5) 译码模块 根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的密文字符进行译 码。 2.2. 数据结构说明数据结构说明 在程序中主要用到了二叉树和链表等数据结构。 2.2.1. 结构体定义说明结构体定义说明 1) struct _NODE 结构 结构体定义如下： typedef struct _NODE char word; int value; _NODE *left,*right; Node,*LPNode; 结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树。 2) struct _CONTAINER 结构 沈阳航空航天大学课程设计报告 4 结构体定义如下： typedef struct _CONTAINER LPNode v; struct _CONTAINER *last,*next; Container,*LPContainer; 结构体用途：用于在用户输入时保存字符信息，并构成双向链表。 3) struct _ CODENODE 结构 结构体定义如下： typedef struct _CODENODE char word; char code100; struct _CODENODE *next; CodeNode,*LPCodeNode; 结构体用途：作为单链表的结点结构，构成字符-哈夫曼编码对照表。 2.2.2. 哈夫曼树哈夫曼树 在本程序中，哈夫曼树是使用 struct _NODE 结构构建的二叉树，其满足树的 叶子结点的带全路径和在所有可能组成的二叉树中最小。 2.2.3. 字符字符-哈夫曼编码对照表哈夫曼编码对照表 在本程序中，字符-哈夫曼编码对照表是一个单链表，用于保存字符与哈夫曼 编码的对应关系。 2.3. 函数说明函数说明 1) GetInput 函数 该函数的功能是读取用户输入的字符集数据，并构建相应的哈夫曼树。 函数的返回值是哈夫曼树的指针。 2) createHuffmanTree 函数 该函数的功能是根据用户输入构建哈夫曼树。 沈阳航空航天大学课程设计报告 5 3) createCodeList 函数 该函数的功能是根据哈夫曼树构建与之对应的字符-哈夫曼编码对照表。 4) code 函数 该函数用于实现编码功能。 5) uncode 函数 该函数用于实现译码功能。 沈阳航空航天大学课程设计报告 6 3. 算法描述 3.1. 哈夫曼树的构建哈夫曼树的构建 在本程序中，GetInput 函数首先将用户输入的每个字符信息储存到 struct _NODE 结构中看做是哈夫曼树的叶子结点，并将 struct _NODE 结构的地址储存 到 struct _CONTAINER 结构中，按字符出现频率升序插入到双向链表中，然后调 用 createHuffmanTree 函数构造哈夫曼树。 在构造哈夫曼树的过程中，首先从双向链表中选取字符出现频率最小和第二 小的结点，从中提取哈夫曼树的子树，将两个子树合并成一个子树，再将父节点 的地址存入 struct _CONTAINER 结构中，并插入到双向链表中。 重复此步骤直到链表中只剩下一个结点。这样该 struct _CONTAINER 结构中 存储的 struct _NODE 类型的指针就指向要得到哈夫曼树的根节点了。 3.2. 字符字符-哈夫曼编码对照表哈夫曼编码对照表 用深度优先搜索的方法递归的遍历哈夫曼树，展开的过程中向调用的递归函 数传递要访问的结点的哈夫曼编码。当访问叶子结点时，从结点中提取字符信息， 并和其哈夫曼编码一同储存到 struct _ CODENODE 结构中，然后将 struct _ CODENODE 结构插入到单链表中。 如此，当遍历完成时，字符-哈夫曼编码对照表便构造完成了。 3.3. 编码编码 从源文件中读取一个字符，在字符-哈夫曼编码对照表中查找该字符，将查找 到的结点中储存的哈夫曼编码写入到目标文件中。 沈阳航空航天大学课程设计报告 7 开始 从双向链表中提取 字符出现频率最小 的两棵子树 双向链表中只 有一个节点 合并两棵子树 将子树储存并插入双 向链表 提取哈夫曼树 结束 N Y 开始 t!=EOF 在字符-哈弗曼编码 对照表中查找t 结束 N Y 从源文件中读取字 符t 从源文件中读取字 符t 向目标文件中输出t 的哈夫曼编码 图 3-1 构建哈夫曼树流程图 图 3-2 编码流程图 3.4. 译码译码 从源文件中读取字符，按照字符的指示访问哈夫曼树的子树，即从根节点出 发，若读取到0则访问左子树，若读取到1则访问右子树，知道子树为哈 夫曼树的叶子结点为止，此时向目标文件中输出结点中的字符。 沈阳航空航天大学课程设计报告 8 开始 t=0 p指向p的左子树 结束 N Y 从源文件中读取字 符t 从源文件中输出字符p 所指向结点中的字符 p指向树根 p指向p的右子树 t!=EOF p指向叶子结点 Y N 图 3-3 译码流程图 沈阳航空航天大学课程设计报告 wk 9 4. 程序测试 4.1. 字符集输入字符集输入 输入的字符集及字符出现频率如表 4-1 所示： 表 4-1 字符集输入用例 字符abc 出现频率1035 预计生成字符-哈夫曼编码对照如表 4-2 所示： 表 4-2 字符-哈夫曼编码对照表 字符abc 哈夫曼编码10001 程序运行效果如图 4-1 所示： 图 4-1 程序运行效果图 沈阳航空航天大学课程设计报告 wk 10 4.2. 编码测试编码测试 运行程序编码模块，如图 4-2 所示： 图 4-2 程序运行编码模块效果图 程序编码输入文件如图 4-3 所示： 图 4-3 程序编码输入文件截图 输出分析如表 4-3 所示： 表 4-3 编码输出分析 abcbcaacb 100010001110100 沈阳航空航天大学课程设计报告 wk 11 程序编码输入文件如图 4-4 所示： 图 4-4 程序编码输出文件截图 4.3. 译码测试译码测试 将编码后的文件逆向输入进行译码。 运行程序译码模块，如图 4-5 所示： 图 4-5 程序运行译码模块效果图 程序译码输入文件如图 4-6 所示： 沈阳航空航天大学课程设计报告 wk 12 图 4-6 程序译码输入文件截图 程序译码输出文件如图 4-7 所示： 图 4-7 程序译码输出文件截图 沈阳航空航天大学课程设计报告 wk 13 参考文献 1 严蔚敏,吴伟民.数据结构(C 语言版)M.北京:清华大学出版社,2006 2 吕国英.算法设计与分析M.北京:清华大学出版社,2006 3 徐宝文,李志.C 程序设计语言M.北京:机械工业出版社,2004 4 Erich Gamma,Richaed Helm.设计模式(英文版)M.北京:机械工业出版社,2004 沈阳航空航天大学课程设计报告 14 附 录（程序清单） #include #include #include typedef struct _NODE char word; int value; _NODE *left,*right; Node,*LPNode; typedef struct _CONTAINER LPNode v; struct _CONTAINER *last,*next; Container,*LPContainer; typedef struct _CODENODE char word; char code100; struct _CODENODE *next; CodeNode,*LPCodeNode; void insert(LPContainer list,LPContainer node) LPContainer p; p=list-last; while(node-v-valuev-value) p=p-last; 沈阳航空航天大学课程设计报告 15 node-last=p; node-next=p-next; p-next-last=node; p-next=node; LPNode createHuffmanTree(LPContainer list) LPContainer p; LPNode left,right,t; while(list-next!=list-last) p=list-next; list-next=p-next; left=p-v; free(p); p=list-next; list-next=p-next; list-next-last=list; right=p-v; t=(LPNode)malloc(sizeof(Node); t-word=-1; t-value=left-value+right-value; t-left=left; t-right=right; p-v=t; insert(list,p); 沈阳航空航天大学课程设计报告 16 p=list-next; list-next=p-next; list-next-last=list; left=p-v; free(p); return left; LPNode GetInput() Container list; LPContainer p; LPNode head; int i,num; printf(输入字符集规模：); scanf(%d, list.v=(LPNode)malloc(sizeof(Node); list.v-word=-1; list.v-value=0; list.v-left=list.v-right=NULL; list.next= list.last= for(i=0;iv=(LPNode)malloc(sizeof(Node); p-v-left=p-v-right=NULL; getchar(); printf(输入字符：); 沈阳航空航天大学课程设计报告 17 scanf(%c, printf(输入该字符的权值：); scanf(%d, insert( printf(正在构造哈夫曼树n); head=createHuffmanTree( printf(哈夫曼树创建成功!n); free(list.v); return head; void dfs(LPNode t,char *code,LPCodeNode list) LPCodeNode p; char l100,r100; if(t-word!=-1) p=(LPCodeNode)malloc(sizeof(CodeNode); p-word=t-word; strcpy(p-code,code); p-next=list-next; list-next=p; return; strcpy(l,code); strcat(l,0); dfs(t-left,l,list); strcpy(r,code); 沈阳航空航天大学课程设计报告 18 strcat(r,1); dfs(t-right,r,list); LPCodeNode createCodeList(LPNode tree) CodeNode head; head.next=NULL; dfs(tree, return head.next; void code(LPCodeNode list) FILE *sfp,*dfp; char path256,c; LPCodeNode p; printf(请输入源文件路径：); scanf(%s,path); sfp=fopen(path,rt); printf(请输入目标文件路径：); scanf(%s,path); dfp=fopen(path,wt); while(c=fgetc(sfp)!=EOF) p=list; while(p-word!=c) p=p-next; fputs(p-code,dfp); 沈阳航空航天大学课程设计报告 19 fclose(sfp); fclose(dfp); void uncode(LPNode tree) FILE *sfp,*dfp; char path256,c; LPNode p; printf(请输入源文件路径：); scanf(%s,path); sfp=fopen(path,rt); printf(请输入目标文件路径：); scanf(%s,path)