哈夫曼编译码器

  1 //eg:
  2 //    4        A B C D        9 5 2 4
  3 //    A: 0    B: 10    C: 110    D: 111
  4 //  ABCDCBA    010110111110100
  5 #include<stdio.h>
  6 #include<stdlib.h>
  7 #include<string.h>
  8 #include<conio.h>
  9 #define OK 1
 10 #define ERROR 0
 11 typedef struct HTNode{
 12     char ch;
 13     int weight;
 14     int parent, lchild, rchild;
 15 } HTNode;
 16 typedef struct HTNode* HuffmanTree;
 17 typedef char** HuffmanCode;
 18 //定义全局变量
 19 HuffmanTree HT;
 20 HuffmanCode HC;
 21 int n;
 22 //选择两个最小结点
 23 void select(int k, int *s1, int *s2){
 24     int i, ti, t=1000;
 25     for(i = 1; i <= k; i++){
 26         if(!HT[i].parent){ 
 27             if(t > HT[i].weight){
 28                 t = HT[i].weight;//t最后为最小的weight
 29                 ti = i;
 30             }
 31         }
 32     }
 33     *s1 = ti;
 34     t = 1000;
 35     ti = 0;
 36     for(i = 1; i <= k; i++){
 37         if((!HT[i].parent) && i!=*s1){ //parent为0
 38             if(t > HT[i].weight){
 39                 t = HT[i].weight;
 40                 ti = i;
 41             }
 42         }
 43     }
 44     *s2 = ti;
 45 }
 46 //打印哈夫曼树
 47 void printHT(int m){
 48     int i;
 49     printf("
");
 50     printf("char  weight  parent  lchild  rchild
");
 51     for(i = 1; i <= m; i++){
 52         printf("  %c  %5d  %5d  %5d  %5d
", HT[i].ch, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 53     }
 54     printf("
");
 55 }
 56 //初始化(建树和编码表)
 57 int Init(){
 58     int m = 2*n-1;
 59     int i, s1, s2;
 60     int w[n+1];//weight 0下标不使用
 61     char ch[n+1];//字符 
 62     char title;
 63     char* cd;
 64     int start, c, f;
 65     //建立哈夫曼树
 66     while(title = getchar() != '
');
 67     printf("■请输入各字符(用空格分开):");
 68     for(i=1; i<=n; i++){
 69         scanf("%c", &ch[i]);
 70         getchar();
 71     }
 72     printf("■请输入各权值(用空格分开):");
 73     for(i=1; i<=n; i++)
 74         scanf("%d", &w[i]);
 75     HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号节点不使用
 76     for(i=1; i<=n; i++){
 77         HT[i].ch = ch[i];
 78         HT[i].weight = w[i];
 79         HT[i].lchild = 0;
 80         HT[i].rchild = 0;
 81         HT[i].parent = 0;
 82     }
 83     for(; i<=m; i++){
 84         HT[i].ch='-';
 85         HT[i].weight=0;
 86         HT[i].lchild=0;
 87         HT[i].rchild=0;
 88         HT[i].parent=0;
 89     }
 90     for(i=n+1; i<=m; i++){
 91         select(i-1, &s1, &s2);
 92         HT[s1].parent=i;
 93         HT[s2].parent=i;
 94         HT[i].lchild=s1;
 95         HT[i].rchild=s2;
 96         HT[i].weight=HT[s1].weight+HT[s2].weight;
 97     }
 98     printf("
■生成的哈夫曼树为:");
 99     printHT(m);
100     //从叶子到根逆向求每个字符的哈夫曼编码 
101     HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量 
102     cd = (char*)malloc(n*sizeof(char));//分配求编码的工作空间 
103     cd[n-1]='';//编码结束符 
104     printf("■其编码表为:
");
105     for(i=1; i<=n; i++){//逐个字符求哈夫曼编码 
106         start = n-1;//编码结束符位置 
107         for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent){
108             if(HT[f].lchild==c)
109                 cd[--start]='0';
110             else
111                 cd[--start]='1';
112         }
113         HC[i] = (char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 
114         strcpy(HC[i], &cd[start]);//从cd复制编码到HC 
115         printf("%c: ", HT[i].ch);
116         puts(HC[i]);
117     }
118     free(cd);
119     return OK;
120 }
121 //编码
122 int Encoding(){
123     char s[20], title;
124     int i, j;
125     while(title = getchar() != '
');
126     printf("
■请输入字符串:
");
127     scanf("%s", s);
128     printf("■编码结果为:
");
129     for(i=0; s[i]!=''; i++){
130         for(j=1; j<=n; j++){
131             if(s[i]==HT[j].ch){
132                 printf("%s", HC[j]);
133                 continue;
134             }
135         }
136     }
137     printf("
");
138     return OK;
139 }
140 //译码
141 int Decoding(){
142     char s[20], title;
143     int i=0, p=2*n-1;//p在根节点位置;
144     while(title = getchar() != '
');
145     printf("
■请输入编码:
");
146     scanf("%s", s);
147     printf("■译码结果为:
");
148     for(i = 0; s[i] != ''; i++){
149         if(s[i]=='0')
150             p=HT[p].lchild;
151         if(s[i]=='1')
152             p=HT[p].rchild;
153         if(p<=n){
154             printf("%c", HT[p].ch);
155             p=2*n-1;
156         }
157     }
158     printf("
");
159     return OK;
160 }
161 //菜单
162 void menu(){
163         printf("■■■■■哈夫曼编译码器■■■■■
");
164         printf("■	 ★1-建立哈夫曼树	■
");
165         printf("■	 ★2-编码		■
");
166         printf("■	 ★3-译码		■
");
167         printf("■	 ★4-退出		■
");
168         printf("■■■■■■■■■■■■■■■■■
");
169         printf("■请选择:");
170 }
171 int main(){
172     char ch, title;
173     while(1){
174         menu();
175         scanf("%c", &ch);
176         switch(ch){
177         case '1':
178             printf("
■请输入字符数n(n>0):");
179             scanf("%d", &n);
180             Init();
181             break;
182         case '2':
183             Encoding();
184             break;
185         case '3':
186             Decoding();
187             break;
188         case '4':
189             printf("Finished, God bless you!"); 
190             exit(0);
191         }
192         printf("
");
193         while(title = getchar() != '
');
194     }
195     return 0;
196 }