3、哈夫曼编码/译码系统（树应用）
3、哈夫曼编码/译码系统（树应用）
[问题描述]
利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。
[实现提示]
在本例中设置发送者和接受者两个功能，
发送者的功能包括：
①输入待传送的字符信息；
②统计字符信息中出现的字符种类数和各字符出现的次数（频率）；
②根据字符的种类数和各自出现的次数建立哈夫曼树；
③利用以上哈夫曼树求出各字符的哈夫曼编码；
④将字符信息转换成对应的编码信息进行传送。
接受者的功能包括：
①接收发送者传送来的编码信息；
②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。
从以上分析可发现，在本例中的主要算法有三个：
（1）哈夫曼树的建立；
（2）哈夫曼编码的生成；
（3）对编码信息的翻译。
一、算法设计
1.哈夫曼树的建立相对来说比较容易，每一轮选择权重最小的两个结点加入。而且采用的是结构体数组的形式，用起来比链表要方便许多。编码的时候是从叶子结点到根结点逐步向上求取的，并将得到的编码保存在数组当中。而译码的过程则是从根结点开始，逐个读取字符，读到1就找左孩子，读到0就找右孩子，直到当前结点既没有左孩子也没有右孩子，就输出当前结点存储的结点值。重新找到根结点进入下一轮的循环，知道字符串的完结，任务结束。由于刚开始思维比较局限，想要统计字符串中不同字符出现的次数作为权重，并且按照由小到大的顺序排序，结果直接做成了只能够偶辨别英文字母大小写的系统，其他的一概不行。各个函数之间调用关系如下所示：
|
main() |
|
HuffmanTree() |
2.本程序中包含2个模块
(1)主函数：int main()；
(2)构造一棵哈夫曼树：void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)；
3.元素类型、结点类型和指针类型
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
intbit[MAXBIT];
intstart;
} HCodeType; /* 编码结构体 */
typedef struct Hnode
{
charzifu = NULL;
intweight = 0;
intparent = -1;
intlchild = -1;
intrchild = -1;
} HNodeType; /* 结点结构体 */
二、实验测试
源代码：
#pragma warning(disable:4996)
#include<stdio.h>
#include<cstdio>
#include<string>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<math.h>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<list>
#include<fstream>
#include<ostream>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct Hnode
{
char zifu = NULL;
int weight = 0;
int parent = -1;
int lchild = -1;
int rchild = -1;
} HNodeType; /* 结点结构体 */
/* 构造一棵哈夫曼树 */
void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
for (i = 0; i<n - 1; i++)/* 循环构造 Huffman 树 */
{
m1 = m2 = MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1 = x2 = 0;
for (j = 0; j<n + i; j++)/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
{
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
{
m2 = HuffNode[j].weight;
x2 = j;
}
}
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n + i;
HuffNode[x2].parent = n + i;
HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n + i].lchild = x1;
HuffNode[n + i].rchild = x2;
}
}
int main(void)
{
system("color 57");
while (1)
{
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p;
/*---------------------------------------------------*/
string s;
printf("请输入需要编码的字符串(暂且只支持大小写英文编码，只可包含英文字母不可有空格):
");
cin >> s;
int ans[27] = { 0 };
int bns[27] = { 0 };
int l = s.length();
int n = 0;/*统计共有多少个不同字母*/
for (int i = 0; i < l; i++)/*统计字符串中出现的字母与其频数*/
{
for (char p = 'a'; p <= 'z'; p++)
{
if (s[i] == p)
{
ans[p - 'a']++;
}
}
for (char q = 'A'; q <= 'Z'; q++)
{
if (s[i] == q)
{
bns[q - 'A']++;
}
}
}
for (char p = 'a'; p <= 'z'; p++)
{
if (ans[p - 'a'] != 0)
{
cout << p << ":" << ans[p - 'a'] << endl;
n++;
}
}
for (char q = 'A'; q <= 'Z'; q++)
{
if (bns[q - 'A'] != 0)
{
cout << q << ":" << bns[q - 'A'] << endl; /*统计成功*/
n++;
}
}
j = 0;
for (i = 0; i < 26; i++)
{
if (ans[i] != 0)
{
HuffNode[j].weight = ans[i];
HuffNode[j].zifu = char(i + 'a');
j++;
}
}
for (i = 0; i < 26; i++)
{
if (bns[i] != 0)
{
HuffNode[j].weight = bns[i];
HuffNode[j].zifu = char(i + 'A');
j++;
}
}
HuffmanTree(HuffNode, n);
for (i = 0; i < n; i++)
{
cd.start = n - 1;
c = i;
p = HuffNode[c].parent;
while (p != -1) /* 父结点存在 */
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求编码的低一位 */
c = p;
p = HuffNode[c].parent; /* 设置下一循环条件 */
}
/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j = cd.start + 1; j < n; j++)
{
HuffCode[i].bit[j] = cd.bit[j];
}
HuffCode[i].start = cd.start;
}
printf("字符 哈夫曼编码
");/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i = 0; i < n; i++)
{
printf("%c ", HuffNode[i].zifu);
for (j = HuffCode[i].start + 1; j < n; j++)
{
printf("%d", HuffCode[i].bit[j]);
}
printf("
");
}
i = 0;
printf("原来的字符串译码为:");
while (i < l)
{
for (j = 0; j < n; j++)
{
if (HuffNode[j].zifu == s[i])
{
for (int k = HuffCode[j].start + 1; k < n; k++)
{
printf("%d", HuffCode[j].bit[k]);
}
}
}
i++;
}
printf("
");
getchar();
printf("请按照上述给出的编码输入需要破译的代码（只可包含0与1,不可有空格）：
");
string order;//需要破译的字串
cin >> order;
int jishuqi = 0;
/*-------------------------------------------------------译码过程*/
j = 0;
while (HuffNode[j].parent != -1)/*寻找出根结点*/
{
j = HuffNode[j].parent;
}
int t = j;
cout << "译码后原文为:";
while (order[jishuqi] != ' ')/*以此判断每一位是1还是0，左右孩子都为空时输出，否则继续寻找*/
{
if (order[jishuqi] == '0')/*0为左孩子*/
{
t = HuffNode[t].lchild;
}
else if (order[jishuqi] == '1')/*1为右孩子*/
{
t = HuffNode[t].rchild;
}
if (HuffNode[t].zifu != NULL)
{
cout << HuffNode[t].zifu;
t = j;
}
jishuqi++;
}
cout << endl;
system("pause");
system("cls");
}
return 0;
}