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

开始 打开文件夹codefile.txt, cjs=0, i=0 !feof(fp) 结束 (i

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

三、源代码

// hafuman.cpp : 定义控制台应用程序的入口点。 //

#include \#include \#include \#include \

#define n 100 int num;

typedef struct { int weight;

int parent,lchild,rchild; }HTNode;

typedef HTNode HafumanTree[m+1];

typedef struct {char ch; char bits[10]; int len; }CodeNode;

typedef CodeNode HafumanCode[n+1];

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

//声明一个数组用以存放26字符的权值

//声明一个char型指针用于指向字符//声明m+1个树节点 //声明n+1个code //声明需要调用的函数

char getstr[300],str[27]; char *s;

//重命名CodeNode

//结构体由于存放每个字符的密文和长度

//重命名HTNode

//结构体用于存放树节点包括节点的父节点、左子、右子以及权值

//叶节点的个数小等于n //总结点的个数为m=2*n-1

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

#define m 2*n-1

//声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符 HafumanTree HT;

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);

HafumanCode HC;

- 6 -

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

printf(\请输入要加密的字符串：\\n\gets(getstr);

num=jisuanquan(getstr,quan,str); //printf(\

gjhafumantree(HT,HC,quan,str); Hafumanencode(HT,HC); coding(HC,getstr); s=decode(HC);

printf(\解密为：\\n\printf(\

system(\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++)

{if(*p>='A'&&*p<='Z')

{k=*p-64;

quantemp[k]++;

} } j=0;

for(i=1,j=0;i<27;i++) {if(quantemp[i]!=0) {j++;

str[j]=i+64;

quan[j]=quantemp[i];

} } return j; }

//获得输入的字符串

//统计字符串中含有字符种类个数 //根据字符权值构建哈夫曼树

//根据哈夫曼树确定每个字符的code

//将字符串译码存入文件夹

//将暗文解码

//计算字符串中字符权值

//将所有字符的权值赋成0

//判断字符串是否结束 //判断字符是否为26字母 //看是26个字符中的哪个字符

//字符权值加1

//用于统计字符种类个数

//str按字母表顺序存储出现过的字符

- 7 -

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

void select(HafumanTree HT,int k,int *s1,int*s2) {int i,j;

int min1=9999; for(i=1;i<=k;i++)

//声明一个int类型的数值min1，赋个较大的输给它 //选择权值最小的一个节点（且该节点无父节点）

//选择权值最小的两个

{if((HT[i].weight

min1=9999; for(i=1;i<=k;i++)

{if((HT[i].weight

void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan[],char str[]) //构建哈夫曼树 {int i,s1,s2;

for(i=1;i<2*num-1;i++)

//将所有的节点赋空

{HT[i].lchild=0;HT[i].rchild=0; HT[i].parent=0;HT[i].weight=0; }

for(i=1;i<=num;i++) {HT[i].weight=quan[i]; }

for(i=1;i<=num;i++) {HC[i].ch=str[i]; } i=1;

while(i<=num)

{ printf(\ for(i=num+1;i<=2*num-1;i++) {select(HT,i-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].weight; } }

//父节点的权值为子节点相加（父节点继续放入选择区）

//输出每个字符的及其权值

//将num个字符赋给codenode

//将num个字符的权值赋给num叶节点

{j=i;min1=HT[i].weight;}

//选择权值最小的一个节点（且该节点无父节点）

- 8 -