Huffman树

#include <stdio.h>
#include <stdlib.h>
#define MAX    30
#define ADD    10
struct Sq_Stack
{
    char *base;
    char *top;
    int stack_size;
};
typedef struct Node
{
    char data;
    int sum;
    struct Node *next;
}*Sq_List;
typedef struct huffman
{
    int weight;
    char data;
    int parent, lchild, rchild;
}*Huffman_Tree;
void Init_Stack( Sq_Stack &S );
void Push_Stack( Sq_Stack &S, char e );
void Pop_Stack( Sq_Stack &S );
void Destory_Stack( Sq_Stack &S );
void Init_List( Sq_List &L );
void print( Sq_List L );
int Amount_List( Sq_List L );
int Select( Huffman_Tree &HT, int i );
void Huffman_Coding( Huffman_Tree &HT, Sq_List L );
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;
}

void Init_Stack( Sq_Stack &S )
{
    S.base = new char[1];
    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;
}

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 );//表示有多少个要进行编码
    int i;
    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( 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;
    }
    int j, c;
    Sq_Stack S;
    Init_Stack( S );
    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 )
                Push_Stack(S, '1');
            else
                Push_Stack(S, '0');
        }
        while( S.top!=S.base )
            Pop_Stack(S);
        printf("\n");
    }
}