368 lines
11 KiB
C++
368 lines
11 KiB
C++
//#include <hwloc/helper.h>
|
|
#define Change(x,y) (x)^=(y)^=(x)^=(y);
|
|
struct HNode{
|
|
int weight;
|
|
int parent;
|
|
int LChild;
|
|
int RChild;
|
|
char data;
|
|
bool operator<(HNode & r){
|
|
if(this->parent != -1) return false;
|
|
if(r.parent != -1) return true;
|
|
return (this->weight < r.weight);
|
|
}
|
|
};
|
|
struct HCode{
|
|
char data;
|
|
char code[100];
|
|
bool operator==(char &_in){ return this->data == _in;}
|
|
};
|
|
class Huffman{
|
|
private:
|
|
HNode *HTree; // 哈弗曼树
|
|
HCode *HCodeTable; // 哈弗曼编码表
|
|
void SelectMin(int &x,int &y,int begin,int end); // 找两个最小值
|
|
void Reveres(char a[]); // 字符串倒置
|
|
public:
|
|
void CreateHTree(const int a[],const char *b,int n);
|
|
void CreateCodeTable(int n);
|
|
void Encode(char *s,char *b);
|
|
void Decode(char *s,char *b);
|
|
explicit Huffman(const char *a);
|
|
HCode *GetHCodeTable(){return HCodeTable;}
|
|
HNode *GetHTree(){return HTree;}
|
|
~Huffman();
|
|
};
|
|
void Huffman::SelectMin(int &x, int &y, int begin, int end){
|
|
x = begin-1;while (HTree[++x].parent !=-1);
|
|
y = x;while (HTree[++y].parent !=-1);
|
|
if(HTree[y] < HTree[x]) Change(x,y);
|
|
for(int i = x;i < end;i++) if(HTree[i] < HTree[x]) x = i;
|
|
for(int i = y;i < end;i++) if(HTree[i] < HTree[y] && i != x) y = i;
|
|
}
|
|
void Huffman::Reveres(char *a) {
|
|
int l = 0;
|
|
while (a[++l] != '\0');
|
|
for(int i = 0;i<l/2;i++) Change(a[i],a[l-1-i]);
|
|
}
|
|
void Huffman::CreateHTree(const int *a,const char *b, int n) {
|
|
HTree = new HNode[2*n-1];
|
|
for(int i = 0;i<n;i++){
|
|
HTree[i].weight = a[i];
|
|
HTree[i].LChild = HTree[i].RChild = HTree[i].parent = -1;
|
|
HTree[i].data = b[i];
|
|
}
|
|
int x,y;
|
|
for(int i = n;i <2*n-1;i++){
|
|
SelectMin(x,y,0,i);
|
|
HTree[x].parent = HTree[y].parent = i;
|
|
HTree[i].weight = HTree[x].weight + HTree[y].weight;
|
|
HTree[i].LChild = x;
|
|
HTree[i].RChild = y;
|
|
HTree[i].parent = -1;
|
|
}
|
|
}
|
|
void Huffman::CreateCodeTable(int n){
|
|
HCodeTable = new HCode[n];
|
|
for(int i = 0;i < n;i++){
|
|
HCodeTable[i].data = HTree[i].data;
|
|
int child = i;
|
|
int parent = HTree[i].parent;
|
|
int k = 0;
|
|
while (parent != -1){
|
|
if(child == HTree[parent].LChild)
|
|
HCodeTable[i].code[k] = '0';
|
|
else
|
|
HCodeTable[i].code[k] = '1';
|
|
k++;
|
|
child = parent;
|
|
parent = HTree[child].parent;
|
|
}
|
|
HCodeTable[i].code[k] = '\0';
|
|
Reveres(HCodeTable[i].code);
|
|
}
|
|
}
|
|
void Huffman::Decode(char *s, char *b) {
|
|
while (*s!='\0'){
|
|
int parent = -1;
|
|
while (HTree[++parent].parent != -1);
|
|
while (HTree[parent].LChild != -1){
|
|
if(*s == '0')
|
|
parent = HTree[parent].LChild;
|
|
if(*s == '1')
|
|
parent = HTree[parent].RChild;
|
|
s++;
|
|
}
|
|
*b = HCodeTable[parent].data;
|
|
b++;
|
|
}
|
|
}
|
|
void Huffman::Encode(char *s, char *b) {
|
|
int h=0;
|
|
int n = -1;
|
|
while (s[++n] != '\0');
|
|
for(int i = 0;i<n;i++){
|
|
int j = -1;
|
|
while (HCodeTable+(++j)){
|
|
if(HCodeTable[j] == s[i])break;
|
|
}
|
|
int hc = 0;
|
|
while (HCodeTable[j].code[hc] != '\0')
|
|
b[h++] = HCodeTable[j].code[hc++];
|
|
}
|
|
}
|
|
Huffman::~Huffman() {
|
|
delete[](HCodeTable);
|
|
delete[](HTree);
|
|
}
|
|
Huffman::Huffman(const char *a){
|
|
int cont = 0;
|
|
HTree = nullptr;
|
|
HCodeTable = nullptr;
|
|
while (a[++cont] != '\0');
|
|
auto *A = new char[cont]{'\0'};
|
|
auto *B = new int[cont]{0};
|
|
for(int i = 0; i<cont;i++){
|
|
int head = 0;
|
|
for(;head <= cont;head++){
|
|
if(head == cont){
|
|
head = -1;
|
|
while (B[++head] != 0);
|
|
A[head] = a[i];
|
|
break;
|
|
}
|
|
if(A[head] == a[i]) break;
|
|
}
|
|
B[head]++;
|
|
}
|
|
cont = -1;
|
|
while (B[++cont] != 0);
|
|
CreateHTree(B,A,cont);
|
|
CreateCodeTable(cont);
|
|
delete[] A;
|
|
delete[] B;
|
|
}
|
|
#include <iostream>
|
|
#include <iomanip>
|
|
#include <vector>
|
|
#include <cmath>
|
|
|
|
#ifdef WIN32
|
|
#define CLEAR "cls"
|
|
#elif defined(linux)
|
|
#define CLEAR "clear"
|
|
#endif
|
|
using namespace std;
|
|
void printTheHuffmanTree(Huffman &_in);
|
|
void printTheHuffmanCodeTable(Huffman &_in);
|
|
void DEplay(Huffman &_in);
|
|
int main(){
|
|
system(CLEAR);
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"| 哈弗曼树实现 |"<<endl;
|
|
cout <<"| |"<<endl;
|
|
cout <<"| 请先输入字符 |"<<endl;
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"输入字符：";
|
|
char a[100]={'\0'};
|
|
//cin >> a;
|
|
cin.get(a,100);
|
|
Huffman Huffman1(a);
|
|
char b[800]={'\0'};
|
|
char c[100]={'\0'};
|
|
int nb = -1,nc = -1;
|
|
Huffman1.Encode(a,b);
|
|
Huffman1.Decode(b,c);
|
|
while(b[++nb] != '\0');
|
|
while(c[++nc] != '\0');
|
|
system(CLEAR);
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"| 哈弗曼树实现 |"<<endl;
|
|
cout <<"| |"<<endl;
|
|
cout <<"| 哈弗曼树初始完毕 |"<<endl;
|
|
cout <<"| 初始化使用的字符串为： |"<<endl;
|
|
cout <<"|"<<setw(28)<<setiosflags(ios::left)<<a<<"|"<<endl;
|
|
cout <<"| 该字符串编码为： |"<<endl;
|
|
cout <<"|"<<setw(28)<<setiosflags(ios::left)<<b<<"|"<<endl;
|
|
cout <<"| 编码重新解码为： |"<<endl;
|
|
cout <<"|"<<setw(28)<<setiosflags(ios::left)<<c<<"|"<<endl;
|
|
cout <<"| 按Enter进入菜单 |"<<endl;
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"编码前长度"<<endl;
|
|
cout << nc*8 << endl;
|
|
cout << "编码后长度" <<endl;
|
|
cout << nb << endl;
|
|
cout << "压缩率" << endl;
|
|
cout << (double)nb/(nc*8) << endl;
|
|
cin.get();cin.get();
|
|
int chouse;
|
|
goback:;
|
|
system(CLEAR);
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"| 哈弗曼树实现 |"<<endl;
|
|
cout <<"| |"<<endl;
|
|
cout <<"| 输入下面数字完成对应的操作 |"<<endl;
|
|
cout <<"| 0 打印哈弗曼树的结构 |"<<endl;
|
|
cout <<"| 1 打印哈弗曼编码表 |"<<endl;
|
|
cout <<"| 2 进行其他编码/解码操作 |"<<endl;
|
|
cout <<"| 3 退出 |"<<endl;
|
|
cout <<"+----------------------------+"<<endl;
|
|
cout <<"请输入：";
|
|
cin >> chouse;
|
|
switch(chouse){
|
|
case 0:
|
|
printTheHuffmanTree(Huffman1);
|
|
break;
|
|
case 1:
|
|
printTheHuffmanCodeTable(Huffman1);
|
|
break;
|
|
case 2:
|
|
DEplay(Huffman1);
|
|
break;
|
|
case 3:
|
|
return 0;
|
|
default:
|
|
goto goback;
|
|
}
|
|
goto goback;
|
|
}
|
|
void printTheHuffmanTree(Huffman & _in){
|
|
HNode * root = _in.GetHTree();
|
|
int a = -1;
|
|
HNode * Hlist = root;
|
|
while (Hlist[++a].parent != -1);
|
|
root = &Hlist[a];
|
|
HNode * list[100][100];
|
|
list[0][0] = root;
|
|
int deep = 0;
|
|
bool end;
|
|
do{
|
|
deep++;
|
|
for(int bh = 0;bh<pow(2,deep-1);bh++){
|
|
if(list[deep-1][bh]){
|
|
if(list[deep-1][bh]->LChild != -1)
|
|
list[deep][bh*2] = &Hlist[list[deep-1][bh]->LChild];
|
|
if(list[deep-1][bh]->RChild != -1)
|
|
list[deep][bh*2+1] = &Hlist[list[deep-1][bh]->RChild];
|
|
}
|
|
}
|
|
end = true;
|
|
for(int bh = 0;bh<pow(2,deep);bh++)if(list[deep][bh]) end = false;
|
|
}while (!end);
|
|
system(CLEAR);
|
|
auto *soot = new int[deep];
|
|
soot[0]=2;
|
|
for(int n=1;n<deep;n++)soot[n]=2*soot[n-1]+1;
|
|
for(int n=0;n<deep;n++){
|
|
for(int bh = 0;bh < pow(2,n);bh++) {
|
|
if(!list[n][bh])
|
|
cout <<setw(soot[deep - n] + 1) << ' ';
|
|
else{
|
|
if (n != 0)
|
|
cout << setw(soot[deep - n] + 1)
|
|
<< setfill(' ')
|
|
<< setiosflags(ios::left);
|
|
if(list[n][bh]->data == '\0')
|
|
cout << list[n][bh]->weight ;
|
|
else
|
|
cout << list[n][bh]->data;
|
|
}
|
|
}
|
|
cout << endl;
|
|
for(int bh = 0;bh < pow(2,n);bh++) {
|
|
if(list[n][bh] && list[n][bh]->data == '\0')
|
|
cout << setw(soot[deep-n-1]+1)
|
|
<< setfill('-')
|
|
<< setiosflags(ios::left)
|
|
<< '|'
|
|
<< setw(soot[deep-n-1]+1)
|
|
<< setfill(' ')
|
|
<< setiosflags(ios::left)
|
|
<< '+';
|
|
else cout << setw(2*(soot[deep-n-1]+1))
|
|
<< setfill(' ') << ' ';
|
|
}
|
|
cout << endl;
|
|
for(int bh = 0;bh < pow(2,n);bh++) {
|
|
if(list[n][bh] && list[n][bh]->data == '\0')
|
|
cout << setw(soot[deep-n-1]+1)
|
|
<< setfill(' ')
|
|
<< setiosflags(ios::left)
|
|
<< '|'
|
|
<< setw(soot[deep-n-1]+1)
|
|
<< setfill(' ')
|
|
<< setiosflags(ios::left)
|
|
<< '|';
|
|
else cout << setw(2*(soot[deep-n-1]+1))
|
|
<< setfill(' ') << ' ';
|
|
}
|
|
cout << endl;
|
|
}
|
|
delete[] soot;
|
|
cout<< "按回车回到主菜单";
|
|
cin.get();cin.get();
|
|
}
|
|
/*
|
|
* 0 0
|
|
* |-----+ |-----+
|
|
* | | | |
|
|
* 1 1 1 1
|
|
* |--+ |--+ |--+ |--+
|
|
* | | | | | | | |
|
|
* 2 2 2 2 2 2 2 2
|
|
*/
|
|
void printTheHuffmanCodeTable(Huffman &_in){
|
|
HCode * table = _in.GetHCodeTable();
|
|
system(CLEAR);
|
|
cout << "+------+----------+"<<endl;
|
|
cout << "| code | coding |"<<endl;
|
|
cout << "+------+----------+"<<endl;
|
|
int i = -1;
|
|
while (table[++i].code[0] != '\0'){
|
|
cout <<"| "<<table[i].data<<" |"<<setw(10)<<setfill(' ')<<table[i].code<<"|"<<endl;
|
|
}
|
|
cout << "+------+----------+"<<endl;
|
|
cout << "按回车返回菜单"<<endl;
|
|
cin.get();cin.get();
|
|
}
|
|
void DEplay(Huffman &_in){
|
|
cout << "请选择："<<endl;
|
|
cout << "1. 编码"<<endl;
|
|
cout << "2. 解码"<<endl;
|
|
cout << "当前可以编码的字符：";
|
|
HCode * table = _in.GetHCodeTable();
|
|
int i = -1;
|
|
while (table[++i].code[0] != '\0'){
|
|
cout <<table[i].data<<" ";
|
|
}
|
|
cout <<endl;
|
|
cout << "当前可以解码的字符：";
|
|
i = -1;
|
|
while (table[++i].code[0] != '\0'){
|
|
cout <<table[i].code<<" ";
|
|
}
|
|
cout <<endl;
|
|
cout << "请输入：";
|
|
cin >> i;
|
|
char a[800];
|
|
char b[100];
|
|
if(i == 2){
|
|
cout << "请输入需要解码的字符：";
|
|
cin >> a;
|
|
_in.Decode(a,b);
|
|
cout << "解码完毕 结果是："<<endl;
|
|
cout << b <<endl;
|
|
} else{
|
|
cout << "请输入需要编码的字符：";
|
|
cin >> b;
|
|
_in.Encode(b,a);
|
|
cout << "编码完毕 结果为："<< endl;
|
|
cout << a<<endl;
|
|
cout << "顺便帮你解一下"<<endl;
|
|
_in.Decode(a,b);
|
|
cout << b << endl;
|
|
}
|
|
cout << "按回车返回"<<endl;
|
|
cin.get();cin.get();
|
|
}
|