实验目的:
(1) 掌握二叉树的定义;
(2) 掌握哈夫曼树和哈夫曼编码算法的实现.???
实验内容:
实现一个哈夫曼编码系统, 系统包括以下功能:
(1) 字符信息统计: 读取待编码的源文件 SourceFile.txt, 统计出现的字符及其频率.
附: SourceFile.txt 文件内容为
U ARE THE BEST IN MY HEART
(2) 建立哈夫曼树: 根据统计结果建立哈夫曼树.
(3) 建立哈夫曼码表: 利用得到的哈夫曼树, 将各字符对应的编码表保存在文件 Code.txt 中.
(4) 对源文件进行编码: 根据哈夫曼码表, 将 SourceFile.txt 中的字符转换成相应的编码文件 ResultFile.txt.
实现提示:
(1) 字符信息统计: 假设源文件 SourceFile.txt 中的字符只有大小写英文字母 (同一个字母的大小写看作一个字符), 则字符统计算法的实现过程可以归纳为: 先定义一个含有 26 个元素的整形数组, 用来存储各个字母出现的次数, 最后还要排除其中出现次数为 0 的数组元素.
(2) 建立哈夫曼树: 参考教材算法 5.10, 补充函数 Select 的实现.
(3) 建立哈夫曼码表: 参考教材算法 5.11, 将编译表 HC 中的内容写到文件 Code.txt 中.
(4) 对源文件进行编码: 依次读入文件 SourceFile.txt 中的字符? c, 在编码表? HC? 中找到此字符, 将字符 c 转换为编码表中存放的编码串, 写入编码文件 ResultFile.txt 中, 直到所有的字符处理完毕为止.
代码实现
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<fstream>
- #include<string>
- using namespace std;
- typedef struct{
- int weight;
- int parent, lchild, rchild;
- }HTNode, *HuffmanTree;
- typedef char **HuffmanCode;
- int a[24 + 1], b[24 + 1];
- char c[24 + 1];
- void Select(HuffmanTree &HT, int n, int &s1, int &s2){
- for (int i = 1; i <= n; i++)
- if (HT[i].parent == 0 && s1 == 0) { s1 = i; break; }
- for (int i = 1; i <= n; i++)
- if (HT[i].parent == 0 && HT[i].weight<HT[s1].weight) s1 = i;
- for (int i = 1; i <= n; i++)
- if (HT[i].parent == 0 && s2 == 0 && i != s1) { s2 = i; break; }
- for (int i = 1; i <= n; i++)
- if (HT[i].parent == 0 && HT[i].weight<HT[s2].weight&&i != s1) s2 = i;
- }
- void CreateHuffmanTree(HuffmanTree &HT, int n){
- if (n <= 1) return;
- int m = 2 * n - 1;// 构造一棵哈夫曼树所需要的所有节点数
- HT = new HTNode[m + 1];//m+1 指从第一个结点开始, 第 0 个结点不用
- for (int i = 1; i <= m; i++){
- HT[i].parent = 0;
- HT[i].lchild = 0;
- HT[i].rchild = 0;
- }
- for (int i = 1; i <= n; i++) HT[i].weight = b[i];// 把字母出现的次数赋值给哈夫曼树的 weight
- for (int i = n + 1; i <= m; i++){
- int s1 = 0, s2 = 0;
- Select(HT, 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;
- }
- }
- void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n){
- HC = new char*[n + 1];
- char *cd = new char[n];
- cd[n - 1] = '\0';
- for (int i = 1; i <= n; i++){
- int start = n - 1, c = i, f = HT[i].parent;
- while (f){
- --start;
- if (HT[f].lchild == c) cd[start] = '0';
- else cd[start] = '1';
- c = f;
- f = HT[f].parent;
- }
- HC[i] = new char[n - start];
- strcpy(HC[i], &cd[start]);
- }
- delete cd;
- }
- int main(){
- freopen("SourceFile.txt", "r", stdin);// 打开输入文件
- memset(a, 0, sizeof(a));
- string str;
- getline(cin, str);// 接收文件的字符串并保存到 str 中
- for (int i = 0; i<str.length(); i++)// 统计每个字母出现的频率即次数
- a[str[i] - 64]++;
- int n = 0;
- for (int i = 1, j = 1; i <= 24; i++)// 统计有多少个不同的字母以及把没出现的字母去除掉
- if (a[i] != 0){
- n++;
- b[j] = a[i];
- c[j++] = i + 64;
- }
- HuffmanTree HT;
- HuffmanCode HC;
- CreateHuffmanTree(HT, n);
- CreateHuffmanCode(HT, HC, n);
- freopen("Code.txt", "w", stdout);
- for (int i = 1; i <= n; i++)
- cout << c[i] << ':' << HC[i] << endl;
- freopen("ResultFile.txt", "w", stdout);
- for (int i = 0; i<str.length(); i++){
- for (int j = 1; j <= n; j++){
- if (str[i] == c[j]) cout << HC[j];
- }
- }
- return 0;
- }
- Code.txt
- A:000
- B:0110
- E:111
- H:001
- I:0111
- M:1000
- N:1001
- R:010
- S:1010
- T:110
- U:1011
- ResultFile.txt
- 101100001011111000111101101111010110011110011000001111000010110
实验结果
来源: http://www.bubuko.com/infodetail-3331131.html