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

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

typedef struct tree_Node    //二叉樹結點
{
    char ch;    //字符內容
    int amount;    //字符在字符串中出現的次數
    struct tree_Node *left,*right;    //指向左子樹與右子樹
}tnode,*bt;

typedef struct list_node        //鏈表結點
{
    char ch;    //存儲字符串中的字符
    int amount;    //字符在字符串中出現的次數
    tnode *son;    //鏈表結點帶有二叉子樹的根結點指針
    struct list_node *next;    //指向鏈表中下一個結點
}Node,*L;

typedef struct stack_node
{
    char ch;    //存儲字符
    int amount;        //出現次數
    bt son;        //指向二叉樹的某結點
    struct stack_node *next;
}snode,*stack;


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


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

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

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

        if(exist==0)    //若當前字符不存在于鏈表中，則分配一個結點入表
        {
            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++;    //讀下一個字符
    }

    printf("統計結果:\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種字符輸入，字符總數%d\n",char_num,char_amount);
}

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

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

    //=========================================
    //這些變量用于構造二叉子樹
    bt left,right,root;
    //==========================================

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

    while(list_element_amount()>=2)    //若表中還有兩個或以上結點，則歸并繼續
    {
        //選擇次數值最小的兩個結點

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

        while(t->next!=NULL)
        {
            t=t->next;
            if(min1>t->amount)    //發現更小的結點
            {
                min1=t->amount;        //將當前結點的次數值賦給min1
                min1_pos=t;            //將當前結點的位置指針賦給min1_pos
                min1_c=t->ch;        //將當前結點的字符賦值給min1_c
                min1_son=t->son;    //將當前結點的二叉指針賦值給min1_son
            }
        }//退出本循環時，最小結點的信息找出，將該結點刪除

        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        //退出循環時min_pri指向min1_pos的前驅
        min_pri->next=min1_pos->next;        //刪除結點min1_pos
        //尋找第一個小結點完成
        //=================================================================

        //=================================================================
        //先尋找第二個小結點
        t=l->next;
        min2=t->amount;        //將第二個結點的次數值賦給min2
        min2_pos=t;            //將第二個結點的位置指針賦給min2_pos
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始終指向最小結點的前驅，以方便刪除最小結點

        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)    //發現更小的結點
            {
                min2=t->amount;        //將當前結點的次數值賦給min2
                min2_pos=t;            //將當前結點的位置指針賦給min2_pos
                min2_c=t->ch;
                min2_son=t->son;
            }
        }//退出本循環時，最小結點的信息找出，將該結點刪除

        min_pri=l;
        while(min_pri->next!=min2_pos)
            min_pri=min_pri->next;
        //退出循環時min_pri指向min1_pos的前驅
        min_pri->next=min2_pos->next;        //刪除結點min2_pos
        //尋找第二個小結點完成
        //=================================================================


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

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

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

        //生成一個對應上面已產生二叉子樹地址的鏈表結點
        made=(L)malloc(sizeof(Node));
        made->amount=root->amount;
        made->ch=root->ch;
        made->next=NULL;
        made->son=root;

        //將生成的鏈表結點插入鏈表中
        temp_p=l;
        while(temp_p->next!=NULL)
            temp_p=temp_p->next;
        //退出循環時temp_p指向鏈表最后一個結點
        temp_p->next=made;        //將生成的結點插入鏈表
    }

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

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