/*
 *Beijing Jiaotong University CIT_2003 JK0309 Copyright@2005
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define MAX_SINGLECODE_LEN 10          //單個(gè)字符最大碼長(zhǎng)
#define MAX_STRING_LEN 1000            //要編碼的字符串的最大長(zhǎng)度
#define MAX_CODESTRING_LEN 10000       //產(chǎn)生的二進(jìn)制碼的最大長(zhǎng)度
#define MAX_WORDS 1000                 //要編碼的字符串中字符種數(shù)最大值
#define END_TREE 9999                  //樹(shù)部分存儲(chǔ)的結(jié)束符
#define PATH_LEN 50                    //路徑串最大長(zhǎng)度

/*****哈夫曼樹(shù)結(jié)構(gòu)定義*****/
typedef struct Huffmantree{
    char ch;                           //字符
    int  weight;                       //結(jié)點(diǎn)權(quán)值
    int  mark;                         //標(biāo)記是否加入樹(shù)中
    struct Huffmantree *parent,*lchild,*rchild,*next;
}HTNode,*LinkTree;

/*****編碼表結(jié)構(gòu)定義*****/
typedef struct{
    char ch;                           //字符部分
    char code[MAX_SINGLECODE_LEN];     //編碼部分
}CodeDictionary;

/*********函數(shù)聲明*********/
LinkTree setWeight(char *);
LinkTree sortNode(LinkTree);
LinkTree createHTree(LinkTree);
void codeHTree(LinkTree,CodeDictionary *);
void decodeHTree(LinkTree,char *,char *);
void deleteNode(LinkTree);
void compressString(char *s,CodeDictionary *,char *);
void readFile(char *);
void writeFile(char *);
void readCode(LinkTree,char *);
void writeCode(LinkTree,char *);
void menu();

/*主函數(shù)*/
int main(){
    char choice;                       //菜單選擇變量
    char string[MAX_STRING_LEN];       //保存從文件中讀取的內(nèi)容
    LinkTree temp;                     //保存賦了權(quán)值的表
    LinkTree ht;                       //保存排序后的表
    LinkTree htcopy,tempcopy;          //表備份
    LinkTree htree;                    //保存哈夫曼樹(shù)
    LinkTree ptr=NULL;
    CodeDictionary codedictionary[MAX_WORDS];    //編碼字典
    char codestring[MAX_CODESTRING_LEN];         //保存0-1形的代碼串     
    char codestring2[MAX_CODESTRING_LEN];        //保存0-1形的代碼串
    LinkTree ht2;                       //保存讀取的樹(shù)
    LinkTree htree2;                    //保存排序后的表
    char filestring[MAX_STRING_LEN];    //解碼后要寫(xiě)入文件中的內(nèi)容

    if((ht2=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建鏈表的頭結(jié)點(diǎn)
    {
        printf("內(nèi)存分配失??！");
        getch();
        exit(0);
    }
    ht2->next=NULL;

    while(1)
    {
        menu();                        //調(diào)入主菜單
        choice=getch();                //讀入用戶(hù)選項(xiàng)
        switch(choice)                 //判斷用戶(hù)選擇
        {
            case 'c':
            case 'C':
                printf("\n\n\n\n\n\n\n\n\n\n\n\n\n");
                printf("\n您選擇了文件編碼方式!\n\n");
                readFile(string);                //讀取要編碼的文件（字符串）
                temp=setWeight(string);          //得到有權(quán)值的表
                tempcopy=setWeight(string);
                ht=sortNode(temp);               //按權(quán)值排序后的表
                htcopy=sortNode(tempcopy);       //用于記錄解碼樹(shù)
                htree=createHTree(ht);           //得到哈夫曼樹(shù)
                codeHTree(htree,codedictionary); //哈夫曼編碼
                compressString(string,codedictionary,codestring);//壓縮為0-1碼
                writeCode(htcopy,codestring);    //將解碼樹(shù)和0-1碼保存                
                deleteNode(htree);               //釋放空間*/
                break;
            case 'd':
            case 'D':
                printf("\n\n\n\n\n\n\n\n\n\n\n\n\n");
                printf("\n您選擇了文件解碼方式!\n\n");
                readCode(ht2,codestring2);       //讀取要解碼的0-1碼
                htree2=createHTree(ht2);         //得到哈夫曼樹(shù)
                codeHTree(htree2,codedictionary);//哈夫曼編碼
                decodeHTree(htree2,codestring2,filestring);//解碼
                writeFile(filestring);           //將解碼文件保存
                deleteNode(htree2);              //釋放空間
                break;
            case 'q':
            case 'Q':
                exit(0);                         //退出程序
        }
    }
}


/*
 *整理輸入的字符串，統(tǒng)計(jì)每個(gè)字符在數(shù)組中出現(xiàn)的次數(shù)，作為其權(quán)值
 */
LinkTree setWeight(char *string)
{
    int i=0;                                     //文件字符串下標(biāo)
    LinkTree tree;                               //頭指針
    LinkTree ptr,beforeptr;                      //創(chuàng)建指針與其前驅(qū)
    HTNode *node;
    
    if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建鏈表的頭結(jié)點(diǎn)
        return NULL;
    tree->next=NULL;
    
    for(i=0;string[i]!='\0';i++)
    {    
        ptr=tree;
        beforeptr=tree;
        
        if((node=(HTNode *)malloc(sizeof(HTNode)))==NULL)
            return NULL;
        node->next=NULL;
        node->parent=NULL;
        node->lchild=NULL;
        node->rchild=NULL;
        node->mark=0;
        node->ch=string[i];
        node->weight=1;
        
        if(tree->next==NULL)                     //如果是第一個(gè)非頭結(jié)點(diǎn)
            tree->next=node;
        else
        {    
            ptr=tree->next;
            while(ptr&&ptr->ch!=node->ch)        //查找相同字符
            {    
                ptr=ptr->next;
                beforeptr=beforeptr->next;
            }
            if(ptr&&ptr->ch==node->ch)           //如果鏈表中某結(jié)點(diǎn)的字符與新結(jié)點(diǎn)的字符相同
            {    
                ptr->weight++;                   //將該結(jié)點(diǎn)的權(quán)加一  
                free(node);    
            }
            else                                 //將新結(jié)點(diǎn)插入鏈表后
            {    
                node->next=beforeptr->next;
                beforeptr->next=node;
            }
        }
    }
    return tree;                                 //返回頭指針
}

/*
 *將整理完的字符串（帶權(quán)鏈表）按出現(xiàn)次數(shù)從小到大的順序排列
 */
LinkTree sortNode(LinkTree tree)
{    
    LinkTree head;                               //頭指針
    LinkTree ph,beforeph;                        //創(chuàng)建指針及其前驅(qū)
    LinkTree pt;
    
    if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//創(chuàng)建新鏈表的頭結(jié)點(diǎn)
        return NULL;
    head->next=NULL;
    
    ph=head;
    beforeph=head;
    
    while(tree->next)
    {    
        pt=tree->next;                           //取被操作鏈表的頭結(jié)點(diǎn)
        tree->next=pt->next;
        pt->next=NULL;
        
        ph=head->next;
        beforeph=head;
        
        if(head->next==NULL)
            head->next=pt;                       //創(chuàng)建當(dāng)前操作鏈表頭結(jié)點(diǎn)
        else
        {
            while(ph&&ph->weight<pt->weight)     //將被操作結(jié)點(diǎn)插入相應(yīng)位置
            {    
                ph=ph->next;
                beforeph=beforeph->next;
            }
            pt->next=beforeph->next;
            beforeph->next=pt;
        }
    }
    free(tree);
    return head;                                 //返回排序后的頭指針
}

/*
 *用排完序的字符串建立哈夫曼樹(shù)
 */
LinkTree createHTree(LinkTree tree)
{   
    LinkTree p,q,beforep;
    HTNode *newnode;
    
    for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)
                                                 //p、q初值為頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)，即最小權(quán)結(jié)點(diǎn)
    {
        tree->next=q->next;
        q->next=NULL;
        p->next=NULL;
        
        if((newnode=(HTNode *)malloc(sizeof(HTNode)))==NULL)
                                                 //申請(qǐng)新結(jié)點(diǎn)作為哈夫曼樹(shù)的中間結(jié)點(diǎn)
            return NULL;
        newnode->next=NULL;
        newnode->mark=0;
        
        newnode->lchild=p;                       //取鏈表頭結(jié)點(diǎn)后的兩個(gè)結(jié)點(diǎn)作為新結(jié)點(diǎn)的左、右孩子
        newnode->rchild=q;
        p->parent=newnode;
        q->parent=newnode;
        newnode->weight=p->weight+q->weight;     //權(quán)值相加
        
        p=tree->next;
        beforep=tree;
        
        if(p!=NULL&&p->weight>=newnode->weight)
        {
            newnode->next=beforep->next;         //將新結(jié)點(diǎn)插入原鏈表的相應(yīng)位置
            beforep->next=newnode;    
        }
        else
        {
            while(p!=NULL&&p->weight<newnode->weight)
            {    
                p=p->next;
                beforep=beforep->next;
            }
            newnode->next=beforep->next;
            beforep->next=newnode;
        }
    }
    return (tree->next);
}

/*
 *對(duì)哈夫曼樹(shù)進(jìn)行編碼
 */
void codeHTree(LinkTree tree,CodeDictionary *codedictionary)
{   
    int index=0,k=0;
    char code[MAX_SINGLECODE_LEN];               //用于統(tǒng)計(jì)每個(gè)字符的哈夫曼編碼
    LinkTree ptr=tree;                           //從樹(shù)的根結(jié)點(diǎn)開(kāi)始

    if(ptr==NULL)
    {
        printf("要進(jìn)行編碼的文件為空!\n");
        //exit(0);
    }
    else
    {
        while(ptr->lchild&&ptr->rchild&&ptr->mark==0)
        {
            while(ptr->lchild&&ptr->lchild->mark==0)
            {
                code[index++]='0';               //左支路編碼為0
                ptr=ptr->lchild;
                if(!ptr->lchild&&!ptr->rchild)   //如果沒(méi)有左右孩子，即葉子結(jié)點(diǎn)
                {
                    ptr->mark=1;                 //作標(biāo)記，表明該字符已被編碼
                    code[index]='\0';            //編碼0-1字符串結(jié)束
                    codedictionary[k].ch=ptr->ch;//給字典賦字符值
                    for(index=0;code[index]!='\0';index++)
                        codedictionary[k].code[index]=code[index];//給字典賦碼值
                    codedictionary[k].code[index]='\0';
                    k++;