参照严蔚敏教材<<数据结构>>第2版
描述
输入一串字符串,根据给定的字符串中字符出现的频率建立相应哈夫曼树,构造哈夫曼编码表,在此基础上可以对待压缩文件进行压缩(即编码),同时可以对压缩后的二进制编码文件进行解压(即译码)。
输入
多组数据,每组数据一行,为一个字符串(只考虑26个小写字母即可)。当输入字符串为“0”时,输入结束。
输出
每组数据输出2n+3行(n为输入串中字符类别的个数)。第一行为统计出来的字符出现频率(只输出存在的字符,格式为:字符:频度),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态(形如教材139页表5.2(b),一行当中的数据用空格分隔)。第2n+1行为每个字符的哈夫曼编码(只输出存在的字符,格式为:字符:编码),每两组字符之间用一个空格分隔,字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串,第2n+3行为解码后的字符串(与输入的字符串相同)
输入样例
aaaaaaabbbbbccdddd
aabccc
0
输出样例
a:7 b:5 c:2 d:4
1 7 7 0 0
2 5 6 0 0
3 2 5 0 0
4 4 5 0 0
5 6 6 3 4
6 11 7 2 5
7 18 0 1 6
a:0 b:10 c:110 d:111
00000001010101010110110111111111111
aaaaaaabbbbbccdddd
a:2 b:1 c:3
1 2 4 0 0
2 1 4 0 0
3 3 5 0 0
4 3 5 2 1
5 6 0 3 4
a:11 b:10 c:0
111110000
aabccc
算法实现
#include<iostream>
#include<map>
#include<string>
#include<stdio.h>
#include<memory.h>
using namespace std;
typedef struct{
char c;
int weight;
int lchild,rchild,parent;
}HuffmanNode,*HuffmanTree;
typedef struct {
char ch;
char *pHC;
}HuffCodeNode;
typedef HuffCodeNode *HuffmanCode;
void Select(HuffmanTree &HT, int index, int &s1, int &s2)
{
int i;
for (i = 1; i <= index; i++)
if (HT[i].parent == 0)
break;
s1 = i;
for (int j = s1 + 1; j <= index; j++)
if (HT[j].parent == 0 && HT[j].weight < HT[s1].weight)
s1 = j;
int k;
for (k = 1; k <= index; k++)
if (HT[k].parent == 0 && k != s1)
break;
s2 = k;
for (int j = s2 + 1; j <= index; j++)
if (HT[j].parent == 0 && HT[j].weight < HT[s2].weight&&j != s1)
s2 = j;
}
int CreateHuffmanTree(HuffmanTree& HT, string str)
{
map<char,int> mymap;
for(int i=0;i<str.length();i++)
mymap.find(str[i]) != mymap.end() ? mymap[str[i]]++ : mymap[str[i]] = 1;
for(auto it=mymap.begin();it!=mymap.end();it++)
cout<<it->first<<":"<<it->second<<" ";
cout<<endl;
int n = mymap.size();
HT=new HuffmanNode[2*n];
for(int i=0;i<2*n;i++)
{
HT[i].c='\0';
HT[i].weight=0;
HT[i].lchild=HT[i].rchild=0;
HT[i].parent=0;
}
map<char,int>::iterator it=mymap.begin();
for(int i=1;i<=n, it!=mymap.end();i++,it++)
{
HT[i].c=it->first;
HT[i].weight=it->second;
}
for(int i=n+1;i<2*n;i++)
{
int s1,s2;
Select(HT, i-1, s1, s2);
HT[i].lchild=s1;HT[i].rchild=s2;
HT[s2].parent=i;
HT[s1].parent=i;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
return n;
}
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
HC = new HuffCodeNode[n + 1];
char *dc = new char[n];
dc[n - 1] = '\0';
int start;
for (int i = 1; i <= n; i++)
{
HC[i].ch = HT[i].c;
start = n - 1;
int c = i, f = HT[c].parent;
while (f)
{
if (HT[f].lchild == c)
dc[--start] = '0';
else
dc[--start] = '1';
c = f;
f = HT[f].parent;
}
int m = n - start;
HC[i].pHC = new char[m];
memcpy(HC[i].pHC, dc + start, m);
}
}
void HuffmanPrintInfo(HuffmanTree& HT, int n)
{
for (int i = 1; i < 2 * n; i++)
{
cout << i <<' '<< HT[i].weight << ' ' << HT[i].parent
<< ' ' << HT[i].lchild << ' ' << HT[i].rchild << endl;
}
}
void HuffmanCodePrint(HuffmanCode &HC, int n)
{
for (int i = 1; i <= n; i++)
cout << HC[i].ch<<":"<<HC[i].pHC <<" ";
cout<<endl;
}
string EncodeStr(HuffmanCode &HC, string str, int n)
{
string res="";
for(int i=0;i<str.length();i++)
{
for(int j=1;j<=n;j++)
{
if(str[i]==HC[j].ch)
{
res+=HC[j].pHC;
break;
}
}
}
return res;
}
string DeCodeStr(HuffmanTree HT, int n, string code)
{
string res = "";
char ch;
int start = 0;
int i = 0;
while ((ch=code[i++])!='\0')
{
if (ch == '0')
start = HT[2 * n - 1].lchild;
else if (ch == '1')
start = HT[2 * n - 1].rchild;
while (HT[start].lchild != 0)
{
if ((ch = code[i++]) == '\0') return res;
if (ch == '0')
start = HT[start].lchild;
else if (ch == '1')
start = HT[start].rchild;
}
res += HT[start].c;
}
return res;
}
int main()
{
string str;
cin >> str;
while (str != "0")
{
HuffmanTree HT;
HuffmanCode HC;
int n = CreateHuffmanTree(HT, str);
CreateHuffmanCode(HT, HC, n);
HuffmanPrintInfo(HT, n);
HuffmanCodePrint(HC, n);
string encode = EncodeStr(HC, str, n);
cout << encode << endl;
string decode = DeCodeStr(HT, n, encode);
cout << decode << endl;
cin >> str;
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)