第1个回答 2006-05-23
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1~kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中,常为树中的结点赋上一有意义的实数,该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
第2个回答 2006-05-17
基本术语
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1~kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中,常为树中的结点赋上一有意义的实数,该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
树的带权路径长度为树中所有叶子结点的带权路径长度之和,记为WPL= ∑ wili
i=1
哈夫曼树
哈夫曼(Huffman)树又称最优二叉树,它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树
构造算法如下:
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点,其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树,且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵,同时把新树加入F中
(4) 重复第(2)和第(3)步,直到F中只含有一棵为止,此树便为哈夫曼树
哈夫曼编码
等长编码缺点:使传送电文总长度很长
不等长编码缺点:译码的二义性或多义性
前缀编码:对某一字符集进行不等长编码时,任一字符编码都不是其它字符编码的前缀
哈夫曼编码:由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例:在一电文中,六个字符A,B,C,D,E,F的出现频率依次为4,2,6,8,3,2,如图(a)
由此构造的哈夫曼编码树如图(b)所示
A、B、C、D、E、F的哈夫曼编码依次为:00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61
参考资料:http://202.119.2.197/webcourses/sjjg/content/cha5/06_2.htm
第3个回答 2006-05-19
既然这么急,就说是用什么语言啊,C/C++、Basic...
还有,英文词典里的单词统计前,是读带单词表的文件,还是自定义初始化赋值就可以了呢!
你说要用C,我用的是Turbo C 2 编译的,怎么不是C++呢,我可是从百忙中啊!
其中假设英语词典以单词表形式保存在C:\word.txt中,且每一行一个单词。
代码如下:
-----------------------------------------------------------
/*
HuffmanCode BY TC 2
Author: ejau
Ver 1.00
Data:19/05/2006
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
typedef struct {
float weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);
void main()
{
HuffmanTree T=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n=26;
printf("Default Input n = %d\n",n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
float *kt=(float *)malloc((n+1)*sizeof(float *));
kt[0]=0;
for(i=0;i<=n;i++)
w[i] = 0;
char * count;
FILE * file1;
char filen[30] = "C:\\word.txt";
if((file1 = fopen(filen,"r"))==NULL)
{
printf("File Read Error!\n");
exit(0);
}
while(fscanf(file1,"%s",count)!=EOF)
{
int temp;
if(countofpoint[0]>='a'&&count[0]<='z')
temp = (int)count[0]-96;
if(countofpoint[0]>='A'&&count[0]<='Z')
temp = (int)count[0]-64;
w[temp]++;
}
fclose(file1);
int tatolnum=0;
for(i=0;i<=n;i++)
tatolnum=tatolnum+w[i];
for(i=1;i<=n;i++)
kt[i]=(float *)w[i]/tatolnum;
HC=HuffmanCoding(HT,HC,kt,n);
printf("HuffmanCode:\n");
printf("Letter\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%c\t\t%f\t\t%s\n",i+64,kt[i],HC[i]);
}
void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,float *kt,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,kt++)
{
p->weight=*kt;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
printf("HT List:\n");
printf("Letter\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%c\t\t%f\t\t%d\t\t%d\t\t%d\n",i+64,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}
MinCode Select(HuffmanTree HT,unsigned int n)
{
float min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
第4个回答 2006-05-18
基本术语
路径和路径长度
若在一棵树中存在一个结点序列k1,k2,…kj ,使得ki是ki+1的双亲(1≤i≤j),则称此结点序列是从k1到kj的路径。从k1~kj所经过的分支数称为这两结点间的路径长度。
结点的权和带权路径长度
在许多应用中,常为树中的结点赋上一有意义的实数,该实数称为结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度
n
树的带权路径长度为树中所有叶子结点的带权路径长度之和,记为WPL= ∑ wili
i=1
哈夫曼树
哈夫曼(Huffman)树又称最优二叉树,它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
构造哈夫曼树
构造算法如下:
(1) 根据与n个权值{w1,w2…wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2…Tn},其中第i棵二叉树Ti(1 ≤ i ≤ n)都只有一个权值为wi的根结点,其左、右子树均为空
(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树,且置新树的根结点的权值为其左、右子树上根结点权值之和
(3) 从F中删除构成新树的那两棵,同时把新树加入F中
(4) 重复第(2)和第(3)步,直到F中只含有一棵为止,此树便为哈夫曼树
哈夫曼编码
等长编码缺点:使传送电文总长度很长
不等长编码缺点:译码的二义性或多义性
前缀编码:对某一字符集进行不等长编码时,任一字符编码都不是其它字符编码的前缀
哈夫曼编码:由编码哈夫曼树所得到的字符编码(由编码哈夫曼树所得到的字符编码)
例:在一电文中,六个字符A,B,C,D,E,F的出现频率依次为4,2,6,8,3,2,如图(a)
由此构造的哈夫曼编码树如图(b)所示
A、B、C、D、E、F的哈夫曼编码依次为:00、1010、01、11、100、1011
电文的最短传送长度L=WPL=4×2+2×4+6×2+8×2+3×3+2×4=61