梦见坐过山车脱轨了:huffman压缩与解压程序
来源:百度文库 编辑:偶看新闻 时间:2024/10/05 10:44:06
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*huffman压缩与解压程序(解压部分复杂度挺高,可由读者换种算法实现)*/
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/****************************************************************/
/*头文件的包含*/
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define SIZE 514 //树节点的上限,最多256个内节点,257个叶节点,最后一个结束;
#define CODE 32 //编码数组长度;
/*****************************************************************/
/*****************************************************************/
struct Huffman_node{ //Huffman树节点的结构;
charch_; //字符;
longfreq_; //字符出现频率;
intlc_; //左子;
intrc_; //右子;
intparent_; //父节点;
charcode_[CODE]; //哈弗曼编码;
};
typedef struct Huffman_node Hfmn;
/*****************************************************************/
/*****************************************************************/
/*全局变量*/
Hfmn root; //根节点;
Hfmn Node[SIZE]; //定义Huffman树节点数组;
int min; //频率最小节点下标;
int total; //内点数;
string file; //要压缩的文件;
int zero; //补‘
double first=0,last=0; //压缩前与压缩后文件长度;
clock_t start1,finish1; //计算压缩时间;
clock_t start2,finish2; //计算解压时间;
//string filey;
/*****************************************************************/
/*****************************************************************/
/*函数声明*/
void Node_initialize(void); //初始化数组Node;
void Freq_count(void); //打开指定文件统计字符出现频率;
void Node_selectmin(long a[],int b);//从数组中找出概率最小的;
void Huffman_tree_create(void); //构造Huffman树;
void Huffman_code(void); //构建Huffman编码;
void Huffman_save(void); //存储Huffman树到文件;
void Huffman_compress(void); //实现Huffman压缩;
void Huffman_decompress(void); //实现Huffman解压;
/*****************************************************************/
/*****************************************************************/
/*函数实现*/
/*初始化数组Node函数*/
void Node_initialize(void)
{
for(inti=0;i Node[i].ch_='#'; Node[i].freq_=0; Node[i].lc_=-1; Node[i].rc_=-1; Node[i].parent_=-1; for(intk=0;k (Node[i].code_)[k]='\0'; } } } /*统计频率函数*/ void Freq_count(void) { charch; //暂存从文件读出的字符; inti=0,j=0; //用于循环控制; boolsame; //判断是否是新的字符; cout<<"请输入要压缩的文件:"< getline(cin,file); //获取要压缩的文件; start1=clock(); //压缩开始时间; fstreamtfile(file.c_str(),ios_base::binary|ios_base::in); ch=tfile.get(); //读取文件中第一个字符; if(!tfile.eof()){ Node[i].ch_=ch; //添加新字符到数组; Node[i].freq_++; //频率加1; i++; //推进数组; ch=tfile.get(); //读下一个字符; while(!tfile.eof()){ for(j=0;j ch==Node[j].ch_?same=true:same=false; if(same==true){ //如果相同,频率加1; Node[j].freq_++; break; } } if(same==false){ //如果不同,添加进数组; Node[i].ch_=ch; Node[i].freq_++; i++; //推进数组; } ch=tfile.get(); //往下读; } total=i-1; //获取字符总数; } tfile.close(); } /*找频率最小节点函数*/ void Node_selectmin(long a[],int size) { min=0;