新建文本文档.txt

哈夫曼编码器

#include<stdio.h> 
#include<malloc.h> 
#define maxsize 20 
typedef struct 
{ 
char date,yima[20]; 
int l,r,next,quan; 
}lian,*zhizhen;//备用链表的节点 

typedef struct 
{ 
char zifu;//存储输入的字符 
int zhixiang;//字符对应在li里面的位置 
}jie;//用来存放输入字符的节点 


//队 
typedef struct xhxb 
{ 
zhizhen xhx; 
struct xhxb *next; 
}elem,*zhizhend;//队所用的链表的节点 
typedef struct 
{ 
zhizhend base; 
int size;//队列的当前长度 
}dui;//队的标志（只有一个节点） 
int xunhuan(zhizhend &head,int l)//创建一个循环链表，head为循环链表的头指针（可以看作），l为循环链表的长度 
{ 
zhizhend p,q; 
int i=1; 
head=(zhizhend)malloc(sizeof(elem)); 
if(head==0)return 0; 
p=q=head; 
while(i<l) 
{ 
q=(zhizhend)malloc(sizeof(elem)); 
p->next=q; 
p=q; 
i++; 
} 
p->next=head; 
return 1; 
} 
int chuangjian(dui &d)//创建一个空队 
{ 
int a; 
a=xunhuan(d.base,maxsize); 
if(a==0)return 0; 
d.size=0; 
return 1; 
} 
int chazhao(dui &d,zhizhend &p)//找到队列的头结点，用p返回其地址值 
{ 
int i=1; 
if(d.size==0)return 0; 
p=d.base; 
while(i<=maxsize-d.size+1)/////// 
{ 
p=p->next; 
i++; 
} 
return 1; 
} 
int jindui(dui &d,zhizhen e)//进队 
{ 
if(d.size>=maxsize)return 0; 
d.base=d.base->next; 
d.base->xhx=e; 
d.size++; 
return 1; 
} 
int chudui(dui &d,zhizhen &e)//出队，用e返回出队元素的值  
{ 
int a; 
zhizhend p; 
a=chazhao(d,p); 
if(a==0)return 0; 
e=p->xhx; 
d.size--; 
return 1; 
} 
//队完 






int beiyong(zhizhen &li,zhizhen &s)//创建一个备用静态链表 li返回其首地址 并创建一个已用空链表 用s返回其首地址 
{ 
int i; 
li=(zhizhen)malloc(256*sizeof(lian)); 
if(!li)return 0; 
for(i=0;i<255;i++) 
{ 
(li+i)->next=i+1; 
(li+i)->l=0; 
(li+i)->r=0; 
(li+i)->quan=0;///////////////////////// 
} 
    (li+255)->next=0; 
s=li+1; 
li->next=s->next; 
s->next=0; 
return 1; 
} 
int jmalloc(zhizhen &li,zhizhen &s)//从备用链表中取一个结点放入已用链表s中 
{ 
int p,q; 
p=s->next; 
s->next=li->next; 
q=(li+li->next)->next; 
(s+s->next-1)->next=p; 
li->next=q; 
return 1; 
} 
int min(int &i,int &j,zhizhen s)//找到链表s中权值最小的两个结点 
{ 
int p; 
i=s->next; 
j=(s+s->next-1)->next; 
p=(s+j-1)->next; 
while(p) 
{ 
if((s+p-1)->quan<(s+i-1)->quan||(s+p-1)->quan<(s+j-1)->quan) 
{ 
if((s+p-1)->quan>(s+i-1)->quan)j=p; 
else 
{ 
if((s+p-1)->quan>(s+j-1)->quan)i=p; 
else 
{ 
if((s+i-1)->quan>(s+j-1)->quan)i=p; 
else j=p; 
} 
} 
} 
p=(s+p-1)->next; 
} 
return 1; 
} 
int jfree(int i,int j,zhizhen &s)//从s中把i，j结点剔除 
{ 
int p=1; 
while(p) 
{ 
if((s+p-1)->next==i)(s+p-1)->next=(s+i-1)->next; 
p=(s+p-1)->next; 
} 
p=1; 
while(p) 
{ 
if((s+p-1)->next==j)(s+p-1)->next=(s+j-1)->next; 
p=(s+p-1)->next; 
} 
return 1; 
} 
int hafuman(zhizhen &s,zhizhen &li)//创建一棵霍夫曼树 
{ 
int i,j; 
while((s+s->next-1)->next) 
{ 
min(i,j,s); 
jmalloc(li,s); 
(s+s->next-1)->l=i; 
*((s+i-1)->yima)='0'; 
*((s+i-1)->yima+1)='\0'; 
        (s+s->next-1)->r=j; 
*((s+j-1)->yima)='1'; 
        *((s+j-1)->yima+1)='\0'; 
(s+s->next-1)->quan=((s+i-1)->quan+(s+j-1)->quan);