2022年数据结构课程设计-赫夫曼编码 .pdf

《2022年数据结构课程设计-赫夫曼编码 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计-赫夫曼编码 .pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程设计报告课程设计题目：赫夫曼编码系统学生姓名：章建专业：计算机科学与技术班级：1120702 学号：201120070214 指导教师：艾菊梅2012 年06 月 20 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 16 页 -东华理工大学1 目 录一、设计要求-2 二、存储结构-2 三、设计思想-2 1、设计包含的几个部分-2 2、流程图-3 四、详细设计-4 五、算法复杂度分析-8 六、显示结果-9 七、心得体会-11 八、附录：源程序代码-11 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 16 页 -东华理工大学2 一、设计要求赫夫曼树任务：建立建

2、立最优二叉树函数要求：可以建立函数输入二叉树，实现赫夫曼树的编码和译码系统，重复地显示并处理编码/解码功能，直到选择退出为止。二、存储结构：在本次课程设计中，每一个字符的信息用一个结构体存储，包含结点值、权值、双亲结点、左孩子结点、右孩子结点等数据。赫夫曼码和所有字符都是用一个一维数组建立存储的，所以本次课程设计的存储结构是顺序存储。三、设计思想哈夫曼编译码系统的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在通信中可以采用0 和 1 的不同排列来表示不同的字符，称为二进制编码。而赫夫曼树在数据编码中的应用是数据的最小冗余编码问题他是数据压缩学的基础。若每个字符出现

3、的频率相同，则可以采用等长的二进制编码，频率不同，采用不等长的二进制编码，频率达的字符采用位数较少的编码，频率小的采用位数较多的编码。赫夫曼编码就是一种不等长的二进制编码，而赫夫曼树是一种最优二叉树，它的编码也是一种最优编码。在赫夫曼树中，规定往左编码为0，往右编码为 1，则得到叶子节点的编码为从根结点带叶子结点中所有路径中0 和1 的顺序排列。（1）设计包含的几个方面：赫夫曼树的构造假设有 n 个权值，则构造出的赫夫曼树有n 个叶子结点。n 个权值分别为w1,w2,wn,则赫夫曼树构造规则为：1、将 w1,w2,.wn,看成有 n 棵树的森林。2、在森林中选出两个根结点最小的树合并，作为一棵

4、新树的左右子书，且新树根结点权值为左右子树根结点权值之和。3、从森林中删除选取的两棵树，并将新树加入森林。4、重复 2 和 3 步骤，直到森林中只剩一棵树为止。赫夫曼编码要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：typedet struct char ch;/存放编码的字符char bitsN1;/存放编码位串int len;/编码的长度CodeNode;/编码结构体类型 代码文件的译码在通信中，若将字符用赫夫曼编码形式发送出去，对方接收到编码后将编码还原成字符。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表名师资料总结-精品资料欢迎下载

5、-名师精心整理-第 3 页，共 16 页 -东华理工大学3 比较，遇到相等时，即取出其对应的字符存入一个新串中。（2）其主要流程图如图所示。开始结点数是否大于1 将 data和权值赋给ht 输出根结点和权值调用 SELECT 函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0 I2*N?I+编码为 1 结束否否否右子是否为空是是否否是是是名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 16 页 -东华理工大学4 四、详细设计（1）赫夫曼树的存储结构描述为：#define N 50/叶子结点数#define M 2*N-1/赫夫

6、曼树中结点总数typedef struct int weight;/叶子结点的权值int lchild,rchild,parent;/左右孩子及双亲指针HTNode;/树中结点类型typedef HTNode HuffmanTreeM+1;哈弗曼树的算法void CreateHT(HTNode ht,int n)/调用输入的数组ht,和节点数n int i,k,lnode,rnode;int min1,min2;for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/所有结点的相关域置初值-1 for(i=n;i2*n-1;i+)/构造哈夫

