㈠ void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
很简单了 typedef struct{ /*哈夫曼树的存储表示方法*/ float weight; /* 权重，即概率 */ int parent,lchild,rchild; /*每个结点均有父结点，左孩子，右孩子*/ }HTNode,*HuffmanTree; typedef char **HuffmanCode; /*双重指针存储哈夫曼编码*/ /*哈夫曼编码的算法*/ void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) HuffmanTree &HT //这是一棵哈夫曼树，它是一个已经定义的结构体，此处是引用，不能传值，当然也可以写作HuffmanTree *HT HuffmanCode &HC //存储哈夫曼编码，可以写作HuffmanCode *HC /*开始构造一棵哈夫曼树*/ HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HC=(HuffmanCode)malloc(n*sizeof(char *)); /*存储所有概率的编码*/ - 程序实例 #include #include #include #include #define NULL 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAX_NUM 10000 #define MAX 60 typedef int Status; typedef char **HuffmanCode; typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef struct{ HuffmanTree HT; char *c; int longth; HuffmanCode HC; }Huffman; void Select(HuffmanTree HT,int end,int *s1,int *s2) { int i; int min1=MAX_NUM; int min2; for (i=1;i<=end;i++) { if (HT[i].parent==0&&HT[i].weightHT[i].weight) { *s2=i; min2=HT[i].weight; } } } Huffman HuffmanCoding(Huffman Hfm) { /*---------------------------------*/ int i,n,m,s1,s2,start; int c,f; char *cd; n=Hfm.longth; if(n<=1) return Hfm; m=2*n-1; for(i=n+1;i<=m;++i) { Select(Hfm.HT,i-1,&s1,&s2); Hfm.HT[s1].parent=i; Hfm.HT[s2].parent=i; Hfm.HT[i].lchild=s1; Hfm.HT[i].rchild=s2; Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight; } /*--
㈡ 哈夫曼树HT存储结构的初态和末态怎么写
定义哈夫曼树与编码的存储结构与数据类型
typedef struct
{
char data;//节点值
int weight; //权重
int parent; //双亲节点
int lchild; //左孩子节点
int rchild; //右孩子节点
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼码
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //创建哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根据哈夫曼树计算每个元素的哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n) //输出每个元素的哈夫曼编码
㈢ 哈夫曼树
这是我们的作业题，自己写 的……（可能输入的格式跟你要的不一致，自己改一下）
如果有什么不懂的就问我，我可以把其中所有相关的文件发给你 ^^
注：1、 初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、 用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、 文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、 打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、 打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
注：
input.txt文件中保存一下数据：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}
㈣ Huffman编码，存储结构的终结状态是什么意思怎么来的
哈夫曼树 在一般的数据结构的书中，树的那章后面，着者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
㈤ 简述哈夫曼树的性质。
哈 夫 曼 树
2.9 二叉树的应用
2.9.1 哈夫曼树及应用
哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。
结点之间的路径长度：从一个结点到另一个结点之间的分支数目。
树的路径长度：从树的根到树中每一个结点的路径长度之和。
结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：
WPL为最小的二叉树就称作最优二叉树或哈夫曼树。
完全二叉树不一定是最优二叉树。
哈夫曼树的构造：
（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。
例1：
例2：
结点的存储结构:
构造哈夫曼树的算法说明：
#define n /* 叶子总数 */
#define m 2*n-1 /* 结点总数 */
证：由性质3，叶子结点数 n0=n2+1，故哈夫曼树结点总数为 n0+n2=n0+(n0-1)=2*n0-1
例3 在解某些判定问题时，利用哈夫曼树获得最佳判定算法。
（a)
WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15
（b)(c)
WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2
哈夫曼编码
从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
例，对电文 EMCAD 编码。若等长编码，则
EMCAD => 000001010011100 共15位
设各字母的使用频度为 {E,M,C,A,D}={1,2,3,3,4}。用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，树枝分配代码“0”或“1”:
各字母的编码即为哈夫曼编码： EMCAD => 000001011011 共12位
2.9.2 二叉排序树
二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常被称为树表。可以作为一种排序和检索的手段。
定义 二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。
对二叉排序树，若按中序遍历就可以得到由小到大的有序序列。如上图，中序遍历得：
{2，3，4，8，9，9，10，13，15，18}
二叉排序树的生成
对任意一组数据元素序列{R1,R2,...,Rn}，要生成一棵二叉排序树的过程为：
（1）令R1为二叉树的根；
（2）若R2<R1，令R2为R1左子树的根结点，否则R2为R1右子树的根结点；
（3）对R3,...,Rn结点的插入方法同上。
例，数据元素序列{10，18，3，8，12，2，7，3}，其生成二叉排序树的过程如下：
二叉排序树中结点的删除
要求删除一个结点后的二叉树仍是一棵二叉排序树。算法思想，分以下几种情况考虑：
（1）被删除的结点是叶子结点，则只需修改其双亲结点的指针既可；
（2）被删除结点p只有左子树pL或右子树pR，此时只要使左子树pL或右子树pR成为p双亲结点q的左子树或右子树即可。
（3）若被删除结点p的左、右子树均非空，有两种做法：
*
令pL直接链接到q的左（或右）孩子链域上，pR链接到p结点中序前趋结点s上（s是pL最右下的结点）；
*
以p结点的直接中序前趋或后继替代p所指结点，然后再从原二叉排序树中删去该直接前趋或后继。
㈥ 大神们！！ 帮我把哈夫曼树的代码 添加以下注释吧！！！！ 先谢啦！！！ 急。。。
#include<iostream>
using namespace std;
struct htnode //哈夫曼树结点结构定义
{
char ch; //结点值
int weight; //结点权值
int parent; //父结点下标
int lchild,rchild; //左、右孩子结点下标
};
class huffmantree //哈夫曼树类定义
{
public:
void code(char str1[],int w[],int n); //编码
void uncode(char str1[],char str2[],int n); //解码
private:
htnode ht[3000]; //用数组存储哈夫曼树
void creathuffmantree(char str1[],int w[],int n); // 创建哈夫曼树
void select(int pos,int &r1,int &r2);
};
//在数组ht中从0到pos位置，查找未加入哈夫曼树的权值最小的两个数的位置r1,r2
//r1为权值最小的位置，r2为权值第二小的位置
void huffmantree::select(int pos,int &r1,int &r2)
{
r1=r2=0; //初始化为0位置
for(int i=1;i<=pos;i++)
{
if(ht[i].parent!=0) //父结点不等于0，表示已加入哈夫曼树
continue; //继续向前查找
if(r1==0) //把r1设置为1
r1=i;
else if(r2==0) //把r2设置为2
r2=i;
//从i等于3开始比较。我认为这里程序有问题，无法得到权最小的两位置，你自己再改改
else if(ht[i].weight<ht[r1].weight) //如小于r1的权则设置r1为i
r1=i;
else if(ht[i].weight<ht[r2].weight) //如大于r1的权，再和r2的权比较
r2=i;
}
}
// 创建哈夫曼树，str1[]为结点值数组，w[]为权值数组，共n个结点
void huffmantree::creathuffmantree(char str1[],int w[],int n)
{
int pos;
//把结点值和权值复制到数组ht
for(pos=1;pos<=n;pos++) //注意没有使用ht数组位置为0的空间
{
ht[pos].weight=w[pos-1]; //结点权值
ht[pos].ch=str1[pos-1]; //结点值
ht[pos].parent=ht[pos].lchild=ht[pos].rchild=0; //父结点为0表示未加入哈夫曼树，左右孩子都为0表示叶子结点
}
//这是构造哈夫曼树的过程，即设置数组ht的其他结点
for(pos=n+1;pos<=2*n-1;pos++) //注意用n个数值构造的哈夫曼树有2*n-1个结点
{
int r1,r2;
select(pos-1,r1,r2);
ht[r1].parent=ht[r2].parent=pos; //把r1，r2结点加入哈夫曼树，并设置他们的父结点位置为pos
ht[pos].lchild=r1; //设置pos结点的左孩子为r1
ht[pos].rchild=r2; //设置pos结点的右孩子为r2
ht[pos].weight=ht[r1].weight+ht[r2].weight; //设置pos结点的权值为左右孩子权值的和
ht[pos].parent=0; //其父结点为0
}
}
//求哈夫曼编码
void huffmantree::code(char str1[],int w[],int n)
{
creathuffmantree(str1,w,n); //建立哈夫曼树
int start,c,i,f,j;
char *cd;
cd=new char[n]; //用于保存哈夫曼编码
cd[n-1]='\0'; //设置字符串结束符
for(i=1;i<=n;i++) //分别输出n个结点的哈夫曼编码
{
start=n-1; //注意从cd数组的末尾向前加入编码
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[c].parent) //从叶子结点往上走到根结点为止
{
//左0，右1
if(ht[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
cout<<"结点"<<str1[i-1]<<"的编码为："<<endl;
for(j=start;j<n;j++) //输出所有叶子结点
cout<<cd[j];
cout<<endl;
}
delete []cd; //撤销
}
//翻译哈夫曼编码,str1[]为结点值,str2[]为哈夫曼编码，共n个结点
//输出哈夫曼编码为str2的结点值
void huffmantree::uncode(char str1[],char str2[],int n)
{
int i,f;
char c;
for(i=0;i<strlen(str2);) //从根结点往下走到叶子结点
{
//根结点在数组ht最后一个位置
//从上往下也是左0右1
for(f=2*n-1;ht[f].lchild!=0&&ht[f].rchild!=0;)
{
c=str2[i];
if(c=='1') //等于1往右走
{
f=ht[f].rchild;
i++;
}
else //等于0往左走
{
f=ht[f].lchild;
i++;
}
}
cout<<ht[f].ch; //输出找到的叶子结点
}
cout<<endl;
}
//这个不用注释了吧
int main()
{
char str[27],str2[3000],c;
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int cd[27],s,len,i,w[27];
sb1:
cout<<"请输入要编码的字符串"<<endl;
cin>>str;
huffmantree obj;
s=0;
memset(cd,0,sizeof(cd));
len=strlen(str);
for(i=0;i<len;i++)
{
cd[str[i]-'a']++;
}
for(i=0;i<26;i++)
{
if(cd[i])
{
str[s]=ch[i];
w[s]=cd[i];
s++;
}
}
cout<<"各节点编码如下："<<endl;
obj.code(str,w,s);
sb2:
cout<<"请输入要解码的01串"<<endl;
cin>>str2;
cout<<"解码结果如下："<<endl;
obj.uncode(str,str2,s);
cout<<"是否继续解码?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb2;
cout<<"是否继续编码?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb1;
return 0;
}
㈦ 哈夫曼树的构造是什么
哈夫曼树构造：结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
历史
1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。
导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Rendancy Codes）中发表了这个编码方法。