哈夫曼编码与译码

哈夫曼编码与译码

用哈夫曼树对字符串进行编码译码

、设计思想 程序要求 :

要求每个字符有自己唯一的编码。将得到的一串利用哈夫曼树对字符串进行编

编码后存到一个文件夹中，然后再从这个文件夹中读出这串编

要求字符的区间为大写的 26 个英文字母， 将获得的串字符用

(jsquanzhi())

数， 将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依 次分别赋给两个结构体HT 和HC 利用HT （节点）权值的大小建立哈夫曼树，首先用 选择函数 select （） 函数选择两个权值最小的字符作为叶子节点，创建一个新的节 点作为这两个叶节点的父节点，被选中的节点给他的 HT[i].parent 赋值是他下次 不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区 中，再进行选择 （被选过的不再被使用 ），直到所有的节点都被使用，这样一个哈夫

曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的

0、1 密文 代

码，从叶节点判断该叶节点是其父节点的左右字左字为‘ 0'，右子为‘ 1'，在 判断父节点是上级父节点的左右子直至根节点，将生成的 0、1 字符串按所表示的 字符倒序存入HC 相应的字符的bins[]数组。重新一个一个字符的读取输入的字符

码,

码进行解码。

实现方法 :

计算

进行字符统计， 统计出现的字符种数以及每种字符出现的次权值的函数

字串译成 0、1 输入一串字符，

串，按照字符出现的顺序将它转为0、1 代码并存到一个txt 文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1 代码赋给一个临时字符串cd[] ，用该字符串与每个字符的

HC[i].bins 密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[] 中，清空临时字符串继续读取0、1

代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。

用哈夫曼树对字符串进行编码译码

、算法流程图

开始

获得输入的字符串getstr[] ，i=0 。

判断getstr[i] 是否i++; 为26 个大写字母否

k=getstr[i]-64;quantemp[k]++( quantemp 为int 型数

组开始值都为0)i++;

i=1,j=0

i<27?

结束是quantemp[i]=i++;

0?

j++;str[j]=i+64;

quan[j]=quantemp[i]

图1 计算字符权值及字符种类算法

说明: 将的的字符串进行字符种类级每种字符出现频率的统计

用哈夫曼树对字符串进行编码译码

开始

将所有的几点的父节

点和子节点权值赋成0

i=1;(num 为字

符的种类)

HT[i].weight=quan[i] i<=num

是否

i=num+1

i<=2*num-1?

是结束? 选择权值最小的两个

节点将下标赋给s1,s2.

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weigh

t;

i++

图2 构建哈夫曼树算法

说明: 利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成

哈夫曼数的搭建。

用哈夫曼树对字符串进行编码译码

开始

将str[i] 的值依次赋

给HC[i].ch

i=0;cd[num]='\0';

i<=num;

start=num; c=i

i++

HT[c].parent

strcpy(HC[i].bits, >0 否&cd[start]); 是

HC[i].len=num-start; cd[--start]=(HT[p].

lchild==c)?'0':'1';

c= HT[c].parent; 打开codefile.txt 文件, 获得字符串str 指针，i=0;

i<=num;

是结束否否

HC[i].ch=*str? i++

图3 利用哈夫曼树加密算法

将HC[i].bits[j] 存进文件

说明: 利用每个字符在哈夫曼树中的位子，得到每个字符的0、1 密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。

用哈夫曼树对字符串进行编码译码

开始

cjs=0, i=0 打开文件夹codefile.txt,

!feof(fp)

结束

(i

&&(!feof(fp)

cd[i]='';cd[i+1]='\0';

cd[i]=fgetc(fp);j=1;

j<=num i++

j++

strcmp(HC[j]

.bits,cd)=0

str[k]=HC[j].ch;cjs=1;

k++;str[k]='\0';break;

图4 解密算法

说明: 从文件夹中读出密文，和HC[i].bis 中的密文进行比较译出

字符，存入临时数组。待译码结束后，输出字符串。

用哈夫曼树对字符串进行编码译码

- 5 -

三、源代码

// hafuman.cpp :

定义控制台应用程序的入口点。 //

#include "stdafx.h"

#include "stdlib.h"

#include "string.h"

#include "stdio.h"

叶节点的个数小等于 n #define m 2*n-1 // 总结点的个数为 结构体用于存放树节点包括节点的父节点、左子、右子以 及权值 { int weight;

int parent,lchild,rchild;

}HTNode;

typedef HTNode HafumanTree[m+1]; // 重命名 HTNode

typedef struct // 结构体由于存放每个字符的密文和长度 {char ch;

char bits[10];

int len;

}CodeNode;

typedef CodeNode HafumanCode[n+1]; // 重命名 CodeNode

int _tmain(int argc, _TCHAR* argv[]) {int quan[27]; //

以存放 26字符的权值 char getstr[300],str[27]; // 声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符

char *s; // 声明一个 char 型指针用于指向字符 HafumanTree HT; // 声明 m+1 个树节点 HafumanCode HC; // 声明 n+1 个 code

m=2*n-1 int num; //

定义一个全局变量用于存放字符种类个数

#define n 100 //

typedef struct //

声明一个数组用

int jisuanquan(char *s,int quan[],char str[]); // 声明需要调用的函数void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]);

void Hafumanencode(HafumanTree HT,HafumanCode HC); void

coding(HafumanCode HC,char *str); char *decode(HafumanCode HC);

用哈夫曼树对字符串进行编码译码

printf(" 请输入要加密的字符串:\n");

gets(getstr); // 获得输入的字符串num=jisuanquan(getstr,quan,str); //

统计字符串中含有字符种类个数//printf("%d\n",num);

gjhafumantree(HT,HC,quan,str); // 根据字符权值构建哈夫曼树Hafumanencode(HT,HC); // 根据哈夫曼树确定每个字符的code

coding(HC,getstr); // 将字符串译码存入文件夹s=decode(HC); // 将暗文解码printf(" 解密为:\n");

printf("%s\n",s);

system("pause");

return 0;

// 函数

int jisuanquan(char *s,int quan[],char str[]) // 计算字符串中字符权值{char *p;

int i,j,k,quantemp[27];

for(i=1;i<27;i++) // 将所有字符的权值赋成

{quantemp[i]=0;}

for(p=s;*p!='\0';p++) // 判断字符串是否结束