哈夫曼编码的设计与实现1

《哈夫曼编码的设计与实现1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华北科技学院计算机学院综合性实验报告华北科技学院计算机学院开放实验实验报告实验名称哈夫曼树编码的设计与实现实验学期2014至2015学年第一学期学生所在系部计算机学院年级2013专业班级软件工程B13-2班学生姓名扈鹏程学号201307044213任课教师栾尚敏实验成绩计算机学院制12华北科技学院计算机学院综合性实验报告《哈夫曼树编码的设计与实现》开放实验报告开课实验室：基础（二）年月日实验题目哈夫曼树编码的设计与实现一、实验目的设计哈夫曼树编码系统，锻炼学生的编程能力，巩固哈夫曼算法，熟悉遍历方法。二、设备与环境Windows

2、Xp，VC6.0三、实验内容(1)原理分析：编写此系统是为了实现一个利用哈夫曼算法的编码和译码系统。比如，在利用电报通讯时，需要将文字转换成有二进制的字符组成的字符串。比如需要传送的电文为“ABDCCDA”假设将A,B,C,D分别编码为00,10,10,11。则上述电文便为00011110101100，总长14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的代码。但是这种编码必须遵循:任何一个字符的编码都不是另一个字符编码的前缀。哈夫曼编码恰好可以很好的解决前缀码这一问题。在使用哈夫曼编码时，它会根据结点

3、权值进行，对于使用频率低的字符，会将其置于树层次比较高的地方；相反的是使用频率高的字符。这样做的结果就是使使用频率高的字符编码变得很短而使用频率低的字符编码长一些，而编码长度一般取决于使用频率高的字符，因此这样可以大大缩短字符编码长度，并且不易被别人获取编码规则。运用哈夫曼编码最重要的一点就是建立哈夫曼树，而对于树这种非线性结构，使用链式存储有着多种优势：节省内存空间，因为它不会存在多申请存储空间的情况；同时，指针可以清晰的指示各结点之间的关系，不像顺序存储那样需要进行复杂的逻辑设计；(2)算法设计：采用逐步求精的方法，给出从自

4、然语言描述的算法到类C语言描述的算法；①初始化哈夫曼树1）建立链表，若链表已存在，则销毁原链表，重新建立，用以存储符号及权值。由文件中逐个读取字符，并在链表中查找，找到则权值加1，否则为其新建结点，并赋其权值为1。类C描述：voidnew(Linklist*head){if(head!=NULL)destory(head);p=head->next;while(fp!=EOF){c=getc(fp);while(p!=NULL&&i==0)23华北科技学院计算机学院综合性实验报告{if(c=p->c){p->w++;i++}p0

5、=p;p=p->next;}if(p==NULL){q=Linklist*malloc(space);q->c=c;q->w=1;p0->next=p;}c=getc(fp);}}1）建立哈夫曼树。I在1）建立的链表中，挑选出未标记且权值最小的结点，将其移动至第一个结点位置，并且进行标记，并且重复次操作一次；II新建结点为这两个结点的父节点，并取代这两个结点在链表中的位置，其权值为两个子节点权值之和；III回到步骤I，直至链表中除头外仅剩一个结点。类C描述：voidinit(Linklist*head){while(n>1){s

6、earch(head);search(head);q=Linklist*malloc(space);q->rchild=head->next->next;q->lchild=head->next;q->c=’’;q->lchild->parent=q->rchild->parent=q;q->w=q->lchild->w+q-rlchild->w;q->next=q->rchild->next;head->next=q;n--;}}②哈夫曼树应用1）打印哈夫曼树。I输出根结点存储字符，若没有则不处理；如果此结点为叶结点，则结

7、束；II如果有左子树，画出需要的线条与圆圈，进入左子树处理过程；III如果有右子树，画出需要的线条与圆圈，进入右子树处理过程；类C描述：voidprintHT(Linklist*head){if(head->c!=’’){print(head->c);return;}if(head->lchild!=NULL){line();sq();printHT(head->lchild);}if(head->rchild!=NULL){line();sq();printHT(head->rchild);}}23华北科技学院计算机学院综

8、合性实验报告1）编码I获取一个需要编码的字符；II利用前序遍历的方法找到该字符在哈夫曼树中的位置；III逆序比较，若为左孩子，则向字符串中存入‘0’，否则存入‘1’，直到比较到根，逆序输出编码，同时存入相应文件中；类C描述：voidcode(Linklist*h