/* 哈夫曼编码 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAX 100
/*哈夫曼树结点结构定义 */
typedef struct {
int weight; //存放字符ch的权值
char ch; //记录字符
int lchild, rchild, parent;//存储左孩子、右孩子以及父结点
} TNode, *PHT;
/* 哈夫曼编码表的元素结构定义 */
typedef struct {
char ch; // 编码对应的字符
char *pcode; // 指向编码字符串的指针
} TCode, *PCode;
/*
*统计字符串text中字符出现的频率，参数n为字符串长度
*返回值：text中出现的不同种类的字符个数
*副作用：通过指针参数间接返回两个数组：
* 1)dict：字符数组，存放 text中出现的不同种类的字符
* 2)freq：整型数组，存放 text中出现的不同种类的字符的出现频率
*/
int calc_freq(char text[], int **freq, char **dict, int n){
int i,j, k, nchar = 0;
int *pwght;
char *pch;
int tokens[256] = {0};
//根据输入的文本字符串逐一统计字符出现的频率
for(i = 0; i < n; ++i){
tokens[text[i]]++;
}
//统计共有多少个相异的字符出现在文本串中
for(i = 0; i < 256; i++){
if( tokens[i] > 0 ){
nchar++;
}
}
//为权重数组分配空间
pwght=(int*)malloc(sizeof(int)*nchar);
if(!pwght){
printf("为权重数组分配空间失败！\n");
exit(0);
}
//为字符数组（字典）分配空间
pch=(char *)malloc(sizeof(char)*nchar);
if( !pch ){
printf("为字符数组（字典）分配空间失败！\n");
exit(0);
}
k = 0;
for(i = 0; i < 256; ++i){
if( tokens[i] > 0 ){
pwght[k] = tokens[i];
pch[k] = (char)i; //强制类型转换
k++;
}
}
*freq = pwght;
*dict = pch;
for(i=0;i<nchar;i++)
printf("%c\t%d\n",pch[i],pwght[i]);
return nchar;
}
/*构建哈夫曼树 */
PHT create_htree( int **freq, int n ){
PHT pht;
int i, lc, rc, ntotal = 0;
ntotal = (2 * n) - 1; // Huffman树的结点总数
pht = (PHT) malloc( sizeof( TNode ) * ntotal );
for( i = 0; i < ntotal; ++i ){ // Huffman树结点初始化
pht[i].weight = (i < n) ? *freq[i] : 0;
pht[i].lchild = -1;
pht[i].rchild = -1;
pht[i].parent = -1;
}
for( i = n; i < ntotal; ++i ){ // 构建Huffman树
select_subtree( pht, (i-1), &lc, &rc );
pht[lc].parent = i;
pht[rc].parent = i;
pht[i].lchild = lc;
pht[i].rchild = rc;
pht[i].weight = pht[lc].weight + pht[rc].weight;
}
printf("创建哈夫曼树成功！\n");
return pht;
}
/*子树选择算法 */
int select_subtree(PHT pht, int n, int *pa, int *pb){//n为哈夫曼树结点数目
int id, ida = -1, idb= -1; // ida存放权重最小的结点下标
int wa = INT_MAX, wb = INT_MAX; // wa最小值 wb次小值
for(id = 0; id <= n; id++){
if(pht[id].parent == -1){
if( pht[id].weight < wa ){
idb = ida; // 重置次小值结点下标
wb = wa; //将较大的权值复制给wb
ida = id; //重置最小值结点下标
wa = pht[id].weight; //将最小的权值记录为wa
}
else if(pht[id].weight < wb ){ //新权值大于wa小于wb
idb = id; //重置次小值结点下标
wb = pht[id].weight; //重置次小值
}
}
}
*pa = ida;
*pb = idb;
return 0;
}
/* 根据哈夫曼树pht求哈夫曼编码表book */
void htree_encoding (PHT pht, TCode *book, int n){
int i, c, p, start; // start表示编码在cd中的起始位置
char cd[n+1];
cd[n]='\0'; // 临时存放编码
for(i = 0; i < n; i++){ // 依次求叶子pht[i]的编码
book[i].ch = pht[i].ch; // 读入叶结点pht[i]对应的字符
start = n;
c = i; // 从叶结点pht[i]开始上溯
while( p = pht[c].parent > 0){
if(pht[p].lchild == c)
cd[--start]='0';
else
cd[--start] ='1';
c = p;
} // 继续上溯直到根节点
strcpy(book[i].pcode, &cd[start]); // 复制编码位串
}
printf("哈夫曼编码成功！\n");
}
void print_htreecode(TCode *book,int n){
int i;
for(i=0;i<n;i++){
printf("%c\t%d\n",book[i].ch,book[i].pcode);
}
printf("哈夫曼编码打印成功！\n");
}
void main(){
char text[MAX];
int scount=0,nchar=0,n;
int weights[MAX];
int **freq;
char **dict;
PHT pht;
TCode *book;
//从键盘输入英文字符串
printf("请输入英文字符串：\n");
while((text[scount]=getchar())!='\n')
scount++;
//统计字符串中不同字符出现的频率并打印相应信息
calc_freq(text,freq,dict,scount);
// 构建哈夫曼树
create_htree(freq,nchar);
//遍历哈夫曼树生成哈夫曼编码
htree_encoding (pht,book,nchar);
printf("打印每个字符的哈夫曼编码如下：\n");
printf("字符\t编码\n");
print_htreecode(book,nchar);
}不偏不易
相关分类