/////////////stack.h//////////////////////////////
#ifndef HEAD01_FILE   //避免头文件的重复包含
#define HEAD01_FILE    
/////////////////////
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define TEST printf("her is OK!!\n");
typedef struct N{
    int data;
    struct N *next;
    struct N*per;
}stacknode,*PN;//栈的结点
typedef struct S{  //栈的属性
    PN base;
    PN top;         //为栈顶元素//有数据
    int lenth;
    char *remark;//备注    
}Stack,*PS;

void  InitStack(Stack &st,char *str){
    st.base=st.top=(PN)malloc(sizeof(stacknode));
    st.lenth=0;
    st.remark=(char*)malloc(sizeof(char)*32);
    strcpy(st.remark,str);
}
int Pop(Stack &st)    //弹出元素
{     int d;
    if(st.lenth!=0){
        st.top=st.top->per;    
        free(st.top->next);
        d=st.top->data;            
        st.lenth-=1;
    }
    else d=-1; //表示空栈
    return d;
}
void  Push(Stack &st,int d)  //
{
    st.top->data=d;
    st.top->next=(PN)malloc(sizeof(stacknode));
    st.top->next->per=st.top;
    st.top=st.top->next;
    st.lenth+=1;
}

void outputstack(Stack st)
{
    PN p;
    p=st.base;
    for(int i=0;i<st.lenth;i++,p=p->next)
        printf("**%d** : [ %d ]\n",i+1,p->data);
}

#endif

///////////head01.h/////////////////
#ifndef    HEAD_FILE01
#define HEAD_FILE01
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<windows.h>
#include"stack.h"
////////////////
typedef struct T{    //树结点定义
    char data;       //数据
    int cost;       //权
    int parent;       //父母
    int lchild;       //左孩子
    int rchild;       //右孩子
}TreeNode,*Huftree;

typedef struct C{
    char c;           //字符
    int cost;      //权重
}charlist,*pcharlist;

//////////////////////////////////// 主要函数
pcharlist change(char *str,int &longth);//由字符串生成带权的字符集表//longth:字符集表长度

void madetree(Huftree &tree,pcharlist l,int longth);//由带权的字符集表生成树~~~什么时候开花结果~~

void Select(Huftree ,int longth,int &s1,int &s2);//在带权的森林中找出权最小的两个树(s1<=s2)

char* changetocode(char *str,Huftree tree);//由树生成编码~~~~~~~~什么时候能做好~~~~~~

//////////////////////////////////////辅助函数

int Findchar(char *str,char c);//从字符串中查找字符  返回字符数量

void Deletechar(pcharlist l,int &longth,int s1,int s2);//在带权的字符集表中最小的两个值合并权相加

void outputtree(Huftree); //输出树//

Stack  loadtree(Huftree tree,int n,char *str);//遍历树//返回树的结点//递归调用//未定义

void treetext(Huftree tree);//将哈夫曼树生成文本文件并保存//用于解码用

int loadcode(Stack &st,Huftree tree,int n,char c);//在树中查找C并将对应的编码入栈

void outputstack(Stack st);//输出栈的信息

void begin();//程序运行函数;

#endif
////////////////FUNCTION.CPP///////
#include"head01.h"
///////////////////////////////
//                             //
///////////////////////////////
pcharlist change(char *str,int &longth)//由字符串生成带权的字符集表//longth:字符集表长度

    int i=0,j=0;
    char *s;
    pcharlist list1;    
    s=(char*)malloc(sizeof(char)*strlen(str));
    for(;i<strlen(str);i++) //遍历字符串//找出不相同的字符生成新串s
        if(!Findchar(s,str[i]))
        {
            s[j]=str[i];
            j++;
        }
        longth=j;
        list1=(pcharlist)malloc(sizeof(charlist)*(j));//这句为什么曾经错误 很严重耶        
        for(i=0;i<j;i++){                     
            (list1+i)->c=s[i];
            (list1+i)->cost=Findchar(str,s[i]);
        }        
        return list1;
}                       
/////////////////////////////                      
void madetree(Huftree &tree,pcharlist l,int longth)//由带权的字符集表生成树~~~什么时候开花结果~~
{
    int i,j=0;
    int s1,s2,len; 
    len=2*longth;    
    tree=(Huftree)malloc(sizeof(TreeNode)*(len));
    for(i=longth;i<len;i++){//将字符生成只有一个根的树放在longth-1 ~~~2*longth-1中
        //根的父母为[0] 孩子的父母是对tree的相对位移(整数)//刚好存放字符集表
        (tree+i)->cost=(l+j)->cost;
        (tree+i)->data=(l+j)->c;
        (tree+i)->lchild=0;
        (tree+i)->parent=0;
        (tree+i)->rchild=0;
        j++;     
    } //for
    for(i=1;i<longth;i++){     //longth-1个空间//刚好存放树枝
        Select(tree,len,s1,s2);    
        (tree+i)->lchild=s1;
        (tree+i)->rchild=s2;
        (tree+s1)->parent=i;
        (tree+s2)->parent=i;
        (tree+i)->parent=0;
        (tree+i)->cost=(tree+s1)->cost+(tree+s2)->cost;    
         //printf("我是:[ %d ] \n",i);printf("左孩子:[%d] 右孩子:[%d]\n",(tree+i)->lchild,(tree+i)->rchild);
        
    }//哈夫曼树的根放在 len/2-1 位置//    for(i=9;i<5555;i++)            Sleep(11111);
    tree->lchild=longth-1;
    tree->rchild=0;
    tree->parent=0;
    tree->cost=len;//////////////////////
    printf("%d++++",len);
        


void Select(Huftree tree,int len,int &s1,int &s2)//在带权的森林中找出权最小的两个树(s1<s2)
{    
    int i,k=0;
    s1=0;s2=0;
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost>=k){
            s1=i;//s1记录大的
            k=(tree+s1)->cost;
        }
    }
    s2=s1;
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s1)->cost)
            s1=i;        
    }//for
    for(i=1;i<len;i++){
        if(((tree+i)->parent==0)&&(tree+i)->cost<=(tree+s2)->cost)
            if(s1!=i)    s2=i;        
    }//for    
}


