1022_ハフマンツリーとデコード

ハフマン符号化と復号
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
総提出:573試験合格:213
試合の説明
電文に含まれる文字セットが{A,C,I,M,N,P,T,U}であることが知られており,対応する重み値を入力し,文字セットをハフマン符号化し,電文のハフマン符号化と復号化を完了する.
入力
合計3行:
第1の動作は、文字セット{A,C,I,M,N,P,T,U}の重み値に対応する
第2の動作の文字列が表す電文(長さは1000を超えない).
第3の挙動の1段の電文のハフマン符号化.
しゅつりょく
合計10行:
最初の8行の各文字の符号化;
9行目は2行目の入力に対応するハフマン符号化である.
10行目は3行目の入力に対応する電文です.
サンプル入力
1 2 3 4 5 6 7 8 NUPTICPCACM 1111011111100
サンプル出力
A: 11110 C: 11111 I: 1110 M: 100 N: 101 P: 110 T: 00 U: 01 1010111000111011111110111111111011111100 ACM
ヒント
2012.4.11更新
テーマソース
NUPT ACM
機能は実装されており、VS上でコンパイルは通過したが、g++コンパイラのコンパイルに失敗した.理由(for each)
コードの入力:

#include <iostream>
#include <list>
#include <string>
#include <cctype>
using namespace std;

struct BTnode
{
	char name=' ';
	int Weight;
	BTnode *LChild = NULL;
	BTnode *RChild = NULL;
	string code="";
};

bool Comp1(const BTnode *node1, const BTnode *node2);
bool Comp2(const BTnode *node1, const BTnode *node2);
void PreOrder(BTnode * root, list<BTnode *> & nList);

int main()
{
	char ch[8] = { 'A','C','I','M','N','P','T','U' };
	list<BTnode *> NodeList;//      
	for (int i = 0; i < 8; i++)//   ,   8  ，      
	{
		BTnode *node = new BTnode();
		node->name = ch[i];
		cin >> node->Weight;
		NodeList.push_front(node);
	}

	string line2;//   
	cin >> line2;

	string line3;//   
	cin >> line3;

	NodeList.sort(Comp1);//     
	while (NodeList.size() != 1)//      
	{
		BTnode *FirstNode = NodeList.front();
		NodeList.pop_front();
		BTnode *SecondNode = NodeList.front();
		NodeList.pop_front();
		
		BTnode *NewNode = new BTnode;
		NewNode->Weight = FirstNode->Weight + SecondNode->Weight;
		NewNode->LChild = FirstNode;
		NewNode->RChild = SecondNode;

		NodeList.push_back(NewNode);
		NodeList.sort(Comp1);
	}
	
	BTnode *root = NodeList.front();//root     
	NodeList.clear();//    ，      code   

	PreOrder(root, NodeList);//        ，       list
	
	NodeList.sort(Comp2);//     ，    

	for each (BTnode* node in NodeList)//   8 
	{
		cout << node->name << ": " << node->code << endl;
	}
	
	
	for each (char a in line2)//   9 
	{
		for each (BTnode* node in NodeList)
		{
			if (node->name == a)
				cout << node->code;
		}
	}
	cout << endl;

	BTnode *node = root;//   10 
	for each (char a in line3)
	{
		if (a == '0')
			node = node->LChild;
		else
			node = node->RChild;

		if (isalpha(node->name))
		{
			cout << node->name;
			node = root;
		}
	}
	cout << endl;
	
	return 0;
}

bool Comp1(const BTnode *node1, const BTnode *node2)//      
{
	return node1->Weight < node2->Weight;
}

bool Comp2(const BTnode *node1, const BTnode *node2)
{
	return node1->name < node2->name;
}

void PreOrder(BTnode * root, list<BTnode *> & nList)
{
	if (root == NULL)
		return;

	if (isalpha(root->name))
		nList.push_front(root);

	if (root->LChild)
	{
		root->LChild->code = root->code + "0";
		PreOrder(root->LChild, nList);
	}
	if (root->RChild)
	{
		root->RChild->code = root->code + "1";
		PreOrder(root->RChild, nList);
	}
}