霍夫曼編碼CPP實現(xiàn)

ID:339109 · 發(fā)表于 2018-5-27 15:28

本帖最后由反光鏡于 2018-5-27 15:29 編輯

#include <iostream>

#include <list>

#include <vector>

#include <iomanip>

using namespace std;

struct Huff_node

{

int bit;

float prob;

// Huff_node*next_node1;

// Huff_node*next_node2;

// Huff_node*next_node3;

Huff_node*pre_node;

};

bool compareProb(Huff_node*, Huff_node*);

void ClearHuffNodeIndex(list<Huff_node*> *);

void print_Huff_Code(list<Huff_node*> *);

int main()

{

//vector里依次輸入N個概率，N未定

list<Huff_node*> Huff_node_index_B;

list<Huff_node*> Huff_node_encode_B;

list<Huff_node*> Huff_node_index_T;

list<Huff_node*> Huff_node_encode_T;

int num;

Huff_node*tmpHuff_node;

Huff_node*tmpHuff_node1;

Huff_node*tmpHuff_node2;

Huff_node*tmpHuff_node3;

while(1)

{

//每輸入一個概率，new一個node，存入概率

cout<< "請輸入大于3的概率數(shù)量n=" ;

cin>> num;

if(num<=3)

{

cout<< "請檢查輸入概率數(shù)量n是否大于3!!"<< endl << endl;

continue;

}

cout<< endl << "請輸入概率:" << endl;

while(num>0)

{

tmpHuff_node1 = new Huff_node;

tmpHuff_node2 = new Huff_node;

cin >> tmpHuff_node1->prob;

tmpHuff_node1->pre_node= nullptr;

tmpHuff_node1->bit = -1;

*tmpHuff_node2 = *tmpHuff_node1;

//二進制和三進制分別存儲一份數(shù)據(jù)

Huff_node_index_B.push_back(tmpHuff_node1);

Huff_node_index_T.push_back(tmpHuff_node2);

--num;

}

// if(sumProb>1)

// {

// cout << "ERROR！概率輸入有誤，請重新輸入全部概率" << endl << endl;

// ClearHuffNodeIndex(&Huff_node_index_B);

//清空所有霍夫曼節(jié)點和索引

// ClearHuffNodeIndex(&Huff_node_index_T);

// continue;

// }

//輸入完畢，vector進行sort，從大到小排序，并建立編碼vector組

Huff_node_index_B.sort(compareProb);

Huff_node_index_T.sort(compareProb);

Huff_node_encode_B = Huff_node_index_B;

Huff_node_encode_T = Huff_node_index_T;

//霍夫曼二進制編碼

while(Huff_node_encode_B.size()!=1)//當vector的元素不等于1

{

tmpHuff_node1 = Huff_node_encode_B.back();

Huff_node_encode_B.pop_back();

tmpHuff_node2 = Huff_node_encode_B.back();

Huff_node_encode_B.pop_back();

tmpHuff_node1->bit = 0;

tmpHuff_node2->bit = 1;

//建立前向鏈接

tmpHuff_node = new Huff_node;

tmpHuff_node->bit=-1;

tmpHuff_node->pre_node = nullptr;

tmpHuff_node->prob=tmpHuff_node1->prob+ tmpHuff_node2->prob;

//取出最前面的兩個node，掛接到新new的node后面

tmpHuff_node1->pre_node = tmpHuff_node;

tmpHuff_node2->pre_node = tmpHuff_node;

//將new node放入vector尾部

Huff_node_encode_B.push_back(tmpHuff_node);

//重新sort

Huff_node_encode_B.sort(compareProb);

}

//執(zhí)行霍夫曼二進制的輸出

cout<< endl << endl << "霍夫曼二進制編碼為:"<< endl;

print_Huff_Code(&Huff_node_index_B);

//霍夫曼三進制編碼

while(Huff_node_encode_T.size()>2)//當vector的元素不等于1

{

tmpHuff_node1 = Huff_node_encode_T.back();

Huff_node_encode_T.pop_back();

tmpHuff_node2= Huff_node_encode_T.back();

Huff_node_encode_T.pop_back();

tmpHuff_node3 = Huff_node_encode_T.back();

Huff_node_encode_T.pop_back();

tmpHuff_node1->bit = 0;

tmpHuff_node2->bit = 1;

tmpHuff_node3->bit = 2;

//建立前向鏈接

tmpHuff_node = new Huff_node;

tmpHuff_node->pre_node =nullptr;

tmpHuff_node->prob=tmpHuff_node1->prob+tmpHuff_node2->prob+tmpHuff_node3->prob;

//取出最前面的兩個node，掛接到新new的node后面

tmpHuff_node1->pre_node = tmpHuff_node;

tmpHuff_node2->pre_node = tmpHuff_node;

tmpHuff_node3->pre_node = tmpHuff_node;

//將new node放入vector尾部

Huff_node_encode_T.push_back(tmpHuff_node);

//重新sort

Huff_node_encode_T.sort(compareProb);

}

if(Huff_node_encode_T.size()==2)

{

tmpHuff_node1 = Huff_node_encode_T.back();

tmpHuff_node1->bit = 0;

Huff_node_encode_T.pop_back();

tmpHuff_node2 = Huff_node_encode_T.back();

tmpHuff_node2->bit = 1;

}

//執(zhí)行霍夫曼三進制的輸出

cout<< endl << endl << "霍夫曼三進制編碼為:"<< endl;

print_Huff_Code(&Huff_node_index_T);

ClearHuffNodeIndex(&Huff_node_index_B);

ClearHuffNodeIndex(&Huff_node_index_T);

cout<< endl << endl << endl;

}//Processingcompleted, go to next circle

}

bool compareProb(Huff_node* node1, Huff_node* node2)

{

if(node1->prob > node2->prob )

returntrue;

else

returnfalse;

}

void ClearHuffNodeIndex(list<Huff_node*> *index)

{

for(list<Huff_node*>::iterator i = (*index).begin();i!= (*index).end();i++)

{

delete(*i);

}

(*index).clear();

}

void print_Huff_Code(list<Huff_node*> *to_print)

{

Huff_node*curHuff_node;

vector<int> curCode;

for(list<Huff_node*>::iterator i =(*to_print).begin();i != (*to_print).end();i++)

{

curHuff_node = (*i);

cout<< setw(8) << curHuff_node->prob << " 的編碼: " ;

while(curHuff_node->pre_node!=nullptr)

{

curCode.push_back(curHuff_node->bit);

curHuff_node = curHuff_node->pre_node;

}

if(curHuff_node->bit!=-1)

curCode.push_back(curHuff_node->bit);

for(intj=curCode.size();j>0;j--)

{

cout<< curCode[j-1];

}

curCode.clear();

cout<< endl;

}

帳號		自動登錄	找回密碼
密碼			立即注冊

久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

霍夫曼編碼CPP實現(xiàn)