数据结构C语言版哈夫曼树
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define n 5//叶子数目
#define m (2*n-1)//结点总数
#define maxval 10000
#define maxsize 100//哈夫曼编码的最大位数
typedef char TElemtype;
typedef int status;
typedef struct hufmtree
{
float weight;
int parent,lchild,rchild;
char ch;//字符
}hufmtree;
typedef struct codetype
{
char bits;//位串
int start;//编码在位串中的开始位置
char ch;//字符
}codetype;
void huffman(hufmtree tree[]);//建立哈夫曼树
void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码
void decode(hufmtree tree[]);//依次读入电文，根据哈夫曼树译码
int main()
{
printf("哈夫曼编码:\n");
hufmtree tree;
codetype code;
int i,j;//循环变量
huffman(tree);//建立哈夫曼树
huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
for(i=0;i<n;i++)
{
for(j=code.start;j<n;j++)
{
printf("\n");
printf("读入电文，并进行译码\n");
decode(tree);//依次读入电文，根据哈夫曼树译码
}
}
}
void huffman(hufmtree tree[])//建立哈夫曼树
{
int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
float small1,small2,f;
char c;
for(i=0;i<m;i++)//初始化
{
tree.parent=0;
tree.lchild=-1;
tree.rchild=-1;
tree.weight=0.0;
}
printf("依次读入前%d个结点的字符及权值(中间用空格隔开)\n",n);
for(i=0;i<n;i++)//读入前n个结点的字符及权值
{
printf("输入第%d个字符和权值:\n",i+1);
scanf("%c %f",&c,&f);
getchar();
tree.ch=c;
tree.weight=f;
}
for(i=n;i<m;i++)//进行n-1次合并，产生n-1个新结点
{
p1=0;p2=0;
small1=maxval;small2=maxval;//maxval是float类型的最大值
for(j=0;j<i;j++) //选出两个权值最小的根结点
if(tree.parent==0)
if(tree.weight<small1)
{
small2=small1;//改变最小权、次小权及对应的位置
small1=tree.weight;
p2=p1;
p1=j;
}
else
if(tree.weight<small2)
{
small2=tree.weight;//改变次小权及位置
p2=j;
}
tree.parent=i;
tree.parent=i;
tree.lchild=p1;//最小权根结点是新结点的左孩子
tree.rchild=p2;//次小权根结点是新结点的右孩子
tree.weight=tree.weight+tree.weight;
}
}
void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
{
int i,c,p;
codetype cd;//缓冲变量
for(i=0;i<n;i++)
{
cd.start=n;
cd.ch=tree.ch;
c=i;//从叶结点出发向上回溯
p=tree.parent;//tree是tree的双亲
while(p!=0)
{
cd.start--;
if(tree.lchild==c)
cd.bits='0'; //tree是左子树，生成代码'0'
else
cd.bits='1'; //tree是右子树，生成代码'1'
c=p;
p=tree.parent;
}
code=cd;//第i+1个字符的编码存入code
}
}
void decode(hufmtree tree[])//依次读入电文，根据哈夫曼树译码
{
int i,j=0;
char b;
char endflag='2';//电文结束标志取2
i=m-1;//从根结点开始往下搜索
printf("输入发送的编码(以'2'为结束标志)：");
gets(b);
printf("译码后的字符为");
while(b!='2')
{
if(b=='0')
i=tree.lchild;//走向左孩子
else
i=tree.rchild;//走向右孩子
if(tree.lchild==-1)//tree是叶结点
{
printf("%c",tree.ch);
i=m-1; //回到根结点
}
j++;
}
printf("\n");
if(tree.lchild!=-1&&b!='2')//电文读完，但尚未到叶子结点
printf("ERROR\n");//输入电文有错
}
页:
[1]