哈夫曼树编码实验报告.doc

《哈夫曼树编码实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈夫曼树编码实验报告姓名：沈雅丽班级：09092311学号：09923102需求分析：构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。掌握树的有关操作算法。熟悉树的基本存储方法。学习利用树求解实际问题概要设计：ADTHuffmanTree{数据对象：D={ai

2、ai∈CharSet,i=1,2,……,n, n≥0}数据关系：R={ai-1,ai∈D,ai-1

3、两个结点,其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=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个字符编码的头指针向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='';//编码结束符for(

4、i=1;i<=n;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';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC详细设计：typedefstruct{unsigned

5、intweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表//建立哈夫曼树intm,i,s1,s2,start;unsignedc,f;HuffmanTreep;char*cd;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(p=HT+1,i=1;i<=n;++i,++p,++w){(*p).weight=

6、*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(;i<=m;++i,++p)(*p).parent=0;for(i=n+1;i<=m;++i)//建赫夫曼树{//在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}源代码：#

7、include//malloc()等#include//INT_MAX等#include//EOF(=^Z或F6),NULL#include//cout,cintypedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表intmin(HuffmanTreet,int

8、i){//函数voidselect()调用intj,flag;unsignedintk=UINT_MAX;//取k为不小于可能的值for(j=1;j<=i;j++)if(t[j].weights2){j=s1;s1=s2;s2=j;

9、}}//以上同algo6