7、曼树 min1=min2=32767;/int 的范围是-3276832767 lnode=rnode=-1;/lnode 和 rnode 记录最小权值的两个结点位置for(k=0;k=i-1;k+)if(htk.parent=-1)/只在尚未构造二叉树的结点中查找 if(htk.weightmin1)/若权值小于最小的左节点的权值 min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if(htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/两个最小

8、节点的父节点是i hti.weight=htlnode.weight+htrnode.weight;/两个最小节点的父节点权值为两个最小节点权值之和hti.lchild=lnode;hti.rchild=rnode;/父节点的左节点和右节点 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 16 页 -东华理工大学5（2）哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for(i=0;in;i+)/根据哈夫曼树求哈夫曼编码 hc.start=n;c=i;f=hti.parent;while(f!=

9、-1)/循序直到树根结点结束循环 if(htf.lchild=c)/处理左孩子结点hc.cdhc.start-=0;else/处理右孩子结点hc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;/start 指向哈夫曼编码hc.cd 中最开始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)/输出哈夫曼编码的列表 int i,k;printf(输出哈夫曼编码:n);for(i=0;in;i+)/输出 data中的所有数据，即a-z printf(%c:t,hti.data);for(k=hcdi.start;

10、k=n;k+)/输出所有data中数据的编码 printf(%c,hcdi.cdk);printf(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+)/#为终止标志名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 16 页 -东华理工大学6 for(j=0;jn;j+)if(stringi=htj.data)/循环查

11、找与输入字符相同的编号，相同的就输出这个字符的编码 for(k=hcdj.start;k=n;k+)printf(%c,hcdj.cdk);break;/输出完成后跳出当前for 循环 （3）哈弗曼译码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;in;i+)m=0;/m 为想同编码个数的计数器for(k=hcdi.start,j=0;k=n;k+,j+)/j 为记录所存

12、储这个字符的编码个数 if(codej=hcdi.cdk)/当有相同编码时m 值加 1 m+;if(m=j)/当输入的字符串与所存储的编码字符串个数相等时则输出这个的data 数据 printf(%c,hti.data);for(x=0;codex-1!=#;x+)/把已经使用过的code数组里的字符串删除 codex=codex+j;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 16 页 -东华理工大学7（4）主函数void main()int n=26,i;char orz,back,flag=1;char str=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o

13、,p,q,r,s,t,u,v,w,x,y,z;/初始化int fnum=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 hcdN;/建立结构体for(i=0;in;i+)/把初始化的数据存入ht 结构体中 hti.data=stri;hti.weight=fnumi;while(flag)/菜单函数，当flag 为 0 时跳出循环（5）显示部分源程序：printf(欢迎使用赫夫曼编译系统n);printf(制作人：章建 n);printf(

14、*n);printf(1：显示编码 n);printf(2：进行编码 n);printf(3：进行译码 n);printf(0：退出 n);printf(*n);printf(请输入选择的编号:);scanf(%c,&orz);switch(orz)case 1:system(cls);/清屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(n 按任意键返回.);getch();system(cls);break;case 2:system(cls);printf(请输入要进行编码的字符串(以#结束,字符为小写英

15、文字母):n);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 16 页 -东华理工大学8 CreateHT(ht,n);CreateHCode(ht,hcd,n);editHCode(ht,hcd,n);printf(n 按任意键返回.);getch();system(cls);break;case 3:system(cls);CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(请输入编码(以#结束):n);deHCode(ht,hcd,n);printf(n 按任意键返回.);getch();syst

16、em(cls);break;case 0:flag=0;printf(感谢您的使用！n);break;default:system(cls);五、算法复杂度分析：void editHCode(HTNode ht,HCode hcd,int n)/编码函数void deHCode(HTNode ht,HCode hcd,int n)/译码函数这两个被调函数里面都用了三重循环，其他的调用函数或者主函数都是一重或二重循环，所以算法复杂度为o(n3)。可以看出此算法效率是比较低的，希望能够找出更好的算法来减小复杂度。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 16 页 -东华理工大学

17、9 六、调试结果进入主菜单选 1 时的显示结果名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -东华理工大学10 选择 2 时的显示结果选 3 时的显示结果名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 16 页 -东华理工大学11 七、心得体会通过这次课程设计，让我受益匪浅，使我掌握了二叉树的的存储结构和赫夫曼编码的基本思想。程序中有多处运用了三重循环，这里很多地方可以优化以达到减小时间和空间复杂度。还有字符数组和权值都是在程序代码里面初始化的，这样避免输入时态过繁琐，其实可以在程序代码外输入，这样的更自由，当然输入会比较麻烦。此次课程设计的最大收获

18、就是让我明白一个道理：无论你做的是多么小的一个程序或软件，都要使用模块化设计，这样使程序实现的功能更清晰明了。例如：选2 是进行编码；选 3 时进行译码.这样就能够实现人机交互了！。八、附录：源程序代码源程序如下：#include#include /要用 system 函数要调用的头文件#include/用 getch()要调用的头文件#include#define N 50/义用 N 表示 50 叶节点数#define M 2*N-1/用 M 表示节点总数当叶节点数位n 时总节点数为2n-1#define MAXSIZE 100 typedef struct char data;/结点值in

19、t weight;/权值int parent;/双亲结点int lchild;/左孩子结点int rchild;/右孩子结点HTNode;typedef struct char cdN;/存放哈夫曼码int start;/从 start 开始读 cd 中的哈夫曼码HCode;void CreateHT(HTNode ht,int n)/调用输入的数组ht,和节点数n int i,k,lnode,rnode;int min1,min2;for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/所有结点的相关域置初值-1 for(i=n;i2*n

20、-1;i+)/构造哈夫曼树 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 16 页 -东华理工大学12 min1=min2=32767;/int 的范围是-32768-32767 lnode=rnode=-1;/lnode 和 rnode 记录最小权值的两个结点位置for(k=0;k=i-1;k+)if(htk.parent=-1)/只在尚未构造二叉树的结点中查找 if(htk.weightmin1)/若权值小于最小的左节点的权值 min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if(htk.weightmin2)min2

21、=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;/两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight;/两个最小节点的父节点权值为两个最小节点权值之和hti.lchild=lnode;hti.rchild=rnode;/父节点的左节点和右节点 void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for(i=0;in;i+)/根据哈夫曼树求哈夫曼编码 hc.start=n;c=i;f=hti.parent;wh

22、ile(f!=-1)/循序直到树根结点结束循环 if(htf.lchild=c)/处理左孩子结点hc.cdhc.start-=0;else/处理右孩子结点hc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;/start 指向哈夫曼编码hc.cd 中最开始字符hcdi=hc;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 16 页 -东华理工大学13 void DispHCode(HTNode ht,HCode hcd,int n)/输出哈夫曼编码的列表 int i,k;printf(输出哈夫曼编码:n);for(i=0;in;i+)/输出 d

23、ata中的所有数据，即a-z printf(%c:t,hti.data);for(k=hcdi.start;k=n;k+)/输出所有data中数据的编码 printf(%c,hcdi.cdk);printf(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;jn;j+)if(stringi=htj

24、.data)/循环查找与输入字符相同的编号，相同的就输出这个字符的编码 for(k=hcdj.start;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!=#)名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -东华理工大学14 for(i=0;in;i+)m=0;/m 为

25、想同编码个数的计数器for(k=hcdi.start,j=0;k=n;k+,j+)/j 为记录所存储这个字符的编码个数 if(codej=hcdi.cdk)/当有相同编码时m 值加 1 m+;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;char str=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,

26、p,q,r,s,t,u,v,w,x,y,z;/初始化int fnum=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 hcdN;/建立结构体for(i=0;in;i+)/把初始化的数据存入ht 结构体中 hti.data=stri;hti.weight=fnumi;while(flag)/菜单函数，当flag 为 0 时跳出循环 printf(欢迎使用赫夫曼编译系统n);printf(制作人：章建 n);printf(*n);printf(

27、1：显示编码 n);printf(2：进行编码 n);printf(3：进行译码 n);printf(0：退出 n);名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -东华理工大学15 printf(*n);printf(请输入选择的编号:);scanf(%c,&orz);switch(orz)case 1:system(cls);/清屏函数CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(n 按任意键返回.);getch();system(cls);break;case 2:system(

28、cls);printf(请输入要进行编码的字符串(以#结束,字符为小写英文字母):n);CreateHT(ht,n);CreateHCode(ht,hcd,n);editHCode(ht,hcd,n);printf(n 按任意键返回.);getch();system(cls);break;case 3:system(cls);CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(请输入编码(以#结束):n);deHCode(ht,hcd,n);printf(n 按任意键返回.);getch();system(cls);break;case 0:flag=0;printf(感谢您的使用！n);break;default:system(cls);名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -