#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define NULL 0

typedef struct huff_code_node    //存儲(chǔ)編碼的鏈表
{
    char ch;    //編碼對(duì)應(yīng)的字符
    char code[100];        //字符對(duì)應(yīng)的哈夫曼碼
    struct huff_code_node *next;    
}hnode,*huff;

typedef struct tree_Node    //二叉樹(shù)結(jié)點(diǎn)
{
    char ch;    //字符內(nèi)容
    int amount;    //字符在字符串中出現(xiàn)的次數(shù)
    struct tree_Node *left,*right;    //指向左子樹(shù)與右子樹(shù)
}tnode,*bt;

typedef struct list_node        //鏈表結(jié)點(diǎn)
{
    char ch;    //存儲(chǔ)字符串中的字符
    int amount;    //字符在字符串中出現(xiàn)的次數(shù)
    tnode *son;    //鏈表結(jié)點(diǎn)帶有二叉子樹(shù)的根結(jié)點(diǎn)指針
    struct list_node *next;    //指向鏈表中下一個(gè)結(jié)點(diǎn)
}Node,*L;

typedef struct stack_node
{
    char ch;    //存儲(chǔ)字符
    int amount;        //出現(xiàn)次數(shù)
    bt son;        //指向二叉樹(shù)的某結(jié)點(diǎn)
    struct stack_node *next;
}snode,*stack;


char t[200],*str,*c;    //用于存儲(chǔ)和處理輸入的字符串
bt root=NULL;        //哈夫曼樹(shù)
L l,p,q,new_node;    //鏈表結(jié)點(diǎn)
huff hlist;        //計(jì)算得到的編碼表
int char_num;    //輸入的不同字符數(shù)量
int char_amount;    //輸入的所有字符數(shù)量
int code_sum;        //哈夫曼編碼總長(zhǎng)


void initial()        //初始化操作
{
    l=(Node*)malloc(sizeof(Node));        //建立空鏈表
    l->ch='\0';
    l->amount=0;
    l->son=NULL;
    l->next=NULL;

    str=t;    //將字符串指針指向字符串的第一個(gè)位置
    //鍵盤(pán)輸入字符串
    printf("輸入字符串進(jìn)行哈夫曼編碼:\n");
    scanf("%s",str);
    getchar();    
}

void pull_in_list()
{
    int exist;    //表示當(dāng)前字符是否存在于鏈表中，0為不存在，1為已存在
    int n;    //計(jì)算輸入不同字符的數(shù)量，計(jì)算后賦值給全局變量char_num
    int m;    //計(jì)算輸入所有字符的數(shù)量，計(jì)算后賦值給全局變量char_amount
    
    c=str;    //c指向第一個(gè)字符
    
    while(*c!='\0')        //若字符串未讀完
    {
        exist=0;
        p=l;    //p指向鏈表頭結(jié)點(diǎn)
        //尋找該字符是否已經(jīng)在鏈表中
        while(p->next!=NULL)    //若鏈表非空
        {
            p=p->next;
            if(p->ch==*c)    //若當(dāng)前字符已經(jīng)在鏈表中
            {
                exist=1;
                p->amount++;    //字符出現(xiàn)次數(shù)加1
                break;
            }
        }

        if(exist==0)    //若當(dāng)前字符不存在于鏈表中，則分配一個(gè)結(jié)點(diǎn)入表
        {
            new_node=(Node*)malloc(sizeof(Node));
            new_node->ch=*c;
            new_node->amount=1;
            new_node->next=NULL;
            new_node->son=NULL;
            p->next=new_node;
            p=new_node;
        }
        c++;    //讀下一個(gè)字符
    }

    printf("統(tǒng)計(jì)結(jié)果:\n");
    p=l;
    n=0;
    m=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
        m+=p->amount;
        printf("%c--%d\n",p->ch,p->amount);
    }
    char_num=n;
    char_amount=m;
    printf("一共有%d種字符輸入，字符總數(shù)%d\n",char_num,char_amount);
}

int list_element_amount()        //計(jì)算鏈表中結(jié)點(diǎn)的數(shù)量（不包括頭結(jié)點(diǎn)）
{
    L temp;        //定義臨時(shí)指針
    int n=0;        //結(jié)點(diǎn)數(shù)量
    temp=l;
    while(temp->next!=NULL)    //后面還有結(jié)點(diǎn)
    {
        n++;
        temp=temp->next;
    }
    return n;
}

bt create()    //建立最優(yōu)二叉樹(shù)
{
    //=========================================
    //這些變量用于尋找最小結(jié)點(diǎn)
    L min1_pos,min2_pos,t,min_pri;
    bt min1_son,min2_son;
    int min1,min2;
    char min1_c,min2_c;
    //=========================================

    //=========================================
    //這些變量用于構(gòu)造二叉子樹(shù)
    bt left,right,root;
    //==========================================

    //==========================================
    //這些變量用于將二叉子樹(shù)信息插入鏈表
    L made,temp_p;
    //============================================

    while(list_element_amount()>=2)    //若表中還有兩個(gè)或以上結(jié)點(diǎn)，則歸并繼續(xù)
    {
        //選擇次數(shù)值最小的兩個(gè)結(jié)點(diǎn)

        //============================================================================
        //先尋找第一個(gè)小結(jié)點(diǎn)
        t=l->next;
        min1=t->amount;        //將第一個(gè)結(jié)點(diǎn)的次數(shù)值賦給min1
        min1_pos=t;            //將第一個(gè)結(jié)點(diǎn)的位置指針賦給min1_pos
        min1_c=t->ch;        //將第一個(gè)結(jié)點(diǎn)的字符賦值給min1_c
        min1_son=t->son;    //將第一個(gè)結(jié)點(diǎn)的二叉指針賦值給min1_son
        min_pri=l;            //min_pri始終指向最小結(jié)點(diǎn)的前驅(qū)，以方便刪除最小結(jié)點(diǎn)

        while(t->next!=NULL)
        {
            t=t->next;
            if(min1>t->amount)    //發(fā)現(xiàn)更小的結(jié)點(diǎn)
            {
                min1=t->amount;        //將當(dāng)前結(jié)點(diǎn)的次數(shù)值賦給min1
                min1_pos=t;            //將當(dāng)前結(jié)點(diǎn)的位置指針賦給min1_pos
                min1_c=t->ch;        //將當(dāng)前結(jié)點(diǎn)的字符賦值給min1_c
                min1_son=t->son;    //將當(dāng)前結(jié)點(diǎn)的二叉指針賦值給min1_son
            }
        }//退出本循環(huán)時(shí)，最小結(jié)點(diǎn)的信息找出，將該結(jié)點(diǎn)刪除

        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        //退出循環(huán)時(shí)min_pri指向min1_pos的前驅(qū)
        min_pri->next=min1_pos->next;        //刪除結(jié)點(diǎn)min1_pos
        //尋找第一個(gè)小結(jié)點(diǎn)完成
        //=================================================================

        //=================================================================
        //先尋找第二個(gè)小結(jié)點(diǎn)
        t=l->next;
        min2=t->amount;        //將第二個(gè)結(jié)點(diǎn)的次數(shù)值賦給min2
        min2_pos=t;            //將第二個(gè)結(jié)點(diǎn)的位置指針賦給min2_pos
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始終指向最小結(jié)點(diǎn)的前驅(qū)，以方便刪除最小結(jié)點(diǎn)

        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)    //發(fā)現(xiàn)更小的結(jié)點(diǎn)
            {
                min2=t->amount;        //將當(dāng)前結(jié)點(diǎn)的次數(shù)值賦給min2
                min2_pos=t;            //將當(dāng)前結(jié)點(diǎn)的位置指針賦給min2_pos
                min2_c=t->ch;
                min2_son=t->son;
            }
        }//退出本循環(huán)時(shí)，最小結(jié)點(diǎn)的信息找出，將該結(jié)點(diǎn)刪除

        min_pri=l;
        while(min_pri->next!=min2_pos)
            min_pri=min_pri->next;
        //退出循環(huán)時(shí)min_pri指向min1_pos的前驅(qū)
        min_pri->next=min2_pos->next;        //刪除結(jié)點(diǎn)min2_pos
        //尋找第二個(gè)小結(jié)點(diǎn)完成
        //=================================================================


        //==================================================================
        //兩個(gè)最小結(jié)點(diǎn)找到，由這對(duì)結(jié)點(diǎn)級(jí)成一個(gè)二叉子樹(shù)，將根結(jié)點(diǎn)插入鏈表中
        if(min1_son==NULL)    //該結(jié)點(diǎn)無(wú)二叉子樹(shù)指針，則須新分配一個(gè)二叉樹(shù)結(jié)點(diǎn)
        {
            left=(bt)malloc(sizeof(tnode));        //產(chǎn)生左孩子
            left->amount=min1;        //次數(shù)值復(fù)制
            left->ch=min1_c;        //字符復(fù)制
            left->left=NULL;
            left->right=NULL;
        }
        else    //該結(jié)點(diǎn)為計(jì)算產(chǎn)生的結(jié)點(diǎn)，它已指向一個(gè)二叉子樹(shù)
            left=min1_son;    //left直接指向已經(jīng)生成的二叉子樹(shù)的根結(jié)點(diǎn)

        if(min2_son==NULL)    //該結(jié)點(diǎn)無(wú)二叉子樹(shù)指針，則須新分配一個(gè)二叉樹(shù)結(jié)點(diǎn)
        {
            right=(bt)malloc(sizeof(tnode));        //產(chǎn)生右孩子
            right->amount=min2;        //次數(shù)值復(fù)制
            right->ch=min2_c;        //字符復(fù)制
            right->left=NULL;
            right->right=NULL;
        }
        else
            right=min2_son;    //left直接指向已經(jīng)生成的二叉子樹(shù)的根結(jié)點(diǎn)

        root=(bt)malloc(sizeof(tnode));
        root->amount=min1+min2;
        root->ch='\0';        //對(duì)于計(jì)算產(chǎn)生的樹(shù)結(jié)點(diǎn)，字符均為空
        root->left=left;
        root->right=right;
        //二叉子樹(shù)完成

        //生成一個(gè)對(duì)應(yīng)上面已產(chǎn)生二叉子樹(shù)地址的鏈表結(jié)點(diǎn)
        made=(L)malloc(sizeof(Node));
        made->amount=root->amount;
        made->ch=root->ch;
        made->next=NULL;
        made->son=root;

        //將生成的鏈表結(jié)點(diǎn)插入鏈表中
        temp_p=l;
        while(temp_p->next!=NULL)
            temp_p=temp_p->next;
        //退出循環(huán)時(shí)temp_p指向鏈表最后一個(gè)結(jié)點(diǎn)
        temp_p->next=made;        //將生成的結(jié)點(diǎn)插入鏈表
    }

    temp_p=l->next;
    return temp_p->son;
}

void encoding()        //根據(jù)建立的哈夫曼樹(shù)編碼
{
    stack code,top,temp,readcode;
    bt r;
    huff temp_huff,hp;