注册 登录
编程论坛 数据结构与算法

求解关于哈夫曼树的问题

dolly1822 发布于 2010-12-12 14:38, 478 次点击
#define MAXVALUE 32767
#define MAXLEAF 8
#define MAXNODE MAXLEAF*2-1
#include <stdio.h>
typedef struct hnode
{
  int weight;
  int lchild,rchild;
  int parent;
}HTNode;

typedef struct Code
{
  int bits[MAXLEAF];
  int start;
  char ch;
}HCodeType;

void Huffman_tree(HTNode Ht[MAXNODE])
{
  int i,j,m1,m2,p1,p2;
  for(i=0;i<MAXNODE;i++)
  {
    Ht[i].parent=-1;
    Ht[i].lchild=-1;
    Ht[i].rchild=-1;
  }
  for(i=MAXLEAF;i<MAXNODE;i++)
  {
    m1=m2= MAXVALUE;
    p1=p2=0;
    for(j=0;j<i-1;j++)
    {
      if(Ht[j].weight<m1&&Ht[j].weight==-1)
      {
        m2=m1;
        p2=p1;
        m1=Ht[j].weight;
        p2=j;
      }
      else if(Ht[j].weight<m2&&Ht[j].weight==-1)
      {
        m2=Ht[j].weight;
        p2=j;
      }
    }
    Ht[p1].parent=i;
    Ht[p2].parent=i;
    Ht[i].lchild=p1;
    Ht[i].rchild=p2;
    Ht[i].weight=Ht[p1].weight+Ht[p2].weight;
  }
}

void Huffman_code(HTNode Ht[MAXNODE],HCodeType HuffCode[MAXLEAF])
{
  HCodeType cd;
  int c,p,i,j;
  for(i=0;i<MAXLEAF;i++)
  {
    cd.start=MAXLEAF;
    c=i;
    p=Ht[i].parent;
    while(p!=-1)
    {
      cd.start--;
      if(Ht[p].lchild==c)
    cd.bits[cd.start]='0';
      else cd.bits[cd.start]='1';
      c=p;
      p=Ht[p].parent;
    }
    cd.start++;
    for(j=cd.start;j<=MAXLEAF;j++)
        HuffCode[i].bits[j]=cd.bits[j];
    HuffCode[i].start=cd.start;
  }
}

void display(HCodeType HuffCode[MAXLEAF])
{
    int i, k;
    for(i=0;i<MAXLEAF;i++)
    {
        printf("%c:\t",HuffCode[i].ch);
        for(k=HuffCode[i].start;k<=MAXLEAF;k++)
            printf("%c",HuffCode[i].bits[k]);
        printf("\n");
    }
}

void main()
{
  HTNode Ht[MAXNODE];
  HCodeType HuffCode[MAXLEAF];
  int i,j;
  printf("please input 8 leafs' weight:\n");
  for(i=0;i<MAXLEAF;i++)
    scanf("%d",&Ht[i].weight);
  printf("qing shu ru zi fu:\n");
  for(j=0;j<MAXLEAF;j++)
    scanf("%c",&HuffCode[j].ch);
  Huffman_tree(Ht);
  Huffman_code(Ht,HuffCode);
  printf("please output huffman bian ma:\n");
  display(HuffCode);
}



大家帮我看看呀,为什么没有没有输出啊。。。
1 回复
#2
寒风中的细雨2010-12-18 11:47
程序代码:
#define MAXVALUE 32767
#define MAXLEAF 8
#define MAXNODE MAXLEAF*2-1
#include <stdio.h>

typedef struct hnode
{
    int weight;
    int lchild,rchild;
    int parent;
}HTNode;

typedef struct Code
{
    int bits[MAXLEAF];
    int start;
    char ch;
}HCodeType;

void Huffman_tree(HTNode Ht[MAXNODE])
{
    int i,j,m1,m2,p1,p2;
    for(i=0;i<MAXNODE;i++)
    {
        Ht[i].parent=-1;
        Ht[i].lchild=-1;
        Ht[i].rchild=-1;
    }
    for(i=MAXLEAF; i<MAXNODE; i++)
    {
        m1 = m2 = MAXVALUE;
        p1 = p2 = 0;
        for(j=0;j<i;j++)
        {
            //if(Ht[j].weight<m1&&Ht[j].weight==-1)
            if( Ht[j].weight<m1 && Ht[j].parent==-1 )
            {
                m2 = m1;
                p2=p1;
                m1 = Ht[j].weight;
                p1=j;
            }
            //else if(Ht[j].weight<m2&&Ht[j].weight==-1)
            else if( Ht[j].weight<m2 && Ht[j].parent==-1 )
            {
                m2 = Ht[j].weight;
                p2 = j;
            }
        }
        Ht[p1].parent=i;
        Ht[p2].parent=i;
        Ht[i].lchild=p1;
        Ht[i].rchild=p2;
        Ht[i].weight = Ht[p1].weight + Ht[p2].weight;
    }
}

void Huffman_code(HTNode Ht[MAXNODE],HCodeType HuffCode[MAXLEAF])
{
    HCodeType cd;
    int c,p,i,j;
    for(i=0;i<MAXLEAF;i++)
    {
        cd.start=MAXLEAF;
        c=i;
        p=Ht[i].parent;
        while(p!=-1)
        {
            cd.start--;
            if(Ht[p].lchild==c)
                cd.bits[cd.start]=0;
            else
                cd.bits[cd.start]=1;
            c = p;
            p=Ht[p].parent;
        }
        //cd.start++;
        for(j=cd.start; j<MAXLEAF; j++)
            HuffCode[i].bits[j]=cd.bits[j];
        HuffCode[i].start=cd.start;
    }
}

void display(HCodeType HuffCode[MAXLEAF])
{
    int i, k;
    for(i=0;i<MAXLEAF;i++)
    {
        printf("%c:\t",HuffCode[i].ch);
        for(k=HuffCode[i].start;k<MAXLEAF;k++)
            printf("%d",HuffCode[i].bits[k]);
        printf("\n");
    }
}

void main()
{
    HTNode Ht[MAXNODE];
    HCodeType HuffCode[MAXLEAF];
    int i,j;
    printf("please input 8 leafs' weight:\n");
    for(i=0;i<MAXLEAF;i++)
        scanf("%d",&Ht[i].weight);
    getchar();
    printf("qing shu ru zi fu:\n");
    for(j=0;j<MAXLEAF;j++)
        scanf("%c ",&HuffCode[j].ch);
   
    Huffman_tree(Ht);
    Huffman_code(Ht,HuffCode);
    printf("please output huffman bian ma:\n");
    display(HuffCode);
}

/*

大家帮我看看呀,为什么没有没有输出啊。。。
*/
只有本站会员才能查看附件,请 登录
1