哈夫曼编译码数据结构C语言版课程设计

1、数据结构课程设计报告设计题目哈夫曼(Huffman)编/译码器学院名称信息工程学院支业班级12计本2姓名张翠翠学号1212210217题目：哈夫曼(Huffman)编/译码器一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传 输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对 待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于 双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编 /译码系统。二、设计目标帮助学生熟练掌握树的应用和基本操作，重点掌握二叉树的存储, 这里以哈夫曼树为设计目标进一步提高学

2、生的设计能力及对树的理 解。三、任务要求一个完整的系统应具有以下功能：1) I :初始化(Initialization )。从终端读入字符集大小 n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree2) E:编码(Encoding)。利用以建好的哈夫曼树(如不在内存， 则从文件hfmTree中读入)，对文件ToBeTran中的正文进行编码，然 后将结果存入文件CodeFile中。3) D：译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile中。4) P :印代码文件(Print )。将文件CodeFile以紧

3、凑格式显示 在终端上，每行50个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。5) T :印哈夫曼树(Tree Printing )。将已在内存中的哈夫曼树 以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式 的哈夫曼树写入文件TreePrint中。四、需求分析利用哈夫曼树(Huffman)编/译码（一）、初始化哈夫曼树（二）、建立哈夫曼树（三）、对哈夫曼树进行编码（四）、输出对应字符的编码（五）、译码过程五、概要设计哈夫曼树的存储结构描述typedef struct(unsigned int weight;unsigned int parent, Ichild,

4、rchild;HTNode, *HuffmanTree;哈弗曼树的算法void CreateHT(HTNode ht,int n)点数n调用输入的数组ht,和节11/所有结点的相关域置初值/构造哈夫曼树min1=min2=32767;/int 的范围是-32768 32767lnode=rnode=-1;/lnode和rnode记录最小权值的int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;-1for (i=n;i<2*n-1;i+)两个结点位置for

5、(k=0;k<=i-1;k+)(if (htk.parent=-1)/只在尚未构造二义树的结点中查找(if (htk.weight<min1)/若权值小于最小的左节点的权值(min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)(min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/两个最小节点的父节点是ihti.weight=htlnode.weight+htrnode.weight;/ 两个最小节点的父节点权值为两个最小节

6、点权值之和hti.lchild=lnode;hti.rchild=rnode;/ 父节点的左节点和右节点哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n)(int i,f,c;HCode hc;for (i=0;i<n;i+)(hc.start=n;c=i;f=hti.parent;while (f!=-1)(if (htf.lchild=c)hc.cdhc.start-='0'elsehc.cdhc.start-='1'c=f;f=htf.parent;hc.start+;中最开始字符hcdi=hc;/根据哈

7、夫曼树求哈夫曼编码/循序直到树根结点结束循环/处理左孩子结点/处理右孩子结点/start指向哈夫曼编码 hc.cdvoid DispHCode(HTNode ht,HCode hcd,int n)/ 输出哈夫曼编码的列表(int i,k;printf("输出哈夫曼编码：n");for (i=0;i<n;i+)输出data中的所有数据,即A-Z(printf("%c：t",hti.data);for (k=hcdi.start;k<=n;k+)输出所有data中数据的编码(printf("%c",hcdi.cdk);prin

8、tf("n");void editHCode(HTNode ht,HCode hcd,int n)(char stringMAXSIZE;int i,j,k;scanf("%s",string);string数组中/编码函数/把要进行编码的字符申存入printf("n输出编码结果：n");for (i=0;stringi!='#'i+)(for (j=0;j<n;j+)(if(stringi=htj.data)/#为终止标志/循环查找与输入字符相同的编号，相同的就输出这个字符的编码(for (k=hcdj.sta

9、rt;k<=n;k+)(printf("%c",hcdj.cdk);哈弗曼译码break;输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n)/ 译码函数(char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s”,code);/把要进行译码的字符申存入code数组中while(code0!='#')for (i=0;i<n;i+)(m=0;/m为想同编码个数的计数器for (k=hcdi.start,j=0;k<=n;k+,j+)的编码个数/j为记

10、录所存储这个字符(if(codej=hcdi.cdk)当有相同编码时m值加1m+;if(m=j)/当输入的字符申与所存储的编码字符申个数相等时则输出这个的data数据(printf("%c",hti.data);/把已经使用过的code数/建立结构体/建立结构体把初始化的数据存入ht结构体中for(x=0;codex-1!='#'x+)组里的字符申删除(codex=codex+j;主函数void main()(int n=26,i;char orz,back,flag=1;charstr='A','B','C'

11、,'D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W,'X','Y','Z'/ 初始化intfnum=186,64,13,22,32,

12、103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16;初始化HTNode htM;HCode hcdN;for (i=0;i<n;i+)hti.data=stri;hti.weight=fnumi;while (flag)菜单函数，当flag为0时跳出循环显示部分源程序:printf("n");printf("*printf("n* 1 显小编码*");printf("n* 2 进行编码*");printf("n* 3 进行译码*");

13、printf("n* 4退出*n");printf(" printf("n");* *");printf("请输入选择的编号：，scanf("%c",&orz);switch(orz)(case 'a':/活屏函数case 'A':system("cls");CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf("n按任意键返回.");getch();s

14、ystem("cls");break;case 'b':case 'B':system("cls");printf("请输入要进行编码的字符申(以#结束):n");editHCode(ht,hcd,n);printf("n按任意键返回.")；getch();system("cls");break;case 'c':case 'C':system("cls");DispHCode(ht,hcd,n);printf(

15、"请输入编码(以#结束):n");deHCode(ht,hcd,n);printf("n按任意键返回.")；getch();system("cls");break;case 'd':case 'D':flag=0;break;default:system("cls");六、详细设计字仝C符“ABCDEFGHI JKLM 格频18 6 13 22 32 10 21 15 47 57 15 32 20由上表画出哈夫曼树:由哈夫曼树得出各字符的编码:字符编码字符编码空格10D0001A01

16、0E1111B011111F11001C0000G01110关系调用：ii该程序的流程图:19七、测试分析白盒：查看代码完整性白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的 结构测试程序，通过测试来检测产品内部动作是否按照设计规格说 明书的规定正常进行，检验程序中的每条通路是否都能按预定要求 正确工作。 这一方法是把测试对象看作一个打开的盒子，测试人 员依据程序内部 逻辑结构相关信息，设计或选择 测试用例，对程序 所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际 的状态是否与预期的状态一致。黑盒：测试是否可以正确的创建，删除，插入，打印，查找等 操作2d_!1黑盒测试也称功能

17、测试，它是通过测试来检测每个功能是否都 能正常使用。在测试中，把 程序看作一个不能打开的黑盒子，在完 全不考虑程序内部结构和内部特性的情况下，在 程序接口进行测 试，它只检查程序功能是否按照需求规格说明书的规定正常使用， 程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试 着眼于程序外部结构，不考虑内部 逻辑结构，主要针对软件界面和 软件功能进行测试。ztidngcui- 0 error(s), 0 warming(s)I 1坦建/调试X在土件i中萱找"在文件2中查扶工绪栗井iL-gbuggin/ 7八、使用说明1）输入n个字符的权值2）输入对应的字符3）得出各字符的编码九、

18、测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“ THIS PROGRAM IS MY FAVORITE字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 NO P Q RST UVWXYZ频度 57 63 15 1 48 51 80 23 8 18 1 16 1注：学生在测试数据时，需要写出测试用例和截图十、该程序的源代码#include <stdio.h>#include <stdlib.h>#include<con

19、io.h>#include <string.h>#define N 50要用system函数要调用的头文件/用getch()要调用的头文件#define M 2*N-1数为2n-1#define MAXSIZE 100/用M表示节点总数当叶节点数位n时总节点/义用N表示50叶节点数typedef structchar data;/结点值int weight;/权值int parent;双亲结点int lchild;/左孩子结点int rchild;/右孩子结点HTNode;typedef struct(char cdN;/存放哈夫曼码int start;/从start开始读c

20、d中的哈夫曼码HCode;void CreateHT(HTNode ht,int n)/ 调用输入的数组 ht,和节点数n(int i,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;-1for (i=n;i<2*n-1;i+)(min1=min2=32767;lnode=rnode=-1;两个结点位置for (k=0;k<=i-1;k+)(if (htk.parent=-1)中查找/所有结点的相关域置初值/构造哈夫曼树/int 的范围是-32768 327

21、67/lnode和rnode记录最小权值的/只在尚未构造二义树的结点(if (htk.weight<min1)/若权值小于最小的左节点的权值(min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weight<min2)(min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/两个最小节点的父节点是ihti.weight=htlnode.weight+htrnode.weight;/ 两个最小节点的父节点权值为两个最小节点权值之和hti.lchild=lno

22、de;hti.rchild=rnode;/ 父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n)(int i,f,c;HCode hc;for (i=0;i<n;i+)/根据哈夫曼树求哈夫曼编码(hc.start=n;c=i;f=hti.parent;while (f!=-1)(if (htf.lchild=c)hc.cdhc.start-='0'elsehc.cdhc.start-='1'c=f;f=htf.parent;hc.start+;中最开始字符hcdi=hc;/循序直到树根结点结束循环/处

23、理左孩子结点/处理右孩子结点/start指向哈夫曼编码 hc.cd void DispHCode(HTNode ht,HCode hcd,int n) / 输出哈夫曼编码的列表(int i,k;printf("输出哈夫曼编码：n");for (i=0;i<n;i+)输出data中的所有数据,即A-Z(printf(" %c：t",hti.data);for (k=hcdi.start;k<=n;k+)输出所有 data 中数据的编码(printf("%c",hcdi.cdk); printf("n");

24、void editHCode(HTNode ht,HCode hcd,int n)(char stringMAXSIZE;int i,j,k;scanf("%s",string);string数组中printf("n输出编码结果：n");for (i=0;stringi!='#'i+)(for (j=0;j<n;j+)(if(stringi=htj.data)号，相同的就输出这个字符的编码(for (k=hcdj.start;k<=n;k+)(printf("%c",hcdj.cdk);break;/编码函

25、数/把要进行编码的字符申存入/#为终止标志/循环查找与输入字符相同的编输出完成后跳出当前for循环23void deHCode(HTNode ht,HCode hcd,int n)/ 译码函数(char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s”,code);/把要进行译码的字符申存入code数组中while(code0!='#')for (i=0;i<n;i+)(/j为记录所存储这个字符m=0;/m为想同编码个数的计数器for (k=hcdi.start,j=0;k<=n;k+,j+)的编码个数(if(codej=hcd

26、i.cdk)当有相同编码时 m 值加 1m+;if(m=j)/当输入的字符申与所存储的编码字符申个数相等时则输出这个的data数据(printf("%c",hti.data);for(x=0;codex-1!='#'x+)把已经使用过的 code 数组里的字符申删除(codex=codex+j;void main()(int n=26,i;char orz,back,flag=1;charstr='A','B','C','D','E',F,'G','H&#

27、39;,T,'J',K,'L','M',N,'O','P','Q','R','S','T','U','V','W,'X','Y','Z'/ 初始化intfnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16;初始化HTNode htM;/建立结构体HCode hc

28、dN;/建立结构体for (i=0;i<n;i+)把初始化的数据存入ht结构体中hti.data=stri;hti.weight=fnumi;while (flag)printf("n");printf("printf("nprintf("nprintf("n菜单函数，当flag为0时跳出循环*,);*a 显示编码*");*B进行编码*");*C 进行译码*");printf("n* D退出25printf("*”)；printf("n");printf（-请

29、输入选择的编号:"）;scanf("%c",&orz);switch(orz)case 'a':case 'A':system("cls");/ 活屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf("n按任意键返回.")；getch();system("cls");break;case 'b':case 'B':system("cls&quo

30、t;);printf("请输入要进行编码的字符申(以#结束):n");editHCode(ht,hcd,n);printf("n按任意键返回.")；getch();system("cls");break;case 'c':case 'C':system("cls");DispHCode(ht,hcd,n);printf("请输入编码(以#结束):n");deHCode(ht,hcd,n);printf("n按任意键返回.")；getch();s

31、ystem("cls");break;case 'd':case 'D':flag=0;break;default:system("cls");:该程序的截图：初始化界面截图如下X:Pr0gr3m FitesIVicrio5oft Visual StudioMyProjectsdddDebugddd.exe'旬 £3选A时的显示结果截图如下Kj TiXProgram Fi'esXMicrcsoft Visual StudioyrojertsXdddDebugddd.exe'| 三回 |l S3%D：60 900E：10110F：010G：110&L1IP011010i:eaat J：Billx：eii00ieseL：O110010L1H：l&lllH：1100100：1930P：1091Q：011011B：011061001S=8010T：BO11U=1161U：