给定权值｛2,3,4,7,8,9｝,构造赫夫曼树.

给定权值｛2,3,4,7,8,9｝,构造赫夫曼树.
给定权值｛2,3,4,7,8,9｝,构造赫夫曼树.

给定权值｛2,3,4,7,8,9｝,构造赫夫曼树.
#include
#include
#include
#include
enum {CODESIZE = 20, SIZE = 128};
typedef struct HTNode
{
unsigned int weight;
char ch;
HTNode *lchild, *rchild;
}*HuffmanTree;
typedef struct
{
unsigned int add;
char ch;
}weight;
typedef char **HuffmanCode;
int n = 0;
void Count(FILE *in, weight *w)
{
char c;
int i;
unsigned all = 0;
while((c = fgetc(in)) != EOF)
{
for(i = 0; i < n; i ++)
if(w[i].ch == c)
{
w[i].add ++;
break;
}
if(i == n)
{
w[n].ch = c;
w[n].add = 1;
n ++;
}
all ++;
}
for(i = 0; i < n; i++)
w[i].add = (unsigned int)((double)w[i].add / (double)all * 100.0);
}
void MakeHuffmanTree(HuffmanTree &root, weight *w)
{
int cmp(const void *, const void *);
HTNode *p[n], *t;
int m = n;
for(int i = 0; i < n; i ++)
{
p[i] = (HuffmanTree)malloc(sizeof(HTNode));
p[i] -> ch = w[i].ch;
p[i] -> weight = w[i].add;
p[i] -> lchild = NULL;
p[i] -> rchild = NULL;
}
while(m > 1)
{
qsort(p, m, sizeof(HuffmanTree), cmp);
t = (HuffmanTree)malloc(sizeof(HTNode));
t -> ch = 0;
t -> weight = ((p[m - 1] -> weight) + (p[m - 2] -> weight));
t -> rchild = p[m - 1];
t -> lchild = p[m - 2];
p[m - 2] = t;
m --;
}
root = t;
}
void Coding(HuffmanTree T, int i, int &j, HuffmanCode code, char *temp)
{
if(!T)
return;
if(!(T -> lchild) && !(T -> rchild))
{
temp[i] = '\0';
code[j][0] = T -> ch;
strcpy(&code[j][1], temp);
j ++;
return;
}
if(T)
{
temp[i] = '0';
Coding((T -> lchild), (i + 1), j, code, temp);
temp[i] = '1';
Coding((T -> rchild), (i + 1), j, code, temp);
}
}
void HuffmanCoding(HuffmanTree &root, HuffmanCode &code, char *temp)
{
code = (HuffmanCode)malloc(n * sizeof(char *));
for(int i = 0; i < n; i ++)
code[i] = (char *)malloc(CODESIZE * sizeof(char));
int j = 0;
if(!n)
root = NULL;
Coding(root, 0, j, code, temp);
}
void Huffman(HuffmanCode code, FILE *in, FILE *out)
{
char c;
while((c = fgetc(in)) != EOF)
{
for(int i = 0; i < n; i ++)
if(code[i][0] == c)
{
fputs(&code[i][1], out);
break;
}
}
}
void ReHuffman(FILE *in, FILE *out, HuffmanTree root)
{
char c;
HuffmanTree p;
p = root;
while((c = fgetc(in)) != EOF)
{
if(c == '1')
p = (p -> rchild);
else
p = (p -> lchild);
if(!(p -> lchild) && !(p -> rchild))
{
fputc((p -> ch), out);
p = root;
}
}
}
int main(void)
{
HuffmanTree root;
HuffmanCode code;
char *temp;
weight *w;
w = (weight *)malloc(SIZE * sizeof(weight));
FILE *in, *out;
in = fopen("Text.in", "r");
out = fopen("CodeTable.out", "w+");
Count(in, w);
MakeHuffmanTree(root, w);
free(w);
temp = (char *)malloc(CODESIZE * sizeof(char));
HuffmanCoding(root, code, temp);
free(temp);
for(int i = 0; i < n; i ++)
{
fputc('\'', out);
if(code[i][0] == '\n')
fprintf(out, "\\n");
else if(code[i][0] == '\t')
fprintf(out, "\\t");
else
fputc(code[i][0], out);
fputc('\'', out);
fputc('\t', out);
fputs(&code[i][1], out);
fputc('\n', out);
}
fclose(out);
out = fopen("TextCode.out", "w+");
rewind(in);
Huffman(code, in, out);
fclose(in);
fclose(out);
in = fopen("TextCode.out", "r");
out = fopen("ReText.out", "w+");
ReHuffman(in, out, root);
fclose(in);
fclose(out);
return 0;
}
int cmp(const void *a, const void *b)
{
HuffmanTree p1 = *(HuffmanTree *)a;
HuffmanTree p2 = *(HuffmanTree *)b;
if((p1 -> weight) > (p2 -> weight))
return -1;
if((p1 -> weight) < (p2 -> weight))
return 1;
return 0;
}
这是我以前写的,输入在Text.in里输入一篇文章,程序自动统计每个字母出现个数,算出权重,然后生成Huffman树,建立CodeTable.out存储对应字母的编码值,生成TextCode.out文件产生文章编码,最后再把解码的结果写入ReText.out文件