#include "iostream.h"
#include "stdlib.h"
#include "fstream.h"
#include "iomanip.h"
struct word{
	char x1;
    int x2;
};
struct LNode{
	word data;
	LNode* next;};
struct Node
	{
		int q1;
		int ha;
		Node *parent;
        Node *right;
        Node *left;
        Node *next;
		char c;
	};

void Insert(LNode*&HL,word& item)//插入函數(shù)
{
LNode* newptr;
newptr=new LNode;
if(newptr==NULL)
{
	cerr<<"Memory allocation failare!"<<endl;
	exit(1);
}
newptr->data=item;
LNode* cp;
LNode* ap;
ap=NULL;cp=HL;
while(cp!=NULL)
if(item.x2<=cp->data.x2)
break;
else
{
	ap=cp;
	cp=cp->next;
}
if(ap==NULL)
{
	newptr->next=HL;
	HL=newptr;
}
else
{
	newptr->next=cp;
	ap->next=newptr;
}
}
void LinkSort(word a[],int n)//排序函數(shù)
{
	LNode* head=NULL;
    int o;
    for(o=1;o<=n;o++)
	Insert(head,a[o]);    //在此插入一個(gè)鏈表用來(lái)記錄標(biāo)號(hào)
	LNode* p=head;
	  o=1;
		while(p!=NULL)
		{
		a[o]=p->data;
		p=p->next;
		o=o+1;
		}       
}
void main()//主函數(shù)
{
long int i=1,j;
	char ch,xuan;
    word a[100];
	cout<<"請(qǐng)確定在當(dāng)前目錄下有需要編碼的文字集（英文）“wr1.txt”文件存在"<<endl;
	cout<<"y:繼續(xù)  n:退出(y/n) :";cin>>xuan;
	if(xuan=='y')
		goto g1;
	if(xuan=='n')
		exit(1);
g1:	fstream of1("wr1.txt",ios::in|ios::out);
	if (!of1){
		cout<<"file not open!";
		exit(1);
	}
	of1.get(ch);//開(kāi)始統(tǒng)計(jì)各字符出現(xiàn)的頻率
	a[1].x1=ch;a[1].x2=1;
	of1.get(ch);
while(ch!=EOF)
{
for(j=1;j<=i;j++)
{
	if(a[j].x1==ch)
{a[j].x2++;break;}

}
if(j>i)
{a[i+1].x1=ch;a[i+1].x2=1;i=i+1;}
of1.get(ch);
}
of1.close();//統(tǒng)計(jì)結(jié)束
LinkSort(a,i);
cout<<endl<<"各字符對(duì)應(yīng)的頻率："<<endl;
 for(int k=1;k<=i;k++)	 
 { cout<<a[k].x1<<"："<<a[k].x2<<"  ";if(k%10==0)cout<<endl;}
cout<<endl<<endl;
cout<<"各個(gè)字符對(duì)應(yīng)的哈弗曼編碼:"<<endl;
Node *h,*w,*h1,*h2,*h3,*h4,*h5,*gen;
h=h1=new Node;
for(int f=1;f<=i;f++)
{
	w=new Node;
	h->left=NULL;
	w->q1=a[f].x2; w->c=a[f].x1;
	 h->next=w;  h->right=w; h=w;  
	 h->parent=NULL; h->ha=0;
}
h->left=NULL;
h->next=NULL;h->right=NULL;
h5=h4=h2=h=h1->next;
Node *n;
while(h->next!=NULL)
{   
	n=new Node;
	n->q1=(h->q1+h->next->q1);
	n->left=h; n->right=h->next; n->next=NULL; n->ha=0; n->c='@';
	n->parent=NULL; h->ha=0; h->next->ha=1;
	h->parent=n; h->next->parent=n;
	h=h->next->next;

	Node *cp1;//插入剛才的新產(chǎn)生的結(jié)點(diǎn):n
    Node *ap1;
	ap1=NULL;
	cp1=h;
	while(cp1!=NULL)
	
		if(n->q1<=cp1->q1)
			break;
		else
		{
			ap1=cp1;
			cp1=cp1->next;
		}
		if(ap1==NULL)
		{
			n->next=h;
			h=n;
		}
		else
		{
			n->next=cp1;
			ap1->next=n;
		}
		
}
h->parent=NULL;
gen=h;

int y[100];
i=1;
while(h2!=NULL)
{int y1;
h3=h2;
y1=1;

while(h3->parent!=NULL)
{
	y[y1]=h3->ha;
	h3=h3->parent;
	y1++;
}
cout<<a[i].x1<<":";
for(int y2=y1-1;y2>=1;y2--)
cout<<y[y2];cout<<"  ";
if(i%5==0)cout<<endl;
h2=h2->right;
i=i+1;
}
cout<<endl<<endl;
cout<<"對(duì)應(yīng)wr1文字集的哈夫曼編碼并將其保存在當(dāng)前目錄wr2.txt文件中:"<<endl;
char ch2;
fstream of3("wr2.txt",ios::in|ios::out);                                    
fstream of2("wr1.txt",ios::in);
		of2.get(ch2);
		while(ch2!=EOF)
		{
			   while(h4!=NULL)
			   {
				  if(h4->c==ch2)
				  {
					  int y[100];

                      int y1;
                      h3=h4;
                      y1=1;
                      while(h3->parent!=NULL)
					 {
	                    y[y1]=h3->ha;
           	            h3=h3->parent;
	                    y1++;
					  }
                      for(int y2=y1-1;y2>=1;y2--)
                      {
					//	  cout<<y[y2];
					  int ch5;
		              ch5=y[y2];
					  of3<<ch5<<" ";
					  }
					  break;
				  }
				  else 
				   h4=h4->right;
			}			
			of2.get(ch2);
			h4=h5;
		}
		of3<<2<<" ";
		of3.close();
	of2.close();
	char xuan2;
	cout<<"是否輸出文字集的哈夫曼編碼："<<endl;
	cout<<"y:是  n:否(y/n)";cin>>xuan2;
	if(xuan2=='y')goto g3;
	if(xuan2=='n')goto g4;
g3:	of3.open("wr2.txt",ios::in);
		int ch1;
        of3>>ch1;//輸出文字集的哈夫曼編碼
	while(ch1!=2)
		{
		cout<<ch1;
		of3>>ch1;
		}of3.close();
	cout<<endl<<endl;
g4:	cout<<"是否需要對(duì)剛才的文字集的編碼進(jìn)行譯碼："<<endl;//對(duì)哈夫曼編碼進(jìn)行編譯
	char xuan1;
	cout<<"y:繼續(xù)  n:退出(y/n) :";cin>>xuan1;
	if(xuan1=='y')
		goto g2;
	if(xuan1=='n')
		exit(0);
g2:	of3.open("wr2.txt",ios::in);
	cout<<endl<<"對(duì)應(yīng)的文字集為："<<endl;
	int ch6;
    of3>>ch6;
while(ch6!=2)
	{
	if(h->c=='@')
		{
		    if(ch6==0)
		     h=h->left;
		    if(ch6==1)
			 h=h->right;
		}
	if(h->c!='@')
		{
			cout<<h->c;
		    h=gen;
		}                   
    of3>>ch6;
	}
		cout<<endl;
}