数据结构课程设计哈夫曼树的应用

题目哈夫曼树的应用学院计算机科学与技术学院专业软件工程专业班级姓名指导教师2013 年元月25 日哈夫曼树的应用摘要应用哈夫曼树的相关知识，解决前缀编码的编码和译码问题，从需求分析到程序的运行，完成一整套编码系统。

关键字哈夫曼树编码译码编码系统Abstract According to the knowledge of Huffman tree , solving the problem of prefix code . Starting from the software requirement analysis to the debugging process and completing the system .Key words Huffman tree , Code , Decoding , The coding system1.引言自1946年第一台计算机诞生以来，计算机产业迅速发展，计算机的类型也由早期的科学计算超大型计算机演变成形式多样、功能各异的新型计算机，并渗透到人类社会的各个领域。

如今，计算机的应用以不再局限于科学计算，而更多的用于控制管理及数据处理等非数值计算的处理工作。

与此相应，计算机加工处理的对象由纯粹的数值发展到字符，表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。

由于描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构，则产生了研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科----数据结构。

[1]在我们用计算机解决实际问题时，往往先从具体问题中抽象出一个数学模型，然后找到解此模型的算法，再根据这个过程编写程序，调试，最终得到解答。

[2]算法是对特定问题求解步骤的一种描述，它是指令的有限序列其中每一条指令表示一个或多个操作。

求解一个问题可能有多种算法，但我们往往要找出其中可行性较强，效率更高的优质算法。

例如，在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。

由于在实际应用中，各个字符的出现频度或使用次数是不相同的，则设计编码时，让使用频率高的用短码，使用频率低的用长码，可以优化编码。

在译码时，为解决码长不同的问题，使用前缀编码（任一个字符的编码都不是另一个字符的编码的前缀），为使频率与码长匹配以达最优，可以利用哈夫曼树（最优二叉树）来设计二进制的前缀编码。

[3]2.需求分析2.1程序的任务与功能在利用哈夫曼编码进行通信时，要求在发送端和接收端各有相应的哈夫曼编码、译码系统，有时需要一端同时具有两种功能，则需兼备哈夫曼编码与译码的程序。

该程序具备以下功能：输入一组数据建立哈夫曼树，设计哈夫曼码，译码。

2.2程序的输入和输出从终端输入有字符串大小n，n个字符以及其对应的权值（频率），以此建立哈夫曼树。

并将其存入文件hfmtree中。

利用程序将得到的哈夫曼树进行编码，得到哈夫曼码，存入文件Codefile中，利用建好的哈夫曼树对文件中代码进行翻译，将结果存入文件Textfile 中。

2.3测试数据用模拟电文传输来对程序进行测试。

