#include??
#include?
#include
#include?
#define?MAXLEN?100?
typedef?struct?Huffmantree?{?
char?ch;?/*鍵值*/?
int?weightmarkhu;/*weight為權(quán)值mark為標(biāo)志域*/?
struct?Huffmantree?*parent*lchild*rchild*next;?
}Hftree*linktree;?
int?sum=0;?
float?k=0.0;
double?r?H=0.0;;
linktree?tidycharacter（char?character[]）?
{?
int?i=0;?
?
for（i=0;character[i]!=‘\0‘&&character[i]!=‘\n‘;i++）?{?/*遍歷直到字符串結(jié)束為止*/?
	sum++;}
?
linktree?treeptrbeforeptrnode;?/*鏈?zhǔn)?tree為頭結(jié)點(diǎn)beforeptr為ptr的前一結(jié)點(diǎn)node為新申請(qǐng)的結(jié)點(diǎn)*/?
tree=（linktree）malloc（sizeof（Hftree））;/*創(chuàng)建單鏈表的頭結(jié)點(diǎn)*/?
if（!tree）return?NULL;?
tree->next=NULL;?/*?頭結(jié)點(diǎn)為空且后續(xù)結(jié)點(diǎn)為空*/?
for（i=0;character[i]!=‘\0‘&&character[i]!=‘\n‘;i++）?{?/*遍歷直到字符串結(jié)束為止*/?
ptr=tree;?
beforeptr=tree;?
node=（linktree）malloc（sizeof（Hftree））;?/*新申請(qǐng)結(jié)點(diǎn)node*/?
if（!node）return?NULL;?
node->next=NULL;?
node->parent=NULL;?
node->lchild=NULL;?
node->rchild=NULL;?/*置空*/?
node->mark=0;?
node->ch=character[i];?
node->weight=1;
node->hu=0;?
if（tree->next==NULL）?
tree->next=node;?/*頭結(jié)點(diǎn)的下一結(jié)點(diǎn)為空連接node*/?
else?{?
ptr=tree->next;?
while（ptr&&ptr->ch!=node->ch）?{/*將指針移至鏈表尾*/?
ptr=ptr->next;?
beforeptr=beforeptr->next;?/*后移*/?
}?
if（ptr&&ptr->ch==node->ch）?{/*如果鏈表中某結(jié)點(diǎn)的字符與新結(jié)點(diǎn)的字符相同*/?
/*將該結(jié)點(diǎn)的權(quán)加一*/?
ptr->weight=ptr->weight+1;?
free（node）;?/*釋放node結(jié)點(diǎn)的存儲(chǔ)空間*/?
}?
else?{/*新結(jié)點(diǎn)與表中結(jié)點(diǎn)不相同將新結(jié)點(diǎn)插入鏈表后*/?
node->next=beforeptr->next;?
beforeptr->next=node;?/*node連接在beforeptr之后*/?
}?
}?
}?
return?tree;?
}?
linktree?taxisnode（linktree?tree）?/*將整理完的字符串按出現(xiàn)次數(shù)從小到大的順序排列?*/?
{?
linktree?headphptbeforeph;?/*head為新鏈表的表頭結(jié)點(diǎn)*/?
head=（linktree）malloc（sizeof（Hftree））;/*創(chuàng)建新鏈表的頭結(jié)點(diǎn)*/?
if（!head）return?NULL;?
head->next=NULL;?/*新結(jié)點(diǎn)的頭結(jié)點(diǎn)為空后續(xù)結(jié)點(diǎn)也為空*/?
ph=head;?
beforeph=head;?
while（tree->next）?{?
pt=tree->next;/*取被操作鏈表的首元結(jié)點(diǎn)*/?
tree->next=pt->next;?
pt->next=NULL;?/*取出pt所指向的結(jié)點(diǎn)*/?
ph=head->next;?
beforeph=head;?
if（head->next==NULL）?
head->next=pt;/*創(chuàng)建當(dāng)前操作鏈表首元結(jié)點(diǎn)*/?
else?{?
while（ph&&ph->weightweight）?{/*將被操作結(jié)點(diǎn)插入相應(yīng)位置*/?
ph=ph->next;?
beforeph=beforeph->next;?
}?
pt->next=beforeph->next;?
beforeph->next=pt;?
}?
}?
ph=head->next;
free（tree）;?

return?head;?
}??
linktree?createHftree（linktree?tree）?/*用排完序的字符串建立霍夫曼樹?*/
{?
linktree?pqnewnodebeforep;p=tree->next;?
while（p!=NULL）{
	??float?t=（float）p->weight/sum;
	??H=-（t*log（t）/log（2））+H;
??????printf（“w[%c]出現(xiàn)的概率為：%f\n“p->cht）;
	??p=p->next;
}?

for（p=tree->nextq=p->next;p!=NULL&&q!=NULL;p=tree->nextq=p->next）?{?
tree->next=q->next;?
q->next=NULL;?
p->next=NULL;?
newnode=（linktree）malloc（sizeof（Hftree））;/*申請(qǐng)新結(jié)點(diǎn)作為霍夫曼樹的中間結(jié)*/?
if（!newnode）return?NULL;?
newnode->next=NULL;?
newnode->mark=0;?
newnode->lchild=p;/*取鏈表頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)作為新結(jié)點(diǎn)的左、右兒子*/?
newnode->rchild=q;?
p->parent=newnode;?
q->parent=newnode;?
newnode->weight=p->weight+q->weight;?
p=tree->next;?
beforep=tree;?
if（p!=NULL&&p->weight>=newnode->weight）?{/*將新結(jié)點(diǎn)插入原鏈表的相應(yīng)位置*/?
newnode->next=beforep->next;?
beforep->next=newnode;?
}?
else?{?
while（p!=NULL&&p->weight