Huffman编码(二叉树应用)

第二章 每个C++程序都有一个main( )函数。函数是指能实现一个或多个功能的代码块。通常函数是由其他函数调用或激活，而main( )属于特殊情况，由操作系统直接调用。程序在开始时会自动调用main( )。和所有函数一样，main( )函数也必须标明其返回类型。 “\n”是格式专用符，它告诉cout另起一行。 endl表示end line,是end-ell 而不是end-one。通常它念作“end-ell”。 “\t”是格式化字符，它用来插入一个制表符。Eg: cout<<"Here is a very big number:\t"<<70000<<endl; cout<<"Here is the sum of 8 and 5:\t"<<8+5<<endl; cout<<"Here's a fraction:\t\t"<<(float)5/8<<endl;使用了“\t”，其目的是使输出数据对齐。 注释不应用来说明发生了什么事情，而应说明为什么发生这种事情。 //Utility.h #include<string.h> //标准串操作 #include<iostream> //标准输入输出操作 #include<limits.h> //数字限定 #include<math.h> //数学函数 #include<fstream> //文件输入输出 #include<ctype.h> //字符分类 #include<time.h> //时间函数 #include<conio.h> //输入输出 #include<stdlib.h> //标准库 #include<stdio.h> //标准输入输出库 enum Error_code{success,fail,underflow,overflow,range_error};//错误码 //enum bool{false,true}; //Lk_stack.h template<class Node_entry> struct Node { // 数据成员 Node_entry entry; Node<Node_entry> *next; // 构造函数 Node(); Node(Node_entry item, Node<Node_entry> *add_on = NULL); }; template<class Stack_entry> class Stack { public: // 标准堆栈方法 Stack(); bool empty() const; Error_code push(const Stack_entry &item); Error_code pop(); Error_code top(Stack_entry &item) const; void clear(); // 相关结构的安全功能 ~Stack(); Stack(const Stack<Stack_entry> &original); void operator =(const Stack<Stack_entry> &original); protected: Node<Stack_entry> *top_node; }; template<class Node_entry> Node<Node_entry>::Node() { next = NULL; } template<class Node_entry> Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *add_on) { entry = item; next = add_on; } template<class Stack_entry> Stack<Stack_entry>::Stack() { top_node=NULL; } template<class Stack_entry> bool Stack<Stack_entry>::empty() const { if(top_node==NULL) return true; else return false; } template<class Stack_entry> Error_code Stack<Stack_entry>::push(const Stack_entry &item) /* Stack_entry 项添加到堆栈的顶部，如果动态内存用尽，则返回成功或返回溢出代码 */ { Node<Stack_entry> *new_top = new Node<Stack_entry>(item, top_node); if (new_top == NULL) return overflow; top_node = new_top; return success; } template<class Stack_entry> Error_code Stack<Stack_entry>::pop() /* 栈的顶部移动。 如果栈为空则返回下溢；否则返回成功。 */ { Node<Stack_entry> *old_top = top_node; if (top_node == NULL) return underflow; top_node = old_top->next; delete old_top; return success; } template<class Stack_entry> Error_code Stack<Stack_entry>::top(Stack_entry &item) const { if(empty()) return underflow; else{ item=top_node->entry; return success; } } template<class Stack_entry> void Stack<Stack_entry>::clear() // 清除元素 /* 栈清空 */ { while (!empty()) pop(); } template<class Stack_entry> Stack<Stack_entry>::~Stack() // 析构函数 /* 栈清空 */ { clear(); } template<class Stack_entry> Stack<Stack_entry>::Stack(const Stack<Stack_entry> &original) // 复制析构函数 /* 复制的析构函数初始化 */ { Node<Stack_entry> *new_copy, *original_node = original.top_node; if (original_node == NULL) top_node = NULL; else { // 复制相关点 top_node = new_copy = new Node<Stack_entry>(original_node->entry); while (original_node->next != NULL) { original_node = original_node->next; new_copy->next = new Node<Stack_entry>(original_node->entry); new_copy = new_copy->next; } } } template<class Stack_entry> void Stack<Stack_entry>::operator = (const Stack<Stack_entry> &original) // 超载分配 /* 复制栈重置 */ { Node<Stack_entry> *new_top, *new_copy, *original_node = original.top_node; if (original_node == NULL) new_top = NULL; else { // 复制相关点 new_copy = new_top = new Node<Stack_entry>(original_node->entry); while (original_node->next != NULL) { original_node = original_node->next; new_copy->next = new Node<Stack_entry>(original_node->entry); new_copy = new_copy->next; } } while (!empty()) // 清除原栈入口 pop(); top_node = new_top; // 用新的栈入口代替 } //Huffman.h const unsigned int n=256; //字符数 const unsigned int m=256*2-1; //结点总数 struct HTNode{ //压缩用Huffman树结点 unsigned long weight; //字符频度（权值） unsigned int parent,lchild,rchild; }; struct Buffer{ //字节缓冲压缩用Huffman树 char ch; //字节 unsigned int bits; //实际比特数 }; class HuffmanTree{ //Huffman树 public: void Code(); //编码 void UnCode(); //译码 private: HTNode HT[m+1]; //树结点表(HT[1]到HT[m]) char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n]) char *HuffmanCode[n+1]; //叶结点对应编码(*HuffmanCode[1]到*HuffmanCode[n]) unsigned int count; //频度大于零的字符数 unsigned int char_index[n]; //字符对应在树结点表的下标(char_index[0]到char_index[n-1]) unsigned long size; //被压缩文件长度 FILE *infp,*outfp; //输入/出文件 Buffer buf; //字符缓冲 void Stat(); //统计字符出现频度并过滤掉频度为零的字符 //在HT[0]~HT[k]中选择parent为-1，树值最小的两个结点s1,s2 void Select(unsigned int k, unsigned int &s1, unsigned int &s2); void Write(unsigned int bit); //向outfp中写入一个比特 void Write(unsigned int num,unsigned int k);//向outfp中写入k个比特 void WriteToOutfp(); //强行写入outfp void Read(unsigned int &bit); //从infp中读出一个比特 void Read(unsigned int &num,unsigned int k);//从infp中读出k个比特 int NToBits(unsigned int num); //0~num之间的整数用二进位表示所需的最少位数 void CreateFromCodeFile(); //由编码文件中存储的树结构建立Huffman树 //由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码 void CreateFromSourceFile(); }; void HuffmanTree::Code() //编码 { char infName[256],outfName[256]; cout<<"Please input source file name(size less than 4GB):"; //被压缩文件最多GB cin>>infName; if((infp=fopen(infName,"rb"))==NULL){ cout<<"Can not open file:"<<infName<<endl; exit(1); } if(feof(infp)!=0){ cout<<"Empty source file:"<<infName<<endl; exit(1); } cout<<"Please input code file name:"; cin>>outfName; if((outfp=fopen(outfName,"wb"))==NULL){ cout<<"Can not open file:"<<outfName<<endl; exit(1); } cout<<"Pocessing..."<<endl; unsigned char ch; unsigned int i,c; for(i=0;i<=n;i++)HuffmanCode[i]=NULL; CreateFromSourceFile(); rewind(infp); ch=fgetc(infp); while(feof(infp)==0){ c=char_index[ch]; for(i=0;i<strlen(HuffmanCode[c]);i++){ if(HuffmanCode[c][i]=='0')Write(0); else Write(1); } ch=fgetc(infp); } WriteToOutfp(); fclose(infp);fclose(outfp); cout<<"Process end."<<endl<<endl; } void HuffmanTree::UnCode() { char infName[256],outfName[256]; cout<<"Please input code file name:"; cin>>infName; if((infp=fopen(infName,"rb"))==NULL){ cout<<"Can not open file:"<<infName<<endl; exit(1); } if(feof(infp)!=0){ cout<<"Empty code file:"<<infName<<endl; exit(1); } cout<<"Please i