哈夫曼树实验报告
for(i=n+1;i<=m;++i) i-1]选择 parent 为 0 且 weight 最小的两个节点,其
序号分别为 s1,s2.
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
三、实验要求
设计思路:
数据结构:
Huffman
#define n 100
H编uf码fm文an件树的的译建码使立用说明
序 1编.运行环境:VC++ 码
从Hu叶ff子ma到n 编根码逆的向 求编码生成
2程.首先选择主控菜单中的操作1,即建表,然后进行其它操作.
六.实验截图 七 实验体会
退出
1、构建哈夫曼树的关键在于找最小树;在 F 中选择两棵根结点权值最小的树 作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左 右子树上根结点的权值之和。 2、由于学习的不足没有实现编码文件的译码,今后会加以改进 (╯﹏╰) 3、在逆向求编码的 for 循环里犯了一个逻辑错误导致求出来的 3、4 位编码 串行,尝试了多钟数据输入才找到原因所在,并加以改正,编写程序需一步 一步的去调试并找到错误所在。 附源程序:
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)
{
eight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for( ;i<=m;++i,++p)
(*p).parent=0;
实
验
报
告
实验名称
专业班级 指导教师
Huffman 编码
计科三班
姓名
日期
学号
一、实验目的
熟练掌握二叉树应用(Huffman 编码)的基本算法实现。
二、实验内容
1.对输入的一串电文字符实现 Huffman 编码,再对 Huffman 编码生成 的代码串进行译码,输出电文字符串。实现功能如下: Huffman 树的建立 Huffman 编码的生成 编码文件的译码
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
arent;f!=0;c=f,f=HT[f].parent) child==Байду номын сангаас)
cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第 i 个字符编码分
#include<> #include<> #include<> #include<> typedef struct { char data; arent==0)
{ s1=i; break;
} } for(i=i+1; i<=m; i++)
{
if (HT[i].parent==0 && HT[s1].weight>HT[i].weight)
配空间
strcpy(HC[i],&cd[start]);
//从 cd 复制编码(串)到 HC
}
free(cd);
//释放空间
}
void main()
{ HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("请输入权值的个数(): "); scanf ("%d",&n); w=(int *)malloc(n*sizeof(int)); printf("请依次输入%d 个权值(整型):\n",n); for(i=0;i<=n-1;i++) scanf ("%d",w+i); HuffmanCoding(HT,HC,w,n); for(i=1;i<=n;i++){ printf("对应的编码为:"); puts(HC[i]);} }
s1=i;
}
for(i=1; i<=m; i++)
{
if(HT[i].parent==0&&i!=s1)
{
s2=i;
break;
}
}
for(i=i+1; i<=m; i++)
{
if(HT[i].parent==0 && HT[i].weight<HT[s2].weight &&
i!=s1)
s2=i;