#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#define N 100

typedef struct {

       double probobility;

       int lnode;

       int rnode;

} node;

node tree[N];

int p = 0, total = 0;

char stk[N], q = 0;

int used[N],node_len[N];

void print_code()

{

       int i = 0;

       for (i = 0; i < q; i++)

              printf("%c", stk[i]);

}

void print_avg_len()

{

       int i;

       double avg_len=0;

       for(i=0;i<total;i++)

              avg_len+=tree[i].probobility * (double)node_len[i];

       printf("The average length is %f\n",avg_len);

}

int find_min()

{

       int i_min = 0, i;

       while (used[i_min] && i_min < p)

              i_min++;

       for (i = 0; i < p; i++)

              if (!used[i]

                  && tree[i].probobility <= tree[i_min].probobility)

                     i_min = i;

       return i_min;

}

 void create_tree()

 void create_tree()

 void create_tree()

{

       int  n1, n2;

       node newnode;

       while (1) {

              if (tree[p - 1].probobility == 1)

                     break;

              n1 = find_min();

              used[n1] = 1;

              n2 = find_min();

              used[n2] = 1;

              newnode.probobility =

                  tree[n1].probobility + tree[n2].probobility;

              newnode.lnode = n1;

              newnode.rnode = n2;

              tree[p++] = newnode;

       }

}

 void traverse_tree(int i)

 void traverse_tree(int i)

 void traverse_tree(int i)

{

       if (tree[i].lnode == -1 && tree[i].rnode == -1) {

              printf("%-f\t\t|", tree[i].probobility);

              print_code();

              printf("\t\t|%-d\n",q);

              node_len[i]=q;

              return;

       }

       stk[q++] = '0';

       traverse_tree(tree[i].rnode);

       q--;

       stk[q++] = '1';

       traverse_tree(tree[i].lnode);

       q--;

}

int main()

int main()

int main()

{

       int i = 0,tmp_total=0;

       double check = 0;

       node x;

       memset(tree, 0, sizeof(tree));

       memset(used, 0, sizeof(used));

       memset(node_len,0,sizeof(node_len));

       printf("How many symbols?:\n");

       scanf("%d", &total);

       if (total <= 0 || total > N / 2) {

              printf("can't accept\n");

              return 1;

       }

       printf("enter ther posibilities\n");

       tmp_total=total;

       while (tmp_total--) {

              scanf("%lf", &x.probobility);

              if (x.probobility < 0 || x.probobility > 1) {

                     printf("illegle\n");

                     return 2;

              }

              check += x.probobility;

              x.lnode = -1;

              x.rnode = -1;

              tree[p++] = x;

       }

       if (fabs(check - 1) > 1e-15) {

              printf("error,the sum should be 1\n");

              return 2;

       }

       create_tree();

       printf("Proboblility\t\t|Code\t\t|Length\n");

       traverse_tree(p - 1);

       print_avg_len();

       return 0;

}

简单测试结果:
How many symbols?:
6
enter ther posibilities
0.25 0.05 0.15 0.05 0.05 0.45
Proboblility              |Code           |Length
0.050000                |00000          |5
0.050000                |00001          |5
0.050000                |0001            |4
0.150000                |001              |3
0.250000                |01                |2
0.450000                |1                  |1
The average length is 2.100000

简单测试结果:
How many symbols?:
6
enter ther posibilities
0.25 0.05 0.15 0.05 0.05 0.45
Proboblility              |Code           |Length
0.050000                |00000          |5
0.050000                |00001          |5
0.050000                |0001            |4
0.150000                |001              |3
0.250000                |01                |2
0.450000                |1                  |1
The average length is 2.100000