void Deletechar(pcharlist l,int &longth,int s1,int s2)//在带权的字符集表中最小的两个值合并权相加
{    
    (l+s1)->cost+=(l+s2)->cost;
    (l+s1)->c=0;  //表示为树枝交叉
    (l+s2)->c=(l+longth)->c;
    (l+s2)->cost=(l+longth)->cost;
    longth--;
}
int Findchar(char *str,char c)//从字符串中查找字符  返回字符数量
{
    int i,l,k=0;
    l=strlen(str);
    for(i=0;i<l;i++){
        if(str[i]==c) k++;
    }
    return k;
}

void outputtree(Huftree tree) //输出树//返回树的结点//递归调用
{
    int i,l;
    l=tree[0].data;
    for(i=0;i<l;i++)
    {      
        if(tree[i].lchild!=0){//树
            printf("**[%d]**:I'm a  [tree] and",i+1);
            printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
            printf("my first child's no. is [] the other one is [%d]",tree[i].lchild,tree[i].rchild);
        }//if
        else   { //叶
            //printf("**[%d]**:I'm a  [leafage] and",i+1); 
                printf("my name is [%c],my parents'no. is [%d]\n",tree[i].data,tree[i].parent);
        }//else
    }//for
}

Stack  loadtree(Huftree tree,int n,char *str)//由字符串生成编码//放在栈中并返回//
{
    int i,len;
    len=strlen(str);
    Stack st;
    InitStack(st,"Haffcode");
    for(i=0;i<len;i++){
        //printf("%d]]字符:%c\n",i+1,str[i]);
        loadcode(st,tree,tree->lchild,str[i]);        
    }
    return st; 
}

int loadcode(Stack &st,Huftree tree,int n,char c)//在树中查找C并将对应的编码入栈//这个函数有点头大哦
{    
    if((tree+n)->data==c){
        //printf("已经找到\n");
        //outputstack(st);
        return 2;
    }
    if((tree+n)->lchild!=0){
        Push(st,0);    //printf("我左孩子是:%d\n",(tree+n)->lchild);
        if(loadcode(st,tree,(tree+n)->lchild,c)==2)
            return 2;
        else 
            Pop(st);     
                
    }
    if((tree+n)->rchild!=0){
        Push(st,1);//    printf("我右孩子是:%d\n",(tree+n)->rchild);
        if(loadcode(st,tree,(tree+n)->rchild,c)==2)
            return 2;
        else 
                Pop(st);
    }
    return 1;
}

void treetext(Huftree tree)//将哈夫曼树生成文本文件并保存//用于解码用
{
    int i,l;
    FILE* treefile;
    treefile=fopen("treecode.txt","wt");
    fputc(tree->cost,treefile);//整数不用转化直接储存
    l=tree->cost;
    //因为一般树的储存长度小于122
    for(i=0;i<l;i++) //这里不关心权重
    {
        fputc((tree+i)->lchild,treefile);//顺序为左孩子
        fputc((tree+i)->rchild,treefile);//右孩子
        fputc((tree+i)->parent,treefile);//父母    
        fputc((tree+i)->data,treefile);//字符值
    }
}



void begin()//程序运行函数
{
    printf("********************************************************************************");
    system("color 4a");
    Stack st;
    Huftree tree;
    pcharlist charlist;
    int listlong;
    char *str;
    char path[64],goodpath[64];
    int lenth;
    FILE *handle,*gfile;
    printf(" 请输入原文件路径: ");
    scanf("%s",path);    
    printf(" 输入目标文件路径: ");
    scanf("%s",goodpath);
    handle=fopen(path,"rt");      //打开文件
    gfile=fopen(goodpath,"wt");
    fseek(handle,0,SEEK_END);     //
    lenth=ftell(handle);         //取文件长度
    lenth+=1; 
    str=(char*)malloc(sizeof(char)*lenth);//多一个字节//存放'\0'
    rewind(handle);     //文件指针回打文件开始
    fgets(str,lenth,handle);      //将文件内容存入str     
    charlist=change(str,listlong); 
    madetree(tree,charlist,listlong); 
    st=loadtree(tree,0,str);
    //outputstack(st);//输出栈的信息//将栈中的每8个二进制数据转化为一个字符存放    
    ///////////////////////////////////////////////////
    int l,i;
    l=st.lenth;
    PN p;
    p=st.base; 
    for(i=0;i<l;i++){
        fputc(p->data+48,gfile);
        p=p->next;
    }
    printf("\n\n");
    //outputstack(st);

    printf(" 编码完成 编码文件存放在 %s \n\n\n",goodpath);
    treetext(tree);
    printf("********************************************************************************\n\n\n");
}
void main()

    begin();
}


//附:将整数转化为字符串的函数:itoa(,,);
//字符转化为整数              : atoi(  );
//共3个文件
//自己做的哈夫曼树
//大家交流交流
//由英语文本文件生成二进制编码存放在另一个文件中
//注意:原文件须在项目工程文件夹下
//生成的编码文件也在项目工程文件夹下