数据结构实验：haffman树的编码

《数据结构实验：haffman树的编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验7：Haffman树的编码一、实验目的1．掌握Haffman树的存储结构。2．掌握Haffman树的构建算法。3．掌握Haffman树的编码算法并能输出。4．将算法用C语言编写完整程序并上机运行，记录实验过程与数据。二、实验仪器：1.硬件：Lenovo通用PC机，2.软件：WINDOWS7，WORD，GCC编译器三、实验原理：1.Haffman树结点的数据结构typedefstructNODE{chardata;intweight，parent，leftChild，rightChild;}haffmanTreeNode;2．Haf

2、fman树的输入intm=2*leafNumber-1;haffmanTreeNode*p;p=(haffmanTreeNode*)malloc((m+1)*sizeof(haffmanTreeNode));for(i=1;i<=m;i++){if(i<=leafNumber)scanf("%c,%d",&p[i].data,&p[i].weight);else{p[i].data='#';p[i].weight=0;}p[i].parent=p[i].leftChild=p[i].rightChild=0;}3.Haffman树的构

3、建for(i=leafNumber+1;i<=m;i++){w1=w2=1000;c1=c2=0;for(j=1;j

4、c2].parent=i;}四、实验步骤：1.设计一个实验样本，字符集合为C，对应的相权值集合为W：C={a,b,c,d,e,f}所对应的权值集合为W={8,3,4,6,5,5}2.将字符及权值存储至一棵haffman树，并将各个字符的编码值输出code=(int*)malloc(leafNumber*sizeof(int));nodeNumber=2*leafNumber-1;p=(*t);haffmanStoragePrint(p);for(i=1;i<=leafNumber;i++){child=i,parent=p[child

5、].parent,j=0;while(parent>0){if(p[parent].leftChild==child)code[j++]=0;elsecode[j++]=1;child=parent;parent=p[parent].parent;}printf("%c(",p[i].data);for(j--;j>=0;j--)printf("%d",code[j]);printf(")");}五、数据处理及结论1.输入：2.输出：七、思考题：1.如果在haffman树的结点设计时删除掉chardata这个数据项是否能完成编码？

6、附代码：#include#include#include//设计haffman树的数据结构typedefstructNODE{chardata;intweight;intparent;intleftChild;intrightChild;}haffmanTreeNode;typedefenum{FALSE,TRUE}status;//构建一棵haffman树statushaffmanTreeCreate(haffmanTreeNode**t,intleafNumber){int

7、i,j;//充当循环变量intw1,w2;//每个结点集中权值最小的两个intc1,c2;//权值最小的两个结点的下标值intm=2*leafNumber-1;//一个有n个叶子结点的haffman树共有2n-1个结点haffmanTreeNode*p=(haffmanTreeNode*)malloc((m+1)*sizeof(haffmanTreeNode));//0号元素不用if(p==NULL)returnFALSE;else(*t)=p;//修改*t的值，相当于置返回值//初始化一棵haffman树的所有结点，前n个叶子结点输

8、入权值，后面n-1个元素置空for(i=1;i<=m;i++){if(i<=leafNumber){printf("pleaseenterthevalueandweightofnode%d:",i);fflush(std