# Huffman_Compress
## 数据结构课程设计:哈夫曼压缩软件设计,男女运动员匹配问题
本目录下(..\Huffman_Compress)是使用vs编写的核心代码部分,main.cpp是测试程序。
..\Huffman_Compress\QTHuffman_Compress目录下是结合利用QT编写的多个界面文件的最终可视化版本。
### A 哈夫曼压缩软件设计
##### 【问题描述】
采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。利用哈夫曼编码对文本或图像进行数据压缩,设计数据压缩软件。
##### 【设计要求】
设计基于哈夫曼编码的文本和图像压缩软件。
(1)采用静态链表的二叉树等数据结构。
(2)可以随机、文件及人工输入数据。
(3)创建哈夫曼树,生成哈夫曼编码和译码。
(4)源码、编码和压缩后的信息均以文件形式保存。
(5)可以查询和更新数据。
(6)其它完善性或扩展性功能。
### B 男女运动员最佳组合
##### 【问题描述】
设有N个男羽毛球运动员和N个女羽毛球运动员,现组成N对男女混合最佳组合。每个男运动员对每个女运动员都有一个满意度排序,用矩阵mf[0:n-1][0:n-1]表示。mf[i][j]表示第i个男运动员对第j个女运动员的满意度,满意度值越高,满意程度越高。同理,每个女运动员对每个男运动员也有一个满意度排序,用矩阵fm[0:n-1][0:n-1]表示。男女运动员之间的一个完全匹配称为一个组合。
##### 【设计要求】
设计对于给定的满意度,求最佳组合的程序,使得满意度总和达到最大。
(1)采用STL的一维向量类构造构造二维向量矩阵。
(2)应用基本运算,设计算法求解。
# 哈夫曼压缩软件设计
# 一、课题概述
## 1.1 课题任务
利用哈夫曼编码的数据压缩技术,设计压缩软件。使用静态链表的二叉树等数据结构。实现能够将原码文件转化成编码文件或压缩文件,并能够将其复原为原码文件的功能。实现能够进行对文本格式和位图格式或其他合适的文件进行压缩的功能。在此基础上,拥有较好的时间和空间性能。
## 1.2 课题原理
1. 哈夫曼树
> 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。树的带权路径长度,即树中所有的叶子结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL= $\sum_{k = 1}^{n}{\omega_{k}l_{k}}$,n 个权值构成一颗有 n个叶结点的二叉树,相应的叶结点的路径长度为$\omega_{k}l_{k}$。可证明哈夫曼树的WPL是最小的。
2. 哈夫曼压缩
> 哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。
## 1.3 相关知识
- 二进制文件的创建、读取、写入操作
- 数学统计
- 哈夫曼树的建立和运用
- 哈夫曼编码的建立和获取
- 字节的位运算
- C++ 类、文件流相关知识的熟悉掌握。
- QT 界面类创建以及相关知识的熟悉掌握
# 二、需求分析
## 2.1 课题调研
随着计算机技术的发展,人们对文件信息的需求量逐渐增大,不光对文件个数的使用量增加,单个文件的内存也增大到几个 G ,这种现象的产生,将导致计算机上内存的消耗过大,以及计算机对文件的操作变得十分困难。
## 2.2 用户需求分析
经过调研,目前用户比较倾向的压缩工具的特点有:使用方便、用户友好,在压缩率以及压缩速度方面表现出色。
在这个背景下,我们小组决定运用哈夫曼算法,设计一款符合大众要求的小压缩工具。
# 三、方案设计
## 3.1 总体功能设计
![](./photo/1e571e51106840ea7a77be59f3ba5832.writebug)
## 3.2 数据结构设计
```c++
/*字母表类:class alphaTable*/
Alpha* alpTab; //指向由字母组成的动态数组首地址
unsigned alpNum; //字母数量(种类数)
unsigned SIZE; //字母表大小
```
```c++
/*哈夫曼树类:class HuffmanTree*/
alphaTable alT; //建树的字母表
HNode *HTree; //有哈夫曼结点类组成的静态链表,存储建好的哈夫曼二叉树
std::string *HCode; //哈夫曼编码表,存储每个字符对应的01编码
std::unordered_map<char, int>hash; //利用stl建立的字符同在树表索引的映射关系
int nowPtr; //当前指针,解码过程中用到,指向当前正在查找的结点的索引
```
## 3.3 类原型设计
![](./photo/6eca9fd120700d3104d1cdc2e19bbeff.writebug)
```c++
/*字母结构体组成*/
typedef struct Alpha {
char ch; //字符
unsigned fre; //当前字符出现频率
Alpha(char ch = 0, unsigned fre = 0):ch(ch),fre(fre) {}
bool operator < (const Alpha& other) {
if (fre != other.fre) return fre < other.fre;
return ch < other.ch;
}
} Alpha;
```
```c++
/*字母表结点类*/
class alphaTable
{
public:
/*字母表类*/
Alpha* alpTab; //指向由字母组成的动态数组首地址
unsigned alpNum; //字母数量(种类数)
unsigned SIZE; //字母表大小
public:
//字母表构造函数,调用初始化函数初始化
alphaTable(const char* filename = "\0", bool isComFile = false, int indx = 0);
//字母表初始化函数
bool init(const char* filename = "\0", bool isComFile = false, int indx = 0);
//从原码文件读取文件建立字母表
bool getAlpTab_File(const char* filename);
//获得字母种类数量
unsigned getAlpNum();
//字母表排序函数
bool sortAlpTab();
//向文件中以二进制形式写入头数据(字母种类数量,各字符种类以及出现频率)
bool writeHdataToFile(const char* filename,int indx = 0);
//从译码文件或压缩文件中读取头数据获得字母表信息
bool getAlpTab_Hdata(const char* filename,int indx = 0);
//字母表信息打印函数,用于控制台字母表类测试
void print();
};
```
```c++
/*哈夫曼树结点类*/
class HNode
{
public:
unsigned weight; //权重
unsigned lch, rch; //左右孩子结点
unsigned par; //双亲结点
public:
//构造函数,利用初始化函数构造
HNode(unsigned wei = 0, unsigned l = 0, unsigned r = 0, unsigned par = 0);
//初始化函数
bool initHNode(unsigned wei = 0, unsigned l = 0, unsigned r = 0, unsigned par = 0);
//运算符重载
bool operator< (const HNode& other);
//输出流重载,用于控制台后序测试
friend std::ostream& operator<< (std::ostream& out, const HNode &node);
};
```
```c++
/*哈夫曼树类*/
class HuffmanTree
{
private:
/*哈夫曼树类*/
alphaTable alT; //建树的字母表
HNode *HTree; //有哈夫曼结点类组成的静态链表,存储建好的哈夫曼二叉树
std::string *HCode; //哈夫曼编码表,存储每个字符对应的01编码
//unsigned hash[270];
std::unordered_map<char, int>hash; //利用stl建立的字符同在树表索引的映射关系
int nowPtr; //当前指针,解码过程中用到,指向当前正在查找的结点的索引
public:
//构造函数
HuffmanTree(alphaTable& alT);
HuffmanTree();
//初始化函数
bool initHTree(alphaTable& alT);
//挑选结点函数,以及建树函数
void Select(std::queue<std::pair<HNode, int> >& fir, std::queue<std::pair<HNode, int> >& sec,
unsigned& min_inx_1, unsigned& min_inx_2, int num);
bool buildTree();
//哈夫曼编码表建立函数
bool buildCode();
//获得
没有合适的资源?快使用搜索试试~ 我知道了~
基于C++设计哈夫曼压缩软件与解决男女运动员匹配问题【100012410】
共92个文件
writebug:32个
png:29个
h:9个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 96 浏览量
2023-05-24
14:13:01
上传
评论
收藏 3.43MB ZIP 举报
温馨提示
1.采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。利用哈夫曼编码对文本或图像进行数据压缩,设计数据压缩软件。 2.设有N个男羽毛球运动员和N个女羽毛球运动员,现组成N对男女混合组合。设计对于给定的满意度,求最佳组合的程序,使得满意度总和达到最大。
资源推荐
资源详情
资源评论
收起资源包目录
100012410-基于C++设计哈夫曼压缩软件与解决男女运动员匹配问题.zip (92个子文件)
huffman_compress
HuffmanCompress.vcxproj 7KB
alphaTable.h 1KB
BitDeal.h 280B
LICENSE 1KB
HuffmanCompress.vcxproj.filters 2KB
FileRW.h 2KB
HNode.cpp 529B
1234.txt 2KB
HNode.h 607B
HuffmanTree.cpp 5KB
main.cpp 5KB
QTHuffman_Compress
QTHuffman_Compress.pro 1KB
copy.png 5KB
mainwindow.h 479B
compress.png 7KB
comdialog.cpp 5KB
mainwindow.cpp 610B
decomdialog.cpp 4KB
decomdialog.h 670B
prog2.ico 254KB
main.cpp 197B
decomdialog.ui 7KB
mainwindow.ui 7KB
comdialog.ui 10KB
pic.qrc 162B
comdialog.h 643B
alpha.h 326B
HuffmanCompress.sln 1KB
alphaTable.cpp 3KB
.gitignore 6KB
HuffmanTree.h 2KB
photo
2ebc1d362b0afe0e00d64eece78f5925.writebug 53KB
image-20220131133402800.png 45KB
image-20220131133442847.png 45KB
image-20220131133529533.png 11KB
image-20220131133728624.png 115KB
0c8074e15e9bb0cac0fc7810f201404e.writebug 94KB
18d3c8eb0a95a23308666d0d1a965497.writebug 49KB
b3f7b8a1e591fc5d057e67d20b91f601.writebug 183KB
image-20220131144506666.png 40KB
image-20220131133428265.png 55KB
image-20220131133435696.png 53KB
image-20220131133540182.png 5KB
4d0d47af4ac7fcdec0c6f890686c5a6b.writebug 56KB
a8c00ed0f376f8f22314e79dd040798a.writebug 68KB
b648a99d913c04b10b0e7625b728beac.writebug 88KB
image-20220131144324893.png 51KB
83f075d0fc79ea25b53bd271a15ded15.writebug 65KB
8c9a19a4f84538c27345db3ac9193966.writebug 16KB
image-20220131133411890.png 46KB
e09af85467f8cda47942fc558af001ae.writebug 103KB
image-20220131144437747.png 42KB
image-20220131133710278.png 67KB
2813795f814b14f603d3cd1938aa29ed.writebug 19KB
15a3fc0215a2f94aa27e6409d4ae6187.writebug 159KB
image-20220131133228164.png 57KB
image-20220131133630499.png 106KB
905d5e5ffe2f42d690dd414489a8ff48.writebug 60KB
1637ceca0cb887eb31be437ecba7a028.writebug 44KB
54846111046713dc92dddf96b3574b60.writebug 19KB
image-20220131133519702.png 69KB
3dd1d6248eaf39011a39c694445633dd.writebug 91KB
image-20220131133639914.png 52KB
28ec9e3097be269db426ceb6e69faec9.writebug 60KB
image-20220131133742916.png 108KB
4f49c8cfc7f24be9ba1ac0eec729a78b.writebug 76KB
91ebe41e36c9b0ed1ac0a58fa022192e.writebug 106KB
b26baea0463ef459e45af275657ba8d1.writebug 174KB
6eca9fd120700d3104d1cdc2e19bbeff.writebug 158KB
image-20220131133554332.png 108KB
image-20220131133311881.png 66KB
41754eccc41829dbbc21bf148f36b804.writebug 76KB
5c397eab61dfed0823e5a6f0d5915a04.writebug 28KB
2b7f8968453faabe9fb4d63daa92061e.writebug 64KB
db22a7041fb4458ee0559a4d754e1174.writebug 45KB
37ba11c49cefbddaba34e23d66f1d6f5.writebug 18KB
6c180d2a845e8c5692513cef8e22dc3e.writebug 65KB
2f2577880b236792ffafb490f48e8def.writebug 56KB
image-20220131133723604.png 5KB
1e571e51106840ea7a77be59f3ba5832.writebug 79KB
4e2af39e5d9d9fab730c2d3cf18f2c29.writebug 19KB
8852a5d6a216ed58605aff2a02574711.writebug 16KB
image-20220131133545885.png 99KB
890e33e0e0406e177f986e52b3509d10.writebug 64KB
image-20220131133735345.png 107KB
image-20220131133420870.png 50KB
image-20220131133621189.png 7KB
image-20220131144403161.png 42KB
image-20220131133449300.png 38KB
image-20220131133717671.png 11KB
FileRW.cpp 11KB
README.md 54KB
共 92 条
- 1
资源评论
神仙别闹
- 粉丝: 2687
- 资源: 7642
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功