/*author:windy_2*/

/*修正版*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

typedef struct slink

{

    char data;

    int wp;

    int bm;

    int mark;

    struct slink *left;

    struct slink *right;

}*link;

struct hfm

{

    char data;

    int wp;

};

struct T

{

    int data;

    struct T *next;

};

struct te

{

    int data;

    struct te *next;

};

struct slink* create_tree(struct hfm arr[],int len);

void print(struct slink *root);

int pop();

void push(int k);

struct T *T;

struct te *te;

int pop_s(struct T *strack);

void push_t(int k);

int pop_t();

int main()

{

    struct slink *root;

    int i,k=;

    char str[];

    char a[];

    int b[];

    int count,j;

    struct hfm *arr;

    T = (struct T*)malloc(sizeof(struct T));

    T->data = ;

    T->next = NULL;

    te = (struct te*)malloc(sizeof(struct te));

    te->data = ;

    te->next = NULL;

    printf("请输入你要进行编码的字符串: \n");

    scanf("%s",str);

    if(str[strlen(str)] == '\0')

    {

        str[strlen(str)]=NULL;

    }

    for(i = ;i < strlen(str);i++)

    {

        if(str[i]!='#')

        {

            a[k] = str[i];

            b[k] = ;

            for(j = ;j<strlen(str);j++)

            {

                if(str[j] == str[i])

                {

                    b[k]++;

                }

            }

            for(j = ;j<strlen(str);j++)

            {

                if(str[j] == a[k])

                {

                    str[j] = '#';

                }

            }

            k++;

        }

        count = k;

    }

    arr = (struct hfm*)malloc(sizeof(struct hfm)*count);

    for(i = ;i < count;i++)

    {

        arr[i].data = a[i];

        arr[i].wp = b[i];

    }

    root = (struct slink*)malloc(sizeof(struct slink));

    root = create_tree(arr,count);

    print(root);

}

struct slink* create_tree(struct hfm arr[],int len)

{

    link ptrarr[];

    link ptr,root = NULL;

    int i,k1 = -,k2,j;

    for(i = ;i < len;i++)

    {

        ptr = (link)malloc(sizeof(struct slink));

        ptr->data = arr[i].data;

        ptr->wp = arr[i].wp;

        ptr->mark = ;

        ptr->left = NULL;

        ptr->right = NULL;

        ptrarr[i] = ptr;

    }

    for(i = ;i < len;i++)

    {

        for(j = ;j < len;j++)

        {

            if(ptrarr[j]!=NULL&&k1==-)

            {

                k1 = j;

                continue;

            }

            if(ptrarr[j]!=NULL)

            {

                k2 = j;

                break;

            }

        }

        for(j = k2;j < len;j++)

        {

            if(ptrarr[j] != NULL)

            {

                if(ptrarr[j]->wp > ptrarr[k1]->wp)

                {

                    k2 = k1;

                    k1 = j;

                }

                else if(ptrarr[j]->wp < ptrarr[k2]->wp)

                {

                    k2 = j;

                }

            }

        }

        root = (link)malloc(sizeof(struct slink));

        ptrarr[k1]->bm = ;

        ptrarr[k2]->bm = ;

        root->wp = ptrarr[k1]->wp + ptrarr[k2]->wp;

        root->data = '!';

        root->mark = ;

        root->left = ptrarr[k1];

        root->right = ptrarr[k2];

        ptrarr[k1] = root;

        ptrarr[k2] = NULL;

    }

    return root;

}

void print(struct slink *root)

{

    int temp;

    struct T *p;

    if(root == NULL)

    {

        return;

    }

    else

    {

        if(root->bm == ||root->bm == )

        {

            push(root->bm);

        }

        if(root->data != '!')

        {

            printf("%c的哈夫曼编码为: ",root->data);

            root->mark = ;

            temp = pop();

            push_t(temp);

            p = T->next;

            while(p!=NULL)

            {

                temp = pop_s(p);

                push_t(temp);

                p = p->next;

            }

            while(te->next!=NULL)

            {

                temp = pop_t();

                printf("%d",temp);

            }

            printf("\n");

            if(root->bm == )

            {

                temp = pop();

            }

        }

        print(root->left);

        print(root->right);

    }

}

int pop()

{

    struct T *p;

    int n;

    if(T->next == NULL)

    {

        return ;

    }

    else

    {

        p = T->next;

        n = p->data;

        T->next = p->next;

        free(p);

        return n;

    }

}

void push(int k)

{

    struct T *strack;

    strack = (struct T*)malloc(sizeof(struct T));

    strack->data = k;

    strack->next = T->next;

    T->next = strack;

}

int pop_s(struct T *strack)

{

    struct T *p;

    int n;

    if(T->next == NULL)

    {

        return ;

    }

    else

    {

        p = strack;

        n = p->data;

        return n;

    }

}

void push_t(int k)

{

    struct te *strack;

    strack = (struct te*)malloc(sizeof(struct te));

    strack->data = k;

    strack->next = te->next;

    te->next = strack;

}

int pop_t()

{

    struct te *p;

    int n;

    if(te->next == NULL)

    {

        return -;

    }

    else

    {

        p = te->next;

        n = p->data;

        te->next = p->next;

        free(p);

        return n;

    }

}