数据结构课程设计之哈夫曼编码.docx
- 文档编号:10930895
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:12
- 大小:78.62KB
数据结构课程设计之哈夫曼编码.docx
《数据结构课程设计之哈夫曼编码.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计之哈夫曼编码.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构课程设计之哈夫曼编码
一、设计思想
(一)哈夫曼树的设计思想
对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树,其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。
首先给定n个权值制造n个只含根结点的二叉树,得到一个二叉树林;再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树,其中新的二叉树的根结点的权值为左右子根结点权值之和;最后在二叉树林中把组合过的二叉树删除,再重复第二步,直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。
(二)哈夫曼编码与解码的设计思想
在数据通讯中,经常要将传送的文字转换为二进制字符0和1组成的二进制串,称这个过程为编码。
与子相对的是解码或是译码,就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。
在这里是通过哈夫曼树实现编码与解码的,所以称作是哈夫曼编码与解码。
首先输入一个字符串,还有相应的在哈夫曼树里的权值,这样用哈夫曼树把字符串用二进制串代替它,这个过程要注意树和编码问题,其中树的问题在上面已经解决,主要看编码的问题,就是根据我们输入的字符串和权值建立相应的树模型,这一步完成那编码就已经完成了,最后打印就行了;然后就是解码,完成编码相应的解码就相对简单了,就是先找到在编码的时候建的那个模型树,将编码中的二进制串再根据权值转换为相应的字符串,这样一步步解码就行了。
以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。
二、算法流程图
(一)哈夫曼树的流程图
图1哈夫曼树的流程图
(二)编码的流程图
(三)解码的流程图
三、源代码
下面给出的是用中缀转后缀算法实现的程序的源代码:
#include"stdio.h"
#include"string.h"
#defineMAX100/*定义常量*/
structHaffNode
{
intweight;/*权值*/
intparent;/*双亲结点下标*/
charch;
intlchild;
intrchild;
}*myHaffTree;/*构造哈夫曼树*/
structCoding
{
charbit[MAX];/*定义数组*/
charch;
intweight;/*字符的权值*/
}*myHaffCode;/*定义结构体*/
voidHaffman(intn)/*定义哈夫曼函数*/
{
inti,j,x1,x2,s1,s2;
for(i=n+1;i<=2*n-1;i++)/*树的初始化*/
{
s1=s2=10000;
x1=x2=0;
for(j=1;j<=i-1;j++)/*构造哈夫曼树的非叶子结点*/
{
if(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=s1;x2=x1; s1=myHaffTree[j].weight;x1=j; } elseif(myHaffTree[j].parent==0&&myHaffTree[j].weight { s2=myHaffTree[j].weight;x2=j; } } myHaffTree[x1].parent=i; myHaffTree[x2].parent=i; myHaffTree[i].weight=s1+s2;/*左右子组合为新树*/ myHaffTree[i].lchild=x1; myHaffTree[i].rchild=x2; } } voidHaffmanCode(intn)/*构造n个结点哈夫曼编码*/ { intstart,c,f,i,j,k; char*cd; cd=(char*)malloc(n*sizeof(char)); myHaffCode=(structCoding*)malloc((n+1)*sizeof(structCoding)); cd[n-1]='\0'; for(i=1;i<=n;++i)/*n个叶子结点的哈夫曼编码*/ { start=n-1; for(c=i,f=myHaffTree[i].parent;f! =0;c=f,f=myHaffTree[f].parent) if(myHaffTree[f].lchild==c)cd[--start]='0'; elsecd[--start]='1'; for(j=start,k=0;j { myHaffCode[i].bit[k]=cd[j]; k++; } myHaffCode[i].ch=myHaffTree[i].ch;/*取编码对应的权值*/ myHaffCode[i].weight=myHaffTree[i].weight; } free(cd); } Init()/*定义有返回值的函数*/ { inti,n,m; printf("pleaseinputthenumberofwords: "); scanf("%d",&n); m=2*n-1; myHaffTree=(structHaffNode*)malloc(sizeof(structHaffNode)*(m+1)); for(i=1;i<=n;i++) { printf("pleaseinputthewordandtheequal: "); scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight); myHaffTree[i].parent=0; myHaffTree[i].lchild=0; myHaffTree[i].rchild=0; } for(i=n+1;i<=m;i++) { myHaffTree[i].ch='#'; myHaffTree[i].lchild=0; myHaffTree[i].parent=0; myHaffTree[i].rchild=0; myHaffTree[i].weight=0; } Haffman(n); HaffmanCode(n); for(i=1;i<=n;i++) { printf("%c%d",myHaffCode[i].ch,myHaffCode[i].weight); printf("\n"); } printf("initsuccess! \n"); returnn; } voidCaozuo_C(intm)/*编码函数*/ { intn,i,j; charstring[50],*p; printf("pleaseinputthewords: "); scanf("%s",string); n=strlen(string);/*计算字符串长度*/ for(i=1,p=string;i<=n;i++,p++)/*进行编码*/ { for(j=1;j<=m;j++) if(myHaffCode[j].ch==*p) printf("%s\n",myHaffCode[j].bit); } } voidCaozuo_D(intn)/*解码函数*/ { inti,c; charcode[1000],*p; printf("pleaseinputthecoding: ");/*输入二进制编码*/ scanf("%s",code); for(p=code,c=2*n-1;*p! ='\0';p++)/*进行解码*/ { if(*p=='0')/*结束条件*/ { c=myHaffTree[c].lchild;/*赋值*/ if(myHaffTree[c].lchild==0)/*扫描*/ { printf("%c",myHaffTree[c].ch); c=2*n-1; continue;/*结束*/ } } elseif(*p=='1') { c=myHaffTree[c].rchild; if(myHaffTree[c].lchild==0) { printf("%c",myHaffTree[c].ch); c=2*n-1;/*赋值*/ continue; } } } printf("\n"); } voidmain() { intn; charchar1;/*定义字符*/ n=Init();/*函数的调用*/ printf("A.codingB.codeprintingC.exit\npleaseinputtheprocess: \n"); while (1) { scanf("%c",&char1); if(char1=='c')/*判断字符*/ break; switch(char1) { case'A': Caozuo_C(n);break;/*执行编码操作*/ case'B': Caozuo_D(n);break;/*执行解码操作*/ case'C': ;break; } } } 四、运行结果 (一)中缀转后缀算法的运行结果: 五、遇到的问题及解决 这部分我主要遇到了如下三个问题,其内容与解决方法如下所列: ●问题1: 刚开始不知道如何建一个好树,因为我开始试着建了几个二叉树,不知道什么原因运行的时候那编码总是不对,跟在草稿纸上自己画的那个二叉树总是不相符,就找原因。 解决方法: 开始时总是编码出错,就试着找错,树的初始化不可能出错,所以首先看那叶子结点的for函数,没什么错误,接着看非叶子结点的for函数,非叶子结点不好弄,找起来麻烦一些,就是费时间,盘查到最后也没什么错,最后就是左右子结点重生结点的一块了,这也比较好查,可是结果却是错处在这儿了,没想到最放心的一块出了错,得好好反省反省了,以后绝不能在这些问题上出错了,还好不是很严重,还可以补回来。 ●问题2: 由于前一个问题的解决,后面小心意义的写,尽量放慢写的速度,省的再花时间找错,可是最后能运行,运行的结果却是错的不容乐观啊,还出现一些不认识的乱码,这样的问题最难了,也是最不想遇到的问题,逻辑问题和一些代码输入有误。 解决方法: 刚开始改的时候不知哪儿错,就是乱改一通,结果还是找不到哪儿出错了,只能请高手了,不过还是问了两个人才解决这个问题的。 最后还是不是怎么懂,马马虎虎吧。 ●问题3: 这个问题是写到前面才想起来的,就是哈夫曼编码与解码这个作业的原理不是很懂,刚开始在课上听的就不是很懂很透,结果过了两天忘了。 解决方法: 这个问题跟别人讨论了一下,然后给我讲了一下就懂了,也没什么难的,就这么轻松的解决了。 六、心得体会 通过这次的作业我充分的认识到了自己的不足,特别是对写程序代码这方面,一个程序从算法到用程序把它实现出来,这一整个过程是很不容易的,你懂得它的算法,不一定就能写的出来,通过这次我也深深的了这一点。 对于一个新手来说,小的错误出现的太多,而且一个小的错误就能让我束手无策,因为想不通错在哪,所以就一直在乱改,逻辑错误就更难了,有时候程序运行语法没有错误,但只要输入表达式计算结果时,出来的结果要不是错的,要不就不出现结果,这种错的原因更难找。 感觉难的原因可能就是平时少练习,代码量也是积累很少的,这样我们寻找程序的错误觉得很难,修改过来就更难了。 但是运行的正确结果出来的时候,觉得有点兴奋。 不管怎么说,这次的作业给我的感触的确不小,懂得发现问题,尝试着从个方面收集资料努力去解决它,提升了自己解决问题的能力,但突然发现自己原来什么都不会,有的也是理论上懂得一点,但实践起来却无法下手,所以觉得自己以后要学的东西实在是太多了,必须多动手才能克服这些低级错误。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 哈夫曼 编码