赫夫曼编译码器 课程设计报告

1、数据结构课程设计报 告 书题目名称 赫夫曼编/译码器 学 院 专 业 专业班级 学 号 学生姓名 指导教师 目 录一 需求分析1二 概要设计1 1 抽象数据类型 2 算法设计的思想 3 程序总体及主要算法的流程图三 源代码4四 测试结果12五 运行结果分析14 六 收获、体会及意见14 一、 需求分析1. 演示过程中，输入字符为26个大写的英文字母与空格，输入个数n<=27,输入形式以一个“#”为结束符，且不可输入非法字符和重复自符，若出现，程序将自动删除。2. 程序执行的命令包括：1） 根据给出的数值构造哈夫曼树。2） 根据哈夫曼树给字符编码。3） 根据所得出的编码进行译码。3.利用哈

2、夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在此程序的运行过程中，充分体现出赫夫曼编译码器可利用价值。二、 概要设计为了实现上述程序功能，需要一个抽象数据类型，如：1.抽象数据类型赫夫曼树的定义如下：ADT HuffmanTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R:若D=F，则R=F，称HuffmanTree为空二叉树；若¹F,则=，是如下二元关系：（1）在中存在唯一的称为根的数据元素root，它在关系H下无前驱;（2）若D-root¹F，则存在D-root=D1,Dr,且D1ÇDr=F;（3） 若D1¹

3、F，则D1中存在唯一的元素x1，<root,x1>ÎH,且存在D1上的关系H1ÌH；若Dr¹F，则Dr中存在唯一的元素xr，<root,xr>ÎH,且存在Dr上的关系HrÌH;H=<root,x1>,<root,xr>,H1,Hr （4） (D1,H1)是一棵符合本定义的二叉树，称为根的左子树，(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。2、算法的设计思想此程序的设计思想为：输入程序所需数据，构建相应的赫夫曼树，利用已有数据进行赫夫曼编码，并进行译码过程，最后对运行结果分析处理。大致思

4、路如下：1）.初始化。根据下表给出的英文字母的使用频度，建立赫夫曼树。调用函数选择出权值最小的两个结点，依照程序构建赫夫曼树。空格：0.2 E：0.105 T：0.071 O：0.0644A：0.063 N：0.059 I：0.054 R：0.053S：0.052 H：0.047 D：0.035 L：0.029C：0.023 U：0.0225 F：0.0221 M：0.021P：0.0175 Y、W：0.012 G：0.011 B：0.0105V：0.008 K：0.003 X：0.002 J、Q：0.001Z：0.0012）. 编码。利用已建好的赫夫曼树，对电报正文进行编码。3）. 译码。对

5、编码好的内容进行译码。4）. 打印编码。3、程序总体及主要算法的流程图 1）.程序总体 输入程序所需数据，运用select函数构建相应的赫夫曼树，利用已有字符进行逆根法求赫夫曼编码，并运用transcode函数进行译码过程，再运用input函数进行字符的输入，最后对运行结果分析处理 2）.主要算法的流程图三、源代码#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>typedef struct int weight; char ch; int parent,

6、lchild,rchild;/定义赫夫曼树HTNode,*HuffmanTree;/动态分布数组存储赫夫曼树typedef structchar ch;char *chs;/定义赫夫曼型的字符和指针HuffmanCode;/ 存储赫夫曼编码typedef struct/char ch;/int weight;/声明字符及权值sw;/ 存储权值和字符typedef struct/HuffmanTree HT;/HuffmanCode *HC;/声明一个赫夫曼树编码huf;/ 存储赫夫曼树HT及其编码HCvoid select(HTNode * HT,int n,int *n1,int *n2)/

7、 int i=1; int n3;/ while(HTi.parent!=0)/ i+;/ *n1=i;/ i+;/ while(HTi.parent!=0) i+;/ *n2=i;/ if(HT*n1.weight<HT*n2.weight)/ n3=*n1;*n1=*n2;*n2=n3;/ for(i+;i<=n;i+)/ if(HTi.parent=0)/ if(HTi.weight<HT*n1.weight)/ *n1=i;/ else if(HTi.weight<HT*n2.weight)/ *n2=i;/ /运用select函数找出最小的两个权值以便构造赫夫

8、曼树huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)/w存放n个字符的权值（均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。int m,i,s1,s2,start,c,f;/HuffmanTree p;/char *cd;/if(n<=1) return 0;/m=2*n-1;/HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0单元未用for(p=HT+1,i=1;i<=n;i+,p+,w+)/p->weight=w->

