Huffman encoding in basic C

[mystic07]

I have learned only basic programming up to now and i have to encode a sentence using huffman in my digital communication module. i have written this so far:

---

Code C - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/* To encode a sentence with special symbols except '|' using Huffman code*/
 
#include<conio.h>
#include<stdio.h>
 
int rearrange(int count1[]);
int z=0,m=0;
 
void main()
{
    char input[100];                 /* Up to 100 characters can be encoded*/
    int i, num,count,n=1, numchar,count1[100],a=0;
 
    printf("\n Enter the number of characters to be encoded: ");
    scanf("%d", &numchar);
 
    printf("\n The sentence to encode is: ");
 
    for(i=0; i<= numchar; ++i)
     {
        scanf("%c", &input[i]);      /* The sentence to be encoded is entered*/
      }                             /* using a for loop*/
 
    for(count=n; count<= numchar; ++count)
    {
        num=1;
        for(i=1; i<=numchar; ++i)
        {
            if(n!=i && input[n]==input[i])   /* the input[n] e.g input[0] is compared */
            {                                /* with all the other inputs i.e input[1], input[2],...*/
            ++num;                           /* if input[n]=input[i], the latter is replaced by '|'*/
            input[i]='|';
            }
 
        }
 
        if(input[n]==' ')
        {
        printf("\n' '=%d", num);
         count1[a]=num;
         ++a;
         ++z;
        }
 
 
        else if(input[n]!='|')           /* thus an output is obtained only if the latter is not*/
        {                                          /* '|' so that there is no repetition*/
          printf("\n %c =%d ", input[n],num);
         count1[a]=num;
         ++a;
         ++z;
        }
        ++n;
      }
 
     for(i=0;i<z;++i)                         /* count1[1]=frequency of input[o]*/
                                                             /* count1[2]=frequency of input[1] if input[0]!=input[1]...*/
     {
        printf("\n count[]=%d",count1[i]);
      }
 
        for(i=0;i<z;++i)
      {
        printf("\n rearrange %d", rearrange(count1));
        ++m;
     }
 }
 
int rearrange(int count1[])
{
        int minimum,p;
 
        minimum=count1[m];
 
 
        for(m; m<z; ++m)
        {
 
        if(minimum>count1[m])
        {
        p=minimum;
        minimum=count1[m];
        count1[m]=p;
 
        }
        }
        m=0;
    return(minimum);
}

---

i.e i am able to input a sentence, count the number of characters and arrange the frequency of occurence in ascending order. (As i told, it's reeeaaalllyy basic programming)

Can anyone please tell me how to proceed??? i've search a lot on the net, and i know there is a function to build a binary tree but eventhough i've tried a lot, i cannot understand how to use it.-----Any feedback may b of great help!

Thanks in advance

 

[omar_elruby]

Hi mystic07,
I have actually done this exact same project 2 months ago.
Since i had to do it in C, I faced this problem also.
What i have done is that I built the tree manually (i created a node, and each node is having right and left child nodes).
Here is an example how to create a node:

---

Code C - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct node_str
 { 
       node leftChild;
       node rightChild;
 }node_str;
 
node node_create(node leftChild, node rightChild)
{   
  node p = malloc(sizeof(struct node_str));
  if(p != NULL )
  {
      p->leftChild = leftChild;
      p->rightChild = rightChild;
  }
  return (p);
}

---

With a simple recursion or iteration you can construct your tree.
Good Luck ...

 

[mystic07]

hey thanks for replying...hope i manage to do it now.