数据结构课程设计---- 赫夫曼编码系统

1、 东华理工大学课程设计报告课程设计题目 ： 赫夫曼编码系统 学生姓名 ： 安国栋专 业 ： 计算机科学与技术 班 级 ： 1320701学 号 ： 201320070105指导教师 ： 刘志峰 2014年 06 月 19 日目 录1、 设计要求-2二、存储结构-2三、设计思想-21、设计包含的几个部分-22、流程图-3四、详细设计-4五、算法复杂度分析-8六、显示结果-9七、心得体会-11八、附录：源程序代码-11一、设计要求赫夫曼树任务 ：建立建立最优二叉树函数 要求：可以建立函数输入二叉树，实现赫夫曼树的编码和译码系统，重复地显示并处理编码/解码功能，直到选择退出为止。二、存储结构：在本次

2、课程设计中，每一个字符的信息用一个结构体存储，包含结点值、权值、双亲结点、左孩子结点、右孩子结点等数据。赫夫曼码和所有字符都是用一个一维数组建立存储的，所以本次课程设计的存储结构是顺序存储。三、设计思想哈夫曼编译码系统的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让

3、出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树用于构造使电文的编码总长最短的编码方案。（1）设计包含的几个方面： 赫夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们

4、可以利用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。 赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN1; / 存放编码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型 代码文件的译码 译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。（2）其主要流程图如图所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结

5、点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I+编码为1结束否否否右子是否为空是是否否是是是四、详细设计（1）赫夫曼树的存储结构描述为： #define N 50 / 叶子结点数 #define M 2*N-1 / 赫夫曼树中结点总数 typedef struct int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1; 哈弗曼树的算法void CreateHT(HTNode h

6、t,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; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉

7、树的结点中查找 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; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode;

8、 /父节点的左节点和右节点（2）哈弗曼编码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' else /处理右孩子结点 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+

9、; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; 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&

10、quot;); 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<=

11、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;i<n;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j为记录所

12、存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已经使用过的code数组里的字符串删除codex=codex+j;（4）主函数void main() int n=26,i; char orz,back,flag=1; char str='a','b','c','d','

13、;e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' /初始化 int fnum=186,64,13,22,32,103,21,15,

14、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+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 （5）显示部分源程序： printf(" 欢迎使用赫夫曼编译系统 n"); printf(" *n"); printf(" 1：显示编码n "); p

15、rintf(" 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); pri

16、ntf("n按任意键返回."); getch(); system("cls"); break; case '2': system("cls"); printf("请输入要进行编码的字符串(以#结束,字符为小写英文字母):n"); editHCode(ht,hcd,n); printf("n按任意键返回."); getch(); system("cls"); break; case '3': system("cls"); Di

17、spHCode(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"); 五、算法复杂度分析：void editHCode(HTNode ht,HCode hcd,int n) /编码函数

18、void deHCode(HTNode ht,HCode hcd,int n) /译码函数这两个被调函数里面都用了三重循环，其他的调用函数或者主函数都是一重或二重循环，所以算法复杂度为o(n3)。可以看出此算法效率是比较低的，希望能够找出更好的算法来减小复杂度。六、调试结果进入主菜单选1时的显示结果选择2时的显示结果选3时的显示结果七、心得体会通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多

19、余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。八、附录：源程序代码源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函数要调用的头文件#include<conio.h> /用getch()要调用的头

20、文件#include <string.h>#define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void Cre

21、ateHT(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; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-32768-32767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k+) if (htk.paren

22、t=-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; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;ht

23、i.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' else /处理右孩子结点 hc.cdhc.start-='1' c=f;f=htf.parent; hc

24、.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; 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(&

25、quot;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.start

26、;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为记录所存

27、储这个字符的编码个数if(codej=hcdi.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; char str='a','b','c','d','e'

28、,'f','g','h','i','j','k','l','m','n','o','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;i<n;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 printf(" 欢迎使用赫夫曼编译系统 n"); printf(" *n&quo