#include<iostream>
#include<fstream>
using namespace std;
const int n = 100;//叶子结点数
typedef struct {
float weight;//权值
int lchild, rchild, parent;//左、右孩子及双亲指针
}HTNode;//树中结点类型
typedef struct {
char ch;//存放编码字符
char bits[n + 1];//存放编码位串
int len;//编码长度
}CodeNode;
char str[27];//存储字符
int cnt[27];//字符对应的权值
class Huffman {
public:
Huffman(char st[]);//构造函数
~Huffman() { delete[] HT; }//析构函数释放空间
void ChuffmanTree(int cnt[], char str[]);//产生哈夫曼树结点表HT
void select(int, int &s1, int &s2);//选择parent为0且权值最小的两个根结点
void HuffmanEncoding();//根据需要编码的字符串和HC,产生编码文件
void coding(char *str);//求哈夫曼编码表HC
void decode();//将编码文件译码输出
private:
void jsq(char *s, int cnt[], char str[]);//统计字符串中各类字母的个数以及字符的种类和权值
int num;//字符种类
HTNode *HT;//哈夫曼树结点表指针
CodeNode *HC;//哈夫曼编码表指针
};
//构造函数
Huffman::Huffman(char st[])
{
//构造函数,分配树控件并初始化
//调用jsq成员函数，统计字符串中各种字母的个数以及字符的种数
//配置类计数器num，把权值存入cnt数组，把对应的字母寻如str数组
jsq(st, cnt, str); //计算num,cnt[],str[]
HC = new CodeNode[num + 1];//申请编码动态存储空间
HT = new HTNode[2 * num];//申请结点动态存储空间
for (int i=1;i<2 * num - 1;i++)
HT[i].lchild = HT[i].rchild = HT[i].parent = 0; //初始化HT
}
//统计函数
void Huffman::jsq(char *s, int cnt[], char str[])
{//统计字符串中各种字母的个数以及字符的种类
//输入:字符串S
//输出:cnt权值数组str存入对应的字母
//num=0；//字符种类置初值
char *p;
int i, j, k;
int temp[27];
for (i = 1;i <= 26;i++)
temp[i] = 0;
for (p = s;*p != 0;p++)
{//统计各种字符的个数
if (*p > 'A' &&*p <= 'Z') {
k = *p - 64;
temp[k]++;
}
}
j = 0;
for (i = 1, j = 0;i <= 26;i++)
if (temp[i] != 0) {
j++;
str[j] = i + 64;
cnt[j] = temp[i];
}
num = j;
}
//选择parent为0且权值最小的两个根结点
void Huffman::select(int k, int &s1, int &s2)
{//在HT[1..k]中选择parent为0且权值最小的两个根结点
//其序号分别存储到s1和s2指向的对应变量中
int i, j;
float min1 = 101;
for (i = 1;i <= k;i++)
if (HT[i].weight < min1&&HT[i].parent == 0) {
j = i;min1 = HT[i].weight;
}
s1 = j;min1 = 32767;
for (i = 1;i <= k;i++)
if (HT[i].weight < min1&&HT[i].parent == 0 && i != s1) {
j = i;
min1 = HT[i].weight;
}
s2 = j;
}
//构造哈夫曼树
void Huffman::ChuffmanTree(int cnt[], char str[])
{//构造哈夫曼树HT,cnt中存放每类字符在电文中的出现频率
//str中存放点蚊不同类的字符
int i, s1, s2;
for (i = 1;i <= num;i++) //输入num个种类的叶结点的权值
HT[i].weight = cnt[i];
for (i = num + 1;i < 2 * num - 1;i++)
{//在HT[1...i-1]中选择parent为0且权值最小的两个根结点，
//其序号分别为s1和s2
select(i - 1, s1, s2);
HT[s1].parent = i;HT[s2].parent = i;
HT[i].lchild = s1;HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;//权值之和
}
for (i = 0;i < num;i++)//输入字符集中的字符
HC[i].ch = str[i];
i = 1;
while (i <= num){
printf("字符%c,次数为：%d\n", HC[i].ch, cnt[i]);
i++;
}
}//求哈夫曼编码表
void Huffman::HuffmanEncoding()
{//根据哈夫曼树HT求哈法曼编码表HC
int c, p, i;//c和p分别指示HT中孩子和双亲的位置
char cd[n + 1];//临时存放编码串
int start;//指示编码在cd中的起始位置
cd[num] = '\0';//最后一行放上串结束符
for (i = 1;i <= num;i++) {
start = num;//初始位置
c = i;//从叶结点HT[i]开始上溯
while (p = HT[c].parent>0) {//上溯到ht[c]是根为止
//若HT[c]是HT[p]的左孩子，则生成代码0,否则生成代码1
cd[--start] = (HT[p].lchild == c) ? '0' : '1';
c = p;
}//end of while
//strcpy(HT[i].bits, &cd[start]);
HC[i].len = num - start;
}//end of for
}
//编码文件
void Huffman::coding(char *str)
{//对str所代表的字符串进行编码，并写入文件
int i, j;
ofstream in;//建立输出流 in
in.open("codefile.txt");//建立输出流in和codefile.txt之间的关联
while (*str) {
for (i = 1;i <= num;i++)
if (HC[i].ch == *str) {
for (j = 0;j < HC[i].len;j++)
in << HC[i].bits[j];//使用输出流in将字符串流向文件
}
str++;
}
in.close();
}
//将编码文件译码并输出原码
void Huffman::decode()
{//输出代码文件codefile.txt的译码
static char cd[n + 1];
int i, j, k = 0, cjs;
ifstream out;//建立输入流out
out.open("codefile.txt");//建立输入流out和codefile.txt之间的关联
while (!out.eof())
{
cjs = 0;
for (i = 0;i < num && cjs == 0 && !out.eof();i++)
{
cd[i] = ' ';cd[i + 1] = '\0';
out.get(cd[i]);//将文件内容读入数组cd
for (j = 1;j <= num;j++)
if (strcmp(HC[j].bits, cd) == 0)
{
cout << HC[j].ch;//输出译码后的内容
k++;
cjs = 1;
}
}
}
cout << endl;
}
半夏丶
Myrat
