#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;

typedef struct {
    unsigned int weight;
    char ch1;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;
typedef struct {
    char ch;
    char code[7];
}codenode,*code;

void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
    for(int i=1;i<=n;i++)
        if(!HT[i].parent){
            s1=i; break;
            }
        for(i++;i<=n;i++)
            if(!HT[i].parent){
                s2=i; break;
                }
            if(HT[s1].weight-HT[s2].weight){
                int temp; temp=s1; s1=s2; s2=temp;
                }
            for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
                if(!HT[i].parent){
                    if(HT[i].weight<HT[s1].weight){s2=s1; s1=i;
                    }
                    else if(HT[i].weight<HT[s2].weight&&i!=s1)
                        s2=i;
                }
}

void prin(){ //终端输出选择菜单cout<<"----------------------------------------------------\n\n"
    <<" ∣ I---创建哈夫曼树 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ E---文件编码 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ D---文件译码 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ P---打印代码文件 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ T---印哈夫曼树 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ O---哈夫曼树的存储结构 ∣\n"
    <<" ∣ ∣\n"
    <<" ∣ Q---退出 ∣\n"
    <<"\n-----------------------------------------------------\n\n"
    printf("选择菜单功能选项：");
}

void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
    int i=0;
    cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
    for(;i<2*n-1;i++){
        th++;
        cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight<<endl;
    }
}

void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
    cout<<"----------------------------------------------------\n\n"
        <<" ∣ 1---自定义 ∣\n"
        <<" ∣ ∣\n"
        <<" ∣ 2---编码课本测试数据 ∣\n"
        <<" ∣ ∣\n"
        <<" ∣ 3---编码源程序 ∣\n"
        <<"\n-----------------------------------------------------\n\n";
    printf("选择菜单功能选项：");
    scanf("%d",&k);
    if(k==1){
        printf("输入需要编码的字符总数: ");
        scanf("%d",&n);
        printf("\n输入需要编码字符的权值:\n");
        for(int d=0;d<n;d++) {
            scanf("%d",&w[d]);
            }
        printf("\n输入需要编码的字符串: ");
        scanf("%s",ch);
    }
    else if(k==2){
        ifstream fin2 ("test.txt");
        fin2>>n;
        for(int d=0;d<n;d++)
            fin2>>w[d];
            fin2>>ch;
            fin2.close();
    }
    else if(k==3){
        ifstream fin1 ("input.txt");
        fin1>>n;
        for(int d=0;d<n;d++)
            fin1>>w[d];
            fin1>>ch;
            fin1.close();
            }
    if(n<=1)
        return;
    int s1,s2,i,num=2*n-1;
    HuffmanTree p;
    HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
    for(p=HT+1,i=1;i<=n;i++,p++){
        p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
    }
    for(;i<=num;p++,i++){
        p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
    }
    for(i=n+1;i<=num;i++){
        select(HT,i-1,s1,s2);
        HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
        HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    char * temp=(char *)malloc(n*sizeof(char));
    temp[n-1]='\0';
    for(i=1;i<=n;i++){
        int start=n-1;
        for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
            if(HT[f].lchild==h)
                temp[--start]='0';
            else
                temp[--start]='1';
            HC[i]=(char *)malloc((n-start)*sizeof(char));
            strcpy(HC[i],&temp[start]);
    }
    ofstream fout ("hfmTree.txt");
    fout<<ch<<endl;
    for(int j=1;j<=n;j++)
        fout<<HC[j]<<endl;
    fout.close();
    free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
    char a[100],b[100][20];
    ifstream fin ("hfmTree.txt");
    fin>>a;
    for(int j=0;j<n;j++) fin>>b[j];
    fin.close();
    ifstream fin1 ("course.txt");
    ifstream fin2 ("sorse.txt");
    ifstream fin3 ("ToBeTran.txt");
    char s[1000];
    if(select==3)
        fin2>>s;
    else if(select==2)
        fin1>>s;
    else fin3>>s;
    ofstream fout ("CodeFile.txt");
    while(s[0]!='\0'){
        for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
            for(int g=0;a[g]!=s[i];g++) ;
            fout<<b[g];
        }
        fout<<'\n';
        if(select==3)
            fin2>>s;
        else if(select==2)
            fin1>>s;
        else fin3>>s;
    }
    fin3.close();
    fin2.close();
    fin1.close();
    fout.close();
}

void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
    ifstream fin ("CodeFile.txt");
    ofstream fout ("TextFile.txt");
    char s[500];
    fin>>s;
    HuffmanTree head=ht+2*n-1;
    int i=0;
    while(s[0]!='\0'){
        while(s[i]!='\0'){
            if(s[i]=='1') head=ht+head->rchild;
            else if(s[i]=='0') head=ht+head->lchild;
            if((head->lchild)==0&&(head->rchild) ==0) {
                fout<<(head->ch1);
                head=ht+2*n-1;
            }
            i++;
        }
        fout<<' ' ;
        i=0;
        fin>>s;
    }
    fin.close();
    fout.close();
}

void Print(){ //打印代码文件，显示在终端，每行50个代码
    ifstream fin ("CodeFile.txt");
    char s[2000];
    int i=1;
    int j=0;
    fin>>s;
    ofstream fout ("CodePrin.txt");
    while(s[0]!='\0'){
        for(;s[j]!='\0';j++){
            printf("%c",s[j]);
            fout<<s[j];
            if(i%50==0){
                fout<<endl;
                printf("\n");
            }
            i++;
        }
        j=0;
        fin>>s;
    }
    fin.close();
    printf("\n");
    fout.close();
}

void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
    printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
    fout<<"|……";
    printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
    printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}

void main(){
    int select;
    int n;
    char ch[100];
    int w[100];
    HuffmanTree HT=NULL;
    HuffmanCode hc=NULL;
    prin();
    char c='I';
    scanf("%c",&c);
    while(c!='Q'){
        switch(c){
            case 'I':
                initial(HT,hc,w,n,ch,select);
                prin();
                break;
                case 'E':
                    encoding(n,select);
                    prin();
                    break;
                    case 'D':
                        decoding(HT,n);
                        prin();
                        break;
                        case 'P':
                            Print();
                            prin();
                            break;
                            case 'T':
                                printTree(HT,HT+2*n-1,1);
                                prin();
                                break;
                                case 'O':
                                    output(HT,n);
                                    prin();
                                    break;
        }
        scanf("%c",&c);
    }
}