哈夫曼编码

《数据结构》实验报告

题 目： 赫夫曼编码设计 班 级： 姓 名： 学 号： 完成日期：

1．问题描述

题目:对某篇500单词左右的英文文本文件中字母、标点符号的使用频率进行统计，然后对出现的字母和标点符号进行哈夫曼编码。

要求:英文文本采用文件方式读取，输出结果中要分别列出各字符（包括字母和标点符号）的出现频率和哈夫曼编码。 2．需求分析

（1）输入的形式和输入值的范围； 打开文件为txt格式的文本文档。 （2）输出的形式；

以文本文档格式读取的英文文本。 （3）程序所能达到的功能。

统计文章中出现的字符的频率和哈弗曼编码。 3．概要设计

（1）说明本程序中用到的所有抽象数据类型的定义（含数据对象、数据关系、基本操作）；

typedef struct node //定义赫夫曼树节点结构体 { 点

}HFMNode,*HFMTree;

typedef struct //定义赫夫曼编码的结构体 {

char ch; //存储对应的字符 char code[N+1]; //存储对应字符的编码 int start; //存储编码的起始位置 int weight;

struct node *LChild,*RChild,*Parent; //分别指向该节点的左孩子，右孩子和struct node *next; //指向建立的赫夫曼树的下一个节

双亲节点

}CodeNode;

（2）系统中子程序及功能要求； void clearscreen()

{ }

void Open(char s[]) //打开存放字符或编码的文件，将其存入字符串数组中

{ }

void Save(char s[]) //保存字符或编码到文件中 {

char name[10]; FILE *fp;

