数据结构实验——赫夫曼编码

数据结构实验——赫夫曼编码

ID:16357134

大小:184.50 KB

页数:11页

时间:2018-08-09

数据结构实验——赫夫曼编码_第1页
数据结构实验——赫夫曼编码_第2页
数据结构实验——赫夫曼编码_第3页
数据结构实验——赫夫曼编码_第4页
数据结构实验——赫夫曼编码_第5页
资源描述:

《数据结构实验——赫夫曼编码》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实习三二叉树应用一、实验目的:熟悉二叉树的存储结构,二叉树的有关的操作。二、实验内容及要求:哈夫曼编/译码器[问题描述]利用哈夫曼编码进行通信可以大大提高信道利用率,这要求在发送端通过一个编码系统对待传输预先编码,在接收端将传来的数据进行译码。对于双工通道,每端都需要一个完整的编/译码系统。[基本要求]试为这样的信息收发站写一个哈夫曼码的编/译码系统。[实现提示]构造哈夫曼树的算法实现:假设哈夫曼树采用双亲孩子表示法存储,并增加权值域,构造哈夫曼树的叶子结点(树木的权)有N个,合并次数为N—1次,则森林中总共

2、有2N—1棵树,(包含合并后删除的)。存储结构描述为:constintn=maxn//maxn表示叶子数目constintm=2*n-1//m为森林中树的棵数classtree{floatweight;//权值intparent;//双亲intlch,rch;//左,右孩子}treehftree[m+1];//规定从第一个元素hftree[1]开始使用数组元素,故定义长度为m+1而不为m结构类型:typedefstruct{chardata;intweight;intparent;intlchild;intr

3、child;}huffnode;typedefstruct{charcd[MAX];intstart;}huffcode;主程序intmain(){初始化:输入字符代码以及权值。编制哈夫曼码:根据权值建立二叉树,输出相应的根节点到叶结点的路径,便是哈夫曼编码。编码:输入字符,输出哈夫曼码。译码:输入哈夫曼,输出字符代码。退出:结束进程,退出程序。三、实验题目:构造哈弗曼树的算法。四、实验源代码:#include#include#includetyp

4、edefstruct{charword;intweight;intparent,lchild,rchild;}htnode,*huffmantree;voidselect(huffmantreeht,inta,int&s1,int&s2){ht[0].weight=1000;s1=0;for(inti=1;i<=a;i++){if(ht[i].parent==0){if(ht[i].weight

5、i++){if(ht[i].parent==0){if(ht[i].weight

6、ight+ht[s2].weight;ht[i].word='x';}}typedefchar**huffmancode;voidcreathuffmancode(huffmantreeht,huffmancode&hc,intN){hc=newchar*[N+1];char*cd=newchar[N];cd[N-1]='';intstart,c,f;for(inti=1;i<=N;i++){start=N-1;c=i;f=ht[i].parent;while(f!=0){--start;if(ht[f]

7、.lchild==c)cd[start]='0';elsecd[start]='1';c=f;f=ht[f].parent;}hc[i]=newchar[N-start];strcpy(hc[i],&cd[start]);}deletecd;}voidbianma(huffmancodehc,huffmantreeht,char*a,intN){inti=0,j;cout<<"该字母组的赫夫曼编码是:";while(a[i]!=''){for(j=1;j<=N;j++){if(ht[j].word==a[

8、i])break;}cout<

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

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

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