霍夫曼编码及香农编码课程设计

霍夫曼编码及香农编码：信源编码主要可分为无失真信源编码和限失真信源编码。无失真信源编码主要适用于离散信源或数字信号，如文本、表格及工程图纸等信源，它们要求进行无失真地数据压缩，要求完全能够无失真地可逆恢复。凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码，为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，是的平均码字长度最短，能得到最佳的编码方法主要有：香农，费诺，霍夫曼编码等，实现至少两种无失真信源编码（香农码，哈夫曼码、费诺码）及其编码效率。

#include  
#include 
#include
#include 
#define MAXLEN 100 
typedef struct Huffmantree { 
char ch; /*键值*/ 
int weightmarkhu;/*weight为权值mark为标志域*/ 
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++） { /*遍历直到字符串结束为止*/ 
	sum++;}
 
linktree treeptrbeforeptrnode; /*链式 tree为头结点beforeptr为ptr的前一结点node为新申请的结点*/ 
tree=（linktree）malloc（sizeof（Hftree））;/*创建单链表的头结点*/ 
if（!tree）return NULL; 
tree->next=NULL; /* 头结点为空且后续结点为空*/ 
for（i=0;character[i]!=‘\0‘&&character[i]!=‘\n‘;i++） { /*遍历直到字符串结束为止*/ 
ptr=tree; 
beforeptr=tree; 
node=（linktree）malloc（sizeof（Hftree））; /*新申请结点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; /*头结点的下一结点为空连接node*/ 
else { 
ptr=tree->next; 
while（ptr&&ptr->ch!=node->ch） {/*将指针移至链表尾*/ 
ptr=ptr->next; 
beforeptr=beforeptr->next; /*后移*/ 
} 
if（ptr&&ptr->ch==node->ch） {/*如果链表中某结点的字符与新结点的字符相同*/ 
/*将该结点的权加一*/ 
ptr->weight=ptr->weight+1; 
free（node）; /*释放node结点的存储空间*/ 
} 
else {/*新结点与表中结点不相同将新结点插入链表后*/ 
node->next=beforeptr->next; 
beforeptr->next=node; /*node连接在beforeptr之后*/ 
} 
} 
} 
return tree; 
} 
linktree taxisnode（linktree tree） /*将整理完的字符串按出现次数从小到大的顺序排列 */ 
{ 
linktree headphptbeforeph; /*head为新链表的表头结点*/ 
head=（linktree）malloc（sizeof（Hftree））;/*创建新链表的头结点*/ 
if（!head）return NULL; 
head->next=NULL; /*新结点的头结点为空后续结点也为空*/ 
ph=head; 
beforeph=head; 
while（tree->next） { 
pt=tree->next;/*取被操作链表的首元结点*/ 
tree->next=pt->next; 
pt->next=NULL; /*取出pt所指向的结点*/ 
ph=head->next; 
beforeph=head; 
if（head->next==NULL） 
head->next=pt;/*创建当前操作链表首元结点*/ 
else { 
while（ph&&ph->weightweight） {/*将被操作结点插入相应位置*/ 
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]出现的概率为：%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））;/*申请新结点作为霍夫曼树的中间结*/ 
if（!newnode）return NULL; 
newnode->next=NULL; 
newnode->mark=0; 
newnode->lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/ 
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） {/*将新结点插入原链表的相应位置*/ 
newnode->next=beforep->next; 
beforep->next=newnode; 
} 
else { 
while（p!=NULL&&p->weight


 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        2881  2011-07-06 09:29  sd.cpp
     文件      199680  2011-07-04 16:22  信息论课程设计.doc
     文件        6696  2011-07-04 16:12  jia.cpp