*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： 风动 E-mail：xidiankeda492@yahoo.com.cn QQ：３０５６８７９１０
*/ 时间： 2007-7-21 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------


#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include <string.h>
#define MAXSIZE 100 //最多子叶数
#define MAXCODE 10000 //编码最大长度

typedef struct
{
char info; //关联字符信息
unsigned int weight; //每个节点的权职
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode; //存储哈弗曼编码

void Select(HuffmanTree HT, int j,int &s1,int &s2)
{//选择双亲节点为0，并且最小的两个子叶节点
int i=1,m;
while(HT[i].parent!=0)
i++; //找第一个双亲节点为0的子叶结点
for(s2=s1=i;i<j;i++)
{//保证s1中的权值最小，s2次小
if(HT[i].parent==0 && HT[i].weight<HT[s1].weight)
{
s2=s1;
s1=i;
}
else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight && HT[i].weight<=HT[s2].weight)
s2=i;
while(HT[i].parent==0 && s1==s2)
{
m=i;
m++;
while(HT[m].parent!=0)
m++;
s2=m;
}
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info)
{//哈弗曼编码
int i,m;
HuffmanTree p;
if(n<1) return;
m = 2*n-1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w,++info)
{//初始化所有已存在的子叶信息
p->info = *info;
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(; i<=m;++i,++p)
{//构造所需要的过度根节点
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}//for
for(i=n+1;i<=m;++i)
{//建立哈弗曼树
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent =i;
HT[s2].parent =i;
HT[i].lchild = s2;
HT[i].rchild = s1;
HT[i].weight = HT[s1].weight+HT[s2].weight;
}//for
//哈弗曼编码
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
char* cd = (char*)malloc(n*sizeof(char));
cd[n-1] = '\0';
for(i=1;i<=n;++i)
{
int f;
unsigned int c;
int start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start] = '0';
else cd[--start] = '1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i], &cd[start]);
}//for
free(cd);
}//HuffmanCoding

void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m)
{//查询哈弗曼编码信息
// char *strcopy=new char[MAXCODE];
for(int i=0; i<m; i++)
{
for(int j=1; HT[j].info != strcheck[i]; j++);
cout<<HC[j];
}
cout<<endl;
}//CheckCoding

void HuffmanTranslateCoding(HuffmanTree HT, int n,char*c)
{//译码过程
int m=2*n-1;
int i,j=0;
while(c[j]!='\0')
{
i=m;
while(HT[i].lchild && HT[i].rchild)
{
if(c[j]=='0')
i=HT[i].lchild;
else if(c[j]=='1')
i=HT[i].rchild;
j++;
}
cout<<HT[i].info;
}
cout<<endl;
}
void main()
{
int n,*w,m;
w=new int[MAXSIZE];
char *info;
char *strcheck=new char[MAXSIZE];
info=new char[MAXSIZE];
char *ch=new char[MAXSIZE];
HuffmanTree HT=new HTNode[MAXSIZE];
HuffmanCode HC=NULL;
cout<<"***********************************************************"<<endl;
cout<<"****** HuffmanCode and HUffmanTranslate ********"<<endl;
cout<<"****** 西安电子科技大学 计算机学院 030514班 ********"<<endl;
cout<<"****** 学号： 03051433 制作人：王甲楼 ********"<<endl;
cout<<"***********************************************************"<<endl;
cout<<"读入叶子节点数 n= ";
cin>>n;
for(int i=0; i<n;i++)
{
cout<<"读入第"<<i+1<<"个叶子结点的权值：";
cin>>w[i];
cout<<"读入编码字符: ";
cin>>info[i];
}
HuffmanCoding( HT, HC, w, n,info);
cout<<"读入要查询的字符串中字符个数: ";
cin>>m;
cout<<"读入要编码的字符串: ";
cin>>strcheck;
CheckCoding(HT,HC,strcheck,m);
cout<<"读入编码: "<<endl;
cin>>ch;
HuffmanTranslateCoding(HT,n,ch);
}

存下来, 看看..
鼓励一下, 加油.

谢了！请多提宝贵意见！

求大神帮忙
一、二元Huffman码
在通信领域，信息编码是一种最基本的理论基础与技术手段，可以针对文字、声音、图像、视频、模型等，分为信源编码、信道编码。编码的方法有很多。1952年，一位外国人提出了一种逐个符号的编码方法，姑且称为H编码方法。其基本思想如下：
设有n个信号u1,u2,…,un，其概率分布依次为p（u1），p（u2），…，p（un），称为信号值，且满足下式：
p（u1）+p（u2）+…+p（un）=1
简记为：
 
H码的编码步骤可以简述为：
（1）    首先将n个信号按值的大小排列。
（2）    将最小的两个信号合并成一个新的信号，新信号的值为该两信号值的和，从而将原n个信号缩减为n－1个信号。
（3）    把缩减后的信号仍按值递减排列，然后再将其中最小的两个信号合并成一个新信号，这样又缩减为n－2个信号。
（4）    依此类推，直至只剩下１个信号为止。
（5）    将每次合并的两个信号分别用“0”和“1”两个符号表示。
（6）    从最后一级开始，向前返回，就得出各信号所对应的符号序列，即为各信号对应的码字。
例如：已知
 
其对应的H码如图所示：
 
再如：对
 
有两种编码过程：
  
方法(a)的具体原则是，把合并后的信号总是放在其他相同值的信号之上（或之左），方法（b）则是把合并后的信号值放在其他相同值的信号之下（或之右）。通过分析，方法（a）优于方法（b），方法（a）的方差比方法（b）的方差要小许多。
二、m元Huffman码
上面讨论的编码方法可称为二元编码，其思想可推广到m元编码。不同的只是每次把值最小的m个信号合并成一个新的信号，并分别用0，1，…，m－1等m个符号来表示。
对于m元编码，信号个数n必须满足下式：
n＝（m－1）Q＋m
式中：     n——信号个数
m——码元数
Q——缩减次数
对于二元码，总能找到一个Q，满足上式。但对于m元码，当n为任意正整数时，不一定能找到一个Q满足上式，此时，可以人为地增加一些值为零的信号以满足上式。然后取值最小的m个信号合并成一个新信号，并把这些信号的值相加作为该新信号的值，重新由大到小排序，再取最小的m个信号合并，如此下去。
m元的H码编码步骤如下：
（1）    验证所给n是否满足上式，若不满足，可以人为地增加一些值为零的信号，以使最后一步有m个信号；
（2）    取最小的m个符号合并成一个新信号，并分别用0，1，…，m－１给各分支赋值，把这些信号的值相加作为该新信号的值；
（3）    将新信号和剩下信号重新排序，重复（2）。
（4）    从最后一级开始，向前返回，就得出各信号所对应的符号序列，即为各信号对应的码字。
后来新加的值为零的信号，虽也赋予码字，但实际上是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等值信号排队时注意到顺序，则码长的方差也是最小的。
例如：
已知
 
其三元编码如下图所示：
 
四元编码如下图：
 
要求：
编写代码，设有50个信号，用二种方法，运行程序后，显现下面的参考界面：
H码编码
============
1．方法A
2．方法B
请选择（1或2 ，0：退出）：
选择一个菜单后，要求输入码元数N，N取值范围为2~16。输入后，显示编码结果。