haffmanTree

  1 /*请在此处编写代码，完成哈夫曼编码，并能输出每个叶子结点的编码*/
  2 /**********  Begin  *********/
  3 
  4 /*请在此处编写代码，完成哈夫曼编码，并能输出每个叶子结点的编码*/
  5 /**********  Begin  *********/
  6 #include 
  7 using namespace std;
  8 #include 
  9 #include 
 10 #define MAX  100000
 11 char a[10]= {'\0'};
 12 struct HtNode {
 13     int data;
 14     int parent,llink,rlink;
 15 };
 16 struct HtTree {
 17     int m;
 18     int root;
 19     struct HtNode *ht;
 20 };
 21 typedef struct HtTree *PHtTree;
 22 
 23 PHtTree fuffman(int m ,int *w)
 24 {
 25     PHtTree pht;
 26     int i,j,x1,x2,m1,m2;
 27     pht=(PHtTree)malloc(sizeof(struct HtNode));
 28     if(pht == NULL)
 29     {
 30         printf("out of space\n");
 31         return pht;
 32     }
 33     pht->ht=(struct HtNode* )malloc(sizeof(struct HtNode)*(2*m-1)) ;
 34     if(pht->ht==NULL)
 35     {
 36         printf("out of space\n");
 37         return pht;
 38     }
 39     for(i=0; i<2*m-1; i++)
 40     {
 41         pht->ht[i].llink=-1;
 42         pht->ht[i].rlink=-1;
 43         pht->ht[i].parent=-1;
 44         if(iht[i].data=w[i];
 45         else pht->ht[i].data=-1;
 46     }
 47     for(i=0; i1; i++)
 48     {
 49         m1=MAX;
 50         m2=MAX;
 51         x1=-1;
 52         x2=-1;
 53         for(j=0; j)
 54         {
 55             if(pht->ht[j].dataht[j].parent==-1)
 56             {
 57                 m2=m1;
 58                 x2=x1;
 59                 m1=pht->ht[j].data;
 60                 x1=j;
 61             }
 62             else if(pht->ht[j].dataht[j].parent==-1)
 63             {
 64                 m2=pht->ht[j].data;
 65                 x2=j;
 66             }
 67         }
 68         pht->ht[x1].parent=m+i;
 69         pht->ht[x2].parent=m+i;
 70         pht->ht[m+i].data=m1+m2;
 71         pht->ht[m+i].llink=x1;
 72         pht->ht[m+i].rlink=x2;
 73     }
 74     pht->root=2*m-2;
 75     return pht;
 76 }
 77 void  print(PHtTree T,int num,int i)
 78 {
 79     if(T->ht[num].rlink==-1&&T->ht[num].llink==-1)
 80     {
 81         printf("%d ",T->ht[num].data);
 82         for(int j=0; j)
 83             printf("%c",a[j]);
 84         printf("\n");
 85         return ;
 86     }
 87     a[i]='0';
 88     print(T,T->ht[num].llink,i+1);
 89     a[i]='1';
 90     print(T,T->ht[num].rlink,i+1);
 91 }
 92 int main()
 93 {
 94     int i,m,w[1000];
 95     cin>>m;
 96     for(i=0; i)
 97         cin>>w[i];
 98     PHtTree pht=fuffman(m,w);
 99     print(pht,pht->root,0);
100 }
101 
102 /**********  End  *********/
103 
104 
105 /**********  End  *********/