西工大数据结构报告 哈夫曼树编码译码

1、数据结构实验报告一实验题目编写一个程序，实现哈夫曼树的编码和译码。二程序设计 (一) 需求分析1需要编写这样一个程序，有以下功能：（1）能够输出不同英文字母所代表的权值；（2）能够根据输入结点的字母的权值，生成哈夫曼树，并得到每个结点的哈夫曼编码；（3）能够在功能2的基础上，将输入的哈夫曼编码翻译为字母。2.程序运行步骤：（1）开始；（2）选择要实现的运算：1.输出字母与权值的对应关系表 2.将字符编译为哈夫曼树 3.将哈夫曼树译码；（3）选择运算后，程序输出运算结果；（4）结束。（二）概要设计程序模块及思想：1.主函数主函数包括定义变量和算法两部分。算法由switch-case结构构成。Ca

2、se有三种情况：（1） 输出权值表；（2） 哈夫曼树的编码：（1） 输入要编码的字母；（2） 以表格形式输出哈夫曼树；（3） 输出每个字符的哈夫曼编码；（4） 结束；（3） 哈弗曼树的译码：（1） 建立哈夫曼树：（1）输入要编码的字母；（2）以表格形式输出哈夫曼树；（3）输出每个字符的哈夫曼编码；（4）结束； （2） 将哈夫曼编码翻译为字母： （1）输入哈弗曼编码； （2）输出翻译结果； （3）结束；（3）结束。2基本操作。typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作结果：动态分配数组储

3、存哈夫曼树。typedef char *HuffmanCode;操作结果：动态分配数组储存哈夫曼编码表。void Error(char *message);操作结果：输出错误的原因。void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); 操作结果：对字母进行哈夫曼树的编码。void Select(HuffmanTree &HT, int n,int *s1,int *s2);操作结果：选择多个节点中权值最小的两个结点 void Decoding(HuffmanTree HT,char Ch,

4、char letter,int n);操作结果：将存在在已知哈夫曼树中的哈夫曼编码翻译为字母。（三）详细设计1结构体定义typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作结果：动态分配数组储存哈夫曼树。typedef char *HuffmanCode;操作结果：动态分配数组储存哈夫曼编码表。2.每个模块的分析：（1） 主程序模块：int main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; cha

5、r letter100,code500; /初始化 char 、str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V'

6、,'W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','

7、u','v','w','x','y','z' int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /权值表 printf("请选择要进行的操作：1.显示权值表 2.将字符编码 3.翻译哈夫曼码 n"); scanf("%d",&a); switch(a) case 1: for(i=1;i<=26;i+) /输出权值表 printf(&q

