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

《数据结构实验——赫夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、树，（包含合并后删除的）。存储结构描述为：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;intrchild;}huffn

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

4、d;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、{if(ht[i].weight

6、'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].lchild==c)cd[start]='0';elsecd[star

7、t]='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[i])break;}cout<

8、dchangetozimu(huffmantreeht,charb[],intN){inti=0,f=2*N-1;cout<<"该赫夫曼编码的含义是："<