sy6_4.c

数据结构实验与学习指导

/*  sy6_4.c  */
#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;/*定义编码结构*/
HTNode Ht[MAXNODE];
HCodeType HuffCode[MAXLEAF];
void Huffman_tree()/*建立哈夫曼树*/
{  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;
    }
  printf("输入8个叶子结点权值:\n");
   for(i=0;i<MAXLEAF;i++)
     scanf("%d",&Ht[i].weight);
   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].parent==-1)
      { m2=m1;p2=p1;
       m1=Ht[j].weight;
       p1=j;
      }
     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;
  }
}/*Huffman_tree*/
void Huffman_code()/*哈夫曼树编码*/
{ HCodeType cd;
   int c,p,i,j;
   for(i=0;i<MAXLEAF;i++)
    {cd.start=MAXLEAF;
     printf("请输入字符: \n");
     getchar();
     scanf("%c",&cd.ch);
     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;
        }
      HuffCode[i]=cd;
    }
  for(i=0;i<MAXLEAF;i++)/*输出字符、权值及编码*/
   { printf("字符 %c 权值 %d,编码是：",HuffCode[i].ch,Ht[i].weight);
     for(j=HuffCode[i].start;j<MAXLEAF;j++)
      printf("  %d ",HuffCode[i].bits[j]);
    printf("\n");
    }
}
void main()
{ Huffman_tree();/*建立哈夫曼树*/
  Huffman_code();/*哈夫曼树编码*/
}