标题: 霍夫曼编码CPP实现 [打印本页]

---

作者: 反光镜    时间: 2018-5-27 15:28
标题: 霍夫曼编码CPP实现

#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的概率数量n=" ;

        cin>> num;

       if(num<=3)

        {

            cout<< "请检查输入概率数量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;

//二进制和三进制分别存储一份数据

           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);

//清空所有霍夫曼节点和索引

//                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);

        }

        //执行霍夫曼二进制的输出

         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;

        }

        //执行霍夫曼三进制的输出

        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;

    }

}

---

欢迎光临 (http://www.51hei.com/bbs/)

Powered by Discuz! X3.1