1. 哈夫曼编码的原理是什么
霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。
2. 霍夫曼编码
霍夫曼(Huffman)在1952年提出
是一种从下到上的编码方法，即从叶子逐步往上生成编码树
编码算法实际上是一个构造霍夫曼树的过程（根据资料出现频率的多寡来建造的树，霍夫曼树的树叶节点用以储存资料元素 ( Data Element ) ，若该元素出现的频率越高，则由该元素至树根所经过的节点数越少）
(1) 对资料中出现过的每一元素各自产生一外部节点，并赋予外部节点该元素之出现频率。
(2) 令 L 是所有外部节点所成之集合。
(3) 产生一个新节点 N 。令 N 为 L1 和 L2 的父节点，L1 和 L2 是 L 中出现频率最低的两个节点。令 N 节点的出现频率等于 L1 和 L2 的出现频率总和。由 L 中删除 L1 和 L2 ，并将 N 加入 L 中。
(4) 重复步骤 (3) 的动作，直到 | L | = 1 。
(5) 标示树中各节点的左子树链结为 0 ，右子树链结为 1 。（不一定，只要一枝为0一枝为1）
是码长可变的编码
霍夫曼算法和香农范诺算法的编码都不需要额外的同步码（解释）
霍夫曼树是最小二叉树，编码效率比香农范诺高
霍夫曼编码对错误敏感，错一位，可能导致后面的解码都是错误的，而且计算机也无法纠错，我们称为错误传播
霍夫曼编码是变长编码，整个编码结果是一个整体，无法随意解压缩其中的某一个部分
3. 赫夫曼树
注：第一题 huffman 树以及 huffman编码
我将第二题与第三题与用邻接矩阵存储图相关的操作放在了一起完成
第三题则是利用邻接表
1.第一题
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define LEN 8
#define MAXLEAF 6 // 最大叶子结点数目
#define MAXNODE (MAXLEAF*2)-1
typedef float ElemType;
typedef struct /* this structure stores the information of code */
{
int start; /* 存放编码的起始位置右至左（高位至低位）*/
int bit[LEN]; /* 存放 huffman编码 */
}HCode;
typedef HCode HuffCode[MAXLEAF];
typedef struct /* huffman tree结点的结构 */
{
int parent;
int LChild;
int RChild;
ElemType weight;
}HNode;
typedef HNode Huffman[MAXLEAF*2-1];
void createHuffmanTree(Huffman h,int leaves,ElemType *weight)
{
int i,j;
for(i=0;i<leaves*2-1;i++) /* 初始化huffman tree */
{
(h+i)->parent=-1;
(h+i)->LChild=-1;
(h+i)->RChild=-1;
(h+i)->weight=0;
}
for(i=0;i<leaves;i++) /* 给叶子赋权重 */
{
(h+i)->weight=*(weight+i);
}
/* 上一个循环叶子已经带权,下面这个循环用来生成新根
* 新根数量为n-1
*/
for(i=0;i<leaves-1;i++)
{
ElemType m1, m2;
int m1_pos, m2_pos;
m1=m2=65536; /* m1存放最小的权值m2存放次小的权值 */
m1_pos=m2_pos=0; /* m1存放最小的权值对应下标m2存放次小的权值对应下标*/
for(j=0;j<leaves+i;j++)
{
if((h+j)->weight<m1&&(h+j)->parent==-1)
{
m2=m1;
m1=(h+j)->weight;
m2_pos=m1_pos;
m1_pos=j;
}
else if((h+j)->weight<m2&&(h+j)->parent==-1)
{
m2=(h+j)->weight;
m2_pos=j;
}
}
(h+leaves+i)->parent=-1; // 生成新根，无双亲-1
(h+leaves+i)->LChild=m1_pos; // 新根左孩子在数组中的下标
(h+leaves+i)->RChild=m2_pos; // 新根右孩子在数组中的下标
(h+m1_pos)->parent=leaves+i; // 原根的父亲位置
(h+m2_pos)->parent=leaves+i; // 原根的父亲位置
(h+leaves+i)->weight=m2+m1;
}
}
void huffmancode(Huffman h,HuffCode code,int leaves)
{
int i,j,p,c;
HCode hf;
/*从叶子结点开始向上回溯 从而计算出huffman code */
for(i=0;i<leaves;i++)
{
c=i;
p=h[i].parent;
hf.start=LEN-1;
while(p!=-1)
{
if(h[p].LChild==c)
{
hf.bit[hf.start]=0;
}
else
{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
for(j=hf.start+1;j<LEN;j++)
{
code[i].bit[j]=hf.bit[j];
}
code[i].start=hf.start+1;
}
}
void printhuffmantree(Huffman h,int leaves)
{
int i;
for(i=0;i<leaves*2-1;i++)
{
printf("weight=%-3.2f",h[i].weight);
printf("parent=%-3d",h[i].parent);
printf("LChild=%-3d",h[i].LChild);
printf("RChild=%-3d\n",h[i].RChild);
}
}
void printhuffcode(HuffCode hcode,char characters[])
{
int i,j;
for(i=0;i<strlen(characters);i++)
{
printf("%c的huffman编码:",characters[i]);
for(j=hcode[i].start;j<LEN;j++)
{
printf("%d",hcode[i].bit[j]);
}
printf("\n");
}
}
int main(void)
{
Huffman h;
HuffCode hcode;
char characters[]={"abcdef"}; /* 待编码的字符 */
ElemType weights[]={0.3,0.7,0.4,0.5,0.9,0.1}; /* 字符出现的频率 */
createHuffmanTree(h,strlen(characters),weights);
printhuffmantree(h,strlen(characters));
huffmancode(h,hcode,sizeof(characters));
printhuffcode(hcode,characters);
system("pause");
return 0;
}
2.第二题 代码如下，以及使用说明
例如有如下的图
a->b
/ \
|
c
首先输入顶点与弧的数目
3 2
提示输入顶点
abc
输入弧（弧头弧尾）
ab
ca
那些插入以及删除的操作已经放入主函数
顾回车后可以看到进行相关操作后图的变化
#include<stdio.h>
#include<stdlib.h>
#define MAXVERT 10 // 需要在图中进行插入操作所以设定一个最大值
#define INFINITE 32767
#define ERROR -1
#define FALSE 0
#define OK 1
typedef int ElemType;
enum maritype{DG,UDG,DN,UDN};
typedef struct
{
char vertex[MAXVERT];
ElemType arc[MAXVERT][MAXVERT];
int ArcNum;
int VertexNum;
}adjacentMatrix;
int locate(adjacentMatrix *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->VertexNum;i++)
{
if(G->vertex[i]==v)
{
k=i;
break;
}
}
return(k);
}
void init(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
G->arc[i][j]=0;
}
}
}
void createDN(adjacentMatrix *G)
{
int i,j,k;
char v1,v2,blank;
printf("请输入顶点与弧的数目 \n");
scanf("%d%d",&G->VertexNum,&G->ArcNum);
init(G);
printf("请输入顶点（用字母表示）:\n");
getchar();
for(i=0;i<G->VertexNum;i++)
{
scanf("%c",&G->vertex[i]);
}
getchar();
for(i=0;i<G->ArcNum;i++)
{
printf("请输入弧%d的弧头与弧尾",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
G->arc[j][k]=1;
}
}
int InsertVex(adjacentMatrix *G,char v) /* insert vertex */
{
int i;
if(G->VertexNum>MAXVERT-1)
{
return(FALSE);
}
G->vertex[G->VertexNum++]=v;
for(i=0;i<G->VertexNum;i++)
{
G->arc[i][G->VertexNum-1]=G->arc[G->VertexNum-1][i]=0;
}
return(OK);
}
int InsertAar(adjacentMatrix *G,char v,char w) //插入边
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(FALSE);
}
G->arc[i][j]=1;
return(OK);
}
int DeleteVex(adjacentMatrix *G,char v) //（删除顶点）
{
int i, k;
k=locate(G,v);
if(k==-1)
{
printf("The vertex has not found\n");
return(FALSE);
}
for(i=k;i<G->VertexNum;i++)
{
G->vertex[i]=G->vertex[i+1];
}
--G->VertexNum;
return(OK);
}
int DeleteArc(adjacentMatrix *G,char v,char w)
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(ERROR);
}
G->arc[i][j]=0;
return(OK);
}
void degree(adjacentMatrix *G)
{
int i, j, odsum, idsum, zero=0;
for(i=0;i<G->VertexNum;i++)
{
odsum=0;
idsum=0;
for(j=0;j<G->VertexNum;j++)
{
odsum+=G->arc[i][j];
idsum+=G->arc[j][i];
}
if(!odsum)
{
++zero;
}
printf("顶点 %c 的出度与入度是",G->vertex[i]);
printf("%3d%3d\n",odsum,idsum);
}
printf("度为0的顶点 %d\n",zero);
}
void print(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
printf("%8c",G->vertex[i]);
}
printf("\n");
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
if(!j)
{
printf("%c",G->vertex[i]);
}
printf("%8d",G->arc[i][j]);
}
printf("\n");
}
}
int main(void)
{
int k;
char v, w;
adjacentMatrix G;
createDN(&G);
print(&G); // 邻接矩阵打印
degree(&G); // 求所有顶点出度入度 及度为0的点
InsertVex(&G,'f'); // 插入顶点f
InsertAar(&G,'f','c'); // 插入边 fc
degree(&G); // 观察插入边顶点后度的变化
print(&G); // 邻接矩阵打印
DeleteArc(&G,'f','c'); // 删除边 fc
print(&G); // 邻接矩阵打印 观察变化
DeleteVex(&G,'a'); // 删除顶点a
print(&G); // 邻接矩阵打印 观察删除顶点a后变化
system("pause");
return(0);
}
3.使用同上 示例图也如上所画 使用方式也基本一直
按你的要求只输出 顶点的出度入度以及度为0的顶点
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR -1
#define FALSE 0
#define OK 1
typedef char VertexType;
typedef struct ArcNode // 边表的结构
{
int adjvex; // 与顶点相邻接的顶点在表头结点表（图中）的位置
struct ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode // 表头结点表的结构
{
VertexType data;
ArcNode *firstarc;
}VertexNode;
typedef struct // 存放图信息的结构
{
int vexnum, arcnum; // 顶点与弧的数目
VertexNode vertex[MAX_VERTEX_NUM];
}Adjlist;
int locate(Adjlist *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->vexnum;i++)
{
if(G->vertex[i].data==v)
{
k=i;
break;
}
}
return(k);
}
void createDG(Adjlist *G)
{
int i, j, k;
char v1, v2;
ArcNode *s;
printf("输入顶点与弧的数目 \n");
scanf("%d%d",&G->vexnum,&G->arcnum);
getchar();
printf("请输入顶点（用字母表示）:");
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
scanf("%c",&G->vertex[i].data);
G->vertex[i].firstarc=NULL;
}
getchar();
for(i=0;i<G->arcnum;i++)
{
printf("请输入第%d条边的信息 弧尾与弧头:",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=k;
s->nextarc=G->vertex[j].firstarc;
G->vertex[j].firstarc=s;
}
}
void od(Adjlist *G)
{
int odsum, i;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
odsum=0;
p=G->vertex[i].firstarc;
while(p)
{
++odsum;
p=p->nextarc;
}
printf("\n%c的出度是:%d\n ",G->vertex[i].data,odsum);
}
}
void ind(Adjlist *G)
{
int insum, i, j, k;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
insum=0;
for(j=0;j<G->vexnum;j++)
{
if(i==j)
{
continue;
}
p=G->vertex[j].firstarc;
while(p)
{
if(p->adjvex==i)
{
++insum;
}
p=p->nextarc;
}
}
printf("\n%c的入度是:%d\n ",G->vertex[i].data,insum);
}
}
int main(void)
{
Adjlist G;
int i;
createDG(&G);
od(&G);
ind(&G);
system("pause");
return(0);
}
4. 怎样将建立好的哈夫曼树保存在文件中
哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/union{char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/};struct tree *right; /*树的右结点*/};struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/};例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb 或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为 1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符 0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为 0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。
5. 哈夫曼树及哈夫曼编码的C程序实现(数据结构题)
去年做的课程设计，有什么不合要求的自己改改
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}
6. 什么是哈夫曼树呢
夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。