huffman/priority_queue.c at master · JohnOmena/huffman · GitHub

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdlib.h>
#include "huffman_tree.h"
#include "priority_queue.h"

// Estrutura de um nó
struct huffman_tree {
    h_tree *left;     // filho da esquerda
    h_tree *right;    // filho da direita
    h_tree *next;     // ponteiro para o próximo nó da lista (priority queue)
    u_int frequency;  // frequência do byte
    u_char byte;      // byte
};

// Implementação da função de criação de queue
Prio_queue* create_queue(){
    Prio_queue* p = (Prio_queue*) calloc(1, sizeof(Prio_queue)); // Alocando a Lista;

    p->quant_nodes = 0;
    p->head = NULL; // Setando sua cabeça para NULL (inicialmente)
    return p;

}

// Implementação da função de criar os nodes da lista
h_tree* create_node(u_char by, u_int freq){
    h_tree* nod = (h_tree*) calloc(1, sizeof(h_tree)); // Alocando o node

    // Setando os valores iniciais do node;
    nod->frequency = freq;
    nod->byte = by;
    nod->left = nod->right = nod->next = NULL;


    return nod;
}

// Implementação da função que verifica se a queue esta vazia
int que_empty(Prio_queue* p){
    return (p->head == NULL);
}

// Implementação da função que adiciona o node na lista de prioridade
void add_node_queue(Prio_queue* p, u_char by, u_int freq){

    // cria o node
    h_tree* nod = create_node(by, freq);

    // verfica se a queue esta vazia
    if(que_empty(p) || p->head->frequency >= freq){

        nod->next = p->head;
        p->head = nod;


    } else {

        h_tree* nod_temp = p->head;
        while(nod_temp->next != NULL && nod_temp->next->frequency < freq){
            nod_temp = nod_temp->next;
        }

        nod->next = nod_temp->next;
        nod_temp->next = nod;

    }

    p->quant_nodes ++;
}

void add_parent_node (Prio_queue *p_queue, h_tree *parent_node) {

    if(que_empty(p_queue) || p_queue->head->frequency >= parent_node->frequency){

        parent_node->next = p_queue->head;
        p_queue->head = parent_node;

    }
    else {

        h_tree* nod_temp = p_queue->head;
        while(nod_temp->next != NULL && nod_temp->next->frequency < parent_node->frequency){
            nod_temp = nod_temp->next;
        }

        parent_node->next = nod_temp->next;
        nod_temp->next = parent_node;

    }
    p_queue->quant_nodes ++;
}

h_tree* dequeue_node (Prio_queue *p_queue) {
    // Verifica se está tentando desenfileirar com a fila vazia

    if (!que_empty(p_queue)) {
        h_tree *node = p_queue->head;        // cria um nó que aponta para a cabeça da fila
        p_queue->head = p_queue->head->next; // a cabeça da fila aponta para o próximo nó
        node->next = NULL;                   // remove a ligação de node com a fila
        return node;                         // retorna node
    }
    return NULL;
}

// Implementação da função que adiciona os nodes a lista de prioridade de acordo com array de freq
void construct_queue(Prio_queue* p, u_int str[]){

    // Adionando os nodes
    int i;
    for(i = 0; i < 256; i++){
        if(str[i] != 0){
        add_node_queue(p, i, str[i]);
        }
    }

}