赫夫曼树的应用

1、题目：赫夫曼树的应用课程名称：数据结构课程设计指导教师：专 业：班级：学 号：姓名：学 号：姓名：学 号：姓名：学 号：姓名：完成时间：目录一、前 言2二、程序设计目的3三、需求分析3四、概要设计31、主要需要用到的主要数据结构32、算法流程分析4五、源程序和运行结果51.源程序如下52、运行结果11六、调试分析141.测试的结果142.时间复杂度分析143.各模块在设计和调试时存在问题144.算法的改进设想14七、设计心得和总结15八、参考书籍15一、前 言赫夫曼编码(Huffman Coding)是一种编码方式，赫夫曼编码是可变字长编码(VLC)的一种。赫夫曼压缩是个无损的压缩算法，一般用

2、来压缩文本和程序文件。赫夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。赫夫曼编码的应用很广泛，利用赫夫曼树求地的二进制编码称为赫夫曼编码。赫夫曼树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为对应的编码，这就是赫夫曼编码。我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索

3、查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的的第二步是：算法的的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树，每合并一次，森林中就减少一棵树，产生一个新结点。则要进行n-1次合并，所以共产生n-1个新结点。由此可知，最终求得的赫夫曼树中一共有2n-1个结点。其中， n个结点是初始森林中的n个孤立结点。并且赫夫曼树中没有度数为1的分支的结点。采用赫夫曼编码方案，即应用赫夫曼树构造使电文的编码总长最短的编码方案。二、程序设计目的1.熟悉掌握C语言的基础知识和技能；

4、2.学习利用计算机语言实现赫夫曼树构造的算法；3.了解利用赫夫曼树对给定权值的字符的赫夫曼编码的算法思想。三、需求分析1、打开一个文本文件，用一个指针指向它，指针变量为*pf2、对其进行字母频率统计，把字母和字母的频率放到结构体syr s1中3、用Huffman算法建立Huffman树以及每个字母的Huffman码（Huffman数以及Huffman码两张表，均要求输出，最好能在文本中输出）4、把该文本文件的英文文章利用Huffman树编码生成二进制文件(该文件要求输出)5、打开该二进制文本文件，对其解码，仍然利用刚才的Huffman树进行解码6、输入，输出要求都是读取文件。四、概要设计1、主

5、要需要用到的主要数据结构a、赫夫曼树的数据结构typedef struct char data; int weight; int parent; int lchild; int rchild;HuffmanTreeM; b、 赫夫曼编码的数据结构typedef struct char data; char bitsN;HuffmanCodeN;c、字符串存储单元的数据结构typedef struct str char data;char num;/int num;str;2、算法流程分析 a、建立赫夫曼树的数据结构、赫夫曼编码的数据结构和字符串存储单元的数据结构， 字符串存储单元的数据结构是用

6、来存储字母和对应的权值。b、调用int read(str s2)函数，取读文本ywq1.txt并统计这里出现字符的个数（字母区分大小写、空格键和各种标点符号），再统计该字符在文本中出现的频率（也就是所谓的权值）存放在结构体str s2中，返回字母个数k，打印字母的和对应的权值。c、调用CrtHuffmanTree(ht,s2,k)函数来创建赫夫曼数，首先初始化节点并给其赋值0，利用for的循环语句并调用SelectMin函数，查找哈夫曼链表中两个权值最小的来建立赫夫曼树，打印赫夫曼树各节点的权值和它的左右孩子。d、调用CrtHuffmanCode(ht,hc,k)利用建立好的哈夫曼树对文本文本

7、ywq1.txt进行编码，并把编译的赫夫曼编码储存在文本ywq2.txt中，并且打印出来文本的赫夫曼编码。e、通过调用DecodHuffmanCode(ht,k)将文本ywq2.txt字符的赫夫曼码翻译为字符，这就是所谓的反译码，把翻译的英语文章存储在文本ywq3.txt并且存储，并且在对话执行框中打印出来。五、源程序和运行结果1.源程序如下#include<stdio.h>#include<string.h>#include<stdlib.h>#define N 100#define M 2*N-1typedef struct /定义哈夫曼树存储节点结构体

8、类型 char data; int weight; int parent; int lchild; int rchild;HuffmanTreeM; typedef struct /定义哈夫曼编码结构体类型 char data; char bitsN;HuffmanCodeN;typedef struct str /定义字符串存储单元结构体类型 char data;char num;/int num;str;int read(str s2) FILE *fp; char ch; int i,k; str s1128;for(i=0;i<=128;i+) s1i.num = 0; s1i.

