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

1、实验名称哈夫曼编码和译码的算法设计与实现实验日期实验室 信息系统设计与仿真室I实验台号班级姓名实验方案实验成绩实验操作实验结果一、实验目的1、掌握哈夫曼编码的二叉树结构表示方法；2、编程实现哈夫曼编码译码器；3、掌握贪心算法的设计策略。二、实验任务从文件中读取数据，构建哈夫曼树；利用哈夫曼树，对输入明文进行哈夫曼编码；利用哈夫曼树，对输入编码译码为明文。三、实验设计方案1、结构体设计Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标#define N 29/26个小写字母，逗号，句号和空格字符.struct treenode /静态链表char c; /charint w; /w

2、eightint f;/fatherint l; /left child indexint r; /right child index;struct treenode htree2*N-1;2、自定义函数设计函数原型声明void input();读取文件字符、权值数据void huffman();/建立 huffman 树void getcode(int i, char *str);/得到单个字符的 huffman 编码void encode(char ch);/将明文进行 huffman 编码void decode(char *str);/将 huffman 编码译为明文读取文件字符、权值数

3、据void input() J 爵佑呼工学院iHiinan Iruiiutai tri mrd/接收字符接收权值/接收回车int i; char c; int f; freopen(in.txt”,r”,stdin); for(i=0;iN;i+) c=getchar();scanf(%d”,&f);getchar();hti.c=c;hti.w=f;hti.l=hti.f=hti.r=-1;/初始化父亲、左右孩子下标 freopen( CON, r”, stdin);建立huffman树/使用贪心法建立huffman树,每次选择权值最小的根结点 void huffman() void huf

4、fman() int j,k,n; input(); j=0; k=N; for(n=N;n2*N-1;n+)/建立 huffman 树，共合并 N-1 次int r=0,s=0; htn.l=htn.f=htn.r=-1; while(rhtj.w) & jN) s+=htj.w; if(r=0) htn.l = j;/修改父亲、孩子下标else htn.r=j; htj.f=n; j+; else s+=htk.w; if(r=0) htn.l = k;/修改父亲、孩子下标else htn.r=k; htk.f=n; k+; r+; htn.w=s;/修改权值根据字符下标找到字符的huff

5、man编码/根据字符所在的下标，从叶子结点往上搜索到根节点，然后逆置得到该字符的huffman编码void getcode(int i, char *str)(int n,j,l=0;for(n=i;htn.f!=-1;n=htn.f) /沿着父亲往上搜索int m=htn.f;if(n=htm.l)strl+=0; /左孩子记为 0elsestrl+=1; /右孩子记为 1for(j=0;j=(l-1)/2;j+) /将编码逆置char t;t=strj;strj=strl-1-j;strl-1-j=t;strl=0; / str存放huffman编码，字符串结束标记读入明文生成huffma

6、n编码void encode(char ch)int i;char strN;for(i=0;hti.c!=0;i+)if(hti.c=ch)/找字符下标break;if (hti.c!=0)getcode(i,str); /得到字符的 huffman 编码 printf(%s,str);将huffman编码串译码为明文void decode(char *str)while(*str!=0)int i;for(i=2*N-2;hti.l!=-1;)if(*str=0)i=hti.l;elsei=hti.r;str+;printf(%c”,hti.c);3、主函数设计思路：主函数实现实验任务的基

7、本流程。void main() char ch; int i;char str100;huffman();/建立 huffman 树printf(-请输入明文：，输入明文while(ch=getchar()!=n)encode(ch);/得到 huffman 编码printf(n); printf(n请按字符编码对应表输入密文：n); for(i=0;iN;i+)显示字符编码对应表printf(%c:,hti.c); encode(hti.c); printf(t);scanf(%s”,str);输入编码串decode(str);番羽译成明文printf(n); 四、测试1、字符权值数据存放在in.txt文件中：j 217z 309q 343x 505k 1183w 1328v 1531f 1899.2058y 2815b 2918g 3061,3069h 3724d 4186m 4241p 4283u 49105005c 6028s 6859l 6882n 7948o 8259t 8929r 93