Huffman编码器

#include

#include\

using namespace std;

#define MAX 100

#define N 26

typedef struct

{//哈夫曼树的结点

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*Huffmantree;

typedef struct

{//字符存储结点信息

char data; //待编码的字符

int weight; //字符的权值

char code[N]; //字符的编码

} HTCode;

//初始化结点信息

void InitCode(HTCode *Hr,int &n) {

cout<<\请输入字符编码的个数n：\

cin>>n;

cout<<\请输入待编码字符以及相应的权值：\

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

{

cin>>(Hr+i)->data>>(Hr+i)->weight;

} }

void Select(Huffmantree &HT,int end,int *s1,int *s2)

{//在0~end之间,找出最小和次小的两个结点序号,返回S1,S2

int i;

int min1 = MAX;

int min2;

for (i = 1;i <= end;i++)

{//找最小的结点序号

if ((HT+i)->parent == 0 && (HT+i)->weight<=min1)

{

*s1 = i;

min1 = (HT+i)->weight;

}

}

min2 = MAX;

for(i = 1;i <= end;i++)

{//找次小结点的序号

if ((HT+i)->parent == 0 && *s1 != i && min2 >= (HT+i)->weight)

{

*s2 = i;

min2 = (HT+i)->weight;

}

} }

//初始化哈夫曼树,并把信息存入Hr

void InitHfmtree(Huffmantree &Ht,HTCode Hr[],int &n) {

if(n <= 1) return;

int m,start,i,j,f;

int s1,s2;

m = 2*n-1; //n个顶点有m个节点

Ht = (Huffmantree)malloc((m+1)*sizeof(HTNode));

Huffmantree P;

P = Ht+1;

for(i = 1;i <= m;i++,P++) //0号单元没用

{

if(i <= n) P->weight = Hr[i].weight;

else P->weight = 0;

P->lchild = 0;

P->rchild = 0;

P->parent = 0;

}

for(i = n+1;i <= m;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;

}

char *code;

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

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

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

{//编码存入Hr->code

start = n-1;

for(j = i,f = Ht[j].parent;f != 0;j = f,f = Ht[f].parent)

if(Ht[f].lchild == j)

code[--start] = '0';

else

code[--start] = '1';

strcpy(Hr[i].code,&code[start]);

}

cout<<\字符编码初始化完成！\ }

void Encoding(HTCode *Hr,int n)

{//编码

int i,j;

char *encode;

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

cout<<\请选择你想要编码的字符：\

cin>>encode;

for(i = 0;encode[i]!='\\0';i++)

{

j = 1;

while(encode[i] != Hr[j].data) j++;

if(j>n)

cout<<\您输入编码\错误！\

else