189 8069 5689
由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n－1个结点，可以用一个大小为2n－1的一维数组存放哈夫曼树的各个结点。在哈夫曼树构造好后，为了求得哈夫曼编码需要走一条从根结点出发到叶子结点的路径，则对每个结点既要知道其双亲还要知道孩子结点的信息。所以一维数组的每个元素包括四个数据项：结点的权值、结点的双亲结点下标号、左右孩子结点下标号。数据类型的定义如下：
我们一直强调成都网站设计、做网站对于企业的重要性,如果您也觉得重要,那么就需要我们慎重对待,选择一个安全靠谱的网站建设公司,企业网站我们建议是要么不做，要么就做好,让网站能真正成为企业发展过程中的有力推手。专业的建站公司不一定是大公司,创新互联公司作为专业的网络公司选择我们就是放心。
typedef struct Node
{
int weight ;
int parent, LChild,RChild ;
} HTNode, * HTree;
typedef char *HuffmanCode ;
创建哈夫曼树并求哈夫曼编码的算法如下：
viod CreatHTree(HTree ht , HuffmanCode hc,int * w, int n)
{ /*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc */
int start;
m=2*n-1;
ht=(HTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i=n;i++)
ht[i] ={ w[i],0,0,0};
for(i=n+1;i=m;i++)(* ht)[i] ={0,0,0,0};/* 初始化*/
for(i=n+1;i=m;i++)
{
select(ht,i-1,s1,s2);
/* 在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回，select函数要求在上机调试使补充定义*/
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].LChild=s1;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
} /*哈夫曼树建立完毕*/
/*以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程*/
hc=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char * )malloc(n * sizeof(char));
cd[n-1]＝’\0’；
for(i=1;i=n;i++)
{
start=n-1;
for(c=i,p=ht[i].parent; p!=0; c=p,p=ht[p].parent)
if(ht[p].LChild==c) cd[--start]=‘0’;
else cd[--start]=‘1’;
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],cd);
}
free(cd);
}
数组ht的前n个单元存放叶子结点的信息，最后一个单元存放的是根结点。
自己写个主程序，把八个字符的频率读入，调用CreatHTree就可以了
去年做的课程设计，有什么不合要求的自己改改
#includestring.h
#includestdlib.h
#includestdio.h
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i = n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j = n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i = n;i++)
if((HT[s1].weightHT[i].weight)(!HT[i].parent)(s2!=i))s1=i;
for(j = 1;j = n;j++)
if((HT[s2].weightHT[j].weight)(!HT[j].parent)(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
if (n=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i n;i++)
scanf("%d",w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i = n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}
说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。
#pragmaonce
#includestdio.h
#includetchar.h
#includestdlib.h
#define MAX 100
typedefstruct{ //节点
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码
void SelectMinNode(HuffmanTree HT, int m, int i1, int i2) //找出权值最小的两个节点对应的数组下标
{
HuffmanTree p = HT;
int s1, s2;
s1 = s2 = MAX;
i1 = i2 = 1;
for(int i=1; i=m; i++)
{
if(!(p+i)-parent)
{
if((p+i)-weight s1)
{
i2 = i;
s1 = (p+i)-weight ;
}
}
}
for(int i=1; i=m; i++)
{
if(!(p+i)-parent i!=i2)
{
if((p+i)-weight s2)
{
i1 = i;
s2 = (p+i)-weight ;
}
}
}
}
void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制
{
char *c1, *c2;
c1 = p;
while(q != '\0')
{
*c1 = q;
c1++;
start++;
}
*c1 = q;//别忘了将‘\n’复制过来
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n)
{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数
int i, i1, i2, m;
HuffmanTree p;
if(n=1) return;
m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间
p = HT + 1;
for(i=1;i=n;++i,++p,++w) //n个叶子节点初始化
{
p-weight = *w;
p-lchild = 0;
p-rchild = 0;
p-parent = 0;
}
for(;i=m;++i,++p) //非叶子节点初始化
{
p-weight = 0;
p-lchild = 0;
p-rchild = 0;
p-parent = 0;
}
for(i=n+1;i=m;++i) //对非叶子节点重新计算
{
SelectMinNode(HT, i-1, i1, i2);
HT[i1].parent = i;
HT[i2].parent = i;
HT[i].lchild = i1;
HT[i].rchild = i2;
HT[i].weight = HT[i1].weight + HT[i2].weight ;
}
///从叶子节点到根节点求赫夫曼编码
char* cd;
int start, c, f;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个
cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码
cd[n-1] = '\0';
for(int i=1; i=n; i++)
{
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));
StrCopy(HC[i], cd, start); //将存储的编码copy给HC的第i个数组
}
free(cd);
}
void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码
{
HuffmanCode p;
for(int i=1; i=n; i++)
{
p = HC;
printf("The weight %d HuffmanCode is: ", HT[i]);
while(*p[i]!='\0')
{
printf("%c",*p[i]);
p[i]++;
}
printf("\n");
}
}
void main()
{
int n = 8;
HuffmanTree HT;
HuffmanCode HC;
int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1}
HuffmanCoding(HT, HC, a, n);
PrintHuffmanCode(HT, HC, n);
system("pause");}