#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
