哈夫曼编码原码

#define INT_MAX 10000

#define ENCODING_LENGTH 1000

#include "stdio.h"

#include "string.h"

#include "malloc.h"

typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子

typedef char Elemtype;

typedef struct TNode{

Elemtype letter;

int weight;

int parent;

Which sigh;

char *code;

}HTNode,*HuffmanTree;

int n;

char coding[50];//储存代码

char str[ENCODING_LENGTH];//保存要翻译的句子

void InitTreeNode(HuffmanTree &HT){//初始前N个结点,后M-N个结点置空

int i;int w;char c;

int m=2*n-1;

HuffmanTree p;

HT=(HuffmanTree)malloc((m)*sizeof(HTNode));

printf("input %d database letter and weight",n);

p=HT;

getchar();

for (i=1;i<=n;i++){

scanf("%c%d",&c,&w);

p->code='\0';

p->letter=c;

p->parent=0;

p->sigh=none;

p->weight=w;

p++;

getchar();

}

for (;i<=m;i++,p++){

p->code='\0';

p->letter=' ';

p->parent=0;

p->sigh=none;

p->weight=0;

}

}//INITTREENODE

void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2

int i;

int min1=INT_MAX;

int min2;

for (i=0;i<=end;i++){//找最小的结点序号

if (HT[i].parent==0&&HT[i].weight<min1){

*s1=i;

min1=HT[i].weight;

}

}

min2=INT_MAX;

for(i=0;i<=end;i++){//找次小结点的序号

if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){

*s2=i;

min2=HT[i].weight;

}

}

}

void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN树

int i;int m=2*n-1;

int s1,s2;

for(i=n;i<m;i++){

Select(HT,i-1,&s1,&s2);

HT[s1].parent=i;

HT[s2].parent=i;

HT[s1].sigh=left_child;

HT[s2].sigh=right_child;

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

}

}

void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN译码

int i;

char *temp;

temp=(char *)malloc(n*sizeof(char));

temp[n-1]='\0';

int p;int s;

for (i=0;i<n;i++){

p=i;

s=n-1;

while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1

if (HT[p].sigh==left_child)

temp[--s]='0';

else if (HT[p].sigh==right_child)

temp[--s]='1';

p=HT[p].parent;

}

HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间

strcpy(HT[i].code,temp+s);

printf("%s\n",HT[i].code);

}

}

void GetCodingSen(char *sencence){//输入要编码的句子

int l;

gets(sencence);

l=strlen(sencence);

sencence[l]='\0';

}

void HuffmanTreeEncoding(char sen[],HuffmanTree HT){//将句子进行编码

int i=0;int j;

while(sen[i]!='\0'){

for(j=0;j<n;j++){

if (HT[j].letter==sen[i]) //字母吻合则用代码取代

{strcat(coding,HT[j].code);

break;

}

}

i++;

if (sen[i]==32) i++;

}

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

}

void HuffmanTreeDecoding(HuffmanTree HT,char code[]){//HUFFMAN译码过程,将代码翻译为句子

char sen[100];

char temp[50];

char voidstr[]=" ";

int i;int j;

int t=0;int s=0;

for(i=0;i<strlen(code);i++){

temp[t++]=code[i];

for(j=0;j<n;j++){

if (strcmp(HT[j].code,temp)==0){//代码段吻合

sen[s]=HT[j].letter;s++;

strcpy(temp,voidstr);//将TEMP置空

t=0;

break;

}

}

}

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

}

void main(){

HTNode hnode;

HuffmanTree huff;

huff=&hnode;

printf("input the letter for coding number\n");

scanf("%d",&n);

InitTreeNode(huff);

HuffmanTreeCreat(huff);

HuffmanTreeCode(huff);

GetCodingSen(str);

HuffmanTreeEncoding(str,huff);

HuffmanTreeDecoding(huff,coding);

}