#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define LEN sizeof(HFtree) /*HFtree结构体大小*/
/*哈夫曼树结构体*/
typedef struct tagHFtree
{
char data; /*结点数据,以后用到*/
double weight; /*结点的权重*/
struct tagHFtree* parent; /*双亲结点*/
struct tagHFtree* lchild; /*左孩子*/
struct tagHFtree* rchild; /*右孩子*/
struct tagHFtree* next; /*指向下一个结点*/
}HFtree;
/*哈夫曼编码结构体*/
struct tagHFcode
{
char data; /*结点数据*/
double weight; /*结点的权重*/
int code[20]; /*存放编码*/
int top; /*编码的位数*/
};
/***********************************************
创建哈夫曼树核心部分
************************************************/
void Create(HFtree**head)
{
HFtree*lp,*temp,*lchild,*rchild;
while((*head)->next->next!=NULL)
{
lchild=rchild=(*head); /*每次从头开始查，这里(*head)的weight没用，*/
/*刚好用来放左右孩子*/
temp=(*head)->next; /*最初的的weight*/
lchild->weight=rchild->weight=3.14e+38; /*重新时每次将左右孩子的weight置为最大*/
lp=(HFtree*)malloc(LEN);
lp->parent=NULL;
while(temp!=NULL) /*查最小的作为左孩子*/
{
if(lchild->weight > temp->weight)
{
lchild=temp;
}
temp=temp->next;
}
temp=(*head)->next; /*重新定位到(*head)->next*/
while(temp!=NULL) /*查次小的作为右孩子*/
{ /*注意这里不要用temp->weight!=lchild->weigh*/
if(rchild->weight > temp->weight && temp!=lchild)
{
rchild=temp;
}
temp=temp->next;
}
lp->lchild=lchild; /*对LP及其左右孩子附值*/
lp->rchild=rchild;
lchild->parent = rchild->parent =lp;
lp->weight=lchild->weight + rchild->weight; /*将左右孩子的权值相加*/
lp->next=(*head)->next; /*将LP插到表头*/
(*head)->next=lp; /*每次让(*head)->next指向新加进来的结点*/
temp=lp; /*将lp和temp两个指针重新定位，用来遍历链表*/
lp=lp->next;
while(lp!=NULL) /*将左右孩子从待创建的链表系列中删除*/
{
if(lp==lchild || lp==rchild)
{
temp->next=lp->next;
lp->next=NULL;
}
else
temp=lp;
lp=temp->next;
}
}
}
/***********************************************
创建哈夫曼树
************************************************/
void CreateHFtree(double nodewei[],int n,HFtree**head)
{
int i=0;
HFtree*lp=(HFtree*)malloc(LEN),*rear;
(*head)=(HFtree*)malloc(LEN);
(*head)->parent=NULL;
(*head)->next=rear=lp; /*head头结点，保证指向剩余的结点链*/
lp->parent=lp->lchild=lp->rchild=lp->next=NULL;
while(iweight=nodewei[i++];
rear->next=lp; /*第一次REAR指向自身*/
rear=lp;
lp=(HFtree*)malloc(LEN);
lp->parent=lp->lchild=lp->rchild=lp->next=NULL;
}
free(lp); /*释放最后一个结点*/
Create(head); /*创建一棵树，树的头结点为(*HEAD)->next*/
}
/*************************************************
由先序遍历求出哈夫曼树求出哈夫曼编码
**************************************************/
void HFcoding(HFtree*root,HFtree*temp,struct tagHFcode HFcode[],int*leaftop)
{
if(root!=NULL)
{
if(root->lchild==NULL && root->rchild==NULL) /*是叶子结点，求得编码*/
{
temp=root;
HFcode[(*leaftop)].top=0;
HFcode[(*leaftop)].weight=root->weight;
sizeof结构体大小 HFcode[(*leaftop)].data=root->data;
while(temp->parent!=NULL)
{
if(temp->parent->lchild==temp)
HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=0;
else
HFcode[(*leaftop)].code[HFcode[(*leaftop)].top]=1;
HFcode[(*leaftop)].top++;
temp=temp->parent;
}
(*leaftop)++;
}
HFcoding(root->lchild,temp,HFcode,leaftop);
HFcoding(root->rchild,temp,HFcode,leaftop);
}
}
/***********************************************
输出求得的哈夫曼编码
************************************************/
void OutCoding(struct tagHFcode HFcode[],int leaftop)
{
int i=0,j=0; for(;i<leaftop;i++) { printf("%.1f :",HFcode[i].weight); j=HFcode[i].top-1; while(j>=0 ) { printf("%d",HFcode[i].code[j]); j--; } printf("\n"); }
}
/********************************************
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论