求解Huffman编码，不会了，马上就要上交的，谢谢拉
现在我已经做的部分
#include<iostream>
using namespace std;
typedef struct
{
char elem; //记录字母和空格
int weight; //记录字母和空格的个数，频数
}count;
typedef struct
{
char elem;
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree; //动态分配数字存储Huffman树
typedef char * * HuffmanCode; //动态分配数组存储Huffman编码表
void Select(HuffmanTree &HT, int n, int s1, int s2)
{
for(int i = 1; i < n; i++)
{
if(HT.parent == 0)
{
if(HT.weight < HT[i+1].weight)
{
s1 = i;
HT.parent = i;
}
}
}
for(int j = 1; j < n; j++)
{
if(HT[j].parent == 0)
{
if(HT[j].weight < HT[i+1].weight)
{
s2 = i;
HT[j].parent = j;
}
}
}
return ;
}
//--------------------------------------Huffman树和Huffman编码的存储表示--------------------------------------//
//w存放n个字符的权值，构造huffman树HT，并求出n个字符的huffman编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, count *w, int n)
{
int i,m,s1,s2,start,c,f;
if(n <= 1)
return ;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
//给叶节点赋初值
for(i = 1; i <= n; ++i)
{
HT.weight = w[i-1].weight;
HT.elem = w[i-1].elem;
HT.parent = HT.lchild = HT.rchild = 0;
}
//非叶节点赋初值
for(; i <= m; ++i)
{
HT.weight = 0;
HT.elem = '0';
HT.parent = HT.lchild = HT.rchild = 0;
}
for(i = n + 1; i <= m; ++i) //建huffman树
{
//在HT[1...i - 1]选择parent为0，且weight最小的两个节点，其序号分别为s1,s2;
Select(HT,i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT.lchild = s1; HT.rchild = s2;
HT.weight = HT[s1].weight + HT[s2].weight;
}
//--------------------------------------从叶子到根逆向求每个字符的Huffman编码--------------------------------------//
HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
char* cd = (char *)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1] = '\0'; //编码结束符
for(i = 1; i <= n; ++i) //逐个字符求Huffman编码
{
start = n-1; //编码结束符位置
for(c = i, f = HT.parent; f!=0; c = f, f = HT[f].parent) //从叶子到根逆向求编码
if(HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
HC = (char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC, &cd[start]); //从cd复制编码到HC
}
free(cd); //释放工作空间
}
int main()
{
//给elem赋予自己的字符
count *cou;
cou = (count *)malloc(27*sizeof(count));
cou[0].elem = ' ';
cou[0].weight = 0;
for(int i = 1; i < 27; i++)
{
cou.elem = i + 96;
cou.weight = 0;
}
for(int j = 0; j < 27; j++)
{
cout << cou[j].elem << ":" << cou[j].weight << endl;
}
FILE *fp;
if(fp = fopen("in.dat","r"))
{
cout << "Has open the file!" << endl;
cout << endl;
//读取文件中的字符
char ch = fgetc(fp);
while(ch != EOF)
{
if(ch == 32)
cou[ch - 32].weight++;
else
cou[ch - 96].weight++;
ch = fgetc(fp);
}
for(int j = 0; j < 27; j++)
{
cout << cou[j].elem << ":" << cou[j].weight << endl;
}
HuffmanTree HT;
HuffmanCode HC;
//count *w;
//w存放n个字符的权值，构造huffman树HT，并求出n个字符的huffman编码HC
HuffmanCoding(HT, HC, cou, 27);
}
else
{
cout << "Open the file error!" << endl;
}
fclose(fp);
return 0;
}