以下为测试用数据（频度为模拟）：测试用报文：“I LOVE YOU”给定字符集：字符 A B C D E F G H I J K L M N频度64 13 22 32 103 21 15 47 57 1 5 32 20 57字符O P Q R S T U V W X Y Z频度63 15 1 48 51 80 23 8 18 1 16 13.数据结构设计typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表typedef struct{unsigned int weight;//weight为权值unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedef struct{HuffmanTree HT;char *c;int length;HuffmanCode HC;}Huffman;//分配数组存储字符串及其对应的哈夫曼树Huffman Hfm;char k; //控制循环的标志4.算法设计4.1主程序main(){//主程序为选择功能InitHuffman(Huffman Hfm)；Encoding(Huffman Hfm)；Decoding(Huffman Hfm)；4.2功能模块4.2.1求哈夫曼编码Huffman HuffmanCoding(Huffman Hfm) /*w存放n个字符的权值（均〉0），构造哈夫曼树HT，并求出n个字符的构造哈夫曼编码HC*/{FOR(i=n+1;i<=2*n-1;++i) /*选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2*/{Select(Hfm.HT,i-1,&s1,&s2);修改父亲位置；修改孩子位置；父亲结点权值为左右孩子权值之和；}//从叶子结点到根逆向求每个字符的哈夫曼编码FOR(i=1;i<=n;++i)//逐个字符求哈夫曼编码{ start=n-1;//编码结束符位置for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//从叶子到根逆向求编码{IF(c==Hfm.HT[f].lchild) cd[--start]='0';ELSE cd[--start]='1';}再从cd复制编码到Hfm.HC}RETURN Hfm;}4.2.2初始化Huffman InitHuffman(Huffman Hfm)//初始化哈夫曼数，要求输入字符和相应权值{对文件hfmTree以读文本的形式打开IF(fp==NULL)调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼数中ELSEPRINTF("The Huffmantree has already existed!\nPlease choose again!\n\n"); 读入hfmTree中文本FOR(i=1;i<=n;i++)作为独立结点对结点的parent，lchild，rchild分别赋值0FOR(;i<=2*n-1;++i)作为独立结点对结点的weight，parent，lchild，rchild分别赋值0Hfm=HuffmanCoding(Hfm);RETURN Hfm;4.2.3求相应编码void Encoding(Huffman Hfm)//利用已建好的哈夫曼树（若不在内存，则从文件hfmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

{输出"\n\n*******************Encoding**************************\n\n"IF((ffp=fopen("ToBeTran","rt"))==NULL)提示输入"Please input the sentence: "scanf("%s",ch);printf("\n");以写文本的形式打开CodeFileELSE读入ToBeTran文件中的字符;WHILE(ch[j])FOR(i=1;i<=n;i++)IF(ch[j]==Hfm.c[i])分别在终端和文件CodeFile输入Hfm.HC[i]4.2.4译码void Decoding(Huffman Hfm)/*利用已建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

*/{ 定义char d[500]PRINTF("\n\n******************Decoding************************\n\n");IF((fp=fopen("CodeFile","rt"))==NULL)PRINTF(“Please input the code:”);ELSE将文件Codefile中的内容读到d数组中PRINTF(“The file is :”);以写文本的方式打开TextFileWHILE(d[j])根到叶子结点遍历，并按照lchild——>0，rchild——>1来输出入到文件TextFile中关闭文件}5.程序实现及检测5.1源代码#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表typedef struct{unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedef struct{HuffmanTree HT;char *c;int length;HuffmanCode HC;}Huffman;//全局结构体变量，来存储字符与代码void Select(HuffmanTree HT,int end,int *s1,int *s2)//选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2{int i;int min1=MAX_NUM;int min2;for (i=1;i<=end;i++)//遍历查找权值最小的结点S1{if (HT[i].parent==0&&(int)HT[i].weight<min1){*s1=i;min1=HT[i].weight;}}min2=MAX_NUM;for(i=1;i<=end;i++)//遍历查找除S1外权值最小的结点S2{if(HT[i].parent==0&&(*s1!=i)&&min2>(int)HT[i].weight){*s2=i;min2=HT[i].weight;}}}Huffman HuffmanCoding(Huffman Hfm) //存放n个字符的权值（均〉0），构造哈夫曼树HT，并求出n个字符的构造哈夫曼编码HC{int i,n,m,s1,s2,start;int c,f;char *cd;n=Hfm.length;if(n<=1) return Hfm;m=2*n-1;for(i=n+1;i<=m;++i) //选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2 {Select(Hfm.HT,i-1,&s1,&s2);Hfm.HT[s1].parent=i;//修改父亲位置Hfm.HT[s2].parent=i;Hfm.HT[i].lchild=s1;//修改孩子位置Hfm.HT[i].rchild=s2;Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;//父亲结点权值为左右孩子权值之和}//从叶子结点到根逆向求每个字符的哈夫曼编码Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符for(i=1;i<=n;++i)//逐个字符求哈夫曼编码{start=n-1;//编码结束符位置for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)//从叶子到根逆向求编码{if(c==(int)Hfm.HT[f].lchild) cd[--start]='0';else cd[--start]='1';}Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));strcpy(Hfm.HC[i],&cd[start]);//从cd复制编码到Hfm.HC}free(cd);//释放工作空间return Hfm;}Huffman InputHuffman(Huffman Hfm)//输入函数，控制用户输入字符和相应权值{int i,n;printf("\n\n********************输入数据********************\n"); printf("字符库和权值将保存在文件:\\hfmTree\\n");printf("请输入字符个数:");scanf("%d",&n);if(n<=1){printf("只有一个字符无需编码!");//若只有一个数值则无需编码printf("\n");printf("请输入字符个数:");scanf("%d",&n);}Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));Hfm.c=(char *)malloc((n+1)*sizeof(char));for(i=1;i<=n;i++){printf("请输入字符:");scanf("%s",&Hfm.c[i]);printf("请输入字符对应权值:");scanf("%d",&Hfm.HT[i].weight);Hfm.HT[i].parent=0;Hfm.HT[i].lchild=0;Hfm.HT[i].rchild=0;}for(;i<=2*n-1;++i){Hfm.HT[i].weight=0;Hfm.HT[i].parent=0;Hfm.HT[i].lchild=0;Hfm.HT[i].rchild=0;}Hfm.length=n;return Hfm;}Huffman InitHuffman(Huffman Hfm)//初始化哈夫曼数，要求用户输入字符和相应权值{int n,i,x;FILE *fp;fp=fopen("hfmTree","rt");//对文件hfmTree以读文本的形式打开if(fp==NULL){Hfm=InputHuffman(Hfm);//调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼树中fp=fopen("hfmTree","wt");fprintf(fp,"%d\n",Hfm.length);for(i=1;i<=Hfm.length;i++)fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);rewind(fp);}else{printf("哈夫曼树已经存在\n需要重新初始化吗('Y'or'N')\n\n");//询问是否重新初始化scanf("%s",&x);if(x=='Y'){ Hfm=InputHuffman(Hfm);//调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼中fp=fopen("hfmTree","w+");fprintf(fp,"%d\n",Hfm.length);for(i=1;i<=Hfm.length;i++)fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);rewind(fp);else{fscanf(fp,"%d\n",&n);Hfm.c=(char *)malloc((n+1)*sizeof(char));Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));for(i=1;i<=n;i++)fscanf(fp,"%s %d ",&Hfm.c[i],&Hfm.HT[i].weight);//将已经在文件中的字符和其对应的权重输入到Hfm.c[i]和&Hfm.HT[i].weight中for(i=1;i<=n;i++)//对每个节点初始化{Hfm.HT[i].parent=0;Hfm.HT[i].lchild=0;Hfm.HT[i].rchild=0;}for(;i<=2*n-1;++i){Hfm.HT[i].weight=0;Hfm.HT[i].parent=0;Hfm.HT[i].lchild=0;Hfm.HT[i].rchild=0;}Hfm.length=n;}}fclose(fp);Hfm=HuffmanCoding(Hfm);return Hfm;}void Encoding(Huffman Hfm)//利用已建好的Huffman树（如不在内存，则从文件hfmTree 中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。