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

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

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

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

4、TNodez *HuffmanTree;调用输入的数组ht 口，和节哈弗曼树的算法void CreateHT(HTNode ht,int n)点数nint izk,lnode,mode;for (i=0;i<2*n-l;i+)htiLparent=hti.lchild=hti.rchild=l;所有结点的相关域置初值for (i=n;i<2*n-l;i+)构造哈夫曼树minl=min2=32767;/int 的范围是-3276832767lnode=rnode=-l;两个结点位置/Inode和mode记录最小权值的for (k=O;k<=i-l;k+)if (htk.pare

5、nt=-l)只在尚未构造二叉树的结点中查找if (htk.weight<minl)若权值小于最小的左节点的权值min2=minl;rnode=lnode;minl=htk.weight;lnode=k;)else if (htk.weight<min2)min2=htk.weight;rnode=k;)htlnode.parent=i;htrnode.parent=i;两个最小节点的父节点是i两个最小节父节点的左节hti.weight=htlnode.weight+htrnode.weight;点的父节点权值为两个最小节点权值之和hti.lchild=lnode;hti.rchil

6、d=rnode;点和右节点哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n)根据哈夫曼树求哈夫曼编码循序直到树根结点结束循环处理左孩子结点处理右孩子结点/start指向哈夫曼编码hc.cdHCode he;for (i=0;i<n;i+)hc.start=n;c=i;f=hti. parent;while (f!=-l)if (htf.lchild=c)hc.cdhc.start-='O'elsehc.cdhc.start-='l' c=f;f=htf. parent;)hc.start+;中最开始字符hcdi

7、=hc;void DispHCode(HTNode ht,HCode hcd,int n)输出哈夫曼编码的列表int i,k;printf("输出哈夫曼编码:n“)；for (i=0;i<n;i+)输出data中的所有数据即A-Zprintf(" %c:t"zhti.data);for (k=hcdi.start;k<=n;k+)的编码printf("%c"zhcdi.cdk);)printf("n");输出所有data中数据编码函数char stringMAXSIZE;int ij,k;scanf("

8、%s",string);string数组中printf("n输出编码结果:n“)；for (i=O;stringi!='#'i+)for (j=O;j<n;j+)if(stringi=htj.data)号，相同的就输出这个字符的编码把要进行编码的字符串存入#为终止标志循环查找与输入字符相同的编for (k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);void editHCode(HTNode ht,HCode hcdJnt n)break;输出完成后跳出当前for循环哈弗曼译码void d

