哈夫曼编译器

1、沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计 课程设计题目：哈夫曼编码和译码器院（系）：计算机学院专 业：计算机科学与技术班 级：24010101学 号：2012040101034姓 名：赵文焕指导教师：许清沈阳航空航天大学课程设计报告目 录1 .题目分析11.1. 需求概述11.2. 系统功能需求分析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. 哈夫曼

2、树的构建63.2. 字符-哈夫曼编码对照表63.3. 编码63.4. 译码74 .程序测试94.1. 字符集输入94.2. 编码测试104.3. 译码测试. 画图演示13参考文献14附 录（程序清单）15i沈阳航空航天大学课程设计报告1 .题目分析1.1. 需求概述本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码 器需要根据用户输入的字符集及相应字符出现的频率，对字符集所包含的字符进 行哈夫曼编码。同时，作为编码器需要其对用户提供的明文字符串进行编码，使 明文字符串变为二进制密文；作为译码器需要对用户提供的二进制密文进行译码, 使二进制密文变为字符明文。1.2.

3、 系统功能需求分析通过对课程设计的题目分析，可以得出哈夫曼编码和译码器的功能需求，需 求如下：1）读取用户输入的字符集和相应字符出现的频率；2）根据用户输入构建哈夫曼树；3）根据哈夫曼树构建字符-哈夫曼编码对照表；4）根据字符-哈夫曼编码对照表对明文字符串进行编码；5）根据哈夫曼树对二进制密文进行译码。82 .程序设计2.1. 系统功能模块说明根据对系统的分析，哈夫曼编码与译码器系统共分为五个功能模块， 分别为: 用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码 模块、译码模块。2.1.1. 系统功能模块结构自底向上考虑各系统功能模块之间的依赖关系，译码模块依赖于哈夫曼

4、树构 造模块，编码模块依赖于字符-哈夫曼编码对照表构造模块，字符-哈夫曼编码对 照表构造模块依赖于哈夫曼编码构造模块，哈夫曼编码构造模块依赖于用户输入 获取模块。系统功能结构框图如图2-1:哈夫曼编码和译码器系统用户输入获取模块哈夫曼树构造模块字符哈夫曼编码对照表构造模块编码模块译码模块图2-1哈夫曼编码与译码器系统功能结构框图2.1.2. 系统模块功能说明2.1.3. 获取模块获取并保存用户从键盘上输入的字符集和相应字符出现的频率。2.1.4. 构造模块根据用户输入获取模块保存的字符数据，构造哈夫曼树。2.1.5. 夫曼编码对照表构造模块根据哈夫曼树构造模块构造的哈夫曼树，建立字符-哈夫曼编

5、码对照表。2.1.6.根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表，对 用户提供的明文进行编码。2.1.7.根据哈夫曼树构造模块构造的哈夫曼树，对用户提供的密文字符进行译码。2.2. 数据结构说明在程序中主要用到了二叉树和链表等数据结构2.2.1. 结构体定义说明1) struct _node 结构结构体定义如下：typedef struct _node char word;int value;_node *left,*right;node,*lpnode;结构体用途：作为哈夫曼树的结点结构，构成哈夫曼树2) struct .container 结构结构体定义如下：typed

6、ef 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

7、结构构建的二叉树，具满足树的 叶子结点的带全路径和在所有可能组成的二叉树中最小。2.2.3. 字符-哈夫曼编码对照表在本程序中,字符-哈夫曼编码对照表是一个单链表，用于保存字符与哈夫曼 编码的对应关系。2.3. 函数说明1) getinput 函数函数声明：lpnode getinput();参数声明：无参数。返回值说明：返回创建的哈夫曼树指针。函数功能：该函数的功能是读取用户输入的字符集数据，并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。2) createhuffmantree 函数函数声明：lpnode createhuffmantree(lpcontainer list);参数说明

8、：list:用来构建哈夫曼树的数据链表。返回值说明：返回构建的哈夫曼树。函数功能：该函数的功能是根据用户输入构建哈夫曼树。3) createcodelist 函数函数声明：lpcodenode createcodelist(lpnode tree);参数说明：tree:哈夫曼树。返回值说明：返回字符-哈夫曼编码对照表。函数功能：该函数的功能是根据哈夫曼树构建与之对应的字符-哈夫曼编码对照表。4) code函数函数声明：void code(lpcodenode list);参数说明：list:字符-哈夫曼编码对照表。返回值说明：无返回值。函数功能：该函数用于实现编码功能。5) uncode函数函

9、数声明：void uncode(lpnode tree);参数声明：tree:哈夫曼树。返回值说明：无返回值。函数功能：该函数用于实现译码功能。3 .算法描述3.1. 哈夫曼树的构建在本程序中，getinput函数首先将用户输入的每个字符信息储存到struct_node结构中看做是哈夫曼树的叶子结点，并将 struct _node结构的地址储存 至ij struct .container结构中，按字符出现频率升序插入到双向链表中，然后调 用createhuffmantree函数构造哈夫曼树。在构造哈夫曼树的过程中，首先从双向链表中选取字符出现频率最小和第二 小的结点，从中提取哈夫曼树的子树，将

