Como criar a lista ordenada para o Código (Algoritmo) de Huffman?

Dando continuidade à elaboração do Algoritmo de Huffman, vamos desenvolver nesta aula o passo 2: elaborar uma lista encadeara ou uma fila de prioridade ordenadas com os elementos da tabela de frequência.

Como vamos criar uma lista / fila, precisamos pensar como implementar estas estruturas. Está lembrado das opções que apresentamos na segunda aula sobre o Algoritmo de Huffman?

possiveis nos — Possibilidades para o nó da estrutura de dados lista / fila.

Nesta abordagem irei utilizar a terceira opção, um único nó que pode ser utilizado para nossa lista / fila de prioridade (ordenada de forma crescente) e para a árvore binária.

O trecho de código a seguir implemente este nó. Ele possui um campo caracter, um campo inteiro para a frequência e três ponteiros, um que será usado na lista / fila para apontar o próximo nó, e outros dois que serão utilizados na construção da árvore binária, para os filhos à esquerda e direita.

/*
    Estrutura do nó utilizado na elaboração da fila e da árvore
*/
typedef struct no{
    unsigned char caracter;
    int frequencia;
    struct no *esq, *dir, *proximo;
}No;

A partir de agora irei adotar o uso de uma lista encadeada ordenada. Assim, sempre farei referência à estrutura lista e não mais lista / fila. Para definir esta estrutura vamos utilizar o trecho de código a seguir que possui um ponteiro para um nó, definido acima, e um inteiro para o tamanho da lista.

/*
    Nó para a estrutura lista encadeada
*/
typedef struct{
    No *inicio;
    int tam;
}Lista;

Nossa lista será criada na função main e no início ela deve estar vazia. Assim, o primeiro procedimento que faremos será para inicializar a lista, atribuindo null ao ponteiro e zero ao tamanho.

/*
     Procedimento para inicializar uma lista
*/
void criar_lista(Lista *lista){
    lista->inicio = NULL;
    lista->tam = 0;
}

A nossa lista não é simplesmente uma lista encadeada, é uma lista encadeada ordenada. Assim, precisamos criar um procedimento para fazer a inserção de forma ordenada. Este procedimento receberá o ponteiro para a lista e um ponteiro para o nó a ser inserido. Lembre-se que os nós serão formados a partir da tabela de frequência.

/*
    Procedimento para inserir ordenado na lista encadeada
*/
void inserir_ordenado(Lista *lista, No *no){
    No *aux;
    // a lista está vazia?
    if(lista->inicio == NULL){
        lista->inicio = no;
    }
    // tem frequência menor que o início da lista
    else if(no->frequencia < lista->inicio->frequencia){
        no->proximo = lista->inicio;
        lista->inicio = no;
    }
    else{ // insere no meio ou no fim da lista
        aux = lista->inicio;
        while(aux->proximo && aux->proximo->frequencia <= no->frequencia)
            aux = aux->proximo;
        no->proximo = aux->proximo;
        aux->proximo = no;
    }
    lista->tam++; // incrementa o tamanho da lista
}

Agora que já temos nossa estrutura lista, precisamos percorrer a tabela de frequência e, para toda posição cuja frequência seja maior que zero, precisamos criar um nó, preencher suas informações e inseri-lo na nossa lista ordenada, como feito a seguir.

/*
     Procedimento para preencher a lista a partir da tabela de frequência
*/
void preencher_lista(unsigned int tab[], Lista *lista){
    int i;
    No *novo;
    for(i = 0; i < TAM; i++){ // percorre toda a tabela
        if(tab[i] > 0){ // se quantidade for maior que zero
            novo = malloc(sizeof(No));
            if(novo){
                novo->caracter = i;
                novo->frequencia = tab[i];
                novo->dir = NULL;
                novo->esq = NULL;
                novo->proximo = NULL;

                inserir_ordenado(lista, novo);
            }
            else{
                printf("\tERRO ao alocar memoria em preencher_lista!\n");
                break;
            }
        }
    }
}

