本文共 4123 字，大约阅读时间需要 13 分钟。
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#include #include #include #include #include #include #include #include #include #include #include #include #include
#include using namespace std;#define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1typedef 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 > 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("字符\t哈夫曼编码\n");/* 输出已保存好的所有存在编码的哈夫曼编码 */ for (i = 0; i < n; i++) { printf("%c\t", HuffNode[i].zifu); for (j = HuffCode[i].start + 1; j < n; j++) { printf("%d", HuffCode[i].bit[j]); } printf("\n"); } 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("\n"); getchar(); printf("请按照上述给出的编码输入需要破译的代码（只可包含0与1,不可有空格）：\n"); 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] != '\0')/*以此判断每一位是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;}
发表评论
最新留言
关于作者
