Question

高分求赫夫曼编码

求可以运行的赫夫曼编码的原代码~~~不用很长~~~~注意~~~是可以运行的~~~~很多在网上搜出来的不能运行~~~检测后可以运行的话我会追加100分~~~急~~~在线等~~~~
在VC++6.0环境下可以编译通过并且运行的哦~~~

Answer 1

#include "iostream"
#include "iomanip"
#include "string"
using namespace std;

#define MAX 256
typedef string *STR;

void InputData(string &s);
void DeCode();

typedef struct Huffnode {
unsigned weight; //权值 字符出现频率
bool in; // 是否加入Huffman树
int lchild,rchild;
void Set(unsigned &w,int lc=-1,int rc=-1,bool in = false ) {
weight = w;
lchild = lc;
rchild = rc;
in = in;
}
Huffnode() { weight=0; in = false;lchild=-1;rchild=-1;}
} *HuffTree;

void GetCode(HuffTree &nodes,int &k,STR &Code,string &str,int i,int leafNum,unsigned *Ind) {
if (k<leafNum) {
Code[Ind[k]] = str.substr (0,i);
return;
}
str[i] = '0';
GetCode(nodes,nodes[k].lchild ,Code,str,i+1,leafNum,Ind);
str[i] = '1';
GetCode(nodes,nodes[k].rchild ,Code,str,i+1,leafNum,Ind);
}

void GetMin(HuffTree &nodes,int n,int &min1,int &min2) { //得到两个最小节点下标
unsigned min;
for(int k=0;k<2;k++) {
min = 99999;
int t = 0;
for(int i=0;i<n;i++) {
if(nodes[i].in ) continue;
if(nodes[i].weight < min) {
min = nodes[i].weight;
t = i;
}
}
nodes[t].in = true;
if(k==0) min1 = t;
else min2 = t;
}
}

void MakeTree(HuffTree &Node,unsigned *Wei,int &Num) {
int i;
for(i=0;i<Num;i++) Node[i].Set(Wei[i]);
for(i=Num;i<2*Num-1;i++) {
int m1,m2;
GetMin(Node,i,m1,m2);
unsigned w = Node[m1].weight+Node[m2].weight ;
Node[i].Set(w,m1,m2);
}
}

void HaffmanCoding(string &In,STR &Code,int &N) {
unsigned Weight[MAX] = {0},Ind[MAX] = {0},Wei[MAX];
int i,Num = 0;
for(i=0;i<N;i++) Weight[(In[i]+256)%256]++;
for(i=0;i<MAX;i++) {
if (Weight[i]) {
Ind[Num] = i; //记录Everynode (0~Num-1)所存之字符代码
Wei[Num++] = Weight[i];
}
}
HuffTree Node = new Huffnode [2*Num-1];
MakeTree(Node,Wei,Num);
Code = new string[MAX];
string str; str.resize (MAX);
int nod = 2*Num-2;
GetCode(Node,nod,Code,str,0,Num,Ind);
cout<<endl<<"The Codes is:\n"<<endl;
cout<<"字符总数:"<<Num<<endl;
cout<<setw(10)<<"字符:"<<setw(10)<<"频度:"<<endl;
for(i=0;i<Num;i++) cout <<setw(10)<</*(char)*/Ind[i]<<setw(10)<<Wei[i]<<endl;
cout<<"\n码符:"<<endl;
for(i=0;i<N;i++) cout<<Code[(In[i]+256)%256];//<<" ";
cout<<endl<<endl;
}

void EnCode() {
string Input;
string *Code;
InputData(Input);
int N = Input.length ();
HaffmanCoding(Input,Code,N);
}

int main() {
cout<<"[1]--编码\n[2]--译码\n"<<endl;
if(cin.get ()=='1') {
EnCode();
}
else
DeCode();
cout<<endl;
return 1;
}

void InputData(string &s) {
cout<<"Please Input The Sources:\nPress 'A' & 'Enter' to Start:"<<endl;
char c;
while (cin.get ()!='A');
cin.get ();
cout<<"Start Input!!:"<<endl;
while ((c=cin.get())!='\n') s+=c;
}

