文档介绍：淮海工学院计算机工程学院实验报告书课程名:《算法分析与设计》题目:实验3贪心算法哈夫曼编码班级:软件102班学号:姓名:鹿迅评语:成绩:指导教师:批阅时间:年月日实验3贪心算法实验目的和要求(1)了解前缀编码的概念,理解数据压缩的基本方法;(2)掌握最优子结构性质的证明方法;(3)掌握贪心法的设计思想并能熟练运用(4)证明哈夫曼树满足最优子结构性质;(5)设计贪心算法求解哈夫曼编码方案;(6)设计测试数据,写出程序文档。实验内容设需要编码的字符集为{d1,d2,…,dn},它们出现的频率为{w1,w2,…,wn},应用哈夫曼树构造最短的不等长编码方案。实验环境TurboC或VC++实验学时2学时,必做实验数据结构与算法structhuffman{ doubleweight;//用来存放各个结点的权值 intlchild,rchild,parent;//指向双亲、孩子结点的指针};核心源代码#include<iostream>#include<string>usingnamespacestd;structhuffman{ doubleweight; intlchild,rchild,parent;};staticinti1=0,i2=0;intSelect(huffmanhuff[],inti){ intmin=11000; intmin1; for(intk=0;k<i;k++) { if(huff[k].weight<min&&huff[k].parent==-1) { min=huff[k].weight; min1=k; } } huff[min1].parent=1; returnmin1;}voidHuffmanTree(huffmanhuff[],intweight[],intn){ for(inti=0;i<2*n-1;i++) { huff[i].lchild=-1; huff[i].parent=-1; huff[i].rchild=-1; } for(intl=0;l<n;l++) { huff[l].weight=weight[l]; } for(intk=n;k<2*n-1;k++) { inti1=Select(huff,k); inti2=Select(huff,k); huff[i1].parent=k; huff[i2].parent=k; huff[k].weight= huff[i1].weight+huff[i2].weight; huff[k].lchild=i1; huff[k].rchild=i2; }}voidhuffmancode(huffmanhuff[],intn){strings; intj; for(inti=0;i<n;i++) { s=""; j=i; while(huff[j].parent!=-1) { if(huff