哈夫曼编码编译器

1、 一、 课题：哈夫曼编码编译器设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。二、 功能（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。三、程序结构程序流程图执行程序选择（0）退出选择（1）编码选择（2）译码输入要编码文件输入要译码文件名编码译码保存编码后的文件保存译码后的文件文字说明Main函数：C

2、oding()编码函数TransCode()译码函数Coding()编码函数：clearscreen()清屏函数Open()打开源码文件SearchStr()查找字符串中不同的字符及其出现的次数CreatHFMTree()用每个字符出现的次数作为叶子节点的权值建立哈夫曼树HFMCode()利用哈夫曼树对每个叶子节点进行编码，存入编码表中TotalCoding()利用编码表对字符串进行最终编码Save()保存最终的哈夫曼编码TransCode()译码函数：clearscreen()清屏函数Open()打开编码文件DeCoding(); /将编码进行解码存入字符串数组中Save(); /保存译码后

3、的字符串四、 算法说明1. 执行界面可供三个选择（1） 编码（2） 译码（3） 退出执行（1）选择需要输入要编译的文件名需要输出编码保存文件名选择（1）执行完毕执行（2）选项输入要译码的编码文件名并输入保存的文件名选择(2)执行完毕执行（0）则退出该程序五、报告总结该程序主要采用了哈夫曼编码译码方法，对txt文件进行编译压缩，同时也能对编码后的文件进行解码，程序结构清晰，主干分两大部分：编码部分与解码部分，各部分通过调用函数合理清晰的实现其功能。程序中运用了一些文件的C语言基本操作，例如打开文件open（）、保存文件save（）函数，但程序上对文件类型的处理还有一些缺点，不能实现文件类型的自动

4、保存，需要输入文件名字和类型。通过这次课程设计，不仅提高了自己的编程能力，还让我知道自己在编程方面的缺点，我以后会更加努力扩大自己的知识面提高自己的编程能力。#include <stdio.h>#include <stdlib.h>#include <string.h>#define M 10000 /定义字符串最大长度#define N 128 /定义叶子节点个数typedef struct node /定义哈夫曼树节点结构体int weight;struct node *LChild,*RChild,*Parent; /分别指向该节点的左孩子，右孩子，和

5、双亲节点struct node *next; /指向建立的哈夫曼树的下一个节点HFMNode,*HFMTree;typedef struct /定义哈夫曼编码的结构体char ch; /存储对应的字符char codeN+1; /存储对应字符的编码int start; /存储编码的起始位置CodeNode;int n; /存储真正叶子节点个数void clearscreen()system("cls");void Open(char s) /打开存放字符或编码的文件，将其存入字符串数组中char name10;FILE *fp;int i=0;printf("请输

6、入要打开的文件名：");gets(name); /要打开的文件名if(fp=fopen(name,"rt")=NULL) printf("打开失败！n"); /若打开失败，则直接退出exit(1); si+=fgetc(fp);while(si-1!=EOF) si+=fgetc(fp);si='0' /存取字符串结束fclose(fp);void Save(char s) /保存字符或编码到文件中char name10;FILE *fp;printf("请输入要保存的文件名：");gets(name);if

7、(fp=fopen(name,"wt")=NULL) printf("存储失败！");exit(1); fputs(s,fp);printf("n保存成功，文件名为:%s。n",name);printf("n按回车键继续.");getchar();fclose(fp);void SearchStr(char s,char str,int count) /查找字符串中字符的个数和每个字符出现的次数int i,j,k=0;for(i=0;i<N;i+) /初始化每个字符出现的次数counti=0;for(i=0;

8、si;i+) for(j=0;j<k;j+) /在str中查找是否有该字符if(strj=si) countj+; break; if(j=k) /在str中无该字符，将其存入最后一个单元strk=si; countk+; strk='0' /将字符串结尾置0n=k; /将实际的字符个数作为叶子节点个数存入nvoid SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2)/查找哈夫曼链表中两个权值最小的节点int i,min;HFMTree p;min=32767;for(i=0,p=HT;i<k;i+,p=p-&

9、gt;next) if(p->weight<min&&p->Parent=0) min=p->weight; *HT1=p; min=32767;for(i=0,p=HT;i<k;i+,p=p->next) if(p->weight<min&&p->Parent=0&&p!=*HT1) /令第二个最小的节点不等于第一个节点min=p->weight; *HT2=p; void CreatHFMTree(HFMTree *HT,int count)/创建哈夫曼树int i;HFMTree

