哈夫曼编码和译码的算法设计与实现.pdf
实验名称哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期实 验 室信息系统设计与仿真室I 实验操作实验台号班级姓名实验结果一、实验目的1、掌握哈夫曼编码的二叉树结构表示方法;2、编程实现哈夫曼编码译码器;3、掌握贪心算法的设计策略。二、实验任务 从文件中读取数据,构建哈夫曼树;利用哈夫曼树,对输入明文进行哈夫曼编码;利用哈夫曼树,对输入编码译码为明文。三、实验设计方案1、结构体设计Huffman 树:包括字符,权,父亲下标,左孩子下标,右孩子下标#define N 29/26 个小写字母,逗号,句号和空格字符.struct treenode/静态链表char c;/char int w;/weight int f;/father int l;/left child index int 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 编码译为明文 读取文件字符、权值数据void input()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 huffman()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+;文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5htn.w=s;/修改权值 根据字符下标找到字符的huffman 编码/根据字符所在的下标,从叶子结点往上搜索到根节点,然后逆置得到该字符的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;/左孩子记为0 else strl+=1;/右孩子记为1 for(j=0;j=(l-1)/2;j+)/将编码逆置char t;t=strj;strj=strl-1-j;strl-1-j=t;strl=0;/str 存放 huffman 编码,字符串结束标记 读入明文生成huffman 编码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)文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5i=hti.l;else i=hti.r;str+;printf(%c,hti.c);3、主函数设计思路:主函数实现实验任务的基本流程。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 217 z 309 q 343 x 505 k 1183 w 1328 v 1531 f 1899 文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5.2058 y 2815 b 2918 g 3061,3069 h 3724 d 4186 m 4241 p 4283 u 4910 5005 c 6028 s 6859 l 6882 n 7948 o 8259 t 8929 r 9337 i 9364 a 10050 e 11991 2、测试输入明文:you 输出编码:111011011110101 输入编码:010001111111001000 输入解码:love 五、总结与讨论1、问题与错误2、经验与收获3、改进与设想六、源代码文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5文档编码:CF10W3U3I4Z9 HW6W5C7W8Z8 ZU5D5P9W6T5