如何构造哈夫曼树编码（哈夫曼树和编码应用用C++实现）

本文目录

• 哈夫曼树和编码应用用C++实现
• 怎么样用c语言程序编码哈夫曼树

哈夫曼树和编码应用用C++实现

#include
《stdio.h》
#define
MAXBIT
10
/*定义哈夫曼编码的最大长度*/
#define
MAXVALUE
10000
/*定义最大权值*/
#define
MAXLEAF
30
/*定义哈夫曼树中最多叶子节点个数*/
#define
MAXNODE
MAXLEAF*2-1
/*哈夫曼树最多结点数*/
typedef
struct
{
/*哈夫曼编码信息的结构*/
int
bit;
int
start;}Hcodetype;
typedef
struct
{
/*哈夫曼树结点的结构*/
int
weight;
int
parent;
int
lchild;
int
rchild;
}Hnodetype;
void
huffmantree(Hnodetype
huffnode,int
n)
/*构造哈夫曼树的函数*/
{
int
i,j,m1,m2,x1,x2;
for(i=0;i《2*n-1;i++)
/*存放哈夫曼树结点的数组huffnode初始化*/
{
huffnode.weight=0;
huffnode.parent=-1;
huffnode.lchild=-1;
huffnode.rchild=-1;
}
for(i=0;i《n;i++)
/*输入入N个叶子节点的权值*/
{
printf("please
input
%d
character’s
weight\n",i);
scanf("%d",&huffnode.weight);
}
for(i=0;i《n-1;i++)
/*开始循环构造哈夫曼树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j《n+i;j++)
{
if(huffnode.parent==-1)
{
m2=m1;x2=x1;m1=huffnode.weight;x1=j;
}
else
if(huffnode.parent==-1)
{
m2=huffnode.weight;x2=j;
}
}
huffnode.parent=n+i;
huffnode.parent=n+i;
huffnode.weight;
huffnode.lchild=x1;
huffnode.rchild=x2;
}
}
void
main()
{
Hnodetype
huffnode;
Hcodetype
huffcode,cd;
int
i,j,c,p,n;
printf("please
input
n\n");
scanf("%d",&n);
/*输入叶子节点个数*/
huffmantree(huffnode,n);
/*建立哈夫曼树*/
for(i=0;i《n;i++)
/*该循环求每个叶子节点对应字符的哈夫曼编码*/
{
cd.start=n-1;c=i;
p=huffnode.parent;
while(p!=-1)
{
if(huffnode.lchild==c)
cd.bit=0;
else
cd.bit=1;
cd.start--;c=p;
p=huffnode.parent;
}
for(j=cd.start+1;j《n;j++)
/*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/
huffcode;
huffcode.start=cd.start;
}
for(i=0;i《n;i++)
/*输出每个叶子节点的哈夫曼编码*/
{
printf("%d
character
is:",i);
for(j=huffcode.start+1;j《n;j++)
printf("%d",huffcode);
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!=’\0’; i++)
{
if(ch==s)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.parent==0)
k=t.weight,flag=j;
t.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中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT.parent=i;
HT.rchild=s1;
HT.lchild=s2;
HT.weight;
// printf("HT.rchild:%d\n",i,s2,i,s1);
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量(不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd=’\0’; // 编码结束符
for(i=1; i《=n; i++)
{
// 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT.parent)
// 从叶子到根逆向求编码
if(HT.lchild==c)
cd=’1’;
else
cd=’0’;
HC=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC); // 从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);
}
return 0;
}