算法分析与设计 实验二 哈夫曼编码

(char)); // 为第 i 个编码分配空间 strcpy(hc[i],&cd[start]); } free(cd); for(i=1; i<=n; i++) printf(" 权值为%d 的哈夫曼编码为: %s\n",(*ht)[i].weight,hc[i]); for(i=1; i<=n; i++) w+=(*ht)[i].weight*a[i]; printf("\n 带权路径长度 WPL 为: %d\n\n",w); } void main() { HuffmanTree HT; HuffmanCode HC; int *w,i,n,wei; -6- printf("\t\t\t\t 哈夫曼编码\n" ); printf(" 请输入结点个数: " ); scanf("%d",&n); w=(int *)malloc((n+1)*sizeof(int)); printf("\n 请分别输入这%d 个结点的权值:\n",n); for(i=1; i<=n; i++) { printf(" 结点%d: ",i); fflush(stdin); scanf("%d",&wei); w[i]=wei; } CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n); } 五、实验过程原始记录( 测试数据、图表、计算等)-7- 六、实验结果、分析和结论(误差分析与数据处理、成果总结等。其中,绘制曲线图时必须用计算纸或程序运行结果、改进、收获) 这次实验的内容是哈夫曼编码,哈夫曼树也就是最优二叉树,构造哈夫曼树的过程就是先在所有结点中找到权值最小的两个结点合并,依次这样找到较小的结点合并,最终生成哈夫曼树。树中所有叶子结点的带权路径长度之和最小,带权路径长度就是该结点到树根之间的路径长度与结点上权的乘积,且权值越大的叶子离跟越近。