printf(\"请输入要保存的文件名(加后缀名)：\"); gets(name);

if((fp=fopen(name,\"wt\"))==NULL) {

printf(\"存储失败！\"); exit(1); char name[10]; FILE *fp; int i=0;

printf(\"请输入要打开的文件名(加后缀名)：\");

gets(name); //要打开的文件名 if((fp=fopen(\"name\{ }

s[i++]=fgetc(fp); while(s[i-1]!=EOF)

s[i++]=fgetc(fp);

s[i]='\\0'; //存取字符串结束 fclose(fp);

printf(\"打开失败！\\n\"); //若打开失败，则直接退出 exit(1); system(\"cls\");

}

} fputs(s,fp);

printf(\"\\n保存成功，文件名为:%s。\\n\printf(\"\\n按回车键继续...\"); getchar(); fclose(fp);

void SearchStr(char s[],char str[],int count[]) { }

//查找字符串中字符的个数和每个字符出现的次数 int i,j,k=0;

for(i=0;istr[k]='\\0'; //将字符串结尾置\\0

n=k; //将实际的字符个数作为叶子节点个

for(j=0;jif(str[j]==s[i]) { }

if(j==k) //在str[]中无该字符，将其存入最{ }

str[k]=s[i]; count[k++]++; count[j]++; break;

count[i]=0; for(i=0;s[i];i++)

后一个单元

数存入n

void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2) { }

void CreatHFMTree(HFMTree *HT,int count[]) { 置

p=*HT=(HFMTree)malloc(sizeof(HFMNode));

p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化赫夫曼链表且有for(i=1;i<2*n-1;i++) {

p->next=(HFMTree)malloc(sizeof(HFMNode)); //创建赫夫曼树 int i;

HFMTree p,HT1,HT2; //HT1，HT2分别存放权值最小和次小的节点的位//查找赫夫曼链表中两个权值最小的节点 int i,min; HFMTree p; min=32767;

for(i=0,p=HT;inext)

if(p->weightParent==0) { }

min=32767;

for(i=0,p=HT;inext)

if(p->weightParent==0&&p!=*HT1) //令第二个最小的{ }

min=p->weight; *HT2=p; min=p->weight; *HT1=p;

节点不等于第一个节点

2n-1个节点

值

}

}

p=p->next;

p->next=p->LChild=p->RChild=p->Parent=NULL;

for(i=0,p=*HT;ifor(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; //将两个节点的权值相加存入p=p->next; //p指向下一个没有存储权p->weight=count[i]; p=p->next;

两个节点

最后一个节点中 值的节点

void HFMCode(HFMTree HT,CodeNode HC[],char str[]) { 单元中

{

HC[i].ch=str[i];

HC[i].code[n-1]='\\0'; //初始化编码的最后一位

//从每个叶子节点开始，利用赫夫曼树对每个字符进行编码，最终建立一int i;

HFMTree q,p=HT;

for(i=0;i个赫夫曼表

}

}

for(i=0;iif((fp=fopen(\"对应编码.txt\{ }

for(i=0;ifprintf(fp,\"%c的编码是\fprintf(fp,\"%s\\n\printf(\"无法打开\\n\"); exit(1); HC[i].start=n-1;

for(q=p;q->Parent;q=q->Parent) //判断q所指向的节点，左孩子置0，

if(q==q->Parent->LChild)

HC[i].code[--HC[i].start]='0'; else HC[i].code[--HC[i].start]='1';

p=p->next; //判断下一个叶子节点

右孩子置1

void TotalCoding(char s[],CodeNode HC[],char code[]) {

//利用赫夫曼编码表对整个字符串进行编码 int i,j;

code[0]='\\0'; //编码数组初始化

for(i=0;s[i];i++) //将每个字符在赫夫曼编码表中对应的

for(j=0;j编码存入存放总编码的数组中

}

if(s[i]==HC[j].ch)

strcpy(code+strlen(code),HC[j].code+HC[j].start);

void DeCoding(char code[],HFMTree HT,char str[],char s[]) { 点

}

void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])

{

clearscreen();

printf(\"\\n打开存放字符串的文件...\\n\\n\"); Open(s); //打开源码文件

SearchStr(s,str,count); //查找字符串中不同的字符及其出现的次数 for(i=0,p=root;code[i];i++) //从根节点开始按编码顺序访问树 { }

s[k]='\\0'; //解码完毕，在字符串最后一个单元存入'\\0'

if(code[i]=='0')

p=p->LChild; else p=p->RChild;

if(p->LChild==NULL&&p->RChild==NULL) //到根节点时将该节点对{ }

for(j=0,q=HT;q!=p;q=q->next,j++); s[k++]=str[j];

p=root; //回溯到根节点

//对赫夫曼编码进行解码，放入字符串s中 int i,j,k=0; HFMTree root,p,q;

for(root=HT;root->Parent;root=root->Parent); //用root指向赫夫曼树的根节

应的字符输出

}

CreatHFMTree(HT,count); //用每个字符出现的次数作为叶子节点的权值建HFMCode(*HT,HC,str); //利用赫夫曼树对每个叶子节点进行编码，TotalCoding(s,HC,code); //利用编码表对字符串进行最终编码 printf(\"\\n读入的字符串为:\\n\"); puts(s);

printf(\"\\n最终的赫夫曼编码是:\\n\"); puts(code);

printf(\"\\n对应编码已输出到: 对应编码.txt\\n\"); printf(\"\\n保存编码,\");

Save(code); //保存最终的赫夫曼编码

立赫夫曼树 存入编码表中

void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[]) { }

（3）主程序及各程序模块（函数）之间的层次（调用）关系。 主程序中利用

case '1': Coding(s,str,code,count,&HT,HC);break; //对字符串进行编码 case '2': TransCode(code,str,ss,&HT,HC);break; //对编码进行解码 进行调用子函数。 4．详细设计

主函数中利用case语句对函数Coding函数TransCode函数进行调用，coding函数中，调用子函数：

Open函数 打开源码文件

clearscreen();

printf(\"\\n打开编码的文件...\\n\\n\");

Open(code); //打开编码文件 DeCoding(code,*HT,str,ss); //将编码进行解码存入字符串数组ss[]中 printf(\"\\n得到的最终字符串为:\\n\"); puts(ss);

printf(\"\\n保存译码，\");

Save(ss); //保存译码后的字符串

SearchStr 查找字符串中不同的字符及其出现的次数

CreatHFMTree 用每个字符出现的次数作为叶子节点的权值建立赫夫曼树 HFMCode 利用赫夫曼树对每个叶子节点进行编码，存入编码表中 TotalCoding 利用编码表对字符串进行最终编码 Save 保存最终的赫夫曼编码 TransCode函数调用子函数：

Open 打开编码文件

DeCoding 将编码进行解码存入字符串数组ss[]中 Save 保存译码后的字符串 主函数和子函数之间调用结束。 5．总结

这次试验是关于赫夫曼编码的实验，在实验中我遇到了很多问题，一开始关于文件相关知识记不太清楚了，文件打开后赫夫曼编码出现一些问题，有时不能正确的打开文件，而且统计的时候可能会出现一些错误，造成结果不够精确，这样说明程序的健壮性不够好。在试验中我巩固了自己在课上学习的赫夫曼编码的相关内容，在这次试验中，我更加的了解了赫夫曼编码在实际情况下的应用，为我更好的学习数据结构相关知识有了一个更好地方向。总之这次试验我收获很大，希望下次试验能做的更好。 6．附录 源程序代码：

#include #include #include

#define M 10000 //定义字符串最大长度 #define N 128 //定义叶子节点个数

typedef struct node //定义赫夫曼树节点结构体 {

int weight;

struct node *LChild,*RChild,*Parent; //分别指向该节点的左孩子，右孩子和

双亲节点

点

struct node *next; //指向建立的赫夫曼树的下一个节

}HFMNode,*HFMTree;

typedef struct //定义赫夫曼编码的结构体 {

int n; //存储真正叶子节点个数 void clearscreen() { }

void Open(char s[]) //打开存放字符或编码的文件，将其存入字符串数组中

{

char name[10]; FILE *fp; int i=0;

printf(\"请输入要打开的文件名(加后缀名)：\");

gets(name); //要打开的文件名 if((fp=fopen(\"name\{ }

s[i++]=fgetc(fp); while(s[i-1]!=EOF)

s[i++]=fgetc(fp);

s[i]='\\0'; //存取字符串结束

printf(\"打开失败！\\n\"); //若打开失败，则直接退出 exit(1); system(\"cls\");

char ch; //存储对应的字符 char code[N+1]; //存储对应字符的编码 int start; //存储编码的起始位置

}CodeNode;

}

fclose(fp);

void Save(char s[]) //保存字符或编码到文件中 { }

void SearchStr(char s[],char str[],int count[]) {

//查找字符串中字符的个数和每个字符出现的次数 int i,j,k=0;

for(i=0;ifor(j=0;jif(str[j]==s[i]) {

count[j]++; break;

count[i]=0; for(i=0;s[i];i++) char name[10]; FILE *fp;

printf(\"请输入要保存的文件名(加后缀名)：\"); gets(name);

if((fp=fopen(name,\"wt\"))==NULL) { } fputs(s,fp);

printf(\"\\n保存成功，文件名为:%s。\\n\printf(\"\\n按回车键继续...\"); getchar(); fclose(fp);

printf(\"存储失败！\"); exit(1);

}

}

}

if(j==k) //在str[]中无该字符，将其存入最{ }

str[k]=s[i]; count[k++]++;

后一个单元

str[k]='\\0'; //将字符串结尾置\\0

n=k; //将实际的字符个数作为叶子节点个

数存入n

void SelectMin(HFMTree HT,int k,HFMTree *HT1,HFMTree *HT2) { }

//查找赫夫曼链表中两个权值最小的节点 int i,min; HFMTree p; min=32767;

for(i=0,p=HT;inext)

if(p->weightParent==0) { }

min=32767;

for(i=0,p=HT;inext)

if(p->weightParent==0&&p!=*HT1) //令第二个最小的{ }

min=p->weight; *HT2=p; min=p->weight; *HT1=p;

节点不等于第一个节点

void CreatHFMTree(HFMTree *HT,int count[]) { 置

值

{ //存入赫夫曼链表的前n个单元中 }

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; //将两个节点的权值相加存入p=p->next; //p指向下一个没有存储权p->weight=count[i]; p=p->next;

p=*HT=(HFMTree)malloc(sizeof(HFMNode));

p->next=p->LChild=p->RChild=p->Parent=NULL; //初始化赫夫曼链表且有for(i=1;i<2*n-1;i++) { }

for(i=0,p=*HT;ip->next=(HFMTree)malloc(sizeof(HFMNode)); p=p->next;

p->next=p->LChild=p->RChild=p->Parent=NULL; //创建赫夫曼树 int i;

HFMTree p,HT1,HT2; //HT1，HT2分别存放权值最小和次小的节点的位

2n-1个节点

两个节点

最后一个节点中 值的节点

}

void HFMCode(HFMTree HT,CodeNode HC[],char str[]) { 单元中

{ }

for(i=0;iif((fp=fopen(\"对应编码.txt\{ }

for(i=0;ifprintf(fp,\"%c的编码是\fprintf(fp,\"%s\\n\printf(\"无法打开\\n\"); exit(1); HC[i].start=n-1;

for(q=p;q->Parent;q=q->Parent) //判断q所指向的节点，左孩子置0，

if(q==q->Parent->LChild)

HC[i].code[--HC[i].start]='0'; else HC[i].code[--HC[i].start]='1';

p=p->next; //判断下一个叶子节点 HC[i].ch=str[i];

HC[i].code[n-1]='\\0'; //初始化编码的最后一位

//从每个叶子节点开始，利用赫夫曼树对每个字符进行编码，最终建立一int i;

HFMTree q,p=HT;

for(i=0;i个赫夫曼表

右孩子置1

}

} fclose(fp);

void TotalCoding(char s[],CodeNode HC[],char code[]) { }

void DeCoding(char code[],HFMTree HT,char str[],char s[]) { 点

for(i=0,p=root;code[i];i++) //从根节点开始按编码顺序访问树 {

if(code[i]=='0')

p=p->LChild; else p=p->RChild;

if(p->LChild==NULL&&p->RChild==NULL) //到根节点时将该节点对{

for(j=0,q=HT;q!=p;q=q->next,j++); s[k++]=str[j];

//对赫夫曼编码进行解码，放入字符串s中 int i,j,k=0; HFMTree root,p,q;

for(root=HT;root->Parent;root=root->Parent); //用root指向赫夫曼树的根节//利用赫夫曼编码表对整个字符串进行编码 int i,j;

code[0]='\\0'; //编码数组初始化

for(i=0;s[i];i++) //将每个字符在赫夫曼编码表中对应的

for(j=0;jif(s[i]==HC[j].ch)

strcpy(code+strlen(code),HC[j].code+HC[j].start);

编码存入存放总编码的数组中

应的字符输出

}

}

}

p=root; //回溯到根节点

s[k]='\\0'; //解码完毕，在字符串最后一个单元存入'\\0'

void Coding(char s[],char str[],char code[],int count[],HFMTree *HT,CodeNode HC[])

{ }

void TransCode(char code[],char str[],char ss[],HFMTree *HT,CodeNode HC[]) {

clearscreen();

printf(\"\\n打开编码的文件...\\n\\n\");

Open(code); //打开编码文件 DeCoding(code,*HT,str,ss); //将编码进行解码存入字符串数组ss[]中 printf(\"\\n得到的最终字符串为:\\n\"); clearscreen();

printf(\"\\n打开存放字符串的文件...\\n\\n\"); 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);

printf(\"\\n对应编码已输出到: 对应编码.txt\\n\"); printf(\"\\n保存编码,\");

Save(code); //保存最终的赫夫曼编码

立赫夫曼树 存入编码表中

}

puts(ss);

printf(\"\\n保存译码，\");

Save(ss); //保存译码后的字符串

void main() { 次数

char code[M]; //存放最终编码完成后的编码 char choice;

HFMTree HT; //定义一个赫夫曼树的链表

CodeNode HC[N]; //定义一个赫夫曼编码表的数组，存放每个字do {

clearscreen();

printf(\"赫夫曼编码译码系统\\n\"); printf(\"1.进行编码\\n\"); printf(\"2.进行译码\\n\"); printf(\"0.退出\\n\"); scanf(\"%c\getchar(); switch(choice) {

case '1': Coding(s,str,code,count,&HT,HC);break; //对字符串进行编码 case '2': TransCode(code,str,ss,&HT,HC);break; //对编码进行解码 case '0': break;

default : printf(\" 输入错误！请重新输入！\\n\"); } //主函数

char s[M],ss[M]; //定义字符串数组，s[]存放将要编码的字符串，char str[N]; //存放输入的字符串中n个不同的字符 int count[N]; //存放n个不同字符对应的在原字符串中出现的

ss[]存解码后的字符串

符对应的赫夫曼编码

}

}while(choice!='0');