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

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现哈夫曼编码和译码器院（系）：计算机学院专业：计算机科学与技术班级：24010102学号：2姓名：尹伟和指导教师：徐蕾此页为任务书

目录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题目分析题目重述本次课程设计的目的是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码，使二进制密文变为字符明文。系统功能需求分析通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需求如下：读取用户输入的字符集和相应字符出现的频率；根据用户输入构建哈夫曼树；根据哈夫曼树构建字符-哈夫曼编码对照表；根据字符-哈夫曼编码对照表对明文字符串进行编码；根据哈夫曼树对二进制密文进行译码。程序设计系统功能模块说明根据对系统的分析，哈夫曼编码与译码器系统共分为五个功能模块，分别为：用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码模块、译码模块。系统功能模块结构自底向上考虑各系统功能模块之间的依赖关系，译码模块依赖于哈夫曼树构造模块，编码模块依赖于字符-哈夫曼编码对照表构造模块，字符-哈夫曼编码对照表构造模块依赖于哈夫曼编码构造模块，哈夫曼编码构造模块依赖于用户输入获取模块。系统功能结构框图如图2-1：图STYLEREF1\s2SEQ图\*ARABIC\s11哈夫曼编码与译码器系统功能结构框图系统模块功能说明用户输入获取模块获取并保存用户从键盘上输入的字符集和相应字符出现的频率。哈夫曼树构造模块根据用户输入获取模块保存的字符数据，构造哈夫曼树。字符-哈夫曼编码对照表构造模块根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编码对照表。编码模块根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对用户提供的明文进行编码。译码模块根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的密文字符进行译码。数据结构说明在程序中重要用到了二叉树和链表等数据结构。结构体定义说明struct_NODE结构结构体定义如下：typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode; 结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树。struct_CONTAINER结构结构体定义如下：typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer; 结构体用途：用于在用户输入时保存字符信息，并构成双向链表。struct_CODENODE结构结构体定义如下：typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode; 结构体用途：作为单链表的结点结构，构成字符-哈夫曼编码对照表。哈夫曼树在本程序中，哈夫曼树是使用struct_NODE结构构建的二叉树，其满足树的叶子结点的带全途径和在所有也许组成的二叉树中最小。字符-哈夫曼编码对照表在本程序中，字符-哈夫曼编码对照表是一个单链表，用于保存字符与哈夫曼编码的相应关系。函数说明GetInput函数该函数的功能是读取用户输入的字符集数据，并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。createHuffmanTree函数该函数的功能是根据用户输入构建哈夫曼树。createCodeList函数该函数的功能是根据哈夫曼树构建与之相应的字符-哈夫曼编码对照表。code函数该函数用于实现编码功能。uncode函数该函数用于实现译码功能。

