Huffman編碼 用c++編程

這是以前學算法課時寫的代碼；妳把接口稍微改壹下子，即只要把讀取輸入改成妳的題目要求即可：

核心的代碼：

#ifndef _HUFFAM

#define _HUFFAM

#include<iostream>

#include<vector>

#include<queue>

#include<string>

using namespace std;

/*************

本霍夫曼編碼函數是用模板寫成的

可以對壹些例如int型，char型，string型

進行基本的編碼.

****************/

template<typename T>

struct TreeNode

{

TreeNode()

{

lchild=rchild=0;

}

int frequrcy;

T ch;

TreeNode *lchild;

TreeNode *rchild;

};

//改變優先隊列默認優先級的重載運算符函數,重載為全局函數

template<typename T>

bool operator >(const TreeNode<T> & left,const TreeNode<T> &rigth)

{

return (left.frequrcy>rigth.frequrcy);

}

template<typename T>

TreeNode<T> huffman(vector< TreeNode<T> > &c)

{

size_t n=c.size();

TreeNode<T> huffamNode;

priority_queue<TreeNode<T>,vector<TreeNode<T> >, greater<TreeNode<T> > > q;

//所有的結點插入優先隊列中

for(int i=0;i<static_cast<int>(n);i++)

{

huffamNode=c[i];

//huffamNode.lchild=huffamNode.rchild=0;

q.push(huffamNode);

}

//核心代碼，建樹的過程

for(int i=0;i<static_cast<int>(n-1);i++)

{

TreeNode<T> *tempNode=new TreeNode<T>;

TreeNode<T> *xNode=new TreeNode<T>;

TreeNode<T> *yNode=new TreeNode<T>;

xNode->frequrcy=q.top().frequrcy;

xNode->ch=q.top().ch;

xNode->lchild=q.top().lchild;

xNode->rchild=q.top().rchild;

tempNode->lchild=xNode;

q.pop();

yNode->frequrcy=q.top().frequrcy;

yNode->ch=q.top().ch;

yNode->lchild=q.top().lchild;

yNode->rchild=q.top().rchild;

tempNode->rchild=yNode;

q.pop();

tempNode->frequrcy=xNode->frequrcy+yNode->frequrcy;

q.push(*tempNode);

}

return q.top();

}

//輸出編碼的函數,這個遞歸方式我不喜歡，過段時間改寫了

template<typename T>

void printHufman(TreeNode<T> *root,string s)

{

if(root->lchild!=0)

printHufman(root->lchild,s+"0");

if(root->rchild!=0)

printHufman(root->rchild,s+"1");

if(root->rchild==0&&root->lchild==0)

cout<<"被編碼對象"<<root->ch<<" "<<"頻率"<<root->frequrcy<<" "<<"編碼為"<<s<<endl;

}

#endif _HUFFAM

測試代碼：

#include<iostream>

#include<vector>

#include<queue>

#include<string>

#include"huffam.h"

using namespace std;

int main()

{

//測試string類型的數據，頻率是斐波那契數列

TreeNode<string> w[6];

vector<TreeNode<string> > v1;

w[0].frequrcy=1;

w[0].ch="sd";

w[1].frequrcy=1;

w[1].ch="hjg";

w[2].frequrcy=2;

w[2].ch="jghg";

w[3].frequrcy=3;

w[3].ch="jgh";

w[4].frequrcy=5;

w[4].ch="ui";

w[5].frequrcy=8;

w[5].ch="lk";

copy(w,w+6,back_inserter(v1));

TreeNode<string> re=huffman(v1);

cout<<"編碼的結果為"<<endl;

printHufman(&re,"");

cout<<endl;

//按照教材的數據進行編碼如下

TreeNode<int> v[6];

v[0].frequrcy=5;

v[0].ch=1;

v[1].frequrcy=9;

v[1].ch=3;

v[2].frequrcy=12;

v[2].ch=6;

v[3].frequrcy=45;

v[3].ch=4;

v[4].frequrcy=16;

v[4].ch=2;

v[5].frequrcy=13;

v[5].ch=34;

vector<TreeNode< int > > charv;

copy(v,v+6,back_inserter(charv));

TreeNode<int> charre=huffman(charv);

cout<<"編碼的結果為"<<endl;

printHufman(&charre,"");

return 0;

}

上一篇:總和的公式excel

下一篇:關於日常生活日記200字15篇