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

沈阳航空沈阳航空航天大学航天大学课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：实现哈夫曼编码和译码器实现哈夫曼编码和译码器院（系）：计算机学院专 业：计算机科学与技术班 级：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.程序测试程序测试.84.1.字符集输入.84.2.编码测试.94.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 _NODEchar word;int value;_NODE*left,*right;Node,*LPNode;结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树。2)struct _CONTAINER 结构沈阳航空航天大学课程设计报告 4 结构体定义如下：typedef struct _CONTAINERLPNode v;struct _CONTAINER*last,*next;Container,*LPContainer;结构体用途：用于在用户输入时保存字符信息，并构成双向链表。3)struct _ CODENODE 结构结构体定义如下：typedef struct _CODENODEchar 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 开始从双向链表中提取字符出现频率最小的两棵子树双向链表中只有一个节点合并两棵子树将子树储存并插入双向链表提取哈夫曼树结束NY开始t!=EOF在字符-哈弗曼编码对照表中查找t结束NY从源文件中读取字符t从源文件中读取字符t向目标文件中输出t的哈夫曼编码图 3-1 构建哈夫曼树流程图 图 3-2 编码流程图3.4.译码译码从源文件中读取字符，按照字符的指示访问哈夫曼树的子树，即从根节点出发，若读取到0则访问左子树，若读取到1则访问右子树，知道子树为哈夫曼树的叶子结点为止，此时向目标文件中输出结点中的字符。沈阳航空航天大学课程设计报告 8 开始t=0p指向p的左子树结束NY从源文件中读取字符t从源文件中输出字符p所指向结点中的字符p指向树根p指向p的右子树t!=EOFp指向叶子结点YN图 3-3 译码流程图沈阳航空航天大学课程设计报告 9 4.程序测试4.1.字符集输入字符集输入输入的字符集及字符出现频率如表 4-1 所示：表 4-1 字符集输入用例字符abc出现频率1035预计生成字符-哈夫曼编码对照如表 4-2 所示：表 4-2 字符-哈夫曼编码对照表字符abc哈夫曼编码10001程序运行效果如图 4-1 所示：图 4-1 程序运行效果图沈阳航空航天大学课程设计报告 10 4.2.编码测试编码测试运行程序编码模块，如图 4-2 所示：图 4-2 程序运行编码模块效果图程序编码输入文件如图 4-3 所示：图 4-3 程序编码输入文件截图输出分析如表 4-3 所示：表 4-3 编码输出分析abcbcaacb100010001110100沈阳航空航天大学课程设计报告 11 程序编码输入文件如图 4-4 所示：图 4-4 程序编码输出文件截图4.3.译码测试译码测试将编码后的文件逆向输入进行译码。运行程序译码模块，如图 4-5 所示：图 4-5 程序运行译码模块效果图程序译码输入文件如图 4-6 所示：沈阳航空航天大学课程设计报告 12 图 4-6 程序译码输入文件截图程序译码输出文件如图 4-7 所示：图 4-7 程序译码输出文件截图沈阳航空航天大学课程设计报告 13 参考文献1 严蔚敏,吴伟民.数据结构(C 语言版)M.北京:清华大学出版社,20062 吕国英.算法设计与分析M.北京:清华大学出版社,20063 徐宝文,李志.C 程序设计语言M.北京:机械工业出版社,20044 Erich Gamma,Richaed Helm.设计模式(英文版)M.北京:机械工业出版社,2004沈阳航空航天大学课程设计报告 14 附 录（程序清单）#include#include#include typedef struct _NODEchar word;int value;_NODE*left,*right;Node,*LPNode;typedef struct _CONTAINERLPNode v;struct _CONTAINER*last,*next;Container,*LPContainer;typedef struct _CODENODEchar 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,&num);list.v=(LPNode)malloc(sizeof(Node);list.v-word=-1;list.v-value=0;list.v-left=list.v-rightNULL;list.next=&list;list.last=&list;for(i=0;iv=(LPNode)malloc(sizeof(Node);p-v-left=p-v-right=NULL;getchar();printf(输入字符：);沈阳航空航天大学课程设计报告 17 scanf(%c,&p-v-word);printf(输入该字符的权值：);scanf(%d,&p-v-value);insert(&list,p);printf(正在构造哈夫曼树n);head=createHuffmanTree(&list);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(tright,r,list);LPCodeNode createCodeList(LPNode tree)CodeNode head;head.next=NULL;dfs(tree,&head);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);dfp=fopen(path,wt);p=tree;while(c=fgetc(sfp)!=EOF)if(c=0)p=p-left;elsep=p-right;if(p-word!=-1)fputc(p-word,dfp);p=tree;fclose(sfp);沈阳航空航天大学课程设计报告 20 fclose(dfp);void main()LPNode tree=NULL;LPCodeNode list=NULL;int t;while(1)printf(n1.输入字符集n2.编码n3.解码n4.退出n);scanf(%d,&t);switch(t)case 1:tree=GetInput();list=createCodeList(tree);break;case 2:code(list);break;case 3:uncode(tree);break;case 4:exit(0);沈阳航空航天大学课程设计报告 21 课程设计总结：课程设计总结：通过此次课程设计，是我在数据结构的设计和算法设计等方面有了进一步的提高。关于数据结构方面，我对于链表和树结构的理解更加深刻，链表的建立、遍历、插入等操作；树的建立、遍历等操作更加熟练，已可以运用自如。关于算法方面，我对于插入排序，深度优先搜索等算法，已理解其原理，并能熟练编写。同时，我还深刻认识到，就我们计算机专业的学生来说，只是掌握经典的算法和数据结构是远远不够的。我们要深刻发掘创新能力，培养创新思维，只有这样我们才能在编程解决实际问题的道路上走的更远。指导教师评语：指导教师(签字)：年 月 日课程设计成绩