二叉树,哈夫曼树,生成编码表
#include<iostream>
using namespace std;
//first a jiedian
struct HNode {
int weight;
int parent;
int Lchild;
int Rchild;
};
//second bainmajieidan
struct HCode {
char data;
char code[100];
};
//define huffman class
class Huffman {
private:
HNode*HTree;
HCode*Table;
char str[1024];
char leaf[256];
int a[256];
int N;
public:
int n;
void init();//dingyi huffman tree
void creatHTree(int a[],int n,char name[]);//chuangjian
void selectMin(int &x,int&y,int s, int e);//
void code(int i, string newcode);
void creatCodeTable();//chuangjian bianmacode chart
void Encode(char*d);//bianma
void Decode(char*s, char*d);//jiema
void print(int i, int m);
};
//yizi jiedianshu jinxing jisuan
void Huffman::init() {
int nNum[256] = { 0 };
int ch = cin.get();
int i = 0;
while ((ch != '\r') && (ch != '\n')) {
nNum[ch]++;//统计次数
str[i++] = ch;//记录初识字符
ch = cin.get();//用cin。get函数
}
str[i] = '\0';
n = 0;
for (i = 0; i < 256; i++) {
if (nNum[i] > 0) {
leaf[n] = (char)i;
a[n] = nNum[i];
n++;
}
}
}
//creat tree
void Huffman::creatHTree(int a[], int n, char name[]) {
N = n;
Table = new HCode[N];
HTree = new HNode[2 * N - 1];
for (int i = 0; i < n; i++) {
HTree[i].weight = a[i];
HTree[i].Lchild = HTree[i].Rchild = HTree[i].parent = -1;
Table[i].data = name[i];
}
int x, y;
for (int i = 0; i < 2 * N - 1; i++)//creat huffman tree
{
selectMin(x, y, 0, i);
HTree[x].parent = HTree[y].parent = i;
HTree[i].weight = HTree[x].weight + HTree[y].weight;
HTree[i].Lchild = x;
HTree[i].Rchild = y;
HTree[i].parent = -1;
}
}
//selectmin
void Huffman::selectMin(int &x, int&y, int s, int e) {
int i;
for (i=s;i<=e;i++)
if (HTree[i].parent == -1) {
x = y = i;
break;
}
for(;i<e;i++)
if (HTree[i].parent == -1) {
if (HTree[i].weight < HTree[x].weight) {
y = x;
x = i;
}
else if ((x == y) || (HTree[i].weight < HTree[y].weight))
y = i;
}
}
void Huffman::code(int i, string newcode) {
if (HTree[i].Lchild == -1) {
Table[i].code = newcode;
return;
}
code(HTree[i].Lchild, newcode + "0");
code(HTree[i].Rchild, newcode + "1");
}
//chuangjian bianmacode chart
void Huffman::creatCodeTable() {
code(2 * N - 2, "");
}
必须是可变值,以上是部分代码,代码报错部分在第106行,具体内容
void Huffman::code(int i, string newcode) {
if (HTree[i].Lchild == -1) {
Table[i].code = newcode;
return;
}
code(HTree[i].Lchild, newcode + "0");
code(HTree[i].Rchild, newcode + "1");
}
字符数组拷贝不能直接用=,Table[i].code的类型是char[100],用strcpy函数拷贝