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

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各字符的赫夫曼编码HCi

3、f(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;idata=*data;p-parent=p-lchild=p-rchild=0;p-weight=*w;p-code=(char *malloc(n*sizeof(char; printf(%c %2d %2d

4、 %2d %2dn,p-data,p-parent,p-weight,p-lchild,p-rchild;for(;iparent=p-lchild=p-rchild=p-weight=0;p-data=NULL;p-code=(char *malloc(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;unsigne

5、d int m2=32767;/m1,m2为最小和次小权值int s1=0;int s2=0;/s1,s2为最小和次小节点的序号for(int k=1;k=i-1;k+if(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;print

6、f(-n;printf(存放哈夫曼树的数组HT的终态:n;printf(叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:n;for(p=HT+1,i=1;idata,p-parent,p-weight,p-lchild,p-rchild;for(;iparent,p-weight,p-lchild,p-rchild;/-从叶子到根逆向求每个字符的赫夫曼编码-HC=(HuffmanCodemalloc(n+1*sizeof(char *;/分配n个字符编码的头指针向量char *cd;cd=(char *malloc(n*sizeof(char; /分配求编码的工作空间cdn-1=0; /

7、编码结束符int start;unsigned int f,c;printf(n;printf(-n;printf(每个字符的哈夫曼编码:n;for(p=HT+1,i=1;icode,R;printf(%c ,p-data;printf(%s,HCi;printf(n;printf(输出字符串的赫夫曼编码: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;sc

8、anf(%c,&datai;scanf(%d,π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;四、 测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距本次实验中第三个问题没做出来，我本来想出了一种方法，但是总是出错，我的方法是在结构体中加一个编码域，在形参中加一个字符指针，它的值由主函数中输入的字符串传递过来的。将得出的编码复制到编码域