没有合适的资源?快使用搜索试试~ 我知道了~
首页哈弗曼编码与解码实验报告
哈弗曼编码与解码实验报告
需积分: 10 10 下载量 25 浏览量
更新于2023-03-16
收藏 180KB DOC 举报
第一次输入:字母 及 权值 第二次输入部分字符串 输出 相应哈弗曼编码 第三次输入哈弗曼编码 输出 相应字符串 第四步 输入哈弗曼编码 输出相应字符
资源详情
资源推荐
哈夫曼编码与解码
一、设计思想
第一步输入:
初始化结构体数组,输入 n 个权值及相应字符到已定义好的结构体数组中下标为 0~n-
1。用结构体数组存储全部的权值及其字符,结构体中含有字符、权值、左子下标、右子下
标及父结点下标。因为定义好的数组里面有不可预知的值,为输出没有乱码所以初始化。
第二次输入字符串到字符串数组中,输出编码时通过循环找出对应字符的 huffman 编码。
第二步建树:
CreateHT 为建造 huffman 树函数。本函数的基本思想是在没有成为树左子或右子的结
点中找出权值最小的两个结点,其中最小得作为左子次小的作为右子,构建新树,当出现
两个权值相同的情况,新结点(某孩子结点的父结点)作为右子,如此循环直到所有的结点
都已构建成树。在寻找最小结点过程中利用先已赋给较大值的两个变量 min1 和 min2,依
次和没构造成树的结点中权值相比,把最小结点权值赋给 min1 和次小结点权值赋给
min2,同时用变量 lnode 记录最小结点下标成为左子,变量 rnode 变量记录次小结点下标成
为右子。建树由双重循环控制,外循环从 n~2n-1,因为叶子结点下标从 0~n-1,所有结点
数为 2n-1 个,n~2n-1 控制生成新结点的下标。内循环从 0~i-1,i 从 n~2n-1,内循环数依次变
大,因为结点数不断增大,为从所有结点中找出最小结点所以内循环要从 0~i-1。每找到一
个最小结点和次小结点都把两权值相加和赋给此时的 ht[i].weigh,此时的 ht[i]即为找到的两
个 结 点 的 父 结 点 , 并 且 让 最 小 结 点 和 次 小 结 parent 都 等 于 父 结 点 下 标
(ht[lnode].parent=i;ht[rnode].parent=i;)同时让父结点的 lchild 等于记录的 lnode,rchild 等于记
录的 rnode,如此循环直至所有的结点都被包含在树中。
第三步将 huffman 码及其开始位存入结构体数组 hcd[n]:
叶子结点数为 n,则叶子结点的最长路径不会超过 n。用循环 for(i=0;i<n;i++)控制要到
每个叶子结点,把记录由叶子结点通向根结点的路径长度的变量 hc.start 初值记 n,把当前
结点的下标 i 赋给 c,把当前结点的父结点下标赋给 f。在不为根结点的条件下判断当前结
点是否为左子 if (ht[f].lchild==c),如果是左子,给路径赋值‘0’,hc.cd[--hc.start]='0';如果不
是左子则赋路径值为‘1’,hc.cd[--hc.start]='1';之后再把当前的结点的父结点下标赋给 c,把
当前结点父结点的父结点下标赋给 f,直到 f 为根结点时退出 while 循环,如此完成一个结
点的 huffman 码的记录,最后把临时存放 huffman 编码和开始位置的结构体 hc 赋给结构体
数组 hcd[i]。
第四步输出 huffman 编码:
通过三重循环控制 huffman 编码的输出,第一重循环从 0~n 控制字符串 str 循环,结束
条件 str 字符串当前值为‘