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

《2022年实验六-哈夫曼编码和译码的算法设计与实现.docx》由会员分享，可在线阅读，更多相关《2022年实验六-哈夫曼编码和译码的算法设计与实现.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源实 验 名实 验 方实 验试验六哈夫曼编码和译码的算法设计与实现称案成果实 验 日实验信息系统设计与仿实 验 操2021-04-22期室真室 I作实 验 台信 工 11-1BF李 煌实 验 结34号班级号峰果一、试验目的1、依据算法设计需要 , 把握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编译码器；3、把握贪心算法的一般设计方法；二、预习与参考1、仔细阅读数据结构教材和算法设计教材内容,熟识哈夫曼编码的原理;2、设计和编制哈夫曼编译码器； 参考数据类型或变量 typedef ElemType char；typedef struct nodeint w; int flag;

2、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、1、 设计 SetTree的测试方案和程序, 输入测试数据 , 修改并调试程序 , 直至正确为止 ;2、设计 EnCode的测试方案和程序, 输入测试数据, 修改并调试程序, 直至正确为止;3、设计 DeCode的测试方案和程序, 输入测试数据, 修改并调试程序, 直至正确为止;4、 将你的程序整理胜利能模块存盘备用；5、 将写的程序如下： #include #include #include #include #define maxn 20/最大结点数目#define inf 0xfffffff /无穷大typedef struct nodedouble w; int flag; int c

4、;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 SetTreenode *&root/从终端读入字符集大小n，以及 n 个字符和 n 个权值， 建立哈夫曼树int i,m,j;scanf%d,&n;/输入结点个数 n fori=0;ic=i;scanf%lf,&numi-w;/输入结点的权值m=n

5、;double min1,min2;int pos1=0,pos2=0; fori=0;im-1;i+min1=inf; min2=inf;forj=0;jflag=0ifnumj-ww;pos2=pos1;pos1=j;欢迎下载精品学习资源else ifnumj-ww; 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

6、=numpos1; numn-rlink=numpos2; numpos1-plink=numn; numpos2-plink=numn;n+;root=numn-1; n=m;void EnCodenode *root,int deep,char code /利用已建好的哈夫曼树，对输入的文本进行编码int i;ifroot-c.=-1fori=0;icodei=codei;欢迎下载精品学习资源root-codelen=deep; return;codedeep=0;/左节点编码为 0 EnCoderoot-llink,deep+1,code; codedeep=1;/右节点编码为 1 En

7、Coderoot-rlink,deep+1,code;void DeCodenode *root,char code /利用已建好的哈夫曼树，对输入的代码进行译码int i;node *temproot=root; int len=strlencode;int ansmaxn,anslen=0;fori=0;illink;elsetemproot=temproot-rlink;iftemproot-c.=-1ansanslen+=temproot-c; temproot=root;iftemproot-llink=NULL & temproot-rlink=NULLprintf你输入的数据不存

8、在于该哈弗曼树中.n; return;欢迎下载精品学习资源printf输入数据的译码为： n; fori=0;ianslen;i+printf%d,ansi;printfn;void printint i,j; fori=0;iw; forj=0;jcodelen;j+printf%c,numi-codej; printfn;int mainfreopenin.txt,r,stdin;freopenout.txt,w,stdout;node *root=NULL; root=new node;SetTreeroot;char codemaxn*maxn; EnCoderoot,0,code; print;printf按上面的编码规章输入代码:n;欢迎下载精品学习资源scanf%s,code;DeCoderoot,code;return 0;五、测试输入80.60.20.050.050.030.030.03输出0.6： 00.2： 100.05：11000.05：11110.03：110100.03：110110.03：111010.01：11100六、试验报告要求1、阐述试验目的和试验内容;2、提交试验程序的功能模块;3、 记录最终测试数据和测试结果；七、心得在试验中我把握哈夫曼编码的二叉树结构表示方法；欢迎下载