实验六-哈夫曼编码和译码的算法设计与实现

1、实验名称实验六哈夫曼编码和译码的算法设计与实现实验日期2022-04-22实验室信息系统设计与仿真室1实验台号34号信工11-1BF李煌班级峰实验方案实验成绩实验操作实验结果、实验目的1根据算法设计需要，掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。、预习与参考1、 认真阅读数据结构教材和算法设计教材内容，熟悉哈夫曼编码的原理；2、设计和编制哈夫曼编译码器。参考数据类型或变量typedef ElemType char ；typedef struct no deint w;int flag;ElemType c;struct node *plin

2、k,*llink,*rlink;char codem;Node;Node *numn , *root;参考 子程序接口与功能描述void SetTree( NODE *root )功能：从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树void En Code( Node *p )功能：利用已建好的哈夫曼树，对输入的正文进行编码void DeCode( void )功能 : 利用已建好的哈夫曼树，将输入的代码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。四、实验步骤1、 设计 SetTree 的测试方案和程序 , 输入测试数据 , 修改并

3、调试程序 , 直至正确为止2、设计EnCode的测试方案和程序，输入测试数据，修改并调试程序，直至正确为止3、设计DeCode的测试方案和程序,输入测试数据，修改并调试程序,直至正确为止4、 将你的程序整理成功能模块存盘备用。5、 将写的程序如下：#include <stdio.h>#include <string.h>#include <math.h>#include <string>#define maxn 20 / 最大结点数目#define inf 0xfffffff /无穷大typedef struct nodedouble w;int

4、 flag;int c;struct node *plink，*llink，*rlink;char codemaxn;int codelen;node() / 初始化节点flag=0;llink=NULL;plink=NULL;rlink=NULL;codelen=0; node;node *num2*maxn-1;/ 指针数组int n;void SetTree(node *&root)/从终端读入字符集大小n,以及n个字符和 n个权值,建立哈夫曼树int i,m,j;scanf("%d",&n);/ 输入结点个数 nfor(i=0;i<n;i+)n

5、umi=new node();numi->c=i;scanf("%lf",&numi->w);/输入结点的权值m=n;double min1,min2;int pos1=0,pos2=0;for(i=0;i<m-1;i+)min1=inf;min2=inf;for(j=0;j<n;j+) /寻找权值最小的两个结点,保存在 pos1 和 pos2 中if(numj->flag=0)if(numj->w<min1)min1=numj->w;pos2=pos1;pos1=j;else if(numj->w<min

6、2)min2=numj->w;pos2=j;numpos1->flag=1; / 将 pos1 和 pos2 合并在新结点中，作为新节点的子 节点numpos2->flag=1;numn=new node(); / 新节点编号从 n 开始 numn->c=-1;/ 添加代码，建立新结点 n/ / 建立新结点 n numn->w=numpos1->w+numpos2->w;numn->llink=numpos1; numn->rlink=numpos2; numpos1->plink=numn;numpos2->plink=num

7、n;n+;root=numn-1;n=m;void EnCode(node *root,int deep,char code) / 利用已建好的哈夫曼树，对输入 的文本进行编码int i;if(root->c!=-1)for(i=0;i<deep;i+)root->codei=codei;root->codelen=deep;return;codedeep='0' /左节点编码为 0EnCode(root->llink,deep+1,code);codedeep='1' /右节点编码为 1EnCode(root->rlink,

8、deep+1,code);对输入的代码进/ 根据 codeivoid DeCode(node *root,char code) /利用已建好的哈夫曼树，行译码int i;node *temproot=root;int len=strlen(code);int ansmaxn,anslen=0;for(i=0;i<len;i+)/ 添加代码，根据 codei 的值确定 temproot 的指向 / 的值确定 temproot 的指向if(codei='0') temproot=temproot->llink;elsetemproot=temproot->rlin

9、k; if(temproot->c!=-1) ansanslen+=temproot->c; temproot=root;if(temproot->llink=NULL && temproot->rlink=NULL)printf(" 你输入的数据不存在于该哈弗曼树中 !n"); return;printf(" 输入数据的译码为： n");for(i=0;i<anslen;i+)printf("%d",ansi);printf("n");void print()int

10、i,j;for(i=0;i<n;i+)printf("%.2f:",numi->w);for(j=0;j<numi->codelen;j+)printf("%c",numi->codej); printf("n");int main()freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);node *root=NULL;root=new node();SetTree(root);char codemaxn*maxn;EnCode(root,0,code);print();:n");printf(" 按上面的编码规那么输入代码 scanf("%s",code);DeCode(root,code); return 0;五、测试输入80.6 0.2 0.05 0.05 0.03