用赫夫曼树进行字符串的编码

1、华北水利水电大学 数据结构 实验报告实验三 树的应用一、 实验题目：树的应用哈夫曼编码二、 实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：1 输出存放哈夫曼树的数组HT的初态和终态；2 输出每个字符的哈夫曼编码；3 输入由上述若干字符组成的字符串，对电文进行编码并输出；三、 程序源代码：#include #include #include #define N

2、8#define M 4typedef structchar data;char *code;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *data,int *w,int n,char *str/存放n个字符的权值(均>0，构造赫夫曼树HT，并求出n

3、各字符的赫夫曼编码HCif(n<=1 return;int m=2*n-1; /总节点数HT=(HuffmanTreemalloc(m+1*sizeof(HTNode;/0号单元未用HuffmanTree p;int i,j;printf("n"printf("-n"printf("存放哈夫曼树的数组HT的初态:n"printf("叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:n"for(p=HT+1,i=1;i<=n;+i,+p,+data,+wp->data=*data;p->p

4、arent=p->lchild=p->rchild=0;p->weight=*w;p->code=(char *malloc(n*sizeof(char; printf("%c %2d %2d %2d %2dn",p->data,p->parent,p->weight,p->lchild,p->rchild;for(;i<=m;+p,+ip->parent=p->lchild=p->rchild=p->weight=0;p->data=NULL;p->code=(char *ma

5、lloc(n*sizeof(char; printf(" %2d %2d %2d %2dn",p->parent,p->weight,p->lchild,p->rchild;for(i=n+1;i<=m;+i/建赫夫曼树/在HT1-i-1选择parent为0且weight最小的两个节点，其序号分别为s1和s2unsigned int m1=32767;unsigned int m2=32767;/m1,m2为最小和次小权值int s1=0;int s2=0;/s1,s2为最小和次小节点的序号for(int k=1;k<=i-1;k+if(

6、HTk.parent=0&&(HTk.weight m2=m1;s2=s1;m1=HTk.weight;s1=k;else if(HTk.parent=0&&(HTk.weight m2=HTk.weight;s2=k;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;printf("n"printf("-n"printf("存放哈夫曼树的数组HT的终态:n"printf(

7、"叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:n"for(p=HT+1,i=1;i<=n;+p,+iprintf("%c %2d %2d %2d %2dn",p->data,p->parent,p->weight,p->lchild,p->rchild;for(;i<=m;+p,+iprintf(" %2d %2d %2d %2dn",p->parent,p->weight,p->lchild,p->rchild;/-从叶子到根逆向求每个字符的赫夫曼编码-HC

8、=(HuffmanCodemalloc(n+1*sizeof(char *;/分配n个字符编码的头指针向量char *cd;cd=(char *malloc(n*sizeof(char; /分配求编码的工作空间cdn-1='0' /编码结束符int start;unsigned int f,c;printf("n"printf("-n"printf("每个字符的哈夫曼编码:n"for(p=HT+1,i=1;i<=n;+i,+p /逐个字符求赫夫曼编码start=n-1;/编码结束符位置for(c=i,f=HTi.

9、parent;f!=0;c=f,f=HTf.parent/从叶子到根逆向求编码if(HTf.lchild=c cd-start='0'else cd-start='1'HCi=(char *malloc(n-start*sizeof(char; /为第i个字符编码分配空间char *R=&cdstart;strcpy(HCi,&cdstart;strcpy(p->code,R;printf("%c ",p->data;printf("%s",HCi;printf("n"pri

10、ntf("输出字符串的赫夫曼编码:n"for(i=0;i for(p=HT+1,j=0;j if(stri=p->dataprintf("%s",p->code;free(cd;/释放工作空间int main(char dataN,strM;int pN,i;for(i=0;i printf("输入第%d个字符及频率：n",i+1;scanf("%c",&datai;scanf("%d",&pi;getchar(;printf("输入字符串：n"for(i=0;i scanf("%c",&stri;HuffmanTree HT;HuffmanCode HC;HuffmanCoding(HT,HC,data,p,N,str;printf("n"return 0;四、 测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距本次实验中第三个问题没做出来，我本来想出了一种方法，但是总是出错，我的方法是在结构体中加一个编码域，