// huffman2.cpp : 定義控制臺應(yīng)用程序的入口點。
//

// hafumen.cpp : 定義控制臺應(yīng)用程序的入口點。
//

#include "stdafx.h"
#include <iostream>
#include<string>
#define Null 0
#define MAX 100
using namespace std;


class QNode
{
private:
	char ch;
	int weight;
public:
	QNode *Parent,*LChild,*RChild,*next;
	int flag;
public:
	QNode();
	QNode(char _ch,int _weight);
	void SetQNode(int _weight);
	char GetChar(void);
	int GetWeight(void);

};

QNode::QNode()
{
	ch=Null;
	weight=0;
	Parent=Null;
	RChild=Null;
	LChild=Null;
	next=Null;
	flag=0;
}

QNode::QNode(char _ch,int _weight)
{
	ch=_ch;
	weight=_weight;
	Parent=Null;
	RChild=Null;
	LChild=Null;
	next=Null;
	flag=0;

}
void QNode::SetQNode(int _weight)
{
  weight=_weight;
}

char QNode::GetChar()
{
	return ch;
}

int QNode::GetWeight()
{
	return weight;
}


class HuffQueue
{
private:
	QNode *L,*Rear;
	int count;
public:

	HuffQueue();//初始化一個huff隊列
	~HuffQueue();//析構(gòu)函數(shù)
	void InSertHuff( char _ch,int _weight);//插入一個huff結(jié)點
	void InsertHuff();
	void CreatHuffTree();//創(chuàng)建huff樹
	void PrintHuffCode();//輸出huff編碼
	void Printhufflength();//輸出指令平均字長
	QNode *FindMin(void);
	



};

HuffQueue::HuffQueue()
{
	L=new QNode();
	Rear=L;
	count=0;
}

HuffQueue::~HuffQueue()
{ while(L!=Null)
	{
		QNode *P;
		P=L;
		L=L->next;
		delete(P);
		count--;
	}
}

void HuffQueue::InSertHuff(char _ch, int _weight)
{
	QNode *temp=new QNode(_ch,_weight);
	Rear->next=temp;
	Rear=temp;
	count++;
}
void HuffQueue::InsertHuff()
{
	QNode *temp=new QNode();
	Rear->next=temp;
	Rear=temp;
	
}

QNode * HuffQueue::FindMin()
{
	QNode *temp1,*temp2;
	int s=MAX;
	temp1=L->next;
	temp2=temp1;
	while(temp1!=Rear)
	{
		if(s>temp1->GetWeight()&&temp1->Parent ==Null)
		{
			s=temp1->GetWeight();
			temp2=temp1;
			temp1=temp1->next;
		}
		else
			temp1=temp1->next;

	}
	return temp2;
}

void HuffQueue::CreatHuffTree()
{
	 QNode *s1,*s2;
	  int w1,w2,w;
	 for(int i=0;i<count-1;i++)
	 {   
		
		  InsertHuff();
		 s1=FindMin();
		 s1->Parent =Rear;
		 w1=s1->GetWeight();
	     s2=FindMin();
	     s2->Parent=Rear;
		 w2=s2->GetWeight();
	     w=w1+w2;
	     Rear->SetQNode(w);
		 Rear->LChild =s1;
		 Rear->RChild =s2;



  }
}

void HuffQueue::PrintHuffCode()
{
	QNode *PP;
	string S1=" ";
	string S2;
	PP=Rear;
	int Len=0;
	int Len2=0;
	int aLen=0;
	while(PP)
	{
		if(PP->flag ==0)
		{
			PP->flag =1;
			if(PP->LChild!=Null)
			{
				PP=PP->LChild ;S2="0";
				S1+=S2;

			}
			else if(PP->RChild ==Null)
			{
				cout<<PP->GetChar()<<endl;
				cout<<"   "<<S1<<endl;
				Len2=S1.length()-1;
				int tweight;
				tweight=PP->GetWeight();
				aLen+=Len2*tweight;
				

			}
		}
		else if(PP->flag ==1)
		{
			PP->flag =2;
			if(PP->RChild !=Null)
			{
				PP=PP->RChild ;
				S2="1";
				S1+=S2;
			}
			
		}
		else
		{
			PP->flag=0;
			PP=PP->Parent;
		    Len=S1.length ();
			S1=S1.substr(0,Len-1); 
		}
	}
	cout<<"average"<<aLen<<endl;
}





int _tmain(int argc, _TCHAR* argv[])
{
	char ch;
	int weight;
	HuffQueue Q;
	
	for( ; ;)
	{
		cout<<"Input the char,@ exit"<<endl;
		cin>>ch;
		if(ch=='@')
			break;
		else
			
		{
			cout<<"Input the weight"<<endl;
			cin>>weight;
		   Q.InSertHuff( ch,weight);
			

		}
	}
		Q.CreatHuffTree();
		Q.PrintHuffCode ();


	int x;
	cin>>x;
	return 0;
}