#include"iostream.h"
#include"cstring"
#include"stdlib.h"
#include"stdio.h"
typedef struct
{
int weight;
int parent,lchild,rchild;
char c;
}htnode, *huffmantree;
typedef char** huffmancode;
typedef struct
{
int w;
int n;
}small;
typedef struct
{
char c;
int w1;
}text;
text* input（int& n)
{
text *p;
cout << "please input the number of the chars"<<endl;
cin >> n;
p=new text[n];
cout <<"please input the chars:"<<endl;
for（int i=0; i<n; i++)
scanf（"%c", &p[i].c);
cout << "please input the weights:"<<endl;
for（int j=0; j<n; j++)
{
cin >> p[j].w1;
if（p[j].w1 <=0)
{
cout <<"input error,please continue."<<endl;
j=0;
continue;
}
}
return p;
}
void bubble（small a[],int n)
{
int i,j,t,temp1,temp2;
for（i=1;i<=n-1;i++)
{
t=n-i;
for（j=0;j<t-1;j++)
if（a[j].w>a[j+1].w)
{
temp1=a[j].w ;temp2=a[j].n;
a[j].w =a[j+1].w ;a[j].n =a[j+1].n ;
a[j+1].w =temp1;a[j+1].n =temp2;
}
}
}
huffmancode scoding（huffmantree& ht,int n)
{
int k=0,start,x;
char *cd;
huffmancode hc;
hc=（huffmancode)malloc（（n+1)*sizeof（char*));
cd=new char[n];
cd[n-1]='\0';
for（int i=1;i<=n;++i)
{
x=0;
start=n-1;
for（int c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
if（ht[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=new char[n-start];
for（char *l=hc[i],k=start;k<=n-2;k++,x++)
l[x]=cd[k];
l[x]='\0';
}
delete[] cd;
return hc;
}
void select（huffmantree p,int i,int& a,int& b)
{
small *q=new small[i];
int m=0;
for（int j=1;j<=i;j++)
{
if（p[j].parent ==0)
{
q[m].w =p[j].weight;
q[m].n =j;
m++;
}
}
bubble（q,m);
if（q[0].n <q[1].n)
{
a=q[0].n;
b=q[1].n;
}
else
{
a=q[1].n;
b=q[0].n;
}
}
void bulidtree（huffmantree& ht,text *w,int n)
{
file *fp;
int s1,s2;
huffmantree p;
int m,i;
if（n<=1) return ;
m=2*n-1;
ht=new htnode[m+1];
if（（fp=fopen（"hfmtree.txt","w"))==null)
{
cout<<"can't open file";
exit（0);
}
for（p=ht,i=1;i<=n;++i)
{
p[i].c =w[i-1].c;
p[i].weight =w[i-1].w1;
p[i].parent =0;
p[i].lchild =0;
p[i].rchild =0;
}
for（;i<=m;++i)
{
p[i].c =null;
p[i].weight =0;
p[i].parent =0;
p[i].lchild =0;
p[i].rchild =0;
}
for（i=n+1;i<=m;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;
}
for（int j=1;j<=m;j++)
{
fprintf（fp,"%c %d %d %d %d",ht[j].c ,ht[j].weight ,ht[j].parent ,ht[j].lchild ,ht[j].rchild );
}
}
text* readingtree（huffmancode& h,int& n,huffmantree& p)
{
char c;
int i=1,a,b,e,d,j=0;
text* r;
n=0;
file *fp;
if（（fp=fopen（"hfmtree.txt","r"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
while（fscanf（fp,"%c %d %d %d %d",&c ,&a,&b ,&e ,&d )!=eof&&c !=null)
n++;
rewind（fp);
r=new text[n];
p=new htnode[2*n-1];
while（fscanf（fp,"%c %d %d %d %d", &p[i].c, &p[i].weight, &p[i].parent, &p[i].lchild, &p[i].rchild)!=eof)
{
if（j<=n)
{
r[j].c =p[i].c;
r[j].w1 =p[i].weight;
}
j++;
i++;
}
h=scoding（p,n);
fclose（fp);
return r;
}
void encoding（huffmancode p1,int n,text *r1)
{
bool k=1;
file *fp,*fp1;
char c;
if（（fp=fopen（"codefile.txt","w"))==null)
{
cout<<"can't open file";
exit（0);
}
if（（fp1=fopen（"tobetran.txt","r"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
while（（c=fgetc（fp1))!=eof)
{
for（int i=0;i<n;i++)
{
if（c==r1[i].c)
{
fputs（p1[i+1],fp);
k=0;
}
}
if（k==1)
fputc（c,fp);
k=1;
}
fclose（fp);
}
void decoding（huffmancode p1,int n,text *r2)
{//随机读写
bool k=1;
file* fp,*fp1;
char ch;
int i=0;
if（（fp1=fopen（"textfile.txt","w"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
if（（fp=fopen（"codefile.txt","r"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
while（ch!=eof)
{
while（i<n&&ch!=eof)
{
for（ int j=0;i<n&&j<（signed )strlen（p1[i+1]);j++)
{
ch=fgetc（fp);
if（ch!=p1[i+1][j]&&ch!=eof)
{
if（ch!='1'&&ch!='0')
{
fputc（ch,fp1);
i=0;
j=0;
k=0;
break;
}
fseek（fp,-（j+1),1);
i++;
j=0;
k=0;
break;
}
}
if（k==1&&ch!=eof)
{
fputc（r2[i].c ,fp1);
i=0;
}
k=1;
}
}
fclose（fp);
fclose（fp1);
}
void print（)
{
int i=1;
char ch;
file *fp,*fp1;
if（（fp=fopen（"codefile.txt","r"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
if（（fp1=fopen（"codeprin.txt","w"))==null)
{
cout << "can't open this file."<<endl;
exit（0);
}
while（（ch=fgetc（fp))!=eof)
{
cout <<ch;
fputc（ch,fp1);
if（i%50==0)
{
cout <<endl;
}
i++;
}
cout <<endl;
fclose（fp);
fclose（fp1);
}
htnode findboot（huffmantree ht,int n)
{
for（int i=0; i<（2*n-1)&&ht[i].parent!=0; i++);
return ht[i];
}
void printspace（int i,file *fp1)
{
for（int j=0;j<i;j++)
{
cout<<" ";
fputc（' ', fp1);
}
}
void treeprinting（htnode ht, huffmantree h, int i, file* fp)
{
if（ht.weight !=0)
{
if（ht.lchild )
treeprinting（h[ht.lchild],h,i+2,fp) ;
printspace（i,fp);
cout<<ht.weight <<endl;
fprintf（fp,"%d", ht.weight );
fputc（'\n',fp);
if（ht.rchild)
treeprinting（h[ht.rchild],h,i+2,fp) ;
}
}
