哈夫曼编码实验报告C++实现

1、主要数据类型与变量

1.1使用到的头文件

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> //map数据结构存储HT编码表 #include <queue> //构建的节点的优先性 #include <string> //字符串方便输入输出 #include <iterator> //迭代器输出map展示 #include <fstream> //读写文件

1.2 使用类代替结构体，这里重载比较运算符，便于排序和构造优先队列。

class HTNode{ public: char ch; //字符 int weight;//权重 HTNode *left;//左孩子 HTNode *right;//右孩子 HTNode(int weight) : weight(weight) {} //重载比较运算符，便于排序，构造优先队列 bool operator<(const HTNode &htnode) const{ return weight > htnode.weight; } //两个构造函数 HTNode(char ch, int weight, HTNode *left, HTNode *right) : ch(ch), weight(weight), left(left), right(right) {} HTNode(char ch, int weight) : ch(ch), weight(weight) {} }; 1.3函数结构说明 /** * 通过优先队列构建赫夫曼树 * @param queue */ void CreateHuffmanTree(priority_queue<HTNode> &queue); /** * 通过字符串统计字符的频率 * @param s 需要统计的源数据 * @return 返回一个优先队列，方便赫夫曼树筛选最小节点 */ priority_queue<HTNode> count(string s); /** * 展示每个字符对应的权重 * @param q 优先字符队列 */ void show(priority_queue<HTNode> q); /** * 通过路径读取文件 * @param path 需要读的文件路径 * @return //以字符串类型返回文件中的数据 */ string readFile(string path); /** * 根据路径写入文件 * @param path 文件路径 * @param data 需要写入文件的内容(字符串类型) */ void writeFile(string path,string data); void writeFile(string path,char data);//重载写文件函数，以char类型写入 static map<char,string> huffmanCode; //静态的全局变量map集合：key为字符，string为对应编码，用来作为编码表 /** * 获取编码表，此处配合静态的Map集合存入编码 * @param root 赫夫曼树的根节点 * @param code 路径编码，右为1，左为0 * @param prefix 到该节点的路径，因为使用递归，所以要传入地址 */ void getCodes(HTNode *root,string code,string &prefix); /** * 打印编码表 * @param codes 通过map集合配合迭代器输出每个字符对应的编码 */ void printCode(map<char,string> codes); /** * 通过编码表和文件读取出的数据来生成->编码数据 * @param codetTable 编码表 * @param data 数据源 * @return 返回字符串展示编码数据 */ string BecomeCode(map<char,string> codetTable,string data); /** * 解码：通过编码表和编码后的数据 * @param codetTable 编码表 * @param CodeData 编码数据 */ void deCode(map<char,string> codetTable,string CodeData);

2、算法或程序模块

2.1 程序流程解释： ①创建赫夫曼树：统计字符的频率由小到大放入优先队列，通过队列找出最小频率构建赫夫曼树。 ②生成赫夫曼编码和赫夫曼编码后的数据：通过递归遍历赫夫曼树，通过Map集合创建编码表，再使用编码表和源数据生成编码后的数据。 ③使用赫夫曼编码解码：通过查找编码后的数据配合编码表，通过查找方式输出对应的字符 核心函数解释 构造赫夫曼树：最小左右孩子的权重相加，生成父节点，然后父节点进队列

/** * 创建赫夫曼树 * @param queue 构造的节点队列 * @return 返回哈夫曼树的根节点 */ void CreateHuffmanTree(priority_queue<HTNode> &queue){ while (queue.size()>1){ HTNode *left = new HTNode(queue.top()); queue.pop(); //队列弹出左右孩子 HTNode *right = new HTNode(queue.top()); queue.pop(); HTNode parent('R',left->weight + right->weight,left,right);//通过最小的两个节点权重相加构造父节点 queue.push(parent);//父节点进队列 } } 统计每个字符出现的频率：字符范围是ASCALL:0-128 priority_queue<HTNode> count(string s){ int a[128] = {0}; priority_queue<HTNode> queue; for (int i = 0; i < s.length();i++) { if (s[i] >= 0 && s[i] <= 127) { a[s[i]]++; }//筛选每个字符出现的频率 } for (int i = 0; i < 128;i++) { if (a[i]!=0){ //如果有该字符那就进队列 HTNode *htNode = new HTNode((char)i,a[i]); queue.push(*htNode); } } return queue; } 这里使用了二叉树的DFS方法，进行递归搜索叶子节点，然后存入map编码表中 /** * 获取编码表，此处配合静态的Map集合存入编码 * @param root 赫夫曼树的根节点 * @param code 路径编码，右为1，左为0 * @param prefix 到该节点的路径，因为使用递归，所以要传入地址 */ void getCodes(HTNode *root,string code,string &prefix){ string s=prefix;//拷贝该节点的路径 s.append(code);/通过append方法连接该节点的路径 //判断节点是否为空 if(root){ //如果不是叶子节点 if (root->ch==82){ getCodes(root->left,"0",s);//向左递归 getCodes(root->right,"1",s);//向右递归 }else{如果是叶子节点 huffmanCode[root->ch] = s; } } } 编码：字符串的append追加函数来连接源数据对应的编码表 解码：双层循环移动指针来截取字符串，然后找到对应的编码表，输出字符到文件中 string BecomeCode(map<char,string> codetTable,string data){ string res=""; for (int i = 0; i < data.length(); ++i) { res.append(codetTable[data[i]]); //主要使用了字符串的append追加函数来连接源数据对应的编码表 } ... } void deCode(map<char,string> codetTable,string CodeData){ ...... for (int i = 0; i < CodeData.length(); ++i) { //双指针循环截取字符串 for (int j = 0; j < 10; ++j) { sub = CodeData.substr(i,j); //截取字符串：从i开始，截取j个字符 it = codetTable.begin(); while(it != codetTable.end()){ if(sub == it->second){ char s = it->first; cout<<s; writeFile("D:\\解码文件.txt",s); i = j + i ; //移动指针 j = 0;//移动指针 break; } ++it; ...... 通过路径读文件和写文件 string readFile(string path){ ifstream ifs; ifs.open(path,ios::in);//1、创建输入流对象，并打开 if (!ifs.is_open()) { cout << "文件打开失败" << endl;return ""; } string res; while (getline(ifs, res)) { cout <<"读取的信息为： "<< res << endl; } ifs.close();//关闭文件 return res; } // 写文件 void writeFile(string path,string data) { //1、创建输出流对象，并打开 ofstream ofs(path, ios::out); //2、写文件 ofs<<data<<endl; //3、关闭文件 ofs.close(); } 主程序main函数 int main(){ string s = readFile("D:\\源文件.txt");//打开数据源文件 priority_queue<HTNode> queue = count(s);//获取单词的频率，通过升序进入优先队列 show(queue);//输出队列 CreateHuffmanTree(queue);//创建赫夫曼树 string bulid=""; HTNode root = queue.top();//获取树根节点 getCodes(&root,"",bulid);//开始生成编码表 printCode(huffmanCode);//展示编码表 string res = BecomeCode(huffmanCode,s);//生成编码数据 writeFile("D:\\编码文件.txt",res);//写入生成的01数据放入编码文件 deCode(huffmanCode,res);//将编码数据解码 return 0; }.

程序源代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> //map数据结构存储HT编码表 #include <queue> //构建的节点的优先性 #include <string> //字符串方便输入输出 #include <iterator> //迭代器输出map展示 #include <fstream> //读写文件 using namespace std; class HTNode{ public: char ch; //字符 int weight;//权重 HTNode *left;//左孩子 HTNode *right;//右孩子 HTNode(int weight) : weight(weight) {} //重载比较运算法，便于排序，构造优先队列 bool operator<(const HTNode &htnode) const{ return weight > htnode.weight; } //两个构造函数 HTNode(char ch, int weight, HTNode *left, HTNode *right) : ch(ch), weight(weight), left(left), right(right) {} HTNode(char ch, int weight) : ch(ch), weight(weight) {} }; /** * 通过优先队列构建赫夫曼树 * @param queue */ void CreateHuffmanTree(priority_queue<HTNode> &queue); /** * 通过字符串统计字符的频率 * @param s 需要统计的源数据 * @return 返回一个优先队列，方便赫夫曼树筛选最小节点 */ priority_queue<HTNode> count(string s); /** * 展示每个字符对应的权重 * @param q 优先字符队列 */ void show(priority_queue<HTNode> q); /** * 通过路径读取文件 * @param path 需要读的文件路径 * @return //以字符串类型返回文件中的数据 */ string readFile(string path); /** * 根据路径写入文件 * @param path 文件路径 * @param data 需要写入文件的内容(字符串类型) */ void writeFile(string path,string data); void writeFile(string path,char data);//重载写文件函数，以char类型写入 static map<char,string> huffmanCode; //静态的全局变量map集合：key为字符，string为对应编码，用来作为编码表 /** * 获取编码表，此处配合静态的Map集合存入编码 * @param root 赫夫曼树的根节点 * @param code 路径编码，右为1，左为0 * @param prefix 到该节点的路径，因为使用递归，所以要传入地址 */ void getCodes(HTNode *root,string code,string &prefix); /** * 打印编码表 * @param codes 通过map集合配合迭代器输出每个字符对应的编码 */ void printCode(map<char,string> codes); /** * 通过编码表和文件读取出的数据来生成->编码数据 * @param codetTable 编码表 * @param data 数据源 * @return 返回字符串展示编码数据 */ string BecomeCode(map<char,string> codetTable,string data); /** * 解码：通过编码表和编码后的数据 * @param codetTable 编码表 * @param CodeData 编码数据 */ void deCode(map<char,string> codetTable,string CodeData); /** * 创建哈夫曼树 * @param queue 构造的节点队列 * @return 返回哈夫曼树的根节点 */ void CreateHuffmanTree(priority_queue<HTNode> &queue){ while (queue.size()>1){ HTNode *left = new HTNode(queue.top()); queue.pop(); HTNode *right = new HTNode(queue.top()); queue.pop(); HTNode parent('R',left->weight + right->weight,left,right); queue.push(parent); } } priority_queue<HTNode> count(string s){ int a[128] = {0}; priority_queue<HTNode> queue; for (int i = 0; i < s.length();i++) { if (s[i] >= 0 && s[i] <= 127) { a[s[i]]++; } } for (int i = 0; i < 128;i++) { if (a[i]!=0){ HTNode *htNode = new HTNode((char)i,a[i]); queue.push(*htNode); } } return queue; } void show(priority_queue<HTNode> q){ while(!q.empty()){ HTNode node = q.top(); q.pop(); cout<<node.ch<<": "<<node.weight<<endl; } } void getCodes(HTNode *root,string code,string &prefix){ string s=prefix; s.append(code); if(root){ if (root->ch==82){ getCodes(root->left,"0",s); getCodes(root->right,"1",s); }else{ huffmanCode[root->ch] = s; } } } void printCode(map<char,string> codes){ map<char,string>::const_iterator it = codes.begin(); while(it != codes.end()){ cout<<"符号: "<<it->first<<"编码："<<it->second<<endl; ++it; } } /** * 生成赫夫曼编码数据 * @param codes 赫夫曼编码表 * @param data 需要编码的字符串 * @return */ string BecomeCode(map<char,string> codetTable,string data){ string res=""; for (int i = 0; i < data.length(); ++i) { res.append(codetTable[data[i]]); } return res; } void deCode(map<char,string> codetTable,string CodeData){ map<char,string>::const_iterator it; string sub=""; for (int i = 0; i < CodeData.length(); ++i) { for (int j = 0; j < 10; ++j) { sub = CodeData.substr(i,j); it = codetTable.begin(); while(it != codetTable.end()){ if(sub == it->second){ char s = it->first; cout<<s; writeFile("解码文件.txt",s); i = j + i ; j = 0; break; } ++it; } } } } string readFile(string path){ ifstream ifs; ifs.open(path,ios::in); if (!ifs.is_open()) { cout << "文件打开失败" << endl;return ""; } string res; while (getline(ifs, res)) { cout <<"读取的信息为： "<< res << endl; } ifs.close(); return res; } // 写文件 void writeFile(string path,string data) { //1、创建输出流对象，并打开 ofstream ofs(path, ios::out); //2、写文件 ofs<<data<<endl; //3、关闭文件 ofs.close(); } void writeFile(string path,char data) { //2、创建输出流对象，追加方式写入 ofstream ofs(path, ios::app); //4、写文件 ofs<<data; //5、关闭文件 ofs.close(); } int main(){ string s = readFile("源文件.txt");//打开数据源文件 priority_queue<HTNode> queue = count(s);//获取单词的频率，通过升序进入优先队列 show(queue);//输出队列 CreateHuffmanTree(queue);//创建赫夫曼树 string bulid=""; HTNode root = queue.top();//获取树根节点 getCodes(&root,"",bulid);//开始生成编码表 printCode(huffmanCode);//展示编码表 string res = BecomeCode(huffmanCode,s);//生成编码数据 writeFile("编码文件.txt",res);//写入生成的01数据放入编码文件 deCode(huffmanCode,res);//将编码数据解码 return 0; }