main.cpp

对输入数字计算出Huffman树并输出

#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct TREE
{
	int row;
	int data;//数值 
	int Check;//判断是否已经写入
	TREE * L;
	TREE * R;//左右子树

};



list<TREE> Huf;//存储
TREE Temp;//中间变量 

vector<TREE> Save;//存储
vector<TREE> Mid;//中间变量

void Operate()//开始运算
{
	list<TREE>::iterator t1;
	list<TREE>::iterator t2;
	list<TREE>::iterator t;

	int Min=99999;
	for(t=Huf.begin();t!=Huf.end();t++)
		if(t->Check==0&&t->data<Min)
		{
			t1=t;
			Min=t->data;
		}
		t1->Check=1;
		Temp.L=&(*t1);//找出第一个最小
	
    Min=99999;
	for(t=Huf.begin();t!=Huf.end();t++)
		if(t->Check==0&&t->data<Min)
		{
			t2=t;
			Min=t->data;
		}
		t2->Check=1;
		Temp.R=&(*t2);//找出第二个最小
		
		Temp.data=t1->data+t2->data;
		if(t1->row>=t2->row)
			Temp.row=t1->row+1;
		else 
			Temp.row=t2->row+1;

		/*cout<<t1->data<<' '<<t2->data<<' '<<Temp.data<<endl;*/

		Huf.push_back(Temp);//求和并建立新结点


		/*cout<<t->data<<' ';
		cout<<t->L->data<<' '<<t->R->data<<' '<<endl;*/

	return;
}



void Print()//输出
{
	Mid.clear();
	/*cout<<Save.size()<<endl;*/
	for(vector<TREE>::iterator t=Save.begin();t!=Save.end();t++)
	{
		if((*t).L)
		{
			cout<<(*t).L->data<<','<<(*t).R->data<<"("<<(*t).data<<")"<<' ';
			Mid.push_back(*((*t).L));
			Mid.push_back(*((*t).R));
		
		}
	}//输出结果
	Save=Mid;
	cout<<endl;
	return;
}

int main()
{

	Temp.Check=0;
	Temp.row=1;
	Temp.L=NULL;
	Temp.R=NULL;	

cout<<"请输入数量"<<endl;
	int n;
	cin>>n;
cout<<"按顺序分别输入大小"<<endl;
	for(int i=1;i<=n;i++)
	{
		cin>>Temp.data;
		Huf.push_back(Temp);
	}//初始化 

	//for(list<TREE>::iterator k=Huf.begin();k!=Huf.end();k++)
//cout<<k->data<<' '<<k->Check<<endl;

	for(int i=1;i<=n-1;i++)
		Operate();//开始运算

	//for(list<TREE>::iterator k=Huf.begin();k!=Huf.end();k++)
//cout<<k->data<<' '<<k->Check<<endl;

	list<TREE>::iterator k=Huf.end();
	--k;
	/*cout<<k->row<<endl;*/
	cout<<k->data<<endl;//输出最上层

	Save.push_back((*k));
	for(int i=1;i<=k->row-1;i++)//按层输出
		Print();


	return 0;
}