赫夫曼编译器的简单实现

《赫夫曼编译器的简单实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告赫夫曼编译器数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C★序号学号姓名成绩123指导教师（签名）学　　期：　　2010秋季学期任课教师:实验题目:小组长:　　　联系电话:　　　　　　电子邮件:　完成提交时间：年月日　12数据结构实验报告（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：

2、描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）赫夫曼编码是一种前缀编码，约定左分支表示字符“0”，右分支表示字符“1”，则可以从根节点到叶子节点的路径上分支字符组成的字符串作为该叶子结点字符的编码。求编码的过程就是从叶子结点出发走一条从叶子到根的路径，而译码就是走一条从根出发到叶子结点的路径。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）1、选择森林中根结点的权值最小和次小的两个树，

3、将其根结点的下标号记入s1和s2voidSelect(HuffmanTree&HT,inti,int&s1,int&s2)｛intj,k;for(k=1;k

4、arent!=NULL

5、

6、k==s1)continue;s2=k;break;}for(j=1;j

7、start=1;char*cd;if(n<=1)return;12数据结构实验报告m=2*n-1;if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))exit(OVERFLOW);for(p=HT+1,i=1;i<=n;++i,++zi,++p,++w){/*生成独立的森林*/p->parent=NULL;p->letter=*zi;p->lchild=NULL;p->rchild=NULL;p->weight=*w;}for(;i<=m;++i,++p){(*p).weight=

8、0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;12数据结构实验报告}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*siz

9、eof(char));/*临时的code存储*/cd[n-1]='';for(i=1;i<=n;++i){Istart=n-1;/*按已生成的哈夫曼树，得到各个字符的哈夫曼编码*/for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--Istart]='0';elsecd[--Istart]='1';HC[i]=(char*)malloc((n-Istart)*sizeof(char));strcpy(HC[i],&cd[Istart]);}

10、free(cd);}3、实现译码：j=strlen(c);i=1；while(i<=j){while(HT[yu].lchild!=0)/*因为是完全二叉树*/{12数据结构实验报告if(c[i-1]=='0'){/*用哈夫曼树，将输入的电码（变量