数据结构实验汇报 实验五(篇五)。
“人们只在梦中生活,唯有哲人挣扎着要觉醒过来。”当我们看名人写的优秀的文章时,我们时不时会摘抄一些好句好段,好句好段用到该用的地方,才能彰显出它在特殊语境中的色彩。我们可以从哪里摘抄好句好段呢?有请驻留片刻,小编为你推荐数据结构实验汇报 实验五(篇五),强烈建议你能收藏本页以方便阅读!
报告是一个把你展示给大家的机会,向大家宣布你的成果,让你今后更有信心地做事,当我们结束一阶段的工作。我们时常会使用到报告,有哪些报告是值得我们借鉴学习的?这是一篇有关“数据结构实验汇报 实验五(篇五) ”的网络文章希望对大家有所帮助,相信你能够找到对自己有价值的资料!
一.实验内容:
实现哈夫曼编码的生成算法。
二.实验目的:
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述:
已知n个字符在原文中出现的频率,求它们的哈夫曼编码。
1、读入n个字符,以及字符的权值,试建立一棵Huffman树。
2、根据生成的Huffman树,求每个字符的Huffman编码。并对给定的待编码字符序列进行编码,并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路:
a.首先定义郝夫曼树的存储形式,这里使用了数组
b.用select()遍历n个字符,找出权值最小的两个
c.构造郝夫曼树HT,并求出n个字符的郝夫曼编码HC
总结
1.基本上没有什么太大的问题,在调用select()这个函数时,想把权值最小的两个结点的'序号带回HuffmanCoding(),所以把那2个序号设置成了引用。
2.在编程过程中,在什么时候分配内存,什么时候初始化花的时间比较长
3.最后基本上实现后,发现结果仍然存在问题,经过分步调试,发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i
附:
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储郝夫曼编码
typedef char* *HuffmanCode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i
//下面选出权值最小的结点,用s1指向其序号
s1=i;
for(i=1;i
{
if(HT[i].parent==0&&HT[i].weight
}
//下面选出权值次小的结点,用s2指向其序号
for(i=1;i
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
}
//构造Huffman树,求出n个字符的编码
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n
m=2*n-1; //n个叶子n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用,预分配m+1个单元
HuffmanTree p=HT+1;
w++; //w的号单元也没有值,所以从号单元开始
for(i=1;i
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
}
for(;i
{
p->weight=p->parent=p->rchild=p->lchild=0;
}
for(i=n+1;i
{
Select(HT,i-1,s1,s2); //选出当前权值最小的
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到根逆向求每个字符的郝夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='';//编码结束符
for(i=1;i
{
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
{
if(HT[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码到HC
}
free(cd); //释放工作空间
}
void main()
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
HuffmanTree HT;
HuffmanCode HC;
cout
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值,号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符,号单元未用
cout
for(i=1;i
{
cout