8、uot;%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("请输入要编码的电文：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /创建n+1个单元储存字母的权值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j

9、=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w储存每个字母的权值if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w储存每个字母的权值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼树，并输出 printf("HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;

10、i<=n;i+) /依次输出编号，字母，权值，和哈夫曼编码 printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); / printf("n"); break; case 3: printf("先输入一个拉丁字符串：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /

11、创建n+1个单元储存字母的权值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w储存每个字母的权值 if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w储存每个字母的权值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼树，并输出 printf(

12、"HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); /依次输出编号，字母，权值，和哈夫曼编码; printf("请输入要翻译的哈夫曼编码：n"); gets(code); /根据先前的哈夫曼编码表，输入哈夫曼编码 Decodi

13、ng(HT,code,letter,n); /哈夫曼编码译为字母 printf("n"); break; return 0; （2）基本操作函数：（1）输出错误的原因void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); /输出出现错误的原因（2）建哈夫曼树函数void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /w存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的哈

14、夫曼编码HC int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("输入数据太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; p->

15、parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) /建立哈夫曼树 /在哈夫曼树中选择parent为零且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); printf("Numberttw

16、eightttparentttlchildttrchildn"); /输出序号，权值，父节点，左孩子和右孩子 for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); /从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc(n+1) * sizeof(char *); /分配n个字符编码的头指针 cd=(char *)malloc(n* sizeof(char *); /分配求编码的工作空间 cdn-

17、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='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); /为第i个字符编码分配空间 strcpy(HCi,&cdstart); /从Cd复制字符串到HC free(cd);

18、/释放空间 （3）选择权值最小的两个结点void Select(HuffmanTree &HT,int num,int *s1,int *s2) /变量：哈夫曼树，节点数，两个指针int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=i; break; /S1指向头结点for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /s1指向权值最小的结点 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi

19、.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i; /s2指向次小结点 （4）译码函数。void Decoding(HuffmanTree HT,char Ch,char letter,int n) /已知哈夫曼树，一个用以储存编码的字符数组，一个用以储存译码的字符数组，和输入字符串的长度 int leave; char *p; p=Ch;printf("译码结果如下：n");

20、while(*p!='0') leave=2*n-1; /剩余空间为2*n-1 while(HTleave.lchild!=0) /左孩子存在时 if(*p='0') leave=HTleave.lchild; /如果哈夫曼编码为0，是左孩子 else leave=HTleave.rchild; /否则是右孩子 p+; /指向下一节点 printf("%c",letterleave-1); /输出译码结果 printf("n");四程序使用说明及测试结果程序使用和测试的截图如下：1.显示权值表2.将字符编为哈夫曼码3.将哈

21、夫曼树译码。五）、实验总结(实验心得)1.你在编程过程中花时多少？ 答：从设计到编写，从调试到完成，直至最终完成实验报告一共用了约八个小时。2.多少时间在纸上设计？答：两个小时。3.多少时间上机输入和调试？答：四个多小时。4.多少时间在思考问题？答：设计前就思考，直至完成报告，十多个小时。5.遇到了哪些难题？又是怎么克服的？答：1.知识掌握不熟练。克服方法：认真阅读教科书及有关资料中的相关知识。 2.算法编不出来或错误百出。解决方法：借鉴课本和有关资料中的算法，自己努力思考编写，向同学学习。算法出现错误，慢慢调试，发现错误并不断改进，直到完成程序编写。6.你的收获有哪些？答：首先，我对哈夫曼书

22、树的知识有了更多了解，破除了错误的认识。其次，通过这次作业，我掌握了几种与哈夫曼树有关的算法。最后，我还温习了有关C语言的许多知识。 参考文献：【1】严蔚敏 数据结构 清华大学出版社【2】朱明方 吴及数据结构与算法教程人民邮电出版社附：完整程序#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode;

23、void Error(char *message); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); void Select(HuffmanTree &HT, int n,int *s1,int *s2); void Decoding(HuffmanTree HT,char Ch,char letter,int n); void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); v

24、oid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /建哈夫曼树函数 int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("输入数据太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->

25、;lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; 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.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); print

26、f("Numberttweightttparentttlchildttrchildn"); for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1) * sizeof(char *); cd=(char *)malloc(n* sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c

27、=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); void Select(HuffmanTree &HT,int num,int *s1,int *s2) /选择权值最小的两个结点int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=

28、i; break;for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /从首到尾找出权值最小的 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i;void Decoding(HuffmanTree H

29、T,char Ch,char letter,int n) /译码函数 int leave; char *p; p=Ch;printf("译码结果如下：n"); while(*p!='0') leave=2*n-1; while(HTleave.lchild!=0) if(*p='0')leave=HTleave.lchild; else leave=HTleave.rchild; p+; printf("%c",letterleave-1); printf("n");int main() Huffman

30、Tree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; char letter100,code500; char str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q',&

31、#39;R','S','T','U','V','W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p&

32、#39;,'q','r','s','t','u','v','w','x','y','z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; printf("请选择要进行的操作：1.显示权值表 2.将字符编码 3.翻译哈夫曼码 n"); scanf("%d",&a

33、); switch(a) case 1: for(i=1;i<=26;i+) printf("%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("请输入要编码的电文：n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; wh