哈夫曼树c语言
‘壹’ 数据结构 c语言版 哈弗曼树 实验
#include<iostream>
#include<iomanip>
#include<string>
#include<windows.h>
usingnamespacestd;
typedefstruct{//定义哈夫曼树个结点
intweight;//权值
intparent,lchild,rchild;//双亲，左右孩子结点下标
chardata;//储存相关的字符信息
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼编码树
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表
voidstatistics(char*a,int*w,char*d,int&n)//统计字符
{
intj=0;
intk;
for(inti=0;i<100&&a[i]!=' ';i++){
for(k=0;k<j;k++){
if(a[i]==d[k])
{ w[k]++;
break;
}
}
if(k==j){
d[j]=a[i];
w[j]++;
j++;}
}
n=j;
d[j]=' ';
}
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn,char*d)//w存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
{if(n<=1)return;
intm=2*n-1;//m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以储存一个大小为2n-1的一维数组中
HT=newHTNode[m+1];
HuffmanTreep;
inti;
for(p=HT+1,i=1;i<=n;i++,++p)//初始化哈夫曼树
{ p->data=d[i-1];
p->lchild=p->parent=p->rchild=0;
p->weight=w[i-1]; }
for(;i<=m;++i,++p) {
p->lchild=p->parent=p->rchild=0;
p->weight=0; }
for(i=n+1;i<=m;++i){//建立哈夫曼树
ints1,s2,u,t;
for(u=1;u<=i-1;u++)if(HT[u].parent==0){s1=u;break;}
for(u=u+1;u<=i-1;u++) {
if(HT[s1].weight>HT[u].weight&&HT[u].parent==0)
s1=u; }
for(t=1;t<=i-1;t++)
if(HT[t].parent==0&&t!=s1){s2=t;break;}
for(t=t+1;t<=i-1;t++)
{ if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1)
s2=t; }
HT[s1].parent=i;HT[s2].parent=i;//parent为0且weight最小的的两个结点，一个为s1,一个为s2
HT[i].lchild=s1;HT[i].rchild=s2;//左孩子权值小，右孩子权值大
HT[i].weight=HT[s1].weight+HT[s2].weight; }
HC=newchar*[n+1]; //分配n个字符编码指针
char*cd=newchar[n];//分配编码的工作空间
cd[n-1]=' ';//编码结束符
intstart,c,f;
for(i=1;i<=n;++i){//逐个字符求哈夫曼编码
start=n-1; //编码在数组cd[]的最前位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到树根逆向求哈夫曼编码
if(HT[f].lchild==c)cd[--start]='0';//判断是左孩子还是右孩子（左为0右为1）
elsecd[--start]='1';
HC[i]=newchar[n-start];//为第i个字符分配空间
strcpy(HC[i],&cd[start]); }//讲cd[]数组的start位置到n-1位置复制给HC[i]
delete(cd);}//释放空间
voidmain()
{
chara[100];
chard[100];charbc[1000];
intw[100],n=0;
HuffmanTreeHT;
HuffmanCodeHC;
cout<<"请输入字符： ";
cin>>a;
for(intak=0;ak<100;ak++)w[ak]=0;
statistics(a,w,d,n);//统计
HuffmanCoding(HT,HC,w,n,d);
cout<<"霍夫曼编码为："<<endl;
cout<<"原码"<<"权值"<<"二进制码"<<endl;
system("pause");
}
请采纳，谢谢
‘贰’ 数据结构中哈夫曼树的应用（C语言）
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;
struct worder
{
char words; /*字符*/
}word[100];
struct weighted
{
int weighter; /*转换权值有利于文件的存储*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉树*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子树*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子树*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}
void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼树*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*将每个权值赋值给二维数组a[][],利用这个二维数组可以进行建立二叉树*/
a[i+1][2]=haffTree[n+i].weight;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*对已经建立好的哈夫曼树进行编码*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}
void PrintBiTree(BiTreeNode *bt ,int n) /*将哈夫曼树转换成的二叉树进行打印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}
int search(int a[][3],int m) /*查找和a[][2]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失败返回数字0 查找成功返回和a[][2]相等的数的行数 i*/
else return i;
}
int searcher(int a[][3],int m) /*查找和a[][1]相等的权值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失败返回数字0 查找成功返回和a[][1]相等的数的行数 i*/
i++;
if(i==m) return 0;
else return i;
}
void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼树*/（利用递归）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]为左子树*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]为右子树*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等则只要进行一个的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}
void code(Code myHaffCode[],int n ) /*编码*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存储编码的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*读取存储字符的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*输出每个权值的编码*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字符找到对应的编码*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*输出相应的编码*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}
fclose(fp2);
}
void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存储权值个数的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存储字符的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存储权值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;
printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}
void menu() /*界面*/
{
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*编码*/
printf("\t\t\t2. Decoding:\n\n"); /*译码*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*打印哈夫曼树*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}
void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;
HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;
case 5:exit(0);
}
}
}
getch();
}
‘叁’ C语言 编写哈弗曼树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 10000
typedef struct {
unsigned int weight;
unsigned int lchild,rchild,parent;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
//找到权值最小的两个结点
void select(HuffmanTree HT,int k,int &s1,int &s2)
{
int j;
s1=s2=k;
for(j=0;j<k;j++)
if(HT[j].parent==0)
{
if(HT[j].weight<HT[s1].weight)
{
s2=s1;
s1=j;
}
else if(HT[j].weight<HT[s2].weight)
s2=j;
}
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int *w,int n)
{
int m,i,s1,s2;
HuffmanTree p;
m=2*n-1;
HT=(HuffmanTree)malloc(m*sizeof(HTNode));
for(p=HT,i=0;i<n;i++,p++,w++)
{
p->lchild=p->parent=p->rchild=0;
p->weight=*w;
}
for(i=n;i<m;i++,p++)
p->lchild=p->parent=p->rchild=p->weight=0;
for(i=n;i<m;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void print(HuffmanTree HT,char *u,int n)
{
int i;
char a;
printf("No\tchar\tweight\tlchild\trchild\tparent\n");
for(i=0;i<2*n-1;i++)
{
if(i<n)
a=u[i];
else a='-';
printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,a,HT[i].weight,HT[i].lchild,HT[i].rchild,HT[i].parent);
}
}
//编码哈夫曼树
void Huffmancoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
int i,c,start;
int f;
char *cd;
HC=(HuffmanCode)malloc(n*sizeof(char *));
cd=(char *)malloc((n-1)*sizeof(char));
cd[n-1]='\0';
for(i=0;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]);
}
}
//编码
void code(HuffmanCode HC,char *u,char *v)
{
int i,j;
for(i=0;i<strlen(v);i++)
for(j=0;j<strlen(u);j++)
if(v[i]==u[j])
{
printf("%s",HC[j]);
break;
}
}
//译码
void recode(HuffmanCode HC,int n,char *u,char *v)
{
int i,j,k;
char *p;
i=0;
p=v;
while(i<strlen(v))
{
for(j=0;j<n;j++)
{
char temp[M]={0};
strncpy(temp,p,strlen(HC[j]));
if(strcmp(temp,HC[j])==0)
{
printf("%c",u[j]);
break;
}
}
p+=strlen(HC[j]);
i+=strlen(HC[j]);
}
}
main ()
{
HuffmanTree HT;
HuffmanCode HC;
int n,i;
int *w;
char *u,*v;
u=(char *)malloc(M*sizeof(char));
v=(char *)malloc(M*sizeof(char));
w=(int *)malloc(M*sizeof(int));
printf("请输入字符数:");
scanf("%d",&n);
printf("请输入字符:\n");
scanf("%s",u);
printf("请输入对应的权值:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
CreateHuffmanTree(HT,w,n);
Huffmancoding(HT,HC,n);
printf("各字符对应的编码:\n");
for(i=0;i<n;i++)
printf("%c: %s ",u[i],HC[i]);
printf("\n");
printf("输出哈夫曼树:\n");
print(HT,u,n);
free(w);
//编码
printf("待发送信息:\n");
scanf("%s",v);
printf("编码:\n");
code(HC,u,v);
//译码
printf("\n接收到的编码:\n");
scanf("%s",v);
printf("原文:\n");
recode(HC,n,u,v);
printf("\n");
}
‘肆’ 怎么样用c语言程序编码哈夫曼树
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
// algo6-1.cpp 求赫夫曼编码。实现算法6.12的程序
int min(HuffmanTree t,int i)
{
// 函数void select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值
for(j=1; j<=i; j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{
// s1为最小的两个值中序号小的那个
s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1; i<=n; ++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(; i<=m; ++i,++p)
(*p).parent=0;
for(i=n+1; i<=m; ++i) // 建赫夫曼树
{
// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);
}
return 0;
}
‘伍’ 创建一个哈夫曼树并且进行编码权重如下w={5，29，7 8，14，13 ，3 ，11}写出c语言代码
#include"stdafx.h"
#include"hfm.h"
#include<string.h>
#include<malloc.h>//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#defineTRUE1
#defineFALSE1
#defineOK1
#defineERROR1
#defineINFEASIBLE-1
typedefintStatus;
typedefintBoolean；
/************************************************************************/
/*最优二叉树简称：哈夫曼树*/
/************************************************************************/
//哈夫曼树结构
;typedefstruct{
unsignedintweight;//权重
unsignedintparent,lchild,rchild;//树的双亲节点，和左右孩子
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
//返回i个节点中权值最小的树的根节点的序号，供select()调用
intMin(HuffmanTreeT,inti){
intj,flag;
unsignedintk=UINT_MAX;//%d-->UINT_MAX=-1,%u--->非常大的数
for(j=1;j<=i;j++)
if(T[j].weight<k&&T[j].parent==0)
k=T[j].weight,flag=j;//
T[flag].parent=1;//将parent标志为1避免二次查找
returnflag;//返回
}
voidSelect(HuffmanTreeT,inti,int&s1,int&s2){
//在i个节点中选取2个权值最小的树的根节点序号，s1为序号较小的那个
intj;
s1=Min(T,i);
s2=Min(T,i);
if(s1>s2){
j=s1;
s1=s2;
s2=j;
}
}
//HuffmanCode代表的树解码二进制值
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
intm,i,s1,s2,start;
unsignedc,f;
char*cd;
//分配存储空间
HuffmanTreep;
if(n<=1)
return;
//n个字符(叶子节点)有2n-1个树节点，所以树节点m
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号元素未用
//这一步是给哈夫曼树的叶子节点初始化
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//这一步是给哈夫曼树的非叶子节点初始化
for(;i<=m;++i,++p){
(*p).parent=0;
}
/************************************************************************/
/*做完准备工作后，开始建立哈夫曼树
/************************************************************************/
for(i=n+1;i<=m;i++)
{
//在HT[1~i-1]中选择parent=0且weigh最小的节点，其序号分别为s1,s2
Select(HT,i-1,s1,s2);//传引用
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/************************************************************************/
/*从叶子到根逆求每个叶子节点的哈夫曼编码*/
/************************************************************************/
//分配n个字符编码的头指针向量，（[0]不用）
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]=' ';//结束符
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));//生成一个块内存存储字符
//为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd赋值字符串到cd
}
free(cd);//释放资源
}
//函数声明
intMin(HuffmanTreeT,inti);//求i个节点中的最小权重的序列号，并返回
voidSelect(HuffmanTreeT,inti,int&s1,int&s2);//从两个最小权重中选取最小的(左边)给s1，右边的给s2
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//哈夫曼编码与解码
intmain(){
HuffmanTreeHT;
HuffmanCodeHC;
int*w,n,i;
printf("请输入权值的个数(>1):");
scanf_s("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整形): ",n);
for(i=0;i<=n-1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT,HC,w,n);
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
return0;
}
‘陆’ 求助，哈夫曼树的C语言编程问题万分
根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
for (i = 0; i < n; i++) //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
int k1 = -1, k2;
for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵
{
if (b[j] != NULL && k1 == -1)
{
k1 = j;
continue;
}
if (b[j] != NULL)
{
k2 = j;
break;
}
}
for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小
{
if (b[j] != NULL)
{
if (b[j]->data < b[k1]->data)
{
k2 = k1;
k1 = j;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q = malloc(sizeof(struct BTreeNode));
q->data = b[k1]->data + b[k2]->data;
q->left = b[k1];
q->right = b[k2];
b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置
b[k2] = NULL;//k2位置为空
}
free(b); //删除动态建立的数组b
return q; //返回整个哈夫曼树的树根指针
}
‘柒’ 有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗
在一般的数据结构的书中，树的那章后面，着者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如
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中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
C语言代码实现：
/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解码部分)
* 在 Win-TC 下测试通过
* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
* 父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 结点结构体 */
/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //实际值，可根据情况替换为字母
} /* end for */
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d:
", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */
/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
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;
printf ("x1.weight and x2.weight in round %d: %d, %d
", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
printf ("
");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
} /* end HuffmanTree */
//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n:
");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
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; /* 设置下一循环条件 */
} /* end while */
/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);
printf ("
");
}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?Please Enter code:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}
‘捌’ 用C语言编写Huffman树
//huffmantree and huffmancode
#include <stdio.h>
#include <malloc.h>
#define MAX 10
typedef struct huffmanTreeNode{
int weight;
int parent,left,right;
}htNode;
void select(htNode *ht,int n,int *s1,int *s2){
int i=0;
*s1=*s2=-1;
while(i<n){
if(ht[i].parent!=-1){i++;continue;}
else{
if(ht[i].weight<ht[*s1].weight||*s1==-1){
*s2=*s1;
*s1=i;
}
else if(ht[i].weight<ht[*s2].weight||*s2==-1)
*s2=i;
i++;
}
}
}
bool createHtree(htNode *ht,int n){
int i=n,m=2*n-1,s1,s2;
for(;i<m;i++){
select(ht,n++,&s1,&s2);
if(s1==-1||s2==-1) return true;
ht[i].left=s1; ht[i].right=s2;
ht[s1].parent=i; ht[s2].parent=i;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
return true;
}
void printfData(htNode *ht,int m){
int i=0;
printf("location\tparent\tleft\tright\tweight\n");
while(i<m){
printf("%d\t\t%d\t%d\t%d\t%d\n",i,ht[i].parent,ht[i].left,ht[i].right,ht[i].weight);
i++;
}
}
void initHtree(htNode *ht,int n){
int m=2*n-1,i=0;
printf("Please input the weight of node:");
for(;i<n;i++){
scanf("%d",&(ht[i].weight));
getchar();
ht[i].left=-1;
ht[i].right=-1;
ht[i].parent=-1;
}
for(i=n;i<m;i++){
ht[i].left=-1;
ht[i].right=-1;
ht[i].parent=-1;
ht[i].weight=-1;
}
}
void huffmanCode(htNode *ht,int n){
// char *hc=(char *)malloc(n*sizeof(char *));
char *temp=(char *)malloc(n*sizeof(char));
char **code=(char **)malloc(n*sizeof(char));
int i=0,j=0,start=n,parent,t;
for(i=0;i<n;i++)
code[i]=(char *)malloc(n*sizeof(char));
for(i=0;i<n;i++){
start=n;
parent=ht[i].parent; t=i;
while(parent!=-1){
temp[--start]=(ht[parent].left==t?'0':'1');
t=parent;
parent=ht[parent].parent;
}
for(j=0;start<n;j++,start++){
code[i][j]=temp[start];
}
code[i][j]='\0';
}
free(temp);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(code[i][j]=='\0') break;
else printf("%c",code[i][j]);
}
printf("\t");
}
printf("\n");
}
int main(void){
htNode *ht;
int n,m,i=0;
printf("Please input the number of node:");
scanf("%d",&n); getchar();
m=2*n-1;
ht=(htNode *)malloc(m*sizeof(htNode));
initHtree(ht,n);
createHtree(ht,n);
printfData(ht,m);
printf("\nThe code of huffmanCode is:");
huffmanCode(ht,n);
return 0;
}
哥以前做的