//////////////////////////////////////////////////////////////////////

void DeCode() {
int num,i;
cout<<"输入出现的字符数:"<<endl;
cin>>num;
cout<<"输入每个字符对应的数字代码(0-255)及其频度:\n"
<<"格式: [代码][空格][频度]:\n"<<endl;
unsigned *Ind = new unsigned[num];
unsigned *Wei = new unsigned[num];
for(i=0;i<num;i++) cin>>Ind[i]>>Wei[i];
HuffTree Node = new Huffnode [2*num-1];
MakeTree(Node,Wei,num);
cout<<"Input The Code You Want to DeCode:"<<endl;
cout<<"Please Input The Code You Want to DeCode:\nPress 'A' & 'Enter' to Start:"<<endl;
while (cin.get ()!='A');
cin.get ();
cout<<"Start Input!!:"<<endl;
char c;
int k=2*num-2;
string Out;
while ((c=cin.get ())!='.') {
if(k<num) {
char s = (char)Ind[k];
Out += s;
k=2*num-2;
}
if(c=='0') k = Node[k].lchild ;
else if(c=='1') k = Node[k].rchild ;
}
cout<<"解码结果:\n"<<endl;
cout<<Out;
cout<<endl;
}

//////////////////////////////////////////
用VC6.0编译，程序运行时会提示你怎么输入的

刚开始选择编码还是译码，用1和2区分。
选择1后，编码...按要求输入你要编码的字符串就行了，可以输入任意字符，包括汉字和特殊符号。
选择2后，译码... 将上一部编码的结果现保存起来，再按要求输入程序提示的内容即可。
////////////////////////////////////////////////
下面是例子：
////-----------------
[1]--编码
[2]--译码

1
Please Input The Sources:
Press 'A' & 'Enter' to Start:
A [输入A和回车]
Start Input!!:
Hello,你是谁？ [要编码的内容]
[编码结果：]
The Codes is:

字符总数:13
字符: 频度:
44 1
72 1
101 1
108 2
111 1
163 1
173 1
191 1
196 1
199 1
202 1
203 1
227 1

码符:
0111100001001010010110110100111111110000101110101100
//-------------
[1]--编码
[2]--译码

2
输入出现的字符数:
13 [上一步编码时出现的字符总数，编码结束后有提示]
输入每个字符对应的数字代码(0-255)及其频度:
格式: [代码][空格][频度]:
[编码结束后的提示，copy过来即可]
44 1
72 1
101 1
108 2
111 1
163 1
173 1
191 1
196 1
199 1
202 1
203 1
227 1
Input The Code You Want to DeCode:
Please Input The Code You Want to DeCode:
Press 'A' & 'Enter' to Start:
A
Start Input!!: [开始输入码字]
0111100001001010010110110100111111110000101110101100
. [输入小数点[.]结束]
解码结果:

Hello,你是谁？

Press any key to continue [程序结束]
///////////////////////////////////////////
其实真正应用的时候可以将出现的字符数及其频度都保存在编码后的文件中，直接读取文件，就能解码了！！！！！！！！！

Answer 2

void select(HuffmanTree HT,int n,int& s1, int& s2){
int k;
for(k=1;k<=n;k++)
if(0==HT[k].parent)
{
s1=s2=k;
break;
}

for(int i=k+1;i<=n;i++)
if(HT[i].parent==0&&HT[i].weight<HT[s1].weight)
s1=i;

if(k==s1)
for(;k<=n;k++)
if(0==HT[k].parent)
{
s2 = k;
break;
}

for(i=k+1;i<=n;i++)
if(HT[i].parent==0&&i!=s1&&HT[i].weight<HT[s2].weight)
s2=i;
}

Answer 3

哈夫曼 编码吧?

是不是交课程设计的啊???

如果是交课程设计的话
我家里的本本上到有一个,大学时候用的,觉得可以运行.
不过具体怎么运行,就忘了.
东西是全地

共同学习,进步

Answer 4

http://dev.21tx.com/2005/05/06/11156.html