#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
struct HTNode
{
int weight, letter, lchild, rchild;
HTNode(){}
HTNode( int a, int b, int c, int d ) :weight(a), letter(b), lchild(c), rchild(d) {}
};
struct Info
{
int num, lett, id;
Info();
Info( int a, int c, int b ): num(a), lett(c), id(b) {}
};
bool operator< ( Info const& a, Info const& b )
{
return a.num> b.num;
}
int num[26], len= 0, root;
char str[1000];
string code[26];
vector<HTNode> ht;
priority_queue<Info> info;
void buildtree();
void codeht(int,string);
void decode( int,int);
void input() // 輸入過程
{
printf("注意: 該程序只處理大寫字母， 其它字符不予處理\n");
printf("請輸入文本， 在最后另起一行按 F6 結束輸入:\n");
char ch;
memset( num, 0, sizeof(num) );
while( scanf("%c",&ch)!= EOF )
if( ch>= 'A' && ch<= 'Z' ) num[ch- 'A']++;
printf("各字母個數為:\n");
for(int i= 0; i< 26; ++i )
if( num[i] ) printf("%c %d\n", i+ 'A', num[i] );
}
void test()
{
input();
buildtree();
codeht( root, "" );
printf("各字母的哈夫曼編碼為:\n\n");
for( int i= 0; i< 26; ++i )
if( num[i] ) printf("%c %s\n", i+ 'A', code[i].c_str() );
printf("\n\n\n請輸入你要解碼的字符串，不能有空格，并且輸入合法\n");
scanf("%s", str );
printf("解碼后為:\n\n");
decode(0, root );
printf("\n\n\n");
}
void codeht( int i, string s ) // 編碼過程
{
if( ht[i].lchild== -1 )
{
code[ ht[i].letter ]= s;
}
else
{
codeht( ht[i].lchild, s+ '0' );
codeht( ht[i].rchild, s+ '1' );
}
}
void decode( int i, int j ) // 解碼過程
{
if( ht[j].lchild== -1 && ht[j].rchild== -1 )
{
printf("%c", ht[j].letter+ 'A' );
if( str[i] ) decode( i, root );
}
else if( !str[i] ) return;
else if( str[i]== '0' ) decode( i+ 1, ht[j].lchild );
else if( str[i]== '1' ) decode( i+ 1, ht[j].rchild );
}
void buildtree() // 建樹過程
{
len= 0;
for( int i= 0; i< 26; ++i )
if( num[i] )
{
ht.push_back( HTNode( num[i], i, -1, -1 ) );
info.push( Info( num[i], i, len++ ) );
}
if( info.size()== 1 ) { root= 0; return; }
Info a= info.top(); info.pop();
Info b= info.top(); info.pop();
info.push( Info( a.num+ b.num, -1, len++ ) );
ht.push_back( HTNode( a.num+ b.num, -1, a.id, b.id ) );
while( info.size()> 1 )
{
Info a= info.top(); info.pop();
Info b= info.top(); info.pop();
info.push( Info( a.num+ b.num, -1, len++ ) );
ht.push_back( HTNode( a.num+ b.num, -1, a.id, b.id ) );
}
root= info.top().id;
}
int main()
{
test();
system("pause");
return 0;
}
/*
7 5 2 4 6
*/
posted on 2008-11-12 21:03
Darren 閱讀(300)
評論(0) 編輯 收藏 引用