算法描述哈夫曼树的构建在本程序中，GetInput函数一方面将用户输入的每个字符信息储存到struct_NODE结构中看做是哈夫曼树的叶子结点，并将struct_NODE结构的地址储存到struct_CONTAINER结构中，按字符出现频率升序插入到双向链表中，然后调用createHuffmanTree函数构造哈夫曼树。在构造哈夫曼树的过程中，一方面从双向链表中选取字符出现频率最小和第二小的结点，从中提取哈夫曼树的子树，将两个子树合并成一个子树，再将父节点的地址存入struct_CONTAINER结构中，并插入到双向链表中。反复此环节直到链表中只剩下一个结点。这样该struct_CONTAINER结构中存储的struct_NODE类型的指针就指向要得到哈夫曼树的根节点了。字符-哈夫曼编码对照表用深度优先搜索的方法递归的遍历哈夫曼树，展开的过程中向调用的递归函数传递要访问的结点的哈夫曼编码。当访问叶子结点时，从结点中提取字符信息，并和其哈夫曼编码一同储存到struct_CODENODE结构中，然后将struct_CODENODE结构插入到单链表中。如此，当遍历完毕时，字符-哈夫曼编码对照表便构造完毕了。编码从源文献中读取一个字符，在字符-哈夫曼编码对照表中查找该字符，将查找到的结点中储存的哈夫曼编码写入到目的文献中。图STYLEREF1\s31构建哈夫曼树流程图图STYLEREF1\s32编码流程图译码从源文献中读取字符，按照字符的指示访问哈夫曼树的子树，即从根节点出发，若读取到‘0’则访问左子树，若读取到‘1’则访问右子树，知道子树为哈夫曼树的叶子结点为止，此时向目的文献中输出结点中的字符。图STYLEREF1\s33译码流程图程序测试字符集输入输入的字符集及字符出现频率如表4-1所示：表STYLEREF1\s4SEQ表\*ARABIC\s11字符集输入用例字符abc出现频率1035预计生成字符-哈夫曼编码对照如表4-2所示：表STYLEREF1\s4SEQ表\*ARABIC\s12字符-哈夫曼编码对照表字符abc哈夫曼编码10001程序运营效果如图4-1所示：图STYLEREF1\s4SEQ图\*ARABIC\s11程序运营效果图编码测试运营程序编码模块，如图4-2所示：图STYLEREF1\s4SEQ图\*ARABIC\s12程序运营编码模块效果图程序编码输入文献如图4-3所示：图STYLEREF1\s4SEQ图\*ARABIC\s13程序编码输入文献截图输出分析如表4-3所示：表STYLEREF1\s4SEQ表\*ARABIC\s13编码输出分析abcbcaacb100010001110100程序编码输入文献如图4-4所示：图STYLEREF1\s4SEQ图\*ARABIC\s14程序编码输出文献截图译码测试将编码后的文献逆向输入进行译码。运营程序译码模块，如图4-5所示：图STYLEREF1\s4SEQ图\*ARABIC\s15程序运营译码模块效果图程序译码输入文献如图4-6所示：图STYLEREF1\s4SEQ图\*ARABIC\s16程序译码输入文献截图程序译码输出文献如图4-7所示：图STYLEREF1\s4SEQ图\*ARABIC\s17程序译码输出文献截图参考文献[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2023[2]吕国英.算法设计与分析[M].北京:清华大学出版社,2023[3]徐宝文,李志.C程序设计语言[M].北京:机械工业出版社,2023[4]ErichGamma,RichaedHelm.设计模式(英文版)[M].北京:机械工业出版社,2023附录（程序清单）#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode;typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer;typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode;voidinsert(LPContainerlist,LPContainernode){ LPContainerp; p=list->last; while(node->v->value<p->v->value) { p=p->last; } node->last=p; node->next=p->next; p->next->last=node; p->next=node;}LPNodecreateHuffmanTree(LPContainerlist){ LPContainerp; LPNodeleft,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); } p=list->next; list->next=p->next; list->next->last=list; left=p->v; free(p); returnleft;}LPNodeGetInput(){ Containerlist; LPContainerp; LPNodehead; inti,num; printf("输入字符集规模："); scanf("%d",&num); list.v=(LPNode)malloc(sizeof(Node)); list.v->word=-1; list.v->value=0; list.v->left=list.v->right=NULL; list.next=&list; list.last=&list; for(i=0;i<num;i++) { p=(LPContainer)malloc(sizeof(Container)); p->v=(LPNode)malloc(sizeof(Node)); p->v->left=p->v->right=NULL; getchar(); printf("输入字符："); scanf("%c",&p->v->word); printf("输入该字符的权值："); scanf("%d",&p->v->value); insert(&list,p); } printf("正在构造哈夫曼树……\n"); head=createHuffmanTree(&list); printf("哈夫曼树创建成功!\n"); free(list.v); returnhead;}voiddfs(LPNodet,char*code,LPCodeNodelist){ LPCodeNodep; charl[100],r[100]; 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); strcat(r,"1"); dfs(t->right,r,list);}LPCodeNodecreateCodeList(LPNodetree){ CodeNodehead; head.next=NULL; dfs(tree,"",&head); returnhead.next;}voidcode(LPCodeNodelist){ FILE*sfp,*dfp; charpath[256],c; LPCodeNodep; 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); } fclose(sfp); fclose(dfp);}voiduncode(LPNodetree){ FILE*sfp,*dfp; charpath[256],c; LPNodep; printf("请输入源文献途径："); scanf("%s",path); sfp=fopen(path,"rt"); printf("请输入目的文献途径："); scanf("%s",path);