实验二哈夫曼树及哈夫曼编码译码的实现.docx
- 文档编号:14492138
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:8
- 大小:133.81KB
实验二哈夫曼树及哈夫曼编码译码的实现.docx
《实验二哈夫曼树及哈夫曼编码译码的实现.docx》由会员分享,可在线阅读,更多相关《实验二哈夫曼树及哈夫曼编码译码的实现.docx(8页珍藏版)》请在冰点文库上搜索。
实验二哈夫曼树及哈夫曼编码译码的实现
实验二:
哈夫曼树及哈夫曼编码译码的实现(验证性、4学时)
一、实验目的和要求
构建哈夫曼树及哈夫曼编码,输出哈夫曼树及哈夫曼编码,完成编码与译码的算法。
(1)掌握树的有关操作算法
(2)熟悉树的基本存储方法
(3)学习利用树求解实际问题
二、实验内容和原理
定义哈夫曼树的存储结构;输入要编码的字符权重,根据权重建立哈夫曼树,并进行编码,最后输出哈夫曼编码。
三、实验环境
硬件:
(1)学生用微机
(2)多媒体教室或远程教学(3)局域网环境
软件:
(1)WindowsXP中文操作系统
(2)TurboC3.0
四、算法描述及实验步骤
1.算法描述
(1)建立叶子结点——由于每个叶子结点都有一个权重值,构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和,所以应该有一个权重域和指向左右孩子的两个指针域;
(2)另外在建成哈夫曼树之后,为了求得每个叶子结点的哈夫曼编码,需要走一条从叶子结点到根结点的路径,而译码的过程是从根结点出发到叶子的不断匹配的过程,所以既需要知道孩子结点的信息,也需要知道双亲结点的信息,应该再有一个指向双亲结点的指针域。
(3)构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点,每回退一步走过哈夫曼树的一个分枝得到一个哈夫曼编码值;由于每个叶子结点的哈夫曼编码是从根就诶点到相应叶子结点的路径上各分枝代码所组成的0、1序列,所以先得到的分枝代码为说求编码的低位码而后得到的为高位码。
2.算法流程图
构建哈夫曼树算法流程
哈夫曼编码算法流程
3.代码
#include
#definemaxvalue10000//定义最大权值常量
#definemaxnodenumber100//定义结点最大数目常量
typedefstruct
{intweight;
intparent,lchild,rchild;
}htnode;
typedefhtnode*huffmantree;//定义哈夫曼树类型
htnodeht[maxnodenumber]; //定义静态三叉链表存储区数组
#definemaxbit10//定义哈夫曼编码的最大长度
typedefstruct//定义保存一个叶子结点哈夫曼编码的结构
{intbit[maxbit];//哈夫曼编码域为一维数组
intstart;//开始位置域为整型
}hcodetype;//定义哈夫曼编码类型
hcodetypecd[maxnodenumber];//定义存放哈夫曼编码的数组cd
voidcrthuffmantree(intn);//建立哈夫曼树
voidgethuffmancode(intn);//哈夫曼编码
voidmain()
{
intnodenum;
printf("inputnodenum:
");
scanf("%d",&nodenum);
crthuffmantree(nodenum);
gethuffmancode(nodenum);
}
voidcrthuffmantree(intn)//该算法对n个叶子结点建立哈夫曼树,权重值由键盘逐个输入
{inti,j,m1,m2,k1,k2;//定义局部变量
for(i=0;i<2*n-1;i++)//数组ht初始化
{
ht[i].weight=0;//权重初始化为0
ht[i].parent=-1;//3个指针域初始化为-1,即NULL
ht[i].lchild=-1;
ht[i].rchild=-1;
}
for(i=0;i scanf("%d",&ht[i].weight); for(i=0;i {m1=maxvalue;//预置最小权值变量为最大权值 m2=maxvalue;//预置次小权值变量为最大权值 k1=0;k2=0;//预置最小和次小权值结点位置为下标0处 for(j=0;j if(ht[j].parent==-1&&ht[j].weight {m2=m1;k2=k1;//若第j个结点权小于当前最小的m1改为次小的 m1=ht[j].weight;k1=j;//并记下新的当前最小权值及位置 } else if(ht[j].parent==-1&&ht[j].weight {m2=ht[j].weight;k2=j;}//否则若小于当前次小的m2则更新m2及其位置 ht[k1].parent=n+i;//修改最小权值结点的双亲为刚生成的新结点 ht[k2].parent=n+i;//修改次小权值结点的双亲刚好生成的新结点 ht[n+i].weight=ht[k1].weight+ht[k2].weight;//填新生成结点的权重值 ht[n+i].lchild=k1;//新生成结点的左孩子指针指向k1 ht[n+i].rchild=k2;//新生成结点的右孩子指针指向k2 } } voidgethuffmancode(intn) /*对具有n个叶子结点的哈夫曼树ht,求所有叶子结点的哈夫曼编码并输出*/ {inti,j,c,p; /*定义局部变量*/ for(i=0;i {c=i;j=maxbit; /*为求一个结点的哈夫曼编码初始化c和j*/ do {j--; /*j指向bit中存放编码位的正确位置*/ p=ht[c].parent; /*p指向c的双亲结点*/ if(ht[p].lchild==c) /*如果c是p的左孩子*/ cd[i].bit[j]=0; /*编码位上赋0*/ else cd[i].bit[j]=1; /*否则c是p的右孩子,编码位上赋1*/ c=p; /*更新c为p,为求下一个编码位做准备*/ }while(ht[p].parent! =-1); /*当未到达根结点继续做do循环*/ cd[i].start=j; /*求完一个叶子结点的哈夫曼编码时,记下编码开始位置*/ } for(i=0;i {for(j=cd[i].start;j printf("%d",cd[i].bit[j]); printf("\n"); /*输出完一个哈夫曼编码后换行*/ } } 五、调试过程 一次编译 二次编译 三次编译 六、实验结果 七、总结 (1)深刻体会构建哈夫曼树的整个过程,对整体有个总的理解; (2)复习以前所学C语言的一些语法,例如: for循环,if循环,while循环 (3)理解哈夫曼的编码过程,编码思想 (4)此程序的不足之处在于在进行哈夫曼编码时未能对字符进行编制,有待改进 附录: [1]宇正元 王秀丽。 算法与数据结构。 北京: 清华大学出版社,2006 [2]谭浩强。 C程序设计(第三版)。 北京: 清华大学出版社,2005
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 二哈夫曼树 哈夫曼 编码 译码 实现