数据结构实训1
问题描述：
1、文本文件的编码解码（文本文件压缩为01编码，解码01编码为文本文件）
有一篇英文文章存储在一个文本文件中，现在要以报文形式将文章发送。编写程序，设计Haffman编码将文章转换为01编码。报文接收端要将01编码转换为英文文章，编写程序将Haffman编码报文译码。若编码是等长编码，是给出Haffman码与等长码的压缩比。基本要求：
（1）读英文文章“Text.txt”，统计每个字符在文章中出现的频率；将结果打印到文件“Freq.txt”
（2）构建Haffman树，求出每个字符的Haffman编码；将结果打印到文件“HaffCode.txt”
（3）将英文文章“Text.txt”转换为01字符串，将结果打印到文件“EngtoCode.txt”
（4）读文件“EngtoCode.txt”，将01字符串转换成英文文章。（译码）
(5) 若对文章“Text.txt”进行等长编码，试与Haffman 编码比较，求出该篇文章的压缩比。
算法思想：
(1)首先调用Get_req函数来获取每个字符出现的次数，用哈希将字符映射成出现的次数，并将其写入到Freq.txt文件中;
(2)调用Build_tree函数建立哈夫曼树，现将Freq.txt文件读入，并给叶子结点赋权值，然后每次选择两个权值最小的并且没有父节点的结点，对选择出来的结点构造其父节点，其父节点的权值为左右儿子权值之和，保证左二子的权值小于等于右儿子的权值。因为一共有n个叶子节点，每次操作都会减小一个节点的选择，故重复操作n-1次后，最后仅剩一个根节点，结束循环，建立了一颗哈夫曼树。
(3)调用Creat_Hcode函数，遍历每一个叶子节点，维护其父节点的编号p，然后再寻找其父亲的父亲，知道找到根节点，在寻找根节点的同时，判断当前结点是其父亲的左二子还是右儿子，左儿子记录0，右儿子记录1，用tep字符串记录从叶子到根的路径，因为哈夫曼编码是从根节点开始编码，故再将路径翻转，即为根到叶子的路径，最后通过hash将字符映射成哈夫曼编码，同时将哈夫曼编码映射成对应的字符，供解码使用。
(4)调用work函数，对文本进行加密，维护res字符串储存加密后的01编码，运用hash将字符转换成对应的哈夫曼编码，并加入到res中，遍历完文本后，res即为所求。
(5)调用Decode函数，对加密文本进行解码，维护tep字符串，读取01代码，并判断当前01码是否有对应的字符，有就输出，并清空tep，没有则继续读取01码。（因为每个需要哈夫曼编码字符均为叶子结点，故没有任何字符的哈夫曼编码是其他字符哈夫曼编码的前缀，所以不会输出混乱）
(6)调用cal函数计算压缩比。
压缩比公式 :（等长编码文本长度-哈夫曼编码文本长度）/ 等长编码文本长度
这里需要编码的字符共有40个，故等长编码长度为6（可编码64种不同的字符）最为合适。
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f;
char txt[N];
int n,Len;
map<char,int> fre;
map<char,string> jiami;
map<string,char> jiema;
vector<char> v;
struct Node {
int w;
int L_child,R_child,parent;
char name;
} HNode[N];
string Code[N];
void Get_freq() {
freopen("Text.txt","r",stdin);
freopen("Freq.txt","w",stdout);
cin.getline(txt,N);
int len = strlen(txt);
for(int i=0; i<len; i++) {
if(!fre[txt[i]]) v.push_back(txt[i]);
fre[txt[i]]++;
}
n = v.size();
for(int i=0; i<n; i++)
cout<<v[i]<<" "<<fre[v[i]]<<endl;
fclose(stdin);
fclose(stdout);
}
void Creat_Hcode() {
string tep;
for(int i=1; i<=n; i++) {
tep.clear();
int now_id = i;
int p = HNode[i].parent;
while(p!=-1) {
if(HNode[p].L_child == now_id) tep += "0";
else tep += "1";
now_id = p;
p = HNode[now_id].parent;
}
reverse(tep.begin(),tep.end());
Code[i] = tep;
}
cout<<"将编码信息写入到HaffCode.txt文件中"<<endl;
freopen("HaffCode.txt","w",stdout);
for(int i=1; i<=n; i++) {
cout<<HNode[i].name<<" "<<Code[i]<<endl;
jiami[HNode[i].name] = Code[i];
jiema[Code[i]] = HNode[i].name;
}
fclose(stdin);
fclose(stdout);
}
void Build_tree() {
for(int i=1; i<2*n; i++) { // n个叶子结点 ---> 2n-1个结点
HNode[i].L_child = -1;
HNode[i].R_child = -1;
HNode[i].parent = -1;
HNode[i].w = 0;
}
freopen("Freq.txt","r",stdin);
for(int i=1; i<=n; i++) {
scanf("%c %d",&HNode[i].name,&HNode[i].w);
getchar();
}
for(int i=1; i<n; i++) {
int a = INF;
int b = INF;
int id1 = 0; //最小
int id2 = 0; //次小
for(int j=1; j<n+i; j++) {
if(HNode[j].parent == -1 && HNode[j].w<a) {
b = a;
id2 = id1;
a = HNode[j].w;
id1 = j;
} else if(HNode[j].parent == -1 && HNode[j].w<b) {
b = HNode[j].w;
id2 = j;
}
}
//cout<<id1<<" "<<id2<<endl;
HNode[id1].parent = HNode[id2].parent = n+i;
HNode[n+i].w = HNode[id1].w + HNode[id2].w;
HNode[n+i].L_child = id1;
HNode[n+i].R_child = id2;
}
printf("结点信息:n");
for(int i=1; i<2*n; i++)
cout<<HNode[i].name<<"t"<<HNode[i].w<<"t"<<HNode[i].L_child<<"t"<<HNode[i].R_child<<"t"<<HNode[i].parent<<endl;
cout<<"构造哈夫曼编码"<<endl;
Creat_Hcode();
}
string res;
void work() {
int len = strlen(txt);
res.clear();
for(int i=0; i<len; i++) res += jiami[txt[i]];
freopen("EngtoCode.txt","w",stdout);
cout<<res<<endl;
freopen("CON","w",stdout);
cout<<"已成功将加密文本写入到EngtoCode.txt文件中"<<endl;
cout<<"加密后的文本长度:"<<res.size()<<endl;
fclose(stdout);
}
void Decode() {
freopen("EngtoCode.txt","r",stdin);
freopen("Decode.txt","w",stdout);
string tep;
char x;
tep.clear();
while(~scanf("%c",&x)) {
tep += x;
if(jiema[tep]) {
cout<<jiema[tep];
tep.clear();
}
}
freopen("CON","w",stdout);
cout<<"已成功加译文写入Decode.txt文件中"<<endl;
cout<<"解码密文后的文本和原文本一致"<<endl;
fclose(stdin);
fclose(stdout);
}
void cal() {
double t1 = strlen(txt) * 6; //等长编码文本长度
double t2 = res.size(); //哈夫曼编码文本长度
freopen("CON","w",stdout);
printf("等长编码文本长度(六位)：%.0lfn哈夫曼编码长度:%.0lfn压缩比:%lf%%n",t1,t2,((t1-t2)/t1)*100);
double sum = 0;
for(int i=1; i<=n; i++)
sum += jiami[HNode[i].name].size() * ((double)fre[HNode[i].name]/(double)Len);
printf("等长压缩平均长度:6n");
printf("哈夫曼压缩平均长度:%lfn",sum);
printf("压缩比:%lf%%",((6.0-sum)/6.0)*100);
}
int main() {
Get_freq();
freopen("CON","w",stdout);
Len = strlen(txt);
cout<<"Freq.txt已创建完成"<<endl;
cout<<"文本长度:"<<Len<<endl;
cout<<"字符种类:"<<n<<endl;
Build_tree();
work(); //将文本加密
Decode(); //破译密文
cal();
fclose(stdout);
return 0;
}
建树过程可用堆优化：
Code：
void Build_tree() {
for(int i=1; i<2*n; i++) { // n个叶子结点 ---> 2n-1个结点
HNode[i].L_child = -1;
HNode[i].R_child = -1;
HNode[i].parent = -1;
HNode[i].w = 0;
}
freopen("Freq.txt","r",stdin);
for(int i=1; i<=n; i++) {
scanf("%c %d",&HNode[i].name,&HNode[i].w);
getchar();
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
for(int i=1; i<=n; i++) Q.push({HNode[i].w,i});
for(int i=1; i<n; i++) {
int id1 = Q.top().second;
Q.pop();
int id2 = Q.top().second;
Q.pop();
HNode[id1].parent = HNode[id2].parent = n+i;
HNode[n+i].w = HNode[id1].w + HNode[id2].w;
HNode[n+i].L_child = id1;
HNode[n+i].R_child = id2;
Q.push({HNode[n+i].w,n+i});
}
printf("结点信息:n");
for(int i=1; i<2*n; i++)
cout<<HNode[i].name<<"t"<<HNode[i].w<<"t"<<HNode[i].L_child<<"t"<<HNode[i].R_child<<"t"<<HNode[i].parent<<endl;
printf("构造哈夫曼编码n");
Creat_Hcode();
}
从根向叶子结点进行编码（所有路只走一遍，不会重复走）
如果从叶子向根节点进行编码，因为有共同祖先，所以会有重复走的路径，而从根向叶子结点即不会重复走。
Code：
void C(int now_id,string path) {
if(HNode[now_id].L_child == -1 && HNode[now_id].R_child == -1) Code[now_id] = path; //到了叶子结点
else {
string L = path + "0";
string R = path + "1";
if(HNode[now_id].L_child != -1) C(HNode[now_id].L_child,L);
if(HNode[now_id].R_child != -1) C(HNode[now_id].R_child,R);
}
}
void Creat_Hcode() {
string path;
path.clear();
C(2*n-1,path);
printf("将哈夫曼编码信息写入到HaffCode.txt文件中n");
freopen("HaffCode.txt","w",stdout);
for(int i=1; i<=n; i++) {
cout<<HNode[i].name<<" "<<Code[i]<<endl;
jiami[HNode[i].name] = Code[i];
jiema[Code[i]] = HNode[i].name;
}
fclose(stdin);
fclose(stdout);
}
学无止境，勇闯天涯。 OVO
ʕ ᵔᴥᵔ ʔ 嘿嘿