9、eHCode(HTNode ht,HCode hcd,int n)译码函数char codeMAXSIZE;intscanf("%s",code);code数组中while(code0!='#')for (i=0;i<n;i+)m=0;把要进行译码的字符串存入for (k=hcdi.start,j=O;k<=n;k+,j+)/m为想同编码个数的计数器/j为记录所存储这个字符的编码个数当有相同编码时m值加1if(codej=hcdi.cdk)m+;)if(m=j)当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(&q

10、uot;%c",hti.data);把已经使用过的code数for(x=0;codex-l!="#'x+)组里的字符串删除codex=codex+j;)主函数void main()int n=26,i;char orz,back,flag=l;charY','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)；/初始化建立结构体HCode hcdN;建立结构体for (i=0;i<n;i+)把初始化的数据存入

11、ht结构体中hti.data=stri;hti.weight=fnumi;while (flag)显示部分源程序:菜单函数，当flag为0时跳出循环printf(,nH);printf("| Xi hprintf("n* 显不编码*“)；printf("n* 2进行编码*“)；printf("n* 3进行译码*”)；printf("n* 4退出*n");printf("11printf(,nn)；printf("请输入选择的编号门；scanf(”c”,&orz);switch(orz)case 'a

12、':清屏函数case TV:system("cls");CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcdzn);printf("n按任意键返回.”);getch();system("cls");break;case 15,:case B:system"。);printf(精输入要进行编码的字符串(以#结束):n“);editHCode(htzhcdzn);printf("n按任意键返回)getch();system("cls");break

13、;case 'c':case 'C:system("cls");DispHCode(htzhcdzn);printf(”请输入编码(以#结束):n)deHCode(ht,hcd,n);printf("n按任意键返回.”);getch();system("cls");break;case'd':case 'D':flag=O;break;default:system("cls");)六、详细设计字符频空ABCDEFGHIJKLM 格18 6 13 22 32 10 21

14、15 47 57 15 32 20由上表画出哈夫曼树:由哈夫曼树得出各字符的编码:字符编码字符编码空格10D0001A010E1111B011111F11001C0000G01110关系调用:该程序的流程图:七、测试分析白盒：看看代码完整性白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的 结构测试程序，通过测试来检测产品内部动作是否按照设计规格说 明书的规定正常进行，检验程序中的每条通路是否都能按预定要求 正确工作。这一方法是把测试对象看作一个打开的盒子，测试人 员依据程序内部逻辑结构相关信息，设计或选择测试用例，对程序 所有逻辑路径进行测试，通过在不同点检查程序的状态，确定实际 的状态

15、是否与预期的状态一致。黑盒：测试是否可以正确的创建，删除，插入，打印，查找等 操作黑盒测试也称功能测试，它是通过测试来检测每个功能是否都 能正常使用。在测试中，把程序看作一个不能打开的黑盒子，在完 全不考虑程序内部结构和内部特性的情况下，在程序接口进行测 试，它只检查程序功能是否按照需求规格说明书的规定正常使用， 程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试 着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和 软件功能进行测试。八、使用说明1）输入n个字符的权值2）输入对应的字符3）得出各字符的编码九、测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实 现以

16、下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符空格 ABCDEFGHIJKLM频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 NOPQRSTUVWXYZ频度 57 63 15 1 48 51 80 23 8 18 1 16 1注：学生在测试数据时，需要写出测试用例和截图十、该程序的源代码#include <stdlo.h>#include <stdlib.h>#include<conio.h>#include <string.h>#define N 50#defi

17、ne M 2*N-1数为2n-l#define MAXSIZE 100要用system函数要调用的头文件用getch()要调用的头文件义用N表示50叶节点数typedef structchar data;int weight;int parent;int Ichild;int rchild;结点值权值双亲结点左孩子结点右孩子结点用M表示节点总数 当叶节点数位n时总节点HTNode;typedef struct char cdN;存放哈夫曼码int start;从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n)点数nint i,k,Inod

18、e,mode;int minl,min2;for (i=0;i<2*n-l;i+)hti.parent=hti.lchild=hti.rchild=-l;for (i=n;i<2*n-l;i+)minl=min2=32767;lnode=rnode=-l;两个结点位置for (k=O;k<=i-l;k+)调用输入的数组ht，和节所有结点的相关域置初值构造哈夫曼树/int 的范围是3276832767/Inode和mode记录最小权值的if (htk.parent=-l)只在尚未构造二叉树的结点中查找if (htk.weight<minl)若权值小于最小的左节点的权值mi

19、n2=minl;rnode=lnode;minl=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=lnode;hti.rchild=rnode;点和右节点void CreateHCode(HTNode htzHCode hcdzint n)in

20、tHCode he;for (i=0;i<n;i+)根据哈夫曼树求哈夫曼编码hc.start=n;c=i;循序直到树根结点结束循环处理左孩子结点处理右孩子结点/start指向哈夫曼编码hc.cdif (htf.lchild=c)hc.cdhc.start-='O'elsehc.cdhc.start-='l' c=f;f=htf. parent;)hc.start+;中最开始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcdJnt n)输出哈夫曼编码的列表int i,k;printf("输出哈夫曼编码:n“)；

21、for (i=0;i<n;i+)输出data中的所有数据,即A-Zprintf(" %c:t",hti.data);for (k=hcdi.start;k<=n;k+)输出所有 data 中数据的编码printf("%c",hcdi.cdk);pnntf(,nn);void editHCode(HTNode ht,HCode hcd,int n)编码函数char stringMAXSIZE;scanfCs",string);string数组中把要进行编码的字符串存入printf(nn输出编码结果:n");for (i=O;

22、stringi!=l#,;i+)#为终止标志for (j=O;j<n;j+)if(stringi=htj .data)号，相同的就输出这个字符的编码循环查找与输入字符相同的编for (k=hcdj.start;k<=n;k+)printf("%c”,hcdUkdk);break;输出完成后跳出当前for循环译码函数void deHCode(HTNode ht,HCode hcdzint n)char codeMAXSIZE;int ij,l,k,m,x;scanf("%s",code);把要进行译码的字符串存入code数组中while(code0 !=

23、'#')for (i=0;i<n;i+)m=0;/m为想同编码个数的计数器for (k=hcdi.start,j=O;k<=n;k+zj+)/j 为记录所存储这个字符的编码个数if(codej=hcdi.cdk)当有相同编码时 m 值加 1m+;)if(m=j)当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c",hti.data);for(x=0;codex-l!='#'x+)把已经使用过的 code 数组里的字符串删除codex=codex+j;void main()int n=26,i;

24、char orz,back,flag=l;charY','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)；初始化建立结构体HCode hcdN;建立结构体for (i=0;i<n;i+)把初始化的数据存入ht结构体中菜单函数，当flag为0时跳出循环, I 1 .)，hti.data=stri;hti.weight=fnumi;)while (flag)printf("n");pnntf(Hprintf(nn*

25、A显示编码*"）；pnntf(nn* B进行编码*"）；pnntf(Hn* c进行译码*”）；退出printf("n printf(" printf("n");printf("请输入选择的编号:")；scanf("%c"z&orz);switch(orz)case 'a':case 'A':system("cls");清屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(htzhcdzn)

26、;printf("n按任意键返回.”)；getch();system("cls");break;case 'b':case 'B':system("cls");printf(”请输入要进行编码的字符串(以#结束):n“)；editHCode(htzhcd,n);printf("n按任意键返回.”)；getch();system("cls");break;case c:case 'C:system"©');DispHCode(ht,hcdzn);pr

27、intf(“请输入编码(以#结束):n) deHCode(ht,hcd,n);printf("n按任意键返回.”)；getch();system("cls");break;case'd':case 'D':flag=O;break;default:system("cls");)该程序的截图：初始化界面截图如下RT3 "C:ProgramHle5f/icroscft Visual StudioMyProjectsdddDebugddd.exe"o |臼码码码 曾译 示一觉什出 显讲进退 二二 -请输入选择的编号:选A时的显示结果截图如下选择B时的显示结果截图如下1000011011011140100113 "CProgram FilesMicrosoft Visual StudioMyProjectsdddDebugddd.exe"| o | 0 | 23 情输入要进行编码的字符串以嗡豆)：THIS PROGRAM IS MV FA