1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define max 100
  4 struct BTreeNode
  5 {
  6     char data;
  7     int weight;
  8     struct BTreeNode* left;
  9     struct BTreeNode* right;
 10 };
 11 struct Code
 12 {
 13     int len;
 14     char data;
 15     int *code;
 16     struct Code *next;
 17 };
 18 struct BTreeNode* CreateHuffman(int a[],char p[] ,int n)
 19 {
 20     int i, j;
 21     struct BTreeNode **b, *q;
 22     b = malloc(n*sizeof(struct BTreeNode));
 23     for (i = 0; i < n; i++)
 24     {
 25         b[i] = malloc(sizeof(struct BTreeNode));
 26         b[i]->weight=a[i];
 27         b[i]->data=http://www.mamicode.com/p[i];
 28         b[i]->left = b[i]->right = NULL;
 29     }
 30     for (i = 1; i < n; i++)
 31     {
 32         //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
 33         int k1 = -1, k2;
 34         for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵
 35         {
 36             if (b[j] != NULL && k1 == -1)
 37             {
 38                 k1 = j;
 39                 continue;
 40             }
 41             if (b[j] != NULL)
 42             {
 43                 k2 = j;
 44                 break;
 45             }
 46         }
 47         for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小
 48         {
 49             if (b[j] != NULL)
 50             {
 51                 if (b[j]->weight < b[k1]->weight)
 52                 {
 53                     k2 = k1;
 54                     k1 = j;
 55                 }
 56                 else if (b[j]->weight < b[k2]->weight)
 57                     k2 = j;
 58             }
 59         }
 60         //由最小权值树和次最小权值树建立一棵新树，q指向树根结点
 61         q = malloc(sizeof(struct BTreeNode));
 62         q->weight = b[k1]->weight + b[k2]->weight;
 63         q->data=http://www.mamicode.com/‘#‘;
 64         q->left = b[k1];
 65         q->right = b[k2];
 66         b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置
 67         b[k2] = NULL;//k2位置为空
 68     }
 69     free(b);
 70     return q;
 71 }
 72 struct Code* HuffManCoding(struct BTreeNode* FBT, int len)
 73 {
 74     static struct Code *head;
 75     static int a[10];
 76     if (FBT != NULL)
 77     {
 78         if (FBT->left == NULL && FBT->right == NULL)
 79         {
 80             int i;
 81             struct Code *p;
 82             int *code;
 83             p=(struct Code*)malloc(sizeof(struct Code));
 84             code=(int *)malloc(len*sizeof(int));
 85             p->data=http://www.mamicode.com/FBT->data;
 86             p->len=len;
 87             printf("字母:%c,权值:%d,编码:",FBT->data,FBT->weight);
 88             for (i = 0; i < len; i++)
 89             {
 90                 printf("%d",a[i]);
 91                 code[i]=a[i];
 92             }
 93             p->code=code;
 94             if (head==NULL)
 95             {
 96                 p->next=NULL;
 97                 head=p;
 98             }
 99             else
100             {
101                 p->next=head->next;
102                 head->next=p;
103             }
104             printf("\n");
105         }
106         else
107         {
108             a[len] = 0;
109             HuffManCoding(FBT->left, len + 1);
110             a[len] = 1;
111             HuffManCoding(FBT->right, len + 1);
112         }
113     }
114     return head;
115 }
116 void find(struct Code *head,char x)
117 {
118     int i;
119     while (head)
120     {
121         if (head->data=http://www.mamicode.com/=x)
122         {
123             for (i=0;i<head->len;i++)
124                 printf("%d",head->code[i]);
125             return ;
126         }
127         else
128             head=head->next;
129     }
130 }
131 int main()
132 {
133     struct Code *head;
134     int n=0,k=0,t=1,i,j,weight[max]={0},isread[max]={0};
135     struct BTreeNode* fbt;
136     char S[max],ch,data[max];
137     printf("请输入字符串:");
138     while ((ch=getchar())!=‘\n‘)
139         S[n++]=ch;
140     for (i=0;i<n;t=1,i++)
141     {
142         if (isread[i]==1)
143             continue;
144         ch=S[i];
145         isread[i]=1;
146         for (j=i+1;j<n;j++)
147         {
148             if (ch==S[j])
149             {
150                 isread[j]=1;
151                 t++;
152             }
153         }
154         weight[k]=t;
155         data[k++]=ch;
156     }
157     fbt = CreateHuffman(weight,data,k);
158     printf("树中每个叶子结点的哈夫曼编码：\n");
159     head=HuffManCoding(fbt,0);
160     printf("字符串编码为：");
161     for (i=0;i<n;i++)
162     {
163         find(head,S[i]);
164     }
165     return 0;
166 }