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

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

ID:33585165

大小:73.00 KB

页数:7页

时间:2019-02-27

用赫夫曼树进行字符串的编码_第1页
用赫夫曼树进行字符串的编码_第2页
用赫夫曼树进行字符串的编码_第3页
用赫夫曼树进行字符串的编码_第4页
用赫夫曼树进行字符串的编码_第5页
资源描述:

《用赫夫曼树进行字符串的编码》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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

2、include#defineN8#defineM4typedefstruct{chardata;char*code;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,char*data,int*w,intn,char*str){//存放n个字符的权值(均>

3、0),构造赫夫曼树HT,并求出n各字符的赫夫曼编码HCif(n<=1)return;intm=2*n-1;//总节点数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用HuffmanTreep;第7页共7页inti,j;printf("");printf("------------------------------");printf("存放哈夫曼树的数组HT的初态:");printf("叶子节点以及它的双亲节点,权值,左孩子,右孩子分别为:");for(p=HT+1,i=1;i<=n;++i,+

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

5、izeof(char));printf("%2d%2d%2d%2d",p->parent,p->weight,p->lchild,p->rchild);}for(i=n+1;i<=m;++i){//建赫夫曼树//在HT[1--i-1]选择parent为0且weight最小的两个节点,其序号分别为s1和s2unsignedintm1=32767;unsignedintm2=32767;//m1,m2为最小和次小权值ints1=0;ints2=0;//s1,s2为最小和次小节点的序号for(intk=1;k<=i-1;k++){if((HT[k].parent==0)

6、&&(HT[k].weight

7、n");printf("存放哈夫曼树的数组HT的终态:");printf("叶子节点以及它的双亲节点,权值,左孩子,右孩子分别为:");for(p=HT+1,i=1;i<=n;++p,++i)printf("%c%2d%2d%2d%2d",p->data,p->parent,p->weight,p->lchild,p->rchild);for(;i<=m;++p,++i)printf("%2d%2d%2d%2d",p->parent,p->weight,p->lchild,p->rchild);//----从叶子到根逆向求每个字符的赫

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。