创建哈夫曼树

《创建哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、河北金融学院实验报告纸系别：信息管理与工程系专业：信息管理与信息系统班级：08信管本课程名称数据结构*HC=(HuffmanCode)malloc((n+1)*sizeof(char*));/*分配n个字符编码的头指针向量([0]不用)*/cd=(char*)malloc(n*sizeof(char));/*分配求编码的工作空间*/cd[n-1]='';/*编码结束符*/for(i=1;i<=n;i++){/*逐个字符求赫夫曼编码*/start=n-1;/*编码结束符位置*/for(c=i,f=HT[i].parent;f!=0;c

2、=f,f=HT[f].parent)/*从叶子到根逆向求编码*/if(HT[f].lchild==c)/*c是其双亲的左孩子*/cd[--start]='0';/*由叶子向根赋值'0'*/else/*c是其双亲的右孩子*/cd[--start]='1';/*由叶子向根赋值'1'*/HC[i]=(char*)malloc((n-start)*sizeof(char));/*为第i个字符编码分配空间*/strcpy(HC[i],cd+start);/*从cd复制编码(串)到HC*/}free(cd);/*释放工作空间*/return(HC)

3、;}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w,n,i;char*filename;FILE*f;/*文件指针类型*/clrscr();printf("pleaseinputthefile:");scanf("%s",filename);f=fopen(filename,"r");/*打开数据文件，并以f表示*/fscanf(f,"%d",&n);/*由文件输入数据元素个数*/w=(int*)malloc(n*sizeof(int));/*动态生成存放n个权值的空间*//*printf("

4、npleaseinputthe%dweight:",n);*/for(i=0;i<=n-1;i++)/*scanf("%d",w+i);*//*依次输入权值*/fscanf(f,"%d",w+i);for(i=0;i<=n-1;i++)printf("%d",w[i]);HC=HuffmanCoding(HT,HC,w,n);/*根据w所存的n个权值构造赫夫曼树HT，n个赫夫曼编码存于HC*/for(i=1;i<=n;i++)printf("%-3d%-8s",w[i-1],HC[i]);/*依次输出赫夫曼编码*/}实验名称创

5、建哈夫曼树姓名吴玉洁学号35成绩实验目的体会哈夫曼树的生成及哈夫曼编码的思想和算法实现。实验内容1．哈夫曼编码的顺序存储结构的定义2．各基本操作的实现求n个结点中权值最小的树的根结点，在n个结点中选择2个权值最小的树的根结点，创建建哈夫曼树，进行哈夫曼编码3.验证各操作的正确性要求输入{0.1，0.2，0.15，0.2，0.05，0.3}6个权值，生成相应的哈夫曼编码。实验步骤#include"c1.h"#defineOrder/*定义Order。第2行*/typedefstruct/*结点的结构，在教科书第147页*/{unsigne

6、dintweight;/*结点的权值*/unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/HuffmanCodeHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn)/*算法6.12*/{/*w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC*/intstart;unsignedf;i

7、ntm,i,s1,s2,j,m1,m2;unsignedc;HuffmanTreep;char*cd;if(n<=1)/*叶子结点数不大于n*/return;m=2*n-1;/*n个叶子结点的赫夫曼树共有m个结点*/HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未用*/for(p=HT+1,i=1;i<=n;++i,++p,++w)/*从1号单元开始到n号单元，给叶子结点赋值*/{/*p的初值指向1号单元*/(*p).weight=*w;/*赋权值*/(*p).parent=0;/

8、*双亲域为空(是根结点)*/(*p).lchild=0;/*左右孩子为空(是叶子结点，即单结点树)*/(*p).rchild=0;}for(;i<=m;++i,++p)/*i从n+1到m*/(*p).par