10、p,HT1,HT2; /HT1，HT2分别存放权值最小和次小的节点的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p->next=p->LChild=p->RChild=p->Parent=NULL; /初始化哈夫曼链表且有2n-1个节点for(i=1;i<2*n-1;i+) p->next=(HFMTree)malloc(sizeof(HFMNode); p=p->next; p->next=p->LChild=p->RChild=p->Parent=NULL; for(i=0,p=*HT;i

11、<n;i+) /将各个字符出现的次数作为权值 /存入哈夫曼链表的前n个单元中p->weight=counti; p=p->next; for(i=n;i<2*n-1;i+) /将后n-1个节点赋权值，建树SelectMin(*HT,i,&HT1,&HT2); /每次从前i个节点中选取权值最小的两个节点HT1->Parent=HT2->Parent=p; p->LChild=HT1; p->RChild=HT2; p->weight=HT1->weight+HT2->weight; /将两个节点的权值相加存入最后一

12、个节点中p=p->next; /p指向下一个没有存储权值的节点void HFMCode(HFMTree HT,CodeNode HC,char str)/从每个叶子节点开始，利用哈夫曼树对每个字符进行编码，最终建立一个哈夫曼表int i;HFMTree q,p=HT;for(i=0;i<n;i+) /将字符存入哈夫曼编码结构体数组的字符单元中HCi.ch=stri; HCi.coden-1='0' /初始化编码的最后一位for(i=0;i<n;i+) HCi.start=n-1; for(q=p;q->Parent;q=q->Parent) /判断

13、q所指向的节点，左孩子置0，右孩子置1 if(q=q->Parent->LChild) HCi.code-HCi.start='0' else HCi.code-HCi.start='1' p=p->next; /判断下一个叶子节点void TotalCoding(char s,CodeNode HC,char code)/利用哈夫曼编码表对整个字符串进行编码int i,j;code0='0' /编码数组初始化for(i=0;si;i+) /将每个字符在哈夫曼编码表中对应的编码存入存放总编码的数组中for(j=0;j<n;

14、j+) if(si=HCj.ch) strcpy(code+strlen(code),HCj.code+HCj.start);void DeCoding(char code,HFMTree HT,char str,char s)/对哈夫曼编码进行解码，放入字符串s中int i,j,k=0;HFMTree root,p,q;for(root=HT;root->Parent;root=root->Parent); /用root指向哈夫曼树的根结点for(i=0,p=root;codei;i+) /从根结点开始按编码顺序访问树 if(codei='0') p=p->

15、LChild; else p=p->RChild; if(p->LChild=NULL&&p->RChild=NULL) /到根节点时将该节点对应的字符输出for(j=0,q=HT;q!=p;q=q->next,j+); sk+=strj; p=root; /回溯到根结点 sk='0' /解码完毕，在字符串最后一个单元存入'0'void Coding(char s,char str,char code,int count,HFMTree *HT,CodeNode HC)clearscreen();printf("

16、n打开存放字符串的文件.nn");Open(s); /打开源码文件SearchStr(s,str,count); /查找字符串中不同的字符及其出现的次数CreatHFMTree(HT,count); /用每个字符出现的次数作为叶子节点的权值建立哈夫曼树HFMCode(*HT,HC,str); /利用哈夫曼树对每个叶子节点进行编码，存入编码表中TotalCoding(s,HC,code); /利用编码表对字符串进行最终编码printf("n读入的字符串为:n");puts(s);printf("n最终的哈夫曼编码是:n");puts(code);

17、printf("n保存编码,");Save(code); /保存最终的哈夫曼编码void TransCode(char code,char str,char ss,HFMTree *HT,CodeNode HC)clearscreen();printf("n打开编码的文件.nn");Open(code); /打开编码文件DeCoding(code,*HT,str,ss); /将编码进行解码存入字符串数组ss中printf("n得到的最终字符串为:n");puts(ss);printf("n保存译码，");Save(

18、ss); /保存译码后的字符串int main()/主函数char sM,ssM; /定义字符串数组，s存放将要编码的字符串，ss存解码后的字符串char strN; /存放输入的字符串中n个不同的字符int countN; /存放n个不同字符对应的在原字符串中出现的次数char codeM; /存放最终编码完成后的编码char choice;HFMTree HT; /定义一个哈夫曼树的链表CodeNode HCN; /定义一个哈夫曼编码表的数组，存放每个字符对应的哈夫曼编码do clearscreen(); printf("nn"); printf(" *哈夫曼树*n"); printf(" * *n"); printf(" * 1.编码。 *n"); printf(" * 2.译码。 *n"); printf(" * 0.退出。 *n"); printf(" * *n"); printf(" * *n"); printf(" * *n"); printf(" * 请输入相应操作的序号(0-2) *n"); printf(" *n"