#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h>
#define Maxsize 50
/**************************************/
typedef struct Huff{
int w;
char data;
struct Huff *lchild, *rchild, *parent;
}Huff;
/**************************************/
typedef struct Link{
Huff *Loc;
struct Link *next;
}Link;
/**************************************/
typedef struct{
char *base;
char *top;
}Stack;
/**************************************/
void Create_Huff_Tree(Link *);
Link *Create_Link(void);
Link *Malloc_Link_Node(char , int);
Link *Find(char , Link *);
void Insert(Link *, Link *);
void Choose(Link *);
void EnCode(Link *);
void Codeing(char *, Stack *, Link *);
void DeCode(Link *);
void TransCode(char *, Huff *);
Stack *Initit_Stack(void);
void push(char, Stack *);
char pop(Stack *);
/**********************************************/
void main(void)
{
Link *head;
head=Create_Link();
Create_Huff_Tree(head);
Choose(head);
return;
}
/***********************************************/
Link *Create_Link(void)
{
Link *s, *L;
char *c ,data, flag;
int w;
L=Malloc_Link_Node('0',0);
c=(char *)malloc(2*sizeof(char));
printf("依次输入在赫夫曼树出现的字符，和相对应的权值:\n\n");
while(1){
while(1){
printf("字符:\t");
scanf("%s",c);
data=(*c);
s=Find(data,L);
if(s!=0){
printf("该字符已经存在，是否覆盖(Y/N)?\n");
flag=getch();
if('y'==flag || 'Y'==flag){
printf("权值:\t");
scanf("%d",&w);
s->Loc->w=w;
}
else
break;
}////
else{
printf("权值:\t");
scanf("%d",&w);
s=Malloc_Link_Node(data,w);
Insert(s,L);
}
break;
}//while
printf("1--继续\t2--完成\n");
flag=getch();
if('1'==flag)
continue;
else
break;
}//while
free(c);
return(L);
}
/*********************************************************/
Link *Malloc_Link_Node(char data, int w)
{
Link *p;
p=(Link *)malloc(sizeof(Link));
p->next=0;
p->Loc=(Huff *)malloc(sizeof(Huff));
p->Loc->data=data;
p->Loc->w=w;
p->Loc->lchild=0;
p->Loc->rchild=0;
p->Loc->parent=0;
return(p);
}
/********************************************************/
Link *Find(char c, Link *L)
{
while(L=L->next,L!=0)
if(c==L->Loc->data)
return(L);
return(0);
}
/********************************************************/
void Insert(Link *s, Link *L)
{
Link *p, *q;
int w;
w=s->Loc->w;
p=L;
while(q=p,p=p->next,p!=0)
if(w<p->Loc->w)
break;
s->next=p;
q->next=s;
return;
}
/*********************************************************/
void Create_Huff_Tree(Link *L)
{
Link *p, *q,*s;
int flag, w1,w2;
if(L->next->next==0){
L->Loc=L->next->Loc;
L->Loc->parent=L->Loc;
return;
}
p=L;
flag=0;
while(q=p->next,p=q->next,1){
if(p->next==0)
flag=1;
w1=p->Loc->w;
w2=q->Loc->w;
s=Malloc_Link_Node('0',w1+w2);
if(w1<=w2){
s->Loc->lchild=p->Loc;
s->Loc->rchild=q->Loc;
}
else{
s->Loc->lchild=q->Loc;
s->Loc->rchild=p->Loc;
}
p->Loc->parent=s->Loc;
q->Loc->parent=s->Loc;
Insert(s,p);
if(flag==1)
break;
}//while
L->Loc=p->next->Loc;
return;
}
/***********************************************************************/
void Choose(Link *L)
{
char ch;
system("cls");
while(1){
printf(" 1--编码\n");
printf(" 2--译码\n");
printf(" 0--返回\n\n");
ch=getch();
if(ch=='1')
EnCode(L);
if(ch=='2')
DeCode(L);
if(ch!='1' && ch!='2')
return;
}//while
}
/***************************************************/
void EnCode(Link *L)
{
char *c;
Stack *S;
S=Initit_Stack();
c=(char *)malloc(Maxsize*sizeof(char));
printf("源码:\t");
scanf("%s",c);
printf("译码:\t");
Codeing(c,S,L);
free(c);
free(S->base);
free(S);
getch();
system("cls");
return;
}
/***************************************************/
void Codeing(char *c, Stack *S, Link *L)
{
Huff *p, *q;
Link *T;
T=Find(*c,L);
if(T==0 || *c=='0'){
printf("%3c字符不在编码范围.\n",*c);
return;
}
p=T->Loc;
while(q=p,p=p->parent,1){
if(p->lchild!=0 && p->lchild==q)
push('0',S);
else
push('1',S);
if(p==L->Loc)
break;
}
while(S->base!=S->top)
printf("%c",pop(S));
printf(" ");
c++;
if(*c=='\0')
return;
else
Codeing(c,S,L);
}
/***************************************************/
void DeCode(Link *L)
{
char *s;
Huff *T;
T=L->Loc;
s=(char *)malloc(Maxsize*sizeof(char));
printf("译码:\t");
scanf("%s",s);
printf("源码:\t");
TransCode(s,T);
getch();
system("cls");
free(s);
return;
}
/****************************************************/
void TransCode(char *s, Huff *T)
{
Huff *p;
p=T;
while(p->lchild!=0 && *s!='\0'){
if(*s=='0')
p=p->lchild;
if(*s=='1')
p=p->rchild;
s++;
}//while
if(p->lchild!=0){
printf("\t存在错误的译码段.\n");
return;
}
printf("%c",p->data);
if(*s=='\0'){
printf("\n");
return;
}
else
TransCode(s,T);
}
/****************************************************/
void push(char c, Stack *S)
{
*(S->top)=c;
S->top++;
return;
}
/****************************************************/
char pop(Stack *S)
{
S->top--;
return(*(S->top));
}
/*************************************************/
Stack *Initit_Stack(void)
{
Stack *s;
s=(Stack *)malloc(sizeof(Stack));
s->base=(char *)malloc(50*sizeof(char));
s->top=s->base;
return(s);
}
/************************************************/