10、两个子树合并成一个子树，再将父节点 的地址存入struct .container结构中，并插入到双向链表中。重复此步骤直到链表中只剩下一个结点。这样该struct .container结构中 存储的struct _node类型的指针就指向要得到哈夫曼树的根节点了。3.2. 字符-哈夫曼编码对照表用深度优先搜索的方法递归的遍历哈夫曼树，展开的过程中向调用的递归函 数传递要访问的结点的哈夫曼编码。当访问叶子结点时，从结点中提取字符信息， 并和其哈夫曼编码一同储存到struct _ codenode结构中，然后将 struct _codenode结构插入到单链表中。如此，当遍历完成时，字符-哈夫曼编

11、码对照表便构造完成了。3.3. 编码从源文件中读取一个字符，在字符-哈夫曼编码对照表中查找该字符， 将查找 到的结点中储存的哈夫曼编码写入到目标文件中。提取哈夫曼树n结束图3-2编码流程图开始图3-1构建哈夫曼树流程图3.4. 译码从源文件中读取字符，按照字符的指示访问哈夫曼树的子树，即从根节点出 发，若读取到0则访问左子树，若读取到1则访问右子树，知道子树为哈 夫曼树的叶子结点为止，此时向目标文件中输出结点中的字符。沈阳航空航天大学课程设计报告错误！未指定书签。114.程序测试4.1. 字符集输入输入的字符集及字符出现频率如表 4-1所示:字符abc出现频率123表4-1字符集输入用例程序运

12、行效果如图4-1所示:c:user?小而山由23庆5灶叶津中哈云妄舟:摩西酋一exewwwwwtilfwwwwtnrwwwwwwwwwwwwwwwwwwutiirwwwwirtirwwwww*哈夫曼编/译器*i3正哈_3 s t 1 th * :值值功 :模权权权日焉 码规长的b的匕的夫建. 5字符-子符一子造树 a?m 赞人人人人人人在夫符l哈夫曼编码对照表11io一一 9图4-1程序运行效果图4.2. 编码测试运行程序编码模块，如图4-2所示:uu $ &rjad mini5tr3tordes kttjp课途哈夫昼编任声ssexemkmmmmmmmmmmmmmmmkkmmmkmmmmmmm

13、kmmhkmmkmmmmkm. m m m. m mm m. m哈夫曼编，译器操源目人入入土呈月音- -请输入操作图:图4-2程序运行编码模块效果图程序编码输入文件如图4-3所示：l.txt - 本| c 文件 姆酶揩式3 查看s 耙的时_aaabbbbbcc图4-3程序编码输入文件截图输出分析如表4-3所示:表4-2编码输出分析abcbcaacb100010001110100程序编码输出文件如图4-4所示:文阳月五审同格式查看m 理团旧） |101010111111111100图4-4程序编码输出文件截图4.3. 译码测试将编码后的文件逆向输入进行译码。运行程序译码模块，如图4-5所示：沈阳

14、航空航天大学课程设计报告错误！未指定书签。图4-6程序译码输入文件截图12图4-5程序运行译码模块效果图程序译码输入文件如图4-6所小:0) 2.txt，记事本文件时扁信用同(5 查看m 帮劭(h)11 乳 olullllllllllg沈阳航空航天大学课程设计报告签。错误！未指定书程序译码输出文件如图4-7所示:ie - ss本i d i 日鱼件消蜀国芭看叩印电些aaabbbbbcc图4-7程序译码输出文件截图4.4. 图形演示界面图形演示界面如图4-8所示:参考文献1严蔚敏，吴伟民.数据结构（c语言版）m.北京精华大学出版社，20062吕国英.算法设计与分析m.北京:清华大学出版社,2006

15、3徐宝文，李志.c程序设计语言m.北京:机械工业出版社，20044 erich gamma, richaed helm.设计模式（英文版）m.北京:机械工业出版社,200414沈阳航空航天大学课程设计报告附 录(程序清单)#include #include #include #include图形文件#define r 15typedef struct _nodechar word;int value;_node *left,*right;node,*lpnode;typedef struct pointint x,y; 树节点坐标point;typedef struct _containerl

16、pnode 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;node-last=p;node-next=p-next;p-next-last=

17、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-le

18、ft=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)；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=li

19、st.v-right=null;list.next=&list;list.last=&list;for(i=0;iv=(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);return hea

20、d;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);strcat(r,1);dfs(t-right,r,list);lpcodenode

21、 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;whil

22、e(p-word!=c)p=p-next; fputs(p-code,dfp);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-w

23、ord!=-1)fputc(p-word,dfp);p=tree;fclose(sfp);fclose(dfp);void print(lpcodenode list)printf(n字符-哈夫曼编码对照表n);while(list!=null) printf(%c - %sn,list-word,list-code); list=list-next;printf(n);void window。初始化图形眶initgraph(480, 320,showconsole);setcolor(yellow);point dian6;dian0.x=192;dian0.y=96;dian1.x=128;dian1.y=144;dian2.x=256;dian2.y=144;dian3.x=220;dian3.y=192;dian4.x=320;dian4.y=192;for(int i=0;i5;i+) circle(diani.x,diani.y , r);floodfill(diani.x,diani.y ,yellow);填充颜色sleep(1000);line(di