欢迎各界计算机爱好者加入,弘扬极客精神!

请提供下数据结构哈夫曼编码的思路?

0 喜欢 0 不喜欢
如题
问题关闭原因: 回答过多
最新提问 12月 2, 2016 分类:C# | 用户: Zard (4,402 分)  
已关闭 12月 18, 2016 用户:Megan

13 个回答

0 喜欢 0 不喜欢
思路具体的很难讲,你可以参考数据结构书上面哈夫曼编码那一节的东西,

其实就是根据题目求出编码参数,然后进行传送和译码
最新回答 12月 2, 2016 用户: charles (3,678 分)  
0 喜欢 0 不喜欢
当初我做这个实验用的是书上147页上的算法思想,这个已经给你了部分代码实现,你只需要读懂然后加上

一些它未完成的功能就行了。
最新回答 12月 3, 2016 用户: 黑lol (2,090 分)  
0 喜欢 0 不喜欢
1 喜欢 0 不喜欢
最新回答 12月 5, 2016 用户: harryho97 (4,518 分)  
0 喜欢 0 不喜欢
#include <stdio.h>
#include <string.h>
#define N 50  /*叶子结点数*/
#define M 2*N-1  /*树中结点总数*/
typedef struct
{
 char data[5]; /*结点值*/
 int weight;  /*权重*/
 int parent;  /*双亲结点*/
 int lchild;  /*左孩子结点*/
 int rchild;  /*右孩子结点*/
} HTNode;
typedef struct
{
 char cd[N];  /*存放哈夫曼码*/
 int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
 int i,k,lnode,rnode;
 int min1,min2;
 for (i=0;i<2*n-1;i++)   /*所有结点的相关域置初值-1*/
  ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
 for (i=n;i<2*n-1;i++)   /*构造哈夫曼树*/
 {
  min1=min2=32767;   /*lnode和rnode为最小权重的两个结点位置*/
  lnode=rnode=-1;
  for (k=0;k<=i-1;k++)
   if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/
   {
    if (ht[k].weight<min1)
    {
     min2=min1;rnode=lnode;
     min1=ht[k].weight;lnode=k;
    }
    else if (ht[k].weight<min2)
    {
     min2=ht[k].weight;rnode=k;
    }
   }
  ht[lnode].parent=i;ht[rnode].parent=i;
  ht[i].weight=ht[lnode].weight+ht[rnode].weight;
  ht[i].lchild=lnode;ht[i].rchild=rnode;
 }
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
 int i,f,c;
 HCode hc;
 for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/
 {
  hc.start=n;c=i;
  f=ht[i].parent;
  while (f!=-1) /*循序直到树根结点*/
  {
   if (ht[f].lchild==c) /*处理左孩子结点*/
    hc.cd[hc.start--]='0';
   else     /*处理右孩子结点*/
    hc.cd[hc.start--]='1';
   c=f;f=ht[f].parent;
  }
  hc.start++;  /*start指向哈夫曼编码最开始字符*/
  hcd[i]=hc;
 }
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
 int i,k;
 int sum=0,m=0,j;
 printf("  输出哈夫曼编码:\n"); /*输出哈夫曼编码*/
 for (i=0;i<n;i++)
 {
  j=0;
  printf("      %s:\t",ht[i].data);
  for (k=hcd[i].start;k<=n;k++)
  {
   printf("%c",hcd[i].cd[k]);
   j++;
  }
  m+=ht[i].weight;
  sum+=ht[i].weight*j;
  printf("\n");
 }
 printf("\n  平均长度=%g\n",1.0*sum/m);
}
void main()
{
 int n=15,i;
 char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
 int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
 HTNode ht[M];
 HCode hcd[N];
 for (i=0;i<n;i++)
 {
  strcpy(ht[i].data,str[i]);
  ht[i].weight=fnum[i];
 }
 printf("\n");
 CreateHT(ht,n);
 CreateHCode(ht,hcd,n);
 DispHCode(ht,hcd,n);
 printf("\n");
}
最新回答 12月 6, 2016 用户: big and small (5,556 分)  
0 喜欢 0 不喜欢
最新回答 12月 6, 2016 用户: Re (3,574 分)  
0 喜欢 0 不喜欢
0 喜欢 0 不喜欢
0 喜欢 0 不喜欢

首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点 的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度 为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln) N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径 长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。 

数据结构的树那章节中一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,下面就具体介绍编码步骤和具体的一些用法。

哈夫曼编码步骤: 

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步,直到集合F中只有一棵二叉树为止。 

简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取12构成新树,其结点为1+2=3

第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树

依次建立哈夫曼树

所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010 

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

 

最新回答 12月 7, 2016 用户: weini520aou (2,080 分)  
5 喜欢 0 不喜欢
最新回答 12月 12, 2016 用户: SFGFDG (8,034 分)  
...