赫夫曼树.txt

这是有关数据结构的例程序

definition.h
============================================
typedef struct{
unsigned weight;
unsigned parent, lchild, rchild;
}HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表

void Select(HuffmanTree, unsigned, unsigned *, unsigned *);//选择parent为0，且weight最小的两个结点
==================================================================

main.c
=====================================================
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "definition.h"

int main()
{ unsigned n, m, i, s1, s2, start, c, f;
char *cd;
HuffmanTree HT, p;
HuffmanCode HC;

printf("请问您要输入多少个字符？ ");
scanf("%d", &n);
if(n<2)
  return 1;
m = 2 * n - 1;
HT = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode) );//0号单元未用
if(!HT)
  return 1;
for(p=HT+1, i=1; i<=n; i++, p++){
  printf("请您输入权值：");
  scanf("%d", &p->weight);
  p->lchild = p->parent = p->rchild = 0;
}
for(; i<=m; i++, p++)
  p->lchild = p->parent = p->rchild = p->weight = 0;

//建赫夫曼树
for(i=n+1; i<=m; i++){
  s1 = s2 = 0;
  Select(HT, i, &s1, &s2);//选择parent为0，且weight最小的两个结点
  HT[s1].parent = 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 *) );//分配n个字符编码的头指针向量
if(!HC)
  return 1;
cd = (char *)malloc( n * sizeof(char) );//分配编码的工作空间
if(!cd)
  return 1;
cd[n-1] = '\0';//编码结束符
for(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) );//为第i个字符编码分配空间
  if(!HC[i])
   return 1;
  strcpy(HC[i], &cd[start]);
  printf("%s\n", HC[i]);
}
free(cd);//释放工作空间

return 0;
} //其它动态分配的空间还没释放
==============================================================================

function.c
=================================================================
#include "definition.h"

void Select(HuffmanTree p, unsigned i, unsigned *s1, unsigned *s2)
{//选择parent为0，且weight最小的两个结点
unsigned j;

for(j=1; j<i; j++){
  if( !p[j].parent ){
   if( !*s1 )
    *s1 = j;
   else{
    if(p[*s1].weight > p[j].weight){
     *s2 = *s1;
     *s1 = j;
    }
    else
     *s2 = j;
   }
  }
  if( *s1 && *s2 )
   break;
}
for(j++; j<i; j++){
  if( !p[j].parent ){
   if( p[*s1].weight > p[j].weight ){
    *s2 = *s1;
    *s1 = j;
   }
   else{
    if( p[*s2].weight > p[j].weight )
     *s2 = j;
   }
  }
}
}