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

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业实验六哈夫曼编码和译码的算法设计与实现实验名称实验六 哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期 -04-22实 验 室信息系统设计与仿真室I实验操作实验台号 34号班级姓名信工11-1BF 李煌峰实验结果一、实验目的1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、掌握贪心算法的一般设计方法。二、预习与参考1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2、设计和编制哈夫曼编译码器。参考数据类型

2、或变量typedef ElemType char；typedef struct node int w; int flag; ElemType c;struct node *plink,*llink,*rlink; char codem;Node;Node *numn, *root;参考子程序接口与功能描述void SetTree( NODE *root )功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼树，对输入的正文进行编码 void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代

3、码进行译码三、实验要求上机实验时，一人一组，独立上机，熟练运用二叉树与贪心思想对数据进行压缩。四、实验步骤设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;将你的程序整理成功能模块存盘备用。将写的程序如下：#include #include #include #include #define maxn 20 /最大结点数目#define inf 0 xfffffff /无穷大typedef struct nod

4、e double w; int 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);/输入结点个数n for(i=0;ic=i; sc

5、anf(%lf,&numi-w);/输入结点的权值 m=n; double min1,min2;int pos1=0,pos2=0; for(i=0;im-1;i+) min1=inf; min2=inf; for(j=0;jflag=0) if(numj-ww;pos2=pos1; pos1=j; else if(numj-ww; pos2=j; numpos1-flag=1; /将pos1和pos2合并在新结点中，作为新节点的子节点 numpos2-flag=1; numn=new node(); /新节点编号从n开始 numn-c=-1; /添加代码，建立新结点n/ /建立新结点n nu

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

7、eep+1,code); codedeep=1; /右节点编码为1 EnCode(root-rlink,deep+1,code);void DeCode(node *root,char code) /利用已建好的哈夫曼树，对输入的代码进行译码 int i;node *temproot=root; int len=strlen(code); int ansmaxn,anslen=0; for(i=0;illink;elsetemproot=temproot-rlink; if(temproot-c!=-1) ansanslen+=temproot-c; temproot=root; if(tem

8、proot-llink=NULL & temproot-rlink=NULL) printf(你输入的数据不存在于该哈弗曼树中!n); return; printf(输入数据的译码为：n); for(i=0;ianslen;i+) printf(%d,ansi); printf(n);void print() int i,j; for(i=0;iw); for(j=0;jcodelen;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();printf(按上面的编码规则输入代码:n);scanf(%s,code);DeCode(root,code); return 0;五、测试输入80.6 0.2 0.05 0.05 0.03 0.03 0.03 0.01输出0.6： 00.2： 10