哈夫曼编码算法的实现
文章目录
哈夫曼编码算法的实现1、需求分析二、概要设计2.1、所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）2.2、各子程序（函数和过程）的功能 三、详细设计3.1、数据类型定义3.1.1.1、 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率3.1.2 、选择HT中双亲域为0的权值最小的两个结点3.1.3、建立哈夫曼树：根据统计结果建立哈夫曼树。3.1.4、算法5.11 根据统计结果对各字符进行编码，并保存在Code.txt中3.1.5、菜单选项 四、测试分析4.1、读入文本文档中的数据，并进行统计。4.2、建立哈夫曼树：根据统计结果建立哈夫曼树。4.3、建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。4.4、 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件 五、源程序清单六、用户使用手册1、需求分析
实现一个哈夫曼编码系统，系统包括以下功能：
(1) 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。
(2) 建立哈夫曼树：根据统计结果建立哈夫曼树。
(3) 建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。
(4) 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。
(1) 字符信息统计：
假设源文件SourceFile.txt中的字符只有大小写英文字母（同一个字母的大小写看作一个字符），则字符统计算法的实现过程可以归纳为：先定义一个含有26个元素的整形数组，用来存储各个字母出现的次数，最后还要排除其中出现次数为0的数组元素。
(2) 建立哈夫曼树：参考教材算法5.10，补充函数Select的实现。
(3) 建立哈夫曼码表：参考教材算法5.11，将编译表HC中的内容写到文件Code.txt中。
(4) 对源文件进行编码：依次读入文件SourceFile.txt中的字符 c，在编码表 HC 中找到此字符，将字符c转换为编码表中存放的编码串，写入编码文件ResultFile.txt中，直到所有的字符处理完毕为止。
选做内容:
完成译码功能：对任意一个给定的由01组成的文件，根据哈夫曼码表翻译成由字符组成的源文件。
提示：
对文件进行译码的过程必须借助于哈夫曼树。具体过程是：依次读入文件的二进制码，从哈夫曼树的根结点（即HT[m]）出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子HT[i]时便译出相应的字符编码HC[i]。然后重新从根出发继续译码，直至文件结束。
二、概要设计
2.1、所用数据结构的定义及其相关说明（相关结构体或类的定义及其含义）
2.2、各子程序（函数和过程）的功能
1）//字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。void Count()2）//选择HT中双亲域为0的权值最小的两个结点void Select(HuffmanTree HT,int i,int &s1,int &s2)3）//选择HT中双亲域为0的权值最小的两个结点void Select(HuffmanTree HT,int i,int &s1,int &s2)4）//建立哈夫曼树：根据统计结果建立哈夫曼树。//算法5.10 根据统计结果建立Huffman树void CreatHuffmanTree(HuffmanTree &HT,int cou[])5）//算法5.11 根据统计结果对各字符进行编码，并保存在Code.txt中void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC)6）//对SourceFile.txt进行编码，并保存在ResultFile.txt中void Code(HuffmanTree &HT,HuffmanCode &HC)7）//菜单选项void memu(void)8）//函数int main(void)
三、详细设计
3.1、数据类型定义
3.1.1.1、 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率
void Count() {FILE *fp;char i;char word;char letter[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};//计算输入的字母的个数if((fp=fopen("character.txt","r"))==NULL){printf("can not open the file character.txt"); exit(0); } while((word=fgetc(fp))!=EOF){if (word>='A'&&word<='Z'){word=word+32;}i=word-96;cou[i]++;}fclose(fp);printf("\t\tletter\t频率为\n");for (int j=1;j<=26;j++){if (cou[j]!=0){printf("\t\t%c\t%d\n",letter[j],cou[j]);}}printf("\n");printf("\t\t字符统计完成！\n");}
3.1.2 、选择HT中双亲域为0的权值最小的两个结点
void Select(HuffmanTree HT,int i,int &s1,int &s2){//选择两个最小值，将他们的位序输出到s1,s2int m=0,k=0;for(k=1;k<=n;++k) //得到第一个父节点为零的节点{if(0==HT[k].parent){m=HT[k].weight;s1=k;break;}}for(;k<=n;++k) //得到最小值{if(0==HT[k].parent && HT[k].weight<m){m=HT[k].weight;s1=k;}}for(k=1;k<=n;++k)//得到第二个父节点为零的节点{if(k!=s1 && 0==HT[k].parent){m=HT[k].weight;s2=k;break;}}for(;k<=n;++k) //求得次小元{if(0==HT[k].parent && k!=s1 && HT[k].weight<m){m=HT[k].weight;s2=k;}}}//Select
3.1.3、建立哈夫曼树：根据统计结果建立哈夫曼树。
//算法5.10 根据统计结果建立Huffman树void CreatHuffmanTree(HuffmanTree &HT,int cou[]){if(n<=1) return;int m=2*n-1; HT=new HTNode[m+1];//0 号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点int s1=0,s2=0; //for(int i=1;i<=m;i++) //初始化HuffmanTree 将1~m单元中的双亲，左右孩子的下标初始化为0{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=1;i<=n;i++)//输入叶节点的权值HT[i].weight=cou[i-1];for(i=n+1;i<=m;i++) {Select(HT,i,s1,s2); //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2HT[s1].parent=i; HT[s2].parent=i; //标记其双亲结点为HT[i]HT[i].lchild=s1; HT[i].rchild=s2; //HT[s1]和HT[s2]作为HT[i]的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight; //HT[i]的权值为左右孩子权值之和}printf("\t\thuffmantree构造完成\n");}
3.1.4、算法5.11 根据统计结果对各字符进行编码，并保存在Code.txt中
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC){int start;char *cd;HC=new char*[n+1];cd=new char[n];cd[n-1]='\0';int i,c,f;for (i=1;i<=n;++i){start=n-1;c=i;f=HT[i].parent;while(f!=0){--start;if (HT[f].lchild==c)cd[start]='0';else cd[start]='1';c=f;f=HT[f].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);}delete cd;printf("\t\tHuffmanCode创建完毕\n");}//对SourceFile.txt进行编码，并保存在ResultFile.txt中void Code(HuffmanTree &HT,HuffmanCode &HC){FILE *fp;char word;int i;if((fp=fopen("character.txt","r"))==NULL){printf("can not open the file character.txt"); exit(0); } fp=fopen("character.txt","r");while((word=fgetc(fp))!=EOF){if (word>='A'&&word<='Z'){word=word+32;}i=word-96;cou[i]++;}if(!word)printf("cannot open the file!\n");printf("\t\thuffman编码完成\n");fclose(fp);}
3.1.5、菜单选项
void memu(void){printf("\t\t||************ 欢迎使用学生信息管理系统！****************||\n");printf("\t\t||**name:yuan number:1xxxxxxxxx *******||\n");printf("\t\t|| ********************************* ||\n");printf("\t\t|| * 功能菜单 * ||\n");printf("\t\t|| ***********************************************||\n");printf("\t\t|| 1.字符信息统计,统计出现的字符及其频率||\n");printf("\t\t|| 2.建立哈夫曼树：根据统计结果建立哈夫曼树 ||\n");printf("\t\t|| 3.建立哈夫曼码表将各字符对应的编码表保存在Code.txt||\n");printf("\t\t|| 4.对源文件进行编码,将字符转换成相应的编码文件 ||\n");printf("\t\t|| 5.退出系统 ||\n");printf("\t\t|| ****************************************************||\n");printf("\t\t>>>请选择您需要的服务(1--5):");}
四、测试分析
实验结果：
4.1、读入文本文档中的数据，并进行统计。
ourceFile.txt文件内容为
4.2、建立哈夫曼树：根据统计结果建立哈夫曼树。
4.3、建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。
字符对应的编码表保存在文件Code.txt，结果为：
4.4、 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件
根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt，结果为：
五、源程序清单
//头文件#include "stdio.h"#include "stdlib.h"#include "string.h"int cou[100];//哈夫曼树的结构体typedef struct{int weight; //结点的int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode;int n=2;//字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。void Count() {FILE *fp;char i;char word;char letter[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};//计算输入的字母的个数if((fp=fopen("character.txt","r"))==NULL){printf("can not open the file character.txt"); exit(0); } while((word=fgetc(fp))!=EOF){if (word>='A'&&word<='Z'){word=word+32;}i=word-96;cou[i]++;}fclose(fp);printf("\t\tletter\t频率为\n");for (int j=1;j<=26;j++){if (cou[j]!=0){printf("\t\t%c\t%d\n",letter[j],cou[j]);}}printf("\n");printf("\t\t字符统计完成！\n");}//选择HT中双亲域为0的权值最小的两个结点void Select(HuffmanTree HT,int i,int &s1,int &s2){//选择两个最小值，将他们的位序输出到s1,s2int m=0,k=0;for(k=1;k<=n;++k) //得到第一个父节点为零的节点{if(0==HT[k].parent){m=HT[k].weight;s1=k;break;}}for(;k<=n;++k) //得到最小值{if(0==HT[k].parent && HT[k].weight<m){m=HT[k].weight;s1=k;}}for(k=1;k<=n;++k)//得到第二个父节点为零的节点{if(k!=s1 && 0==HT[k].parent){m=HT[k].weight;s2=k;break;}}for(;k<=n;++k) //求得次小元{if(0==HT[k].parent && k!=s1 && HT[k].weight<m){m=HT[k].weight;s2=k;}}}//Select//建立哈夫曼树：根据统计结果建立哈夫曼树。//算法5.10 根据统计结果建立Huffman树void CreatHuffmanTree(HuffmanTree &HT,int cou[]){if(n<=1) return;int m=2*n-1; HT=new HTNode[m+1];//0 号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点int s1=0,s2=0; //for(int i=1;i<=m;i++) //初始化HuffmanTree 将1~m单元中的双亲，左右孩子的下标初始化为0{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=1;i<=n;i++)//输入叶节点的权值HT[i].weight=cou[i-1];for(i=n+1;i<=m;i++) {Select(HT,i,s1,s2); //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2HT[s1].parent=i; HT[s2].parent=i; //标记其双亲结点为HT[i]HT[i].lchild=s1; HT[i].rchild=s2; //HT[s1]和HT[s2]作为HT[i]的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight; //HT[i]的权值为左右孩子权值之和}printf("\t\thuffmantree构造完成\n");}//算法5.11 根据统计结果对各字符进行编码，并保存在Code.txt中void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC){int start;char *cd;HC=new char*[n+1];cd=new char[n];cd[n-1]='\0';int i,c,f;for (i=1;i<=n;++i){start=n-1;c=i;f=HT[i].parent;while(f!=0){--start;if (HT[f].lchild==c)cd[start]='0';else cd[start]='1';c=f;f=HT[f].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);}delete cd;printf("\t\tHuffmanCode创建完毕\n");}//对SourceFile.txt进行编码，并保存在ResultFile.txt中void Code(HuffmanTree &HT,HuffmanCode &HC){FILE *fp;char word;int i;if((fp=fopen("character.txt","r"))==NULL){printf("can not open the file character.txt"); exit(0); } fp=fopen("character.txt","r");while((word=fgetc(fp))!=EOF){if (word>='A'&&word<='Z'){word=word+32;}i=word-96;cou[i]++;}if(!word)printf("cannot open the file!\n");else{}printf("\t\thuffman编码完成\n");fclose(fp);}//菜单选项void memu(void){printf("\t\t||************ 欢迎使用学生信息管理系统！****************||\n");printf("\t\t||**name:伍思源 number:182034490136 电信18-1 *******||\n");printf("\t\t|| ********************************* ||\n");printf("\t\t|| * 功能菜单 * ||\n");printf("\t\t|| ****************************************************||\n");printf("\t\t|| 1.字符信息统计,统计出现的字符及其频率||\n");printf("\t\t|| 2.建立哈夫曼树：根据统计结果建立哈夫曼树 ||\n");printf("\t\t|| 3.建立哈夫曼码表将各字符对应的编码表保存在Code.txt ||\n");printf("\t\t|| 4.对源文件进行编码,将字符转换成相应的编码文件 ||\n");printf("\t\t|| 5.退出系统 ||\n");printf("\t\t|| ****************************************************||\n");printf("\t\t>>>请选择您需要的服务(1--5):");}int main(void){HuffmanTree ht;HuffmanCode hc;int no;while(1){memu();scanf("%d",&no);printf("\n");switch(no){//字符信息统计,统计出现的字符及其频率 case 1:Count();break;//建立哈夫曼树：根据统计结果建立哈夫曼树case 2:CreatHuffmanTree(ht,cou);break;//建立哈夫曼码表将各字符对应的编码表保存在Code.txtcase 3:CreatHuffmanCode(ht,hc);break;//对源文件进行编码,将字符转换成相应的编码文件case 4:Code(ht,hc);break;//退出系统case 5:printf("\t\t\t退出系统\n");return 0;}printf("\n");}}
六、用户使用手册
用户执行代码后，主菜单会显示5个功能，分别为：
(1) 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。
(2) 建立哈夫曼树：根据统计结果建立哈夫曼树。
(3) 建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。
(4) 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。
（5） //退出系统
首先，用户根据提示选择功能（1）： 读取待编码的源文件SourceFile.txt，统计出现的字符及其频率
若选择功能(2)：用户可以根据自己的需求建立哈夫曼树：根据统计结果建立哈夫曼树
若选择功能(3)：建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。
若选择功能(4)：源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt
若选择功能(5):根据学号进行折半查找，用非递归算法实现，则根据提示输入学生的学号，就可以显示出结果
