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

实习三 二叉树应用 一、实验目的： 熟悉二叉树的存储结构，二叉树的有关的操作。 二、实验内容及要求： 哈夫曼编/译码器 [问题描述] 利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统 对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道，每端都需要一个完整 的编/译码系统。 [基本要求] 试为这样的信息收发站写一个哈夫曼码的编/译码系统。 [实现提示] 构造哈夫曼树的算法实现： 假设哈夫曼树采用双亲孩子表示法存储，并增加权值域，构造哈夫曼树的叶子结点（树 木的权）有N个，合并次数为N—1次，则森林中总共有2N—1棵树，（包含合并后删除的）。 存储结构描述为： const int n=maxn //maxn表示叶子数目 const int m=2*n-1 //m为森林中树的棵数 class tree { float weight; //权值 int parent; //双亲 int lch, rch; //左，右孩子 } tree hftree[m+1]; //规定从第一个元素hftree[1]开始使用数组元素，故定义长 度为m+1而不为m 结构类型： typedef struct { char data; int weight; int parent; int lchild; int rchild; }huffnode; typedef struct { char cd[MAX]; int start; }huffcode; 主程序 int main() { 初始化：输入字符代码以及权值。 编制哈夫曼码：根据权值建立二叉树, 输出相应的根节点到叶结点的路径,便是哈夫曼编码。 编码：输入字符,输出哈夫曼码。 译码：输入哈夫曼,输出字符代码。 退出：结束进程,退出程序。 三、实验题目： 构造哈弗曼树的算法。 实验源代码： #includeiostream.h #includestring.h #includestdio.h typedef struct { char word; int weight; int parent,lchild,rchild; }htnode,*huffmantree; void select(huffmantree ht,int a,int s1,int s2) { ht[0].weight=1000; s1=0; for(int i=1;i=a;i++) { if(ht[i].parent==0) { if(ht[i].weightht[s1].weight) { s1=i; } } } ht[s1].parent=1; s2=0; for(i=1;i=a;i++) { if(ht[i].parent==0) { if(ht[i].weightht[s2].weight) { s2=i; } } } } void creathuffmantree(huffmantree ht,int N) { int m=2*N-1; int s1,s2; for(int i=N+1;i=m;i++) { select(ht,i-1,s1,s2); ht[s1].parent=i; ht[s2].parent=i; ht[i].lchild=s1; ht[i].rchild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight; ht[i].word=x; } } typedef char **huffmancode; void creathuffmancode(huffmantree ht,huffmancode hc,int N) { hc=new char*[N+1]; char *cd=new char[N]; cd[N-1]=\0; int start,c,f; for(int i=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; else cd[start]=1; c=f; f=ht[f].parent; } hc[i]=new char[N-start]; strcpy(hc[i],cd[start]); } delete cd; } void bianma(huffmancode hc,huffmantree h