标题： Huffman树
时 限： 1000 ms
内存限制： 10000 K

总时限： 3000 ms
描述： Huffman树
对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。

输入： 大写字母个数 n
第一个字母 第二个字母 第三个字母 ...  第n个字母
输出： 字母1 出现次数 Huffman编码
字母2 出现次数 Huffman编码
字母3 出现次数 Huffman编码
…
字母n 出现次数 Huffman编码
输入样例： 10
I I U U U I U N U U
输出样例： U 6 1
I 3 01
N 1 00

#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;
}

用栈 就刚好输出正确的顺序 （前缀码）
 
现在看到的是  倒的

在我电脑中  栈用的时候报 内存报不能读

你自己试试看

谁有时间的 请  帮看下  栈   不知道为什么

https://bbs.bccn.net/thread-308527-1-1.html

  哎  笑不起来啊

那地方是知道  
能不能 有方法 解决
把它拉出来 是能跑的

可能VC编译器bug，在g++ 4.3.3 中运行正常。

#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");
    }
}