哈夫曼树上机实验报告

1、霍夫曼树实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。基本要求：熟练掌握树的操作。程序实现：程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。要点分析:题目中涉及的主要知识点： 1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）： （1）由给定的n个权值w0, w1, w2, , wn-1，构造具有n棵二叉树的集合F =T0, T1, T2, , Tn-1，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、

2、右子树均为空。 （2）重复以下步骤, 直到F中仅剩下一棵树为止: 在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵 新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删去这两棵二叉树。 把新的二叉树加入F。 2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2, dn 作为叶子结点，把w1,w2,wn作为叶子结点 的权，构造赫夫曼树。在赫夫曼树中结点的左分支赋0，右 分支赋1，从根结点到叶子结点的路径上的数字拼接起来就 是这个叶子结点字符的编码。 3、译码的过程是分解电文中的字符串，从根出发，按字符0或1确定找左孩子或右孩子，直至叶子节点，便求得该子串

3、相应的字符。心得体会：通过本次实验，我熟练掌握了结构体、指针及二叉树的生成、遍历等操作，掌握了霍夫曼编码和译码的原理，熟练掌握树的操作，尤其是对霍夫曼树有了更深刻的理解。同时，在编写代码的过程中方，对字符串的相关知识进行了回顾。代码#include<stdio.h>#include<stdlib.h>#include<string.h>typedef structint weight;int parent,lchild,rchild;int sign;HTNode,*HuffmanTree;typedef char * *HuffmanCode;void H

4、uffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *s);void select(HuffmanTree &HT,int i,int &s1,int &s2);void creatHuffmanTree(int *w,char *s,char *r);void pr(HuffmanCode &HC,char r,char s,char a);void HuffmanYM(HuffmanCode &HC,char r,char a,int n,HuffmanTree

5、 &HT);void HuffmanPass(HuffmanCode &HC,char r,int n,HuffmanTree &HT);int main()char s100;char r100;char a100="a"int w100;int n,p;HuffmanTree HT;HuffmanCode HC;printf("请输入进行编码的字符串n");scanf("%s",s);p=strlen(s);if(p!=1)creatHuffmanTree(w,s,r);printf("进行编码.

6、n"); if(p!=1) HuffmanCoding(HT,HC,w,strlen(r)-1,r);else printf("%c的霍夫曼编码是: %cn",s0,'0');printf("霍夫曼码序列为：n");if(p!=1) for(int i=0;i<strlen(s);i+) pr(HC,r,si,a);printf("n");n=strlen(r)-1;if(p=1)printf("0n");printf("霍夫曼编码进行译码:n");if(p=1)

7、printf("%c",s0);else HuffmanYM(HC,r,a,n,HT);printf("n"); printf("先序遍历输出叶子节点n");if(p=1)printf("%cn",s0);else HuffmanPass(HC,r,n,HT);return 0;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w,int n,char s)int s1,s2,f,c;int m,i,l;int start;char cd1

8、01;if(n<1)return;l=strlen(s);m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);HT0.weight=10000; for (i=1;i<=n;+i) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign=0; for(;i<=m+1;+i) HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; HTi.sign=0; for(i=n+1;i<=m;i+

9、) select(HT,i-1,s1,s2);/选择最小的两个结点 HTs1.parent=i;HTs2.parent=i;/将它们的父节点赋值 HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n; c=i; for(f=HTi.parent;f!=0;f=HTf.parent) if(HTf.lchild=c) start-; cdsta

10、rt='0' else start-; cdstart='1' c=f; HCi=(char *)malloc(n-start)*sizeof(char); for(int a=0;a<n-start;a+) HCia=cdstart+a; HCia='0' printf("%c的霍夫曼编码是: %sn",si,HCi);void select(HuffmanTree &HT,int i,int &s1,int &s2)s1=0;s2=0;for(int j=1;j<=i;j+)if(HTj

11、.parent=0)if(HTj.weight<=HTs1.weight)s1=j;else continue;else continue;for(j=1;j<=i;j+)if(j=s1)continue;else if(HTj.parent=0) if(HTj.weight<=HTs2.weight) s2=j; else continue; else continue;void creatHuffmanTree(int w,char s,char r)int g=1;int q=0;r0='0'r1=s0;w0=1;for(int e=1;e<str

12、len(s);e+)for(int k=1;k<=g;k+)if(rk=se)wk-1+;q=1;else continue;if(q=0)r+g=se;wg-1=1;q=0;r+g='0'void pr(HuffmanCode &HC,char r,char s,char a)for(int i=1;i<strlen(r);i+)if(ri=s)printf("%s",HCi);strcat(a,HCi);else continue;void HuffmanYM(HuffmanCode &HC,char r,char a,int

13、 n,HuffmanTree &HT)int e=strlen(a);int k=0;int f=2*n-1;char b10="1"for(int j=1;j<=e;j+)if(HTf.lchild!=0|HTf.rchild!=0)bk=aj;k+; if(aj='1') f=HTf.rchild;else if(aj='0')f=HTf.lchild;else for(int s=1;s<=n;s+)if(strcmp(HCs,b)=0)printf("%c",rs);break;else con

14、tinue;for(int u=0;u<10;u+)bu='0'k=0;f=2*n-1;j=j-1;void HuffmanPass(HuffmanCode &HC,char r,int n,HuffmanTree &HT)int f,k=0;char b10="a"f=2*n-1;HTf.sign=0;if(HTf.lchild=0&&HTf.rchild=0)return;doif(HTf.lchild=0&&HTf.rchild=0)for(int s=1;s<=n;s+)if(strcmp(HCs,b)=0)printf("%c",rs);break;else continue; bk-='0'HTf.s