Também é interessante imprimir ao menos parte da lista na tela a fim de conferir se realmente está na ordem crescente. Assim, podemos criar o procedimento a seguir que irá imprimir o caracter e a frequência de cada nó da lista encadeada na tela.

/*
      Procedimento para imprimir uma lista encadeada na tela
*/
void imprimir_lista(Lista *lista){
    No *aux = lista->inicio;

    printf("\n\tLista ordenada: Tamanho: %d\n", lista->tam);
    while(aux){
        printf("\tCaracter: %c Frequência: %d\n", aux->caracter, aux->frequencia);
        aux = aux->proximo;
    }
}

Código parcial para o Algoritmo de Huffman – Parte II – Lista Ordenada

/*
         Código escrito por Wagner Gaspar
         Outubro de 2021
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>

#define TAM 256

typedef struct no{
    unsigned char caracter;
    int frequencia;
    struct no *esq, *dir, *proximo;
}No;

typedef struct{
    No *inicio;
    int tam;
}Lista;

//----------- parte 1: tabela de frequência ----------------------
void inicializa_tabela_com_zero(unsigned int tab[]){
    int i;
    for(i = 0; i < TAM; i++)
        tab[i] = 0;
}

void preenche_tab_frequencia(unsigned char texto[], unsigned int tab[]){
    int i = 0;

    while(texto[i] != '\0'){
        tab[texto[i]]++;
        i++;
    }
}

void imprime_tab_frequencia(unsigned int tab[]){
    int i;

    printf("\tTABELA DE FREQUENCIA\n");
    for(i = 0; i < TAM; i++){
        if(tab[i] > 0)
            printf("\t%d = %u = %c\n", i, tab[i], i);
    }
}

//----------- parte 2: Lista Encadeada Ordenada ----------------------

void criar_lista(Lista *lista){
    lista->inicio = NULL;
    lista->tam = 0;
}

void inserir_ordenado(Lista *lista, No *no){
    No *aux;
    // a lista está vazia?
    if(lista->inicio == NULL){
        lista->inicio = no;
    }
    // tem frequência menor que o início da lista
    else if(no->frequencia < lista->inicio->frequencia){
        no->proximo = lista->inicio;
        lista->inicio = no;
    }
    else{
        aux = lista->inicio;
        while(aux->proximo && aux->proximo->frequencia <= no->frequencia)
            aux = aux->proximo;
        no->proximo = aux->proximo;
        aux->proximo = no;
    }
    lista->tam++;
}

void preencher_lista(unsigned int tab[], Lista *lista){
    int i;
    No *novo;
    for(i = 0; i < TAM; i++){
        if(tab[i] > 0){
            novo = malloc(sizeof(No));
            if(novo){
                novo->caracter = i;
                novo->frequencia = tab[i];
                novo->dir = NULL;
                novo->esq = NULL;
                novo->proximo = NULL;

                inserir_ordenado(lista, novo);
            }
            else{
                printf("\tERRO ao alocar memoria em preencher_lista!\n");
                break;
            }
        }
    }
}

void imprimir_lista(Lista *lista){
    No *aux = lista->inicio;

    printf("\n\tLista ordenada: Tamanho: %d\n", lista->tam);
    while(aux){
        printf("\tCaracter: %c Frequência: %d\n", aux->caracter, aux->frequencia);
        aux = aux->proximo;
    }
}


int main() {

    unsigned char texto[] = "Vamos aprender programação";
    unsigned int tabela_frequencia[TAM];
    Lista lista;
    No *arvore;
    int colunas;
    char **dicionario;
    char *codificado, *decodificado;

    setlocale(LC_ALL, "Portuguese");

    //----------- parte 1: tabela de frequencia ---------------
    inicializa_tabela_com_zero(tabela_frequencia);
    preenche_tab_frequencia(texto, tabela_frequencia);
    imprime_tab_frequencia(tabela_frequencia);

    //----------- parte 2: Lista Encadeada Ordenada -----------
    criar_lista(&lista);
    preencher_lista(tabela_frequencia, &lista);
    imprimir_lista(&lista);

    return 0;
}

Início