9、;weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;/for(;i<=m;i+,p+)/p->weight=0;p->ch=''p->parent=0;p->lchild=0;p->rchild=0;/for(i=n+1;i<=m;i+)/建赫夫曼树 select(HT,i-1,&s1,&s2);/ HTs1.parent=i;HTs2.parent=i;/ HTi.lchild=s1;HTi.rchild=s2;/ HTi.wei

10、ght=HTs1.weight+HTs2.weight;/建树过程调用select函数以建树HC=(HuffmanCode *)malloc(n+1)*sizeof(char);/分配n个字符编码的头指针向量cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1='0'/编码结束符for(i=1;i<=n;i+)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start

11、='0'/ else cd-start='1'/ HCi.ch=HTi.ch;/ HCi.chs=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(HCi.chs,&cdstart);/从cd编制编码（串）到HC printf("%c %-10sn",HCi.ch,HCi.chs);/HUF->HT=HT;/HUF->HC=HC;/return HUF;/char * convert(char *chars,char *chars1,HuffmanCode *

12、hc,int n)/ 编写转换函数 char *p=chars; int i; / strcpy(chars1,"");/ 将输入的字符串复制到chars1中 while(*p)/ i=1; while(hci.ch!=*p&&i<=n) i+;/ strcat(chars1,hci.chs); p+;/将字符串连接起来 printf("the chars translate are:%sn",chars1);/return chars1;/运用convent函数对已写好的字符列进行编码void transcode(HuffmanT

13、ree ht,char *chars2,char*chars3)/ 编写译码过程 int i=1,p; char *q=chars2;char *r=chars3;/ while(hti.parent!=0) i+;/ p=i; / while(*q)/ while(htp.lchild!=0 && *q)/ 当遍历时遇到0则向左走，遇到1则向右走 if(*q='0')/ p=htp.lchild;/ else p=htp.rchild;/ q+;/ if(htp.lchild=0)/*r=htp.ch;r+;/ p=i;/ *r='0'/ pr

14、intf("the chars are:");/ puts(chars3);/ /运用transcode函数进行译码void input(int *n,sw *w)/ int i;/printf("input the mount of char:");/scanf("%d",n);/ for(i=1;i<=*n;i+,w+)/printf("input the %dth char and weight:",i);/ 输入字符和权值fflush(stdin);/scanf("%c%d",&a

15、mp;w->ch,&w->weight);/运用input函数进行字符的输入void main(void)/HTNode HT;/HuffmanCode HC,*hc;/声明一个指针HuffmanTree ht;/huf *HUF,huf2;/int n;/sw w40;/声明一个数组char ch,inchar500,outchar1000;/ 定义输入和输出的最大字符数char *abc;/char *p=inchar;/input(&n,w);/调用input函数HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);

16、/printf("input chars to translate,ends of '#':");/ 输入待翻译的字符fflush(stdin);/清除流,解决输入干扰ch=getchar();/while(ch!='#')/ 字符结束符*p=ch;/p+;/ch=getchar();/*p='0'/hc=HUF->HC;/ht=HUF->HT;/译码abc=convert(inchar,outchar,hc,n);/用convert函数进行字符转换transcode(ht,abc,outchar);/调用transcode函数翻译编码四、测试结果五、运行结果分析1在源代码的编写结束之后，进行调试，等到调试的结果完全正确时，根据要求进行程序运行，输入数据，最终记录得出的结果。2由于对学习的知识理解、掌握不足，在早期的编码过程中存在一些困难，但经过查找相关资料及自己的相关学习，问题已经得到解决。今后应该重点理解二叉树的基本操作和实际