C++数据结构之文件压缩(哈夫曼树)实例详解-创新互联
C++数据结构之文件压缩(哈夫曼树)实例详解
创新互联公司是一家专注于网站设计制作、做网站与策划设计,高县网站建设哪家好?创新互联公司做网站,专注于网站建设10余年,网设计领域的专业建站公司;建站业务涵盖:高县等地区。高县做网站价格咨询:18982081108概要:
项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压
开发环境:windows vs2013
项目概述:
1.压缩
a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树
b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底
c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成
d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编码
e.获取编码后每次凑满8位就将编码串写入到压缩文件(value处理编码1与它即可,0只移动位)
f.写好配置文件,统计每个字符及其出现次数,并以“字符+','+次数”的形式保存到配置文件中
2.解压
a.读取配置文件,统计所有字符的个数
b.构建哈夫曼树,读解压缩文件,将所读到的编码字符的这个节点所所含的字符写入到解压缩文件中,知道将压缩文件读完
c.压缩解压缩完全完成,进行小文件大文件的测试
实例代码:
#pragma once #includetemplate struct Less { bool operator()(const T& l, const T& r) const { return l < r; } }; template struct Greater { bool operator()(const T& l, const T& r) const { return l > r; } }; template class Heap { public: Heap() {} Heap(T* array, size_t n) //建堆 { _array.reserve(n); for (size_t i = 0; i < n; i++) { _array.push_back(array[i]); } for (int i = (_array.size() - 2) >> 1; i >= 0; --i) { _AdjustDown(i); } } const T& Top()const { return _array[0]; } void Push(const T& x) { _array.push_back(x); _AdjustUp(_array.size() - 1); } size_t Size() { return _array.size(); } void Pop() { assert(_array.size() > 0); swap(_array[0], _array[_array.size() - 1]); _array.pop_back(); _AdjustDown(0); } bool Empty() { return _array.size() == 0; } void Print() { for (size_t i = 0; i < _array.size(); ++i) { cout << _array[i] << " "; } cout << endl; } protected: void _AdjustUp(int child) //上调 { Compare ComFunc; int parent = (child - 1) >> 1; while (child) { if (ComFunc(_array[child], _array[parent])) { swap(_array[child], _array[parent]); child = parent; parent = (child - 1) >> 1; } else { break; } } } void _AdjustDown(int root) //下调 { Compare ComFunc; int parent = root; int child = root * 2 + 1; while (child < _array.size()) { if (child + 1 < _array.size() && ComFunc(_array[child + 1], _array[child])) { ++child; } if (ComFunc(_array[child], _array[parent])) { swap(_array[child], _array[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } protected: vector _array; }; void TestHeap() { int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 }; //Heap heap(a, sizeof(a) / sizeof(a[0])); //Heap > heap(a, sizeof(a) / sizeof(a[0])); Heap > heap(a, sizeof(a) / sizeof(a[0])); heap.Print(); heap.Push(25); heap.Print(); heap.Pop(); heap.Print(); }
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章标题:C++数据结构之文件压缩(哈夫曼树)实例详解-创新互联
标题路径:http://scyanting.com/article/jgjdd.html