#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>
#include?<conio.h>
#define?MAX_CHAR_KINDS?128//字符種類最大值。。
#define?MAX_NUM?1000//字符串最大長度。。
typedef?struct?TreeNode
{
int?weight;
int?id;
short?isLeaf;
char?data;
char?bin;//0或者1。。?
struct?TreeNode?*parent;
struct?TreeNode?*lChild,?*rChild;
}?TreeNode;
typedef?struct
{
char?data;
char?code[MAX_CHAR_KINDS];
}?Code;
//字符串倒置。。?
void?ReverseStr(char?*str)
{
int?i;
char?c;
int?length;
length?=?strlen(str);
for?(i?=?0;?i?<?length?/?2;?i++)
{
c?=?str[length?-?1?-?i];
str[length?-?1?-?i]?=?str[i];
str[i]?=?c;
}
}
int?main()
{
char?str[MAX_NUM];
char?pwd[MAX_NUM];
TreeNode?*HFTree;
int?i,?j;
int?length;//字符串長度。。
int?count;//不同字符個數。。
TreeNode?*tree[MAX_CHAR_KINDS];//初始的幾個小樹。。
TreeNode?*eachChar[MAX_CHAR_KINDS];
TreeNode?*temp,?*p;
Code?*HFCode;
int?codeBit;
short?existed;
//輸入，初始化。。
printf("Input?string:\n");?
gets(str);
printf("\n");
length?=?strlen(str);
count?=?0;
//開始統計字符串中各個字符出現的次數。。
for?(i?=?0;?i?<?length;?i++)
{
existed?=?0;
for?(j?=?0;?j?<?count;?j++)
{
if?(str[i]?==?tree[j]->data)
{
tree[j]->weight++;
existed?=?1;
break;
}
}
//如果不是現有的字符，拿個新盒子裝。。
if?(existed?==?0)
{
tree[count]?=?(TreeNode?*)malloc(sizeof(TreeNode));
tree[count]->weight?=?1;
tree[count]->data?=?str[i];
tree[count]->parent?=?NULL;
tree[count]->lChild?=?NULL;
tree[count]->rChild?=?NULL;
eachChar[count]?=?tree[count];//備份。。?
count++;
}
}
//非法輸入。。?
if?(count?==?0)
{
printf("No?char!\n");?
getch();
return?(0);
}
else?if?(count?==?1)
{
printf("At?least?2?kinds?of?char!\n");?
getch();
return?(0);
}
//冒泡，升序。。
for?(i?=?0;?i?<?count?-?1;?i++)
{
for?(j?=?0;?j?<?count?-?1?-?i;?j++)
{
if?(tree[j]->weight?>?tree[j+1]->weight)
{
temp?=?tree[j];
tree[j]?=?tree[j+1];
tree[j+1]?=?temp;
}
}
}
//生成Huffman樹。。
for?(i?=?1;?i?<?count;?i++)
{
temp?=?(TreeNode?*)malloc(sizeof(TreeNode));
temp->lChild?=?tree[i-1];
temp->rChild?=?tree[i];
temp->parent?=?NULL;
temp->weight?=?tree[i-1]->weight?+?tree[i]->weight;
tree[i-1]->parent?=?temp;
tree[i-1]->bin?=?'0';
tree[i]->parent?=?temp;
tree[i]->bin?=?'1';
tree[i]?=?temp;
for?(j?=?i;?j?<?count?-?1;?j++)
{
if?(tree[j]->weight?>?tree[j+1]->weight)
{
temp?=?tree[j];
tree[j]?=?tree[j+1];
tree[j+1]?=?temp;
}
else
{
break;
}
}
}
HFTree?=?tree[count-1];
//冒泡後求各個字符的哈夫曼編碼。。
for?(i?=?0;?i?<?count?-?1;?i++)
{
for?(j?=?0;?j?<?count?-?1?-?i;?j++)
{
if?(eachChar[j]->weight?>?eachChar[j+1]->weight)
{
temp?=?eachChar[j];
eachChar[j]?=?eachChar[j+1];
eachChar[j+1]?=?temp;
}
}
}
HFCode?=?(Code?*)malloc(count?*?sizeof(Code));
for?(i?=?0;?i?<?count;?i++)
{
temp?=?eachChar[i];
HFCode[i].data?=?temp->data;
codeBit?=?0;
while?(temp->parent?!=?NULL)
{
HFCode[i].code[codeBit]?=?temp->bin;
temp?=?temp->parent;
codeBit++;
}
HFCode[i].code[codeBit]?=?'\0';
ReverseStr(HFCode[i].code);
}
//輸出。。
printf("%5s%8s%15s\n",?"char",?"count",?"Huffman?code");
for?(i?=?0;?i?<?count;?i++)
{
printf("?'%c'%8d%15s\n",?eachChar[i]->data,?eachChar[i]->weight,?HFCode[i].code);
}
printf("\n");
getch();
return?(0);
}