有关haffman的问题
我知道网上有很多huffman的源代码，但我还是自己一行一行的写出来了，可惜错了，不知道怎么改，麻烦各位给指导哈
#include <iostream>
#include <string.h>
using namespace std;
struct HNode
{
unsigned int weight;
unsigned int parent;
unsigned int LChild;
unsigned int RChild;
};
struct HCode
{
char data;
char code[100];
};
void Reverse(char *code)
{
int len;
len = strlen(code);
int i,j;
char temp;
for(i=0,j=len-1;i<j;i++,j--)
{
temp = code[i];
code[i] = code[j];
code[j] = temp;
}
}
class Huffman
{
private:
HNode* Htree;
HCode* HcodeTable;
public:
void CreatHTree(int a[],int n);
void CreatCodeTable(char b[],int n);
void Encode(char *s,char *d);
void Decode(char *s,char *d,int n);
void SelectMin(int x,int y,int a,int b);
~Huffman();
};
void Huffman::SelectMin(int x,int y,int a,int b)
{
x=0;y=0;
for(int i=a;i<=b;i++)
{
if(Htree[i].parent == -1)
{
if(Htree[i].weight < Htree[x].weight)
x =i;
}
}
for(int i=a;i<=b;i++)
{
if(Htree[i].parent == -1)
{
if(Htree[i].weight < Htree[y].weight && Htree[i].weight >= Htree[x].weight)
y = i;
}
}
}
void Huffman::CreatHTree(int a[],int n)
{
Htree = new HNode[2*n-1];
for(int i=0;i<n;i++)
{
Htree[i].weight = a[i];
Htree[i].parent = -1;
Htree[i].LChild = -1;
Htree[i].RChild = -1;
}
int x,y;
for(int i=n;i<2*n-1;i++)
{
SelectMin(x,y,0,i);
Htree[x].parent = Htree[y].parent = i;
Htree[i].LChild = x;
Htree[i].RChild = y;
Htree[i].weight = Htree[x].weight + Htree[y].weight;
Htree[i].parent = -1;
}
}
void Huffman::CreatCodeTable(char b[],int n)
{
HCode *HcodeTable = new HCode[n];
for(int i=0;i<n;i++)
{
HcodeTable[i].data = b[i];
int child = i;
int parent = Htree[i].parent;
int k = 0;
while(parent != -1)
{
if(child == Htree[parent].LChild)
HcodeTable[i].code[k] = 0;
else if(child== Htree[parent].RChild)
HcodeTable[i].code[k] = 1;
k++;
child = parent;
parent = Htree[parent].parent;
}
HcodeTable[i].code[k] = '\0';
Reverse(HcodeTable[i].code);
}
}
void Huffman::Encode(char *s,char *d)
{
int len;
while(*s != '\0')
{
int i = 0;
while(HcodeTable[i].data != *s)
{
i++;
}
len = strlen(HcodeTable[i].code);
strncat(d,HcodeTable[i].code,len);
++s;
}
}
void Huffman::Decode(char *s,char *d,int n)
{
int parent = 2*n-1;
while(*s != '\0')
{
while( Htree[parent].LChild != -1)
{
if(*s == '0')
parent = Htree[parent].LChild;
else
parent = Htree[parent].RChild;
s++;
}
*d = HcodeTable[parent].data;
d++;
}
}
int main()
{
Huffman obj;
char *s = "iloveyou";
char *d = NULL;
const int n = 7;
int a[n] = {1,2,3,4,5,6,7};
char b[n] = {'e','o','i','v','u','y','l'};
obj.CreatHTree(a,n);
obj.CreatCodeTable(b,n);
obj.Encode(s,d);
cout<<d<<endl;
}
