一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com
Last edited: 2022.11.20
目录
数据结构“基于哈夫曼树的数据压缩算法”的实验报告
一、实验目的
二、实验设备
三、实验内容
1.【问题描述】
2.【输入要求】
3.【输出要求】
4.【实验提示】
四、实验步骤
4.1
4.2编程和调试
五、实验结果
5.1程序完成后关键源码及运行结果截图
六、实验总结
七、划重点参考代码
数据结构“基于哈夫曼树的数据压缩算法”的实验报告
| 课程名称： |
数据结构 |
| 项目名称： |
基于哈夫曼树的数据压缩算法 |
| 实验类型： |
验证性实验 |
一、实验目的
1.掌握哈夫曼树的构造算法。
2.掌握哈夫曼编码的构造算法。
二、实验设备
装有Dev C++的计算机一台
三、实验内容
结合在头歌上已完成的实训任务进行填写
1.【问题描述】
输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。
2.【输入要求】
多组数据，每组数据1行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”时，输入结束。
3.【输出要求】
每组数据输出2n+3行（n为输入串中字符类别的个数）。第1行为统计出来的字符出现频率（只输出存在的字符，格式为：字符：频度），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态（如主教材139页表5.2（b），一行当中的数据用空格分隔）。第2n+1行为每个字符的哈夫曼编码（只输出存在的字符，格式为：字符：编码），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串，第2n+3行为解码后的字符串（与输入的字符串相同）。
4.【实验提示】
此实验内容即要求实现主教材的案例5.1，具体实现可参考算法5.10和算法5.11。首先，读入一行字符串，统计每个字符出现的频率；然后，根据字符出现的频率利用算法5.10建立相应的哈夫曼树；最后，根据得到的哈夫曼树利用算法5.11求出每个字符的哈夫曼编码。
四、实验步骤
4.1
此部分可包含解题思路、最初填写的但没有通过的程序，通过调试如何找到问题并做出改正，可粘贴调整规范的截图
4.2编程和调试
此部分可包含解题思路、最初填写的但没有通过的程序，通过调试如何找到问题并做出改正，可粘贴调整规范的截图
五、实验结果
5.1程序完成后关键源码及运行结果截图
可以将最终完成的代码及运行结果在此展示。
六、实验总结
用简介、准确的语言描述本次实验重点解决了什么问题，学习了什么知识，自己掌握的如何等等文章来源：https://www.toymoban.com/news/detail-490790.html
七、划重点参考代码
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
#define IOS std::ios::sync_with_stdio(false)
using namespace std;
typedef struct
{
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
char ch[10];
void Select(HuffmanTree HT,int len,int &s1,int &s2)
{
int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;
for(i = 1; i <= len; i ++)
if(HT[i].parent == 0 && min1 > HT[i].weight)
min1 = HT[i].weight, s1 = i;
for(i = 1; i <= len; i ++)
if(i != s1 && HT[i].parent == 0)
if(HT[i].weight < min2)
min2 = HT[i].weight, s2 = i;
}
void CreatHuffmanTree(HuffmanTree &HT, int n, int s[])
{
if(n <= 1) return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for(int i = 1; i <= m; i ++)
HT[i].parent = 0, HT[i].lchild = 0, HT[i].rchild = 0;
for(int i = 1; i <= 26; i ++)
if(s[i] != 0)
HT[i].weight = s[i];
for(int i = n + 1; i <= m; i ++)
{
int s1, s2;
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 CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
char *cd;
HC = new char*[n + 1], cd = new char[n];
cd[n - 1] = '\0';
for(int i = 1; i <= n; i ++)
{
int start = n - 1;
int c = i, f = HT[i].parent;
while(f != 0)
{
-- 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;
}
void show(HuffmanCode HC, int h)
{
for(int i = 1; i <= h; i ++)
cout << HC[i] << endl;
}
void init()
{
IOS;
for(int i = 0; ; i ++)
{
char a; cin >> a;
if(a != '0') ch[i] = a;
else break;
}
}
int main()
{
IOS; init();
int s[27], t = strlen(ch), h = 0;
memset(s, 0, sizeof s);
for(int i = 0; i <= t; i ++) s[ch[i] - 'a' + 1] ++;
for(int i = 0; i <= 26; i ++)
if(s[i] != 0) h ++;
cout << h << endl;
for(int i = 1; i <= 26; i ++)
if(s[i] != 0)
cout << (char)(i + 'a' - 1) << ":" << s[i] << ' ';
cout << endl;
HuffmanTree HT;
HuffmanCode HC;
CreatHuffmanTree(HT, h, s);
CreatHuffmanCode(HT, HC, h);
show(HC, h);
return 0;
}如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……文章来源地址https://www.toymoban.com/news/detail-490790.html
到了这里，关于数据结构“基于哈夫曼树的数据压缩算法”的实验报告的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
