This code is give in a data structures book I issued from my library.
I am not able to understand how the functions are working.
I am aware of the algorithms.
Can anyone please explain how qinsert(),qremove(),build(),encode()
are working.Please explain in detail

``````#include <stdio.h>
#include <string.h>

typedef struct node_t {
struct node_t *left, *right;
int freq;
char c;
} *node;

struct node_t pool[256] = {{0}};
node qqq[255], *q = qqq - 1;
int n_nodes = 0, qend = 1;
char *code[128] = {0}, buf[1024];

node new_node(int freq, char c, node a, node b)
{
node n = pool + n_nodes++;
if (freq) n->c = c, n->freq = freq;
else {
n->left = a, n->right = b;
n->freq = a->freq + b->freq;
}
return n;
}

/* priority queue */
void qinsert(node n)
{
int j, i = qend++;
while ((j = i / 2)) {
if (q[j]->freq <= n->freq) break;
q[i] = q[j], i = j;
}
q[i] = n;
}

node qremove()
{
int i, l;
node n = q[i = 1];

if (qend < 2) return 0;
qend--;
while ((l = i * 2) < qend) {
if (l + 1 < qend && q[l + 1]->freq < q[l]->freq) l++;
q[i] = q[l], i = l;
}
q[i] = q[qend];
return n;
}

/* walk the tree and put 0s and 1s */
void build_code(node n, char *s, int len)
{
static char *out = buf;
if (n->c) {
s[len] = 0;
strcpy(out, s);
code[n->c] = out;
out += len + 1;
return;
}

s[len] = '0'; build_code(n->left,  s, len + 1);
s[len] = '1'; build_code(n->right, s, len + 1);
}

void init(char *s)
{
int i, freq[128] = {0};
char c[16];

while (*s) freq[(int)*s++]++;

for (i = 0; i < 128; i++)
if (freq[i]) qinsert(new_node(freq[i], i, 0, 0));

while (qend > 2)
qinsert(new_node(0, 0, qremove(), qremove()));

build_code(q[1], c, 0);
}

void encode(char *s, char *out)
{
while (*s) {
strcpy(out, code[*s]);
out += strlen(code[*s++]);
}
}

void decode(char *s, node t)
{
node n = t;
while (*s) {
if (*s++ == '0') n = n->left;
else n = n->right;

if (n->c) putchar(n->c), n = t;
}

putchar('\n');
if (t != n) printf("garbage input\n");
}

int main(void)
{
int i;
char *str = "aaaaaaaaabbbbaaaaaaaaccccbbbbeeeeeee", buf[1024];

init(str);
for (i = 0; i < 128; i++)
if (code[i]) printf("'%c': %s\n", i, code[i]);

encode(str, buf);
printf("encoded: %s\n", buf);

printf("decoded: ");
decode(buf, q[1]);
getch();
return 0;
}``````

That is a lot of code to explain. Try understanding one section at a time, and ask specific questions about things you don't quite get.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.