给定权值{2,3,4,7,8,9},构造赫夫曼树.
来源:学生作业帮 编辑:大师作文网作业帮 分类:综合作业 时间:2024/09/24 14:25:22
给定权值{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文件
#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文件
设给定一个权值集合W=(3,5,4,9,11,8,15),要求根据给定的权值集合构造一棵哈夫曼树
给定权值(7,18,3,32,5,26,12,8),构造相应的哈夫曼树
给定权值(15,3,14,2,6,9,16,17),构造相应的哈夫曼树
设给定一个权值集合W=(9,4,10,6,3,10,8,15,12,16,2,11),构造一个哈夫曼树
2.设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度W
给定权3,4,5,6,7,8,9,试用算法构造一棵最优二叉树,画出这棵树并计算出它的权.(离散数学)
给定权值〔3,9,13,5,7〕,构造相应的哈夫曼树,并计算其大带权路径长度,求发图
数据结构问题:给定一组数据{6,2,7,10,3,12}以它构造一棵哈夫曼树,则树高为5,带权路径96,但是
32.对给定的数列R={7,16,4,8,20,9,6,18,5},构造一棵二叉排序树,并且 (1)给出按中序遍历得到
给定数据序列d={7,16,4,8,20,9,6,18,5},构造一棵二叉排列数,并求出该二叉排列树查找成功的平均查找长
给定一列分式,y/x^3,-y^2/x^5,y^3/x^7,-y^4/x^9,.(其中xy不等于0),试写出给定分式中第
给定数列1,2+3+4,5+6+7+8+9,10+11+12+13+14+15+16,……