哈夫曼编码皇星客栈

View Code
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<iostream>
 4 #define MAXVALUE 100                //定义最大权值
 5 #define MAXLEAF 50                  //定义哈夫曼树中叶子节点个数
 6 #define MAXNODE MAXLEAF*2-1
 7 #define MAXBIT  100                 //定义哈夫曼编码的最大长度
 8 
 9 typedef struct{
10     int weight;
11     int parent;
12     int lchild;
13     int rchild;
14     }HNodeType;
15 
16 typedef struct{
17     int bit[MAXBIT];
18     int start;
19 }HCodeType;
20     
21 static int n; 
22 
23 HNodeType HuffNode[MAXNODE];
24 HNodeType *HaffmanTree( ){
25     int i,j,m1,m2,x1,x2;
26     scanf("%d",&n);                     //输入叶子节点个数
27     for(i=0;i<2*n-1;i++)          //数组HuffNode[ ]初始化
28     {
29         HuffNode[i].weight=0;
30         HuffNode[i].parent=-1;
31         HuffNode[i].lchild=-1;
32         HuffNode[i].rchild=-1;
33     }
34     for(i=0;i<n;i++)
35             scanf("%d", &( HuffNode[i].weight));
36     for(i = 0 ; i < n - 1 ; i++ ) {
37      m1=m2=MAXVALUE;
38      x1 = x2 = 0;
39      for( j=0 ; j < n + i ; j++ )  
40      {
41          if(HuffNode[j].parent == -1 && HuffNode[j].weight < m1)
42          {   
43              m2 = m1;
44              x2 = x1;
45              m1 = HuffNode[j].weight;
46              x1 = j;
47          }
48          else
49             if(HuffNode[j].parent == -1 && HuffNode[j].weight < m2 ){
50                m2 = HuffNode[j].weight;                                                                            
51                x2 = j;
52             }
53     }
54     HuffNode[x1].parent = n + i;
55     HuffNode[x2].parent = n + i;
56     HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
57     HuffNode[n+i].lchild = x1;
58     HuffNode[n+i].rchild = x2;
59   }
60   return HuffNode;
61 }
62 
63 void HaffmanCode( ){                  //建立哈夫曼编码
64     HCodeType HuffCode[MAXLEAF],cd;
65     int i,j,c,p;
66     HaffmanTree( );  //建立哈夫曼树
67     for( i = 0 ; i < n ; i++ )  //求每个叶子节点的哈夫曼编码
68     {
69         cd.start = n-1;
70         c = i;
71         p = HuffNode[c].parent;
72         while(p!=-1) {                                     //由叶子节点向上直到树根
73         if(HuffNode[p].lchild==c)
74          cd.bit[cd.start] = 0;
75         else
76          cd.bit[cd.start]=1;
77         cd.start--;
78         c=p;
79         p=HuffNode[c].parent;
80     }
81     for(j=cd.start+1;j<n;j++)
82         HuffCode[i].bit[j] = cd.bit[j];          //保存求出的每个叶节点的哈夫曼编码和编码的起始值
83     
84     HuffCode[i].start = cd.start;
85    }
86    for( i = 0 ; i < n ; i++ ){                  //输出每个叶子的哈夫曼编码
87        for(j = HuffCode[i].start+1 ; j < n ; j++ ) 
88              printf("%d",HuffCode[i].bit[j]);
89    printf("\n");
90   }
91 }
92   
93   
94   int main( )
95   {
96       HaffmanCode( );
97     return 0;
98  }
哈夫曼编码 皇星客栈

哈夫曼编码皇星客栈
