C++程序霍夫曼编码

/****************** 霍夫曼编码 **********************/

//2010-3-31：注释

//程序共有8处需要补充

#include

#include

#include

#define n 100

#define m 2*n-1

// 码结点的存储结构

typedef struct

{

char ch;

char bits[9];

int len;

}CodeNode;

typedef CodeNode HuffmanCode[n+1];

// 树结点的存储结构

typedef struct

{

int weight;

int lchild,rchild,parent;

}HTNode;

typedef HTNode HuffmanTree[m+1];

int num;

// 挑选权值最小的两个结点

void select(HuffmanTree HT, int k, int &s1, int &s2)

{

int i,j;

int minl=32767;

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

if(HT[i].weight{

j=i;

minl=HT[i].weight;

}

s1=j;

minl=32767;

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

if(HT[i].weight{

j=i;

minl=HT[i].weight;

}

s2=j;

}

// 统计输入字符串st中出现的字符种类和各个字符在该字符串中出现的次数，

// 出现的字符存放在str数组中，各个字符在该字符串中出现的次数存放在

// cnt数组中，返回字符串st中字符种类数。

int jsq(char *s, int cnt[], char str[])

{

char*p;

int i,j,k=0;

int temp[257];

for(i=0;i<257;i++)

temp[i]=0;

for(p=s;*p!='\\0';p++)

//程序补充处1：统计字符串中指针p所指向的字符出现的次数，次数保存在数

//组元素temp[*p]中

{

temp[*p]++;

}

for(i=0,j=0;i<=256;i++)

if(temp[i]!=0)

{

//程序补充处2：将字符串中各字符按其在ASCII码表中位置依次存放在数组元

//素str[j]中，并将其在该字符串中出现的次数存放在数组元素cnt[j]中

j++;

str[j]=i;

cnt[j]=temp[i];

}

num=j;

return j;

}

// 建立霍夫曼树

void chuffmanTree(HuffmanTree &HT, HuffmanCode &HC, int cnt[], 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=cnt[i];

//程序补充处3：将霍夫曼树中各叶子节点的权值HT[i].weight设置为该字符在

//字符串中出现的次数cnt[i]

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;

//程序补充处4：将调用select函数得到的两个权值最小的结点s1和s2合并，产生

//一个新结点i，（1）设置结点s1的父结点为结点i；（2）设置结点s2的父结点

//为结点i；（3）设置结点i的左子结点为结点s1；（4）设置结点i的右子结点为

//结点s2；（5）结点i的权值为结点s1和s2权值之和

}

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

HC[i].ch=str[i];

}

// 给霍夫曼树的每个叶子结点分配二进制码

void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC)

{

int c,p,i;

char cd[n];

int start;

cd[num]='\\0';

for(i=1;i<=num;i++) // 1到num为叶子结点，每个结点都有一个二进制编码串

{

start=num;

c=i;

while((p=HT[c].parent)>0)

{

start--;

cd[start]=(HT[p].lchild==c)?'0':'1';

c=p;

}

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

HC[i].len=num-start;

//程序补充处5：求取每个叶子节点的霍夫曼二进制编码的码长HC[i].len

}

}

// 译码

void decode(HuffmanCode HC,char receive[], char s[])

{

char str[268];

char cd[9];

int i,j,k=0,p=0,cjs;

while(receive[p]!='\\0')

{

cjs=0;

for(i=0;i{

cd[i]=' ';

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

cd[i]=receive[p++];

for(j=1;j<=num;j++)

//程序补充处8：补充下述if语句的条件：要求利用strcmp函数对HC[j].bits

//和cd进行比较，当二者相等时执行后述大括号中语句

//strcmp函数：当进行比较的两个字符串相当时，函数返回值为0

if(strcmp(HC[j].bits,cd)==0)

{

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

k++;

cjs=1;

break;

}

}

}

str[k]='\\0';

strcpy(s,str);

}

// 输出字符串的二进制编码

void coding(HuffmanCode HC, char str[],char get[])

{

int i,j=0;

while(str[j]!='\\0')

{

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

if(HC[i].ch==str[j])

{

strcat(get,HC[i].bits);

break;

}

j++;

}

strcat(get,\"\\0\");

//程序补充处6：用函数strcat将get数组的末尾处加上字符串结束标志\"\\0\"

}

// 计算编码效率

double code_ratio(char st[],int cn[],HuffmanCode HC)

{

double up=0.0,down=0.0,temp=0.0;

int i=1,len=strlen(st);

for(i;i<=num;i++)

{

temp=cn[i]/double(len);

//程序补充处7：计算单个字符在字符串中出现的概率temp

up-=temp*(log(temp)/log(2));

down+=temp*HC[i].len;

}

return (up/down)*100;

}

//主函数

void main()

{

char str[257]; // str用于在统计输入序列中的字符时用，存放是什么字符，1到256

char st[10000],s[10000]; // st用来接受输入的字符串，s用来接受解压的字符串

int cn[257]; // cn用于接受统计后的每个字符的频率，1到256

HuffmanTree HT;

HuffmanCode HC;

printf(\"输入要编码的字符串：\");

scanf(\"%s\

// 统计输入字符串st中出现的字符种类和各个字符在该字符串中出现的次数，

// 出现的字符存放在str数组中，各个字符在该字符串中出现的次数存放在

// cn数组中，num为字符串st中字符种类数。

num=jsq(st,cn,str);

// 在str数组中最后一个字符的后面加上一个字符串结束标志'\\0'

str[num+1]='\\0';

chuffmanTree(HT,HC,cn,str); // 建立霍夫曼树

HuffmanEncoding(HT,HC); // 根据霍夫曼树建立霍夫曼编码

printf(\"共有%d种符号\\n\

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

printf(\"字符%c次数为%d,编码为%s\\n\

char get[10000];

get[0]='\\0';

coding(HC,st,get);

printf(\"上述字符串的霍夫曼码为%s\\n\

printf(\"编码效率为%f%%\\n\

printf(\"输入二进制码开始译码：\");

char receive[10000];

scanf(\"%s\

decode(HC,receive,s); // 译码

printf(\"译码得：%s\\n\

}