C语言有关哈夫曼树的问题..救急呀!!!
发布网友
发布时间：2022-05-26 16:41
共3个回答
热心网友
时间：2023-10-28 19:43
#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 [程序结束]
///////////////////////////////////////////
其实真正应用的时候可以将出现的字符数及其频度都保存在编码后的文件中，直接读取文件，就能解码了！！！！！！！！！
热心网友
时间：2023-10-28 19:44
代码342行
使用了一个最小堆 把字母的权重赋好值之后 插入到最小堆里 每次从堆里取出两个权重最小的元素 然后把这两个元素组成一个新的树 树根结点权重等于两个子结点权重之后 然后把这棵树再插入到最小堆中 循环做到只剩一棵树后 该树就为霍夫曼树 先根输出 使用一个递归操作就可完成
楼主加油哈！
热心网友
时间：2023-10-28 19:44
