#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define ADD 10
typedef struct stack
{
char *base;
char *top;
int stack_size;
}Sq_Stack;
typedef struct Node
{
char data;
int sum;
struct Node *next;
}*Sq_List;
//
void Init_Stack( Sq_Stack &S )
{
S.base = (char*) realloc (S.base, (sizeof(char)));
if( !S.base )
exit(0);
S.top = S.base;
S.stack_size = MAX;
}
void Push_Stack( Sq_Stack &S, char e )
{
if( S.top-S.base >= S.stack_size )
{
S.base = (char*) realloc ( S.base, ((ADD+S.stack_size)*sizeof(char)));
S.top = S.base + S.stack_size;
S.stack_size += ADD;
}
*S.top++ = e;
}
void Pop_Stack( Sq_Stack &S )
{
if( S.top == S.base )
return;
printf("%c", *--S.top);
}
void Destory_Stack( Sq_Stack &S )
{
if( S.base )
{
S.base = S.top = NULL;
S.stack_size = 0;
}
}
//
void Init_List( Sq_List &L )
{//L is the head node
printf("输入你的字符串可能的最大长度:");
int i;
scanf("%d", &i);
Sq_List pf, f = L;
char *c = (char*) malloc (i*sizeof(char));
scanf("%s", c);
while( *c != '\0' )
{
pf = L->next;
while( pf )
{
if( pf->data == *c )
{
++pf->sum;
break;
}
f = f->next;
pf = pf->next;
}
if( !pf )
{
Sq_List p;
p = (Sq_List) malloc (sizeof(struct Node));
p->data = *c;
p->sum = 1;
p->next = pf;
f->next = p;
}
f = L;
++c;
}
}
void print( Sq_List L )
{
Sq_List p = L->next;
while( p )
{
printf("%c ", p->data);
p = p->next;
}
printf("\n");
}
int Amount_List( Sq_List L )
{
Sq_List p = L->next;
int e = 0;
while( p )
{
++e;
p = p->next;
}
return e;
}
typedef struct
{
int weight;
char data;
int parent, lchild, rchild;
}*Huffman_Tree;
int Select( Huffman_Tree &HT, int i )
{
int j=1, flag = -1;
while( j<i )
{
if( HT[j].parent == 0 )
{
if( flag == -1 )
flag = j;
if( HT[j].weight < HT[flag].weight )
flag = j;
}
++j;
}
HT[flag].parent = i;
return flag;
}
void Huffman_Coding( Huffman_Tree &HT, Sq_List L )
{
int m = Amount_List( L );//表示有多少个要进行编码
if( m<=1 )
return;
int n = 2*m - 1;
HT = (Huffman_Tree) malloc ((n+1)*sizeof(Huffman_Tree));
Huffman_Tree h = HT+1;
Sq_List p = L->next;
for(; p != NULL; ++h, p = p->next )
{
h->weight = p->sum;
h->data = p->data;
h->parent = 0;
h->lchild = 0;
h->rchild = 0;
}
for( int i=0; i<m-1; ++i, ++h )
{
h->weight = 0;
h->parent = 0;
h->lchild = 0;
h->rchild = 0;
}
int s1, s2;
for( i=m+1; i<=n; ++i )
{
s1 = Select( HT, i );
s2 = Select( HT, i );
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s2].weight + HT[s1].weight;
}
// Sq_Stack S;
// Init_Stack( S );
int j, c;
for( i=1; i<=m; ++i )
{
printf(" %c %d \t", HT[i].data, HT[i].weight );
for( c=i, j=HT[i].parent; j!=0; c=j, j=HT[j].parent )
if( HT[j].lchild == c )
printf("%d", 1);
// Push_Stack(S, '1');
else
printf("%d", 0);
// Push_Stack(S, '0');
// while( S.top!=S.base )
// Pop_Stack(S);
printf("\n");
}
}
int main()
{
Sq_List L = (Sq_List) malloc (sizeof(struct Node));
L->next = NULL;
Huffman_Tree HT;
Init_List( L );printf("\n");
print( L );
Huffman_Coding( HT , L );
return 0;
}