内容:

从键盘接收一串电文字符，输出对应的Huffman(哈夫曼）编码，

同时，能翻译由Huffman编码生成的代码串，输出对应的电文字符串。

设计要求：

  (1).构造一棵Huffman树;

  (2).实现Huffman编码，并用Huffman编码生成的代码串进行译码；

  (3).程序中字符和权值是可变的，实现程序的灵活性。

步骤：

1. 算法分析

本设计使用结构体数组存储Huffman树。

程序中设计了两个函数：

函数HuffmanTree()用来构造一个Huffman树；

函数HuffmanCode()用来生成Huffman编码并输出。

在电报通信中，电文是以二进制代码传送的。在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接受时，要将收到的二进制代码串转化为对应的字符序列，即译码。由于字符集中的字符被使用的频率是非均匀的，在传送电文时，要想将电文总长尽可能短。因此，若对某字符集进行不等长编码的设计，则要求任意一个字符的编码都不是其他字符编码的前缀，这种编码称作前缀编码。由Huffman树求得的编码是最优前缀码，也叫Huffman编码。给出字符集和各个字符的概率分布，构造Huffman树，将Huffman树中每个分支结点的左分支标为0，右分支标为1，将根到每个叶子路径上的标号连起来，就是该叶子所代表字符的编码。

程序中主函数根据提示输入一些字符和字符的权值，则程序输出哈夫曼编码；若输入电文，则可以输出哈夫曼译码。

1. 构造Huffman树的算法

主程序中输入不同字符，统计不同字符出现的次数作为该字符的权值，存于data[]数组中。假设有n种字符，则有n个叶子结点，构造的哈夫曼树有2n-1个结点。具体步骤如下：

1. 将n个字符（叶结点）和其权值存储在HuffNode数组的前n个数组元素中，将2n-1个结点的双亲和左右孩子均置-1.
2. 在所有结点中，选择双亲为-1，并选择具有最小和次小权值的结点m1和m2，用x1和x2指示这两个结点在数组中的位置，将根为HuffNode[x1]和HuffNode[x2]的两棵树合并，使其成为新结点HuffNode[n+i]的左右孩子，其权值为m1+m2.
3. 重复上述过程，共进行n-1次合并就构造了一棵Huffman树。产生的n-1个结点依次放在数组HuffNode[]的n~2n-2的单元中。

2.Huffman编码和译码算法

讯享网

1. 从Huffman树的叶子结点HuffNode[i](0<=i<n)出发，通过HuffNode [c].parent找到其双亲，通过lchild和rchild域可知HuffNode[c]是左分支还是右分支，若是左分支则bit[n-1-i]=0;否则bit[n-1-i]=1.
2. 将HuffNode[c]作为出发点，重复上述过程，直到找到树根所在位置，即进行了Huffman编码。
3. 译码时首先输入二进制代码串，放在数组code中，以回车结束输入。
4. 将代码与编码表进行比较，如果为0，则转向左子树；如果为1，则转向右子树，直到叶结点结束。输出叶子结点的数据域，即所对应的字符。

1. 概要设计

使用C语言，其中设置了以下函数

 程序运行流程图如下：

（1）构造哈夫曼树的程序运行流程图：

 （2）Huffman编码程序运行流程图：

 （3）哈夫曼译码程序运行流程图：

 测试样例：

输入字符为：abbcddd

输出结果为：

 源码如下：

#include<stdio.h> #include<conio.h> #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2-1 #define MAXBIT 50 #define NULL 0 typedef struct node { char letter; int weight; int parent; int lchild; int rchild; } HNodeType; typedef struct { char letter; int bit[MAXBIT]; int start; } HCodeType; typedef struct { char s; int num; } Message; //哈夫曼树的构造算法 void HuffmanTree(HNodeType HuffNode[],int n,Message a[]) { int i,j,m1,m2,x1,x2,temp1; char temp2; for(i=0; i<2*n-1; i++) { //HuffNode[]初始化 HuffNode[i].letter=NULL; HuffNode[i].weight=0; HuffNode[i].parent=-1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for(i=0; i<n-1; i++) for(j=i+1; j<n-1; j++) if(a[j].num>a[i].num) { temp1=a[i].num; a[i].num=a[j].num; a[j].num=temp1; temp2=a[i].s; a[i].s=a[j].s; a[j].s=temp2; } for(i=0; i<n; i++) { HuffNode[i].weight=a[i].num; HuffNode[i].letter=a[i].s; } for(i=0; i<n-1; i++) { //构造哈夫曼树 m1=m2=MAXVALUE; x1=x2=0; for(j=0; j<n+i; j++) { //找出的两棵权值最小的子树 if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) { m2=m1; x2=x1; m1=HuffNode[j].weight; x1=j; } else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) { m2=HuffNode[j].weight; x2=j; } } //将找出的两棵子树合并为一棵子树 HuffNode[x1].parent=n+i; HuffNode[x2].parent=n+i; HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2; } } //生成哈夫曼编码 void HuffmanCode(int n,Message a[]) { HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF],cd; int i,j,c,p; char code[30],*m; HuffmanTree(HuffNode,n,a);//建立哈夫曼树 for(i=0; i<n; i++) { //求每个叶子结点的哈夫曼编码 cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) { //由叶结点向上直到树根 if(HuffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HuffNode[c].parent; } for(j=cd.start+1; j<n; j++) //保存求出的每个叶结点的哈夫曼编码和编码的起始位 HuffCode[i].bit[j]=cd.bit[j] ; HuffCode[i].start=cd.start; } printf("输出每个叶子的哈夫曼编码：\n"); for(i=0; i<n; i++) { //输出每个叶子结点的哈夫曼编码 HuffCode[i].letter=HuffNode[i].letter; printf("%c",HuffCode[i].letter); for(j=HuffCode[i].start+1; j<n; j++) printf("%d",HuffCode[i].bit[j]); printf("\n"); } printf("请输入电文（1/0）：\n"); for(i=0; i<30; i++)code[i]=NULL; scanf("%s",&code); m=code; c=2*n-2; printf("输出哈夫曼译码：\n"); while(*m!=NULL) { if(*m=='0') { c=i=HuffNode[c].lchild; if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) { printf("%c",HuffNode[i].letter); c=2*n-2; } } if(*m=='1') { c=i=HuffNode[c].rchild; if(HuffNode[c].lchild==-1&&HuffNode[c].rchild==-1) { printf("%c",HuffNode[i].letter); c=2*n-2; } } m++; } printf("\n"); } int main() { Message data[30]; char s[100],*p; int i,count=0; printf("\n 请输入一些字符："); scanf("%s",&s); for(i=0; i<30; i++) { data[i].s=NULL; data[i].num=0; } p=s; while(*p) { for(i=0; i<=count+1; i++) { if(data[i].s==NULL) { data[i].s=*p; data[i].num++; count++; break; } else if(data[i].s==*p) { data[i].num++; break; } } p++; } printf("\n"); printf("不同的字符数：%d\n",count); for(i=0; i<count; i++) { printf("%c",data[i].s); printf("权值：%d",data[i].num); printf("\n"); } HuffmanCode(count,data); getch(); }