一个Huffman编码程序,大家可以参考一下

事先说明这个不是我写的 ,选择自 fxsjy 的 Blog 
 

#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 %fn",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()

{

       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)

{

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

              printf("%-ftt|", tree[i].probobility);

              print_code();

              printf("tt|%-dn",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 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 acceptn");

              return 1;

       }

       printf("enter ther posibilitiesn");

       tmp_total=total;

       while (tmp_total–) {

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

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

                     printf("illeglen");

                     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 1n");

              return 2;

       }

       create_tree();

       printf("Proboblilitytt|Codett|Lengthn");

       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

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: