Huffman编码与译码算法

#include

#include //malloc( )

#include // INT ,MAX

//#include //EOF,NULL

#include //atoi( )

#include //eof( )

#include //floor( ),ceil( ),abs( )

#include //exit( )

#include //cout,cin

//函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

//OVERFLOW 在 math.h 中已定义为3

typedef int Status;

typedef int Boolean; // 布尔类型

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

char h;

}HTNode,*HuffmanTree;//......动态分配数组存储huffman树

typedef char * *HuffmanCode;//动态分配数组存储Huffman编码表

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)

{//构造Huffman树HT，并求n个字符的Huffman编码表HC

if(n<=1)return;

int m=2*n-1;

HuffmanTree p;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用

int x,a,k,s1,s2,i,j,start,c,f;

char w;

char *cd;

cout<<\"输入字符与与对应的频度：\";

for(p=HT+1,i=1;i<=n;++i,++p)

{

cin>>w;

cin>>x; 0

p->weight=x;

p->h=w;

p->parent=0;

p->lchild=0;

p->rchild=0;

}

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

{

p->lchild=0;

p->parent=0;

p->rchild=0;

p->weight=0;

}

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

{//建Huffman树

a=HT[i-1].weight;

s1=i-1;

for(k=1;k<=i-1;k++)

{

if(HT[k].parent==0)

if(a>HT[k].weight){a=HT[k].weight;s1=k;}

//else s1=k;

}//求表中的s1

for(j=1;j<=i-1;j++)

{

if(HT[j].parent==0&&j!=s1){a=HT[j].weight;s2=j;}

}

for(k=1;k{

if(HT[k].parent==0&&k!=s1)

if(a>HT[k].weight)

{

a=HT[k].weight;

s2=k;

}

//else s2=k;

}//求表中的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;

}

//------从叶子到根逆向求每个字符的Huffman编码------//

HC=(HuffmanCode)malloc((n+1)*sizeof(char *));

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

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

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

{

start=n-1;

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码

if(HT[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

HC[i]=(char *)malloc((n-start)*sizeof(char));

strcpy(HC[i],&cd[start]);

}

free(cd);

}

void coding(HuffmanCode &HC)

{

cout<<\"a的频度为12\huffman编码为:\"<cout<<\"b的频度为6\huffman编码为:\"<cout<<\"d的频度为4\huffman编码为:\"<cout<<\"e的频度为1\huffman编码为:\"<cout<<\"o的频度为2\huffman编码为:\"<cout<<\"y的频度为8\huffman编码为:\"<}

//.................Huffman的译码算法.........................//

void decode(HuffmanTree &HT,HuffmanCode &HC)

{//实现Huffman的译码算法

cout<<\"请输入一组编码：\";

char string[100];

char *p;

int k;

p=string;

//for(int i=0;i<17;i++)

//cin>>string[i];

cin>>string;

cout<<\"译成的明文码为：\";

for(int i=1;i<=6;)//.......HC[1-6]一个一个的寻找

{

for(k=0;;k++)//........k是用来表示编码的长度

{

if(HC[i][k]==p[k])continue;

else break;

}

if(HC[i][k]=='\\0'){cout<//else if(p[k]=='\\0'){cout<<\"最后一个字符报告错误，无法译出。\";break;}

else

{

i++;

if(i>=7){cout<<\"字符报告错误，无法译出。\";p++;}

continue;}//...........否则则继续查找

}

}

void main()

{

HuffmanTree HT;

HuffmanCode HC;

cout<<\" HuffmanCoding(HT,HC,6);

coding(HC);

decode(HT,HC);

//...........huffman编码与译码.................// \"<}