9、data = 0; s2i.num = 0; s2i.data = 0; if(fp=fopen("ywq1.txt","r")=NULL) printf("n库文件不存在!"); exit(1); printf("n读取字符串为:n"); ch=fgetc(fp); while(!feof(fp) /统计字符频率 printf("%c",ch); s1ch.num+; s1ch.data = ch; ch=fgetc(fp); fclose(fp); for(i=1,k=1;i<=128

10、;i+) if(s1i.num!=0) s2k.num = s1i.num; s2k.data = s1i.data; k+; printf("nn统计结果为(字符 频率):n"); for(i=1;i<k;i+) printf("<%c %d> ",s2i.data,s2i.num); printf(" (共%d种字符)n",k-1); return k;void SelectMin(HuffmanTree ht, int i,int *p1,int *p2) /查找哈夫曼链表中两个权值最小的节点 int j,mi

11、n1,min2; min1 = min2 = -1; for(j = 1;j<=i;j+) if(htj.parent = 0) if(htj.weight<min1|min1=-1) if(min1!=-1) min2 = min1;*p2=*p1; min1 = htj.weight;*p1=j; else if(htj.weight<min2|min2=-1) min2 = htj.weight; *p2=j; void CrtHuffmanTree(HuffmanTree ht,str s,int n) /创建哈夫曼树 int i,m,p1,p2; for(i=1;i

12、<n;i+) /初始化节点 hti.data = si.data; hti.weight = si.num; hti.parent = 0; hti.lchild = 0; hti.rchild = 0; m=2*n-3; for(i=n;i<=m;i+) hti.data = 0; hti.weight = 0; hti.parent = 0; hti.lchild = 0; hti.rchild = 0; for(i=n;i<=m;i+) SelectMin(ht,i-1,&p1,&p2); /调用SelectMin函数 hti.weight=htp1.w

13、eight+htp2.weight; htp1.parent=i;htp2.parent=i; hti.lchild=p1;hti.rchild=p2; void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k) /利用建立好的哈夫曼树对字符串进行编码 int c,p,i; char cdN+1; int start; for(i=1;i<k;i+) hci.data = hti.data; start = k-1; cdstart = '0' c=i; while(p=htc.parent)!=NULL) cd-st

14、art = (htp.lchild=c)?'0':'1' /左分支为0，右分支为1 c=p; strcpy(hci.bits,&cdstart); printf("nn每个字符对应的编码为:n"); for(i=1;i<k;i+) printf("<%d %c %s> n",i,hci.data,hci.bits);void WriteToFile(HuffmanCode hc,int n) /将编码结果存储在文件文件ywq2.txt中 FILE *fp1,*fp2; char ch; int i

15、; if(fp1=fopen("ywq1.txt","r")=NULL) printf("n文件不存在!"); exit(1); if(fp2=fopen("ywq2.txt","w")=NULL) printf("n文件不存在!"); exit(1); ch = fgetc(fp1);printf("n编码结果为："); while(ch != EOF) for(i=1;i<n;i+) if(ch = hci.data) fputs(hci.bit

16、s,fp2); printf("%s",hci.bits); ch = fgetc(fp1); fclose(fp1); fclose(fp2);printf("n");void DecodHuffmanCode(HuffmanTree ht,int n) /码结果进行译码，并将结果存储在文件ywq3中 FILE *fp1,*fp2; char ch; int p,k; if(fp1=fopen("ywq2.txt","r")=NULL) printf("n文件不存在!"); exit(1);

17、if(fp2=fopen("ywq3.txt","w")=NULL) printf("n文件未能创建!"); exit(1); p=k=2*n-3; ch=fgetc(fp1); printf("译码为: ");while(ch!=EOF) if(ch='0')p=htp.lchild; else if(ch='1') p=htp.rchild; if(htp.data!=0) printf("%c",htp.data); fputc(htp.data,fp2);

18、 p=k; ch = fgetc(fp1); printf("n");fclose(fp1); fclose(fp2);void compare(int k)FILE *fp1,*fp2; char s1N,s2N;int i=1,j=1;printf("nn编译前后结果的比较:");if(fp1=fopen("ywq1.txt","rt")=NULL) printf("n打开文件失败！n"); exit(1);printf("nn原文件ywq1中的字符为: "); for(

19、i=1;(s1i=fgetc(fp1)!=EOF;i+)printf("%c",s1i);fclose(fp1); if(fp2=fopen("ywq3.txt","rt")=NULL) printf("n打开文件失败！n"); exit(1); printf("n文 件ywq3中的字符为: "); for(i=1;(s2i=fgetc(fp2)!=EOF;i+)printf("%c",s2i);fclose(fp2); while(j<k)if(s1j=s2j) j+

20、;else printf("n编码失败！n"); break; if(j=k) printf("n前后数据一致，编码成功！n");void main() int i,k;int j=1;HuffmanTree ht; HuffmanCode hc; str s2128; printf("n-哈夫曼编码译码器-");k=read(s2);getchar();CrtHuffmanTree(ht,s2,k); CrtHuffmanCode(ht,hc,k); WriteToFile(hc,k);getchar();printf("nn"); printf("建立的哈夫曼树为:"); printf(&quo