实验二 赫夫曼编码及应用 实验学时：2 实验类型：综合型 一、目的与任务 1．目的：掌握赫夫曼（Huffman）树和赫夫曼编码的基本思想和应用。 2．任务：实现文件中数据的加解密与压缩。 二、内容、要求与安排方式 1．实验内容：将硬盘上的一个文本文件进行加密，比较加密文件和原始文件的大小差别；对加密文件进行解密，比较原始文件和解码文件的内容是否一致。 2．输入和输出： （1）输入：硬盘上给定的原始文件及文件路径。 （2）输出： 硬盘上的加密文件及文件路径； 硬盘上的解码文件及文件路径； 原始文件和解码文件的比对结果。 3．实验要求： 提取原始文件中的数据（包括中文、英文或其他字符），根据数据出现的频率为权重，构建Huffman编码表； 根据Huffman编码表对原始文件进行加密，得到加密文件并保存到硬盘上； 将加密文件进行解密，得到解码文件并保存点硬盘上； 比对原始文件和解码文件的一致性，得出是否一致的结论。 4．实验安排方式： 在实验课前编写出完整程序，在实验课时进行调试； 每组1人，独立完成上机实验。 三、注意事项： 1．本实验涉及到赫夫曼树和赫夫曼编码基本思想和构建方法；C语言文件的建立、读取、写入方法；C语言位运算等知识。 2．请在实验报告中说明Huffman编码表的构建过程。
【实现思路】
加密： 权值构建mapmap构建哈弗曼树构建编码map 解密： 遍历加密串根据map解密字典进行解密并生成string 比对： 对明文生成密文，加载文件密文。比对字符串 //solve.h /** author:mmciel time：2019-5-15 17:07:39 完成哈夫曼树的操作 */ #include <bits/stdc++.h> using namespace std; #ifndef SOLVE_H_INCLUDED #define SOLVE_H_INCLUDED /*=============================哈夫曼树相关=============================*/ //整形最大值 const int INF = 0x3f3f3f3f; //哈夫曼树 typedef struct huffNode { int weight; //权重 int lchild,rchild,parent; //左右子节点和父节点 }HTNode,*HuffTree; typedef char **HuffCode;//哈夫曼编码表，采用二级字符型指针 //权值最小的两个节点下标 void select(const HuffTree &HT,int n,int &s1,int &s2); //HT:哈夫曼树 //HC:哈夫曼编码 //w:构造哈夫曼树节点的权值 //n:构造哈夫曼树节点的个数 void HuffmanCode(HuffTree &HT,HuffCode &HC,int *w,int n); /*=============================文件处理相关=============================*/ //文件读取到字符串 string readFile(string path); void saveFile(string savepath,string data); /*=============================页面交互相关=============================*/ void welcome();//欢迎界面 #endif // SOLVE_H_INCLUDED /** author:mmciel time:2019-5-15 17:09:00 完成字符频度计算逻辑 完成文件交互逻辑 完成加密解密逻辑 */ #include <bits/stdc++.h> #include "solve.h" using namespace std; /**/ /**/ const int nmax = 1000; string textdata;//文件中的数据 string textcode;//密文 string textdecode;//明文 string path,savepath;//文件地址 map<char,int> tmap;//字符串中字符频数 map<char,int> :: iterator iter; map<char,string> tcode; map<char,string> :: iterator iter2; char key[nmax];//char key （从1开始） int w[nmax];//权重 （从1开始） HuffTree HT;//树 HuffCode HC;//结果 int number = 0;//字符串中有多少种char //统计字符频率到tmap void CountStringChar(string s); //打印字频 void PrintTmap(); //tmap 中的规则写入到数组中，便于直接求树 void TempToArray(); //打印编码表 void PrintCode(); //生成密文 string getCode(string data); //生成明文 string getDecode(string data); //初始化内存 void init(); //文件对比 void contrastFile(string code,string decode); int main() { bool flag = true; int order = -1; // cout<<"\t1.文件编码\t2.文件解码"<<endl; // cout<<"\t3.文件对比\t4.查看规则"<<endl; // cout<<"\t5.清空内存\t6.退出程序"<<endl; while(1){ welcome(); cout<<"请输入命令："; cin>>order; switch(order){ case 1: init(); cout<<"请输入文件路径："; cin>>path; textdata = readFile(path); cout<<"文件内容："<<"\n" <<"============================\n" <<textdata<<"\n" <<"============================"<<endl; CountStringChar(textdata);//权重写入map TempToArray();//权重写入array HuffmanCode(HT,HC,w,number); textcode = getCode(textdata); cout<<"密文；"<<endl; cout<<textcode<<endl; cout<<"请输入文件完整路径以便于保存密文："; cin>>savepath; saveFile(savepath,textcode); cout<<"保存成功"<<endl; break; case 2: cout<<"请输入文件路径："; cin>>path; textdata = readFile(path); textdecode = getDecode(textdata); cout<<"明文:"<<endl; cout<<"============================="<<endl; cout<<textdecode<<endl; cout<<"============================="<<endl; break; case 3: cout<<"文件对比会清空已有规则！"<<endl; contrastFile(path,savepath); break; case 4: cout<<"编码规则："<<endl; PrintTmap(); cout<<"编码结果："<<endl; PrintCode(); break; case 5: init(); cout<<"清空成功！"<<endl; break; case 6: flag = false; cout<<"退出..."<<endl; break; default: cout<<"命令异常"<<endl; break; } if(!flag) break; } return 0; }