Fila Dinâmica 13:07

Completando a lista dinâmica e a pilha dinâmica, vejamos esta estrutura dinâmica, a fila, explorando o potencial de alocação sob demana da memória de um computador.

Lembrando: A fila é uma lista com restrição de entrada e saída, assim, só podemos retirar elementos de quem chegou primeiro (início), e os novos elementos devem ser inseridos no final.

Para isso, ao codificarmos um exemplo, precisaremos de dois ponteiros: um que aponta para o início da fila e outro para o final. Podemos criar uma estrutura (struct) para controlar estes ponteiros.

Ainda assim será necessário ter uma estrutura com o elemento e o ponteiro para o próximo elemento.

Vejamos através de imagens e vídeos a representação gráfica desta estrutura de dados:

Exemplos by: http://mda.codeplex.com/

Agora que já esta dominado este conceito, segue um breve exemplo de codificação de uma fila em C:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct Item
{
    int numero;
    struct Item *proximo;
};

struct Fila
{
    Item *inicio;
    Item *fim;
};

void Inicializar(Fila **fila)
{
    // -> Recebe a fila por referencia
    //    para inicializá-la
    *fila = (Fila *) malloc(sizeof(Fila));
    (*fila)->inicio = NULL;
    (*fila)->fim = NULL;
}

int EstaVazia(Fila *fila)
{
    return fila->inicio == NULL;
}

void Inserir(Fila *fila, int elemento)
{
    Item *novo;
    novo = (Item *)malloc(sizeof(Item));  

    // -> Verifica se a memória foi alocada com sucesso
    if (novo != NULL)
    {
        novo->numero = elemento;
        novo->proximo = NULL;

        if(EstaVazia(fila))
        {
            // -> Primeiro Item da Fila.
            fila->inicio = novo;
            fila->fim = novo;
        }
        else
        {
            // -> Ultimo item da Fila
            fila->fim->proximo = novo;
            fila->fim=novo;
        }
    }
}

void Retirar(Fila *fila)
{
    Item *item;

    if(!EstaVazia(fila))
    {
        item = fila->inicio;
        fila->inicio = item->proximo;
        free(item);

        // -> Se a fila acabou devemos atualizar o final
        if (fila->inicio == NULL)
            fila->fim = NULL;
    }
}

void MostrarFila(Fila *fila)
{
    int i = 0;
    Item *item;
    printf("\n\n Listando...\n\n");
    printf("---------------------------------\n");

    if (EstaVazia(fila))
    {
        printf ("A Fila esta vazia!\n");
    }
    else
    {      
        item = fila->inicio;

        while(item != NULL)
        {
            i++;
            printf("[%i] -> %i\n", i, item->numero);
            item = item->proximo;
        }
    }

    printf("---------------------------------\n");
}

void Menu()
{
    printf( "Digite a sua escolha: \n"
        "    1 enfileirar elemento \n"
        "    2 retirar da fila \n"
        "    3 para finalizar \n"
        "? ");
}

void main()
{   
    Fila *fila = NULL;
    int opcao;
    int numero;

    Inicializar(&fila);
    Menu();
    scanf("%i", &opcao);

    while (opcao != 3)
    {

        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);

                Inserir(fila, numero);
                MostrarFila(fila);

                break;
            case 2:
                Retirar(fila);
                MostrarFila(fila);

                break;

            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }

        scanf("%i", &opcao);   
    }

    system("pause");
}

Também é uma estrutura simples, alguns acham ela mais complexa que a pilha, por conta de lidar com dois ponteiros: o inicio e o fim. - Mas como encapsulamos estes ponteiros em uma estrutura, fica fácil manter e compreender o código.

Devemos ficar atento:

• Devemos inserir os elementos no final da fila. Se for o primeiro elemento os dois ponteiros devem apontar para ele, caso contrário, o ponteiro “próximo” do ultimo elemento deve apontar para este novo elemento.
• Removemos elemento sempre do início da fila, se removermos todos, o ponteiro do último também deve ser “zerado”, se não, o ponteiro do inicio deve ser o “proximo” do item inicial atual.

Um pouco confuso, por isso testem.

E para diversão fica:

• Implemente a fila com uma estrutura de aluno, que tenha RA (inteiro), Nome (char de 50).

Obrigado e bons estudos :D

Pilha Dinâmica 22:40

Como já demonstrado antes aqui, a linguagem C/C++ tem o potencial de alocar a memória do computador sobre demanda.

Que tal aproveitarmos este potencial para criar uma pilha dinâmica?

Para resolver isto vamos focar em alguns detalhes:

• A pilha é uma lista com restrição de entrada e saída, ou seja, é acessada pelo topo.
• Para inserir um elemento é necessário empilhar este elemento no topo da pilha.
• Para retirar um elemento, nos desempilhamos do topo da pilha.
• (… nem venham me falar que isto é redundante…)
• Então precisamos de manter um ponteiro para o topo da lista.
• Devemos criar uma estrutura (struct) que contenha o elemento, e um ponteiro para o próximo elemento (o que esta abaixo).

Vejamos graficamente como funciona este conceito, acompanhe a imagem e o vídeo abaixo:

Exemplos by: http://mda.codeplex.com/

Agora, com esta parte funcional esclarecida, vejamos um breve exemplo de código de uma pilha dinâmica em C, construída em cima da lista dinâmica:

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

struct Item
{
    int numero;
    struct Item *proximo;
};

void Inicializar(Item **topo)
{
   *topo = NULL;
}

bool EstaVazia(Item **topo)
{
   if(*topo == NULL)  
      return true;  
   else  
      return false;  
}

void Empilhar(Item **topo, int elemento)
{
    Item *novo;
    novo = (Item *)malloc(sizeof(Item));  
    novo->numero = elemento;
    novo->proximo = *topo; // -> próximo recebe o elemento que estava no topo.
    *topo = novo;
}

int Desempilhar(Item **topo)
{
   int result;
   Item *auxiliar;
   if(EstaVazia(topo))
   {
        printf("\n stack underflow! \n");
        exit(1);
   }
   else // -> Elemento retirado do topo
   {
        result = (*topo)->numero;
        auxiliar = *topo;
        *topo = (*topo)->proximo;
        free(auxiliar);
        return result;
   }  
}

void MostrarPilha(Item *topo)
{
    int i = 0;
    Item *item;
    printf("\n\n Listando...\n\n");
    printf("---------------------------------\n");

    if (EstaVazia(&topo))
    {
        printf ("A Pilha esta vazia!\n");
    }
    else
    {      
        item = topo;

        while(item != NULL)
        {
            i++;
            printf("[%i] -> %i\n", i, item->numero);
            item = item->proximo;
        }
    }

    printf("---------------------------------\n");
}

void Menu()
{
    printf( "Digite a sua escolha: \n"
        "    1 empilhar elemento \n"
        "    2 desempilhar \n"
        "    3 para finalizar \n"
        "? ");
}

void main()
{   
    Item *topo = NULL;
    int opcao;
    int numero;

    Menu();
    scanf("%i", &opcao);

    while (opcao != 3)
    {

        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);

                Empilhar(&topo, numero);
                MostrarPilha(topo);

                break;
            case 2:
                Desempilhar(&topo);
                MostrarPilha(topo);

                break;

            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }

        scanf("%i", &opcao);   
    }

    system("pause");
}

Por ser uma lista com restrição, este exemplo chega a ser bem simples perto da lista dinâmica.

Só vale ressaltar:

• Para inserir, é necessário empilhar, ou seja: Alocar um novo item na memória, fazer com que o item do topo se torne o próximo do novo item, finalmente, o ponteiro do topo deve apontar para o novo elemento.
• Para remover, énecessário retirar o item do topo, assim: Criamos um ponteiro auxiliar que recebe o endereço de memória do conteúdo do topo, o topo deverá receber o próximo (dele mesmo), finalmente, liberamos a memória do conteúdo da variável auxiliar.

Hora da diversão:

• Implemente a pilha com uma estrutura de aluno, que tenha RA (inteiro), Nome (char de 50).

Obrigado, espero que tenha sido esclarecedor. :)

Material Didático de Apoio para Aulas de Computação em C# e C++ 08:54

Pesquisando um pouco para encontrar um material mais dinamico para minhas aulas, encontrei no codeplex este excelente material para aulas de algoritmos, principalmente de estrutura, pesquisa e ordenação de dados.

Foi lembrado aos professores que a sala de aula hoje está munida de projetor e computador, e que o uso desse recurso traz uma dinamica melhor nas aulas.

Tentando deixar um pouco de lado o giz, códigos, textos e desenhos maravilhosos de minha parte sobre pilhas, filhas, listas etc, tentei encontrar animações que mostrassem a dinamica destes algoritmos em seu funcionamento, trazendo uma compreensao mais visual e menos abstrata ao aluno.

Procurando esse tipo de material eu encontrei isso:

Como vocês podem ver, é uma ferramenta que demonstra graficamente, juntamente com uma depuração de código do(C# e C++), o funcionamento de algoritmos de ordenação.

Então, o MDA é um conjunto de ferramentas cujo objetivo é fornecer suporte ao ensino de alguns tópicos abordados em disciplinas de computação.
Tópicos Abrangidos

• Estruturas de Dados
  • Árvores Binárias de Pesquisa
  • Filas
  • Listas Simplesmente Encadeadas
  • Pilhas

• Algorítmos de Ordenação
  • Bubble Sort
  • Heap Sort
  • Insertion Sort
  • Quick Sort
  • Quick Sort Randômico
  • Selection Sort
  • Shell Sort

Desenvolvido por Bárbara Bellaver, sob a orientação do Prof. Manuel M. Oliveira, este projeto procura fornecer ferramentas que sejam de fácil utilização e que apresentem os tópicos acima de forma didática e clara.A linguagem utilizada para o desenvolvimento é a C#.

Logo, para consegui-la, tive que entrar em contato com a Bárbara no Rio Grande do Sul, a qual me passou as informações da ferramenta e seu endereço no Codeplex: http://mda.codeplex.com/

Lá é possível, baixar a ferramenta, testá-la e acompanhar a breve implementação dos códigos e seu funcionamento, além de um comparativo de vários algoritmos rodando ao mesmo tempo :)

Parabéns pela iniciativa, estudem e divirtam-se!

Monografia – WebCrawlers: Ferramentas de Pesquisa, Catalogação e Indexação de Site 22:12

Pessoal, como o prometido a muito tempo, estou abrindo minha monografia para pesquisa.

Agora no mestrado pretendo aprimorá-la como nunca. Tenho grandes ideias e projetos… Basta eu concretizá-los.

Em breve também abrirei o projeto com o código (que já está no apêndice).

Espero que seja útil, e os animem com seus TCCs, Monografias e objetos de pesquisa. Espero o feedback também, para que eu possa sempre aprimorar meu trabalho.

A monografia fala por si mesma, mas para os curiosos e ansiosos, ela explica o funcionamento do google, bing etc. Basicamente eu implementei e expliquei os crawlers, ou webcrawlers: que são programas que funcionam como um robozinho que fica visitando as páginas, colhendo seu conteúdo, e navegando pelos links da mesma.

Um fato curioso e engraçado é que, quando eu rodava uma média de 100 crawlers, eu acabava derrubando a internet do lugar, seja laboratório de informática da faculdade, ou escritório de trabalho. :D Outra curiosidade é que, na época, quando eu rodava a aplicação em casa, demorava 1h para eu colher 40000 sites. Na faculdade foram poucos minutos, o que me deixou extasiado na apresentação… Foi bem hilário também :)

Bem, agora me resta aprimorar, fazendo a catalogação do conteúdo, busca fonética e baseada na posição geográfica.

Desejem-me sorte!

Monografia - Eduardo Spaki - Final

Monografia - Eduardo Spaki - Final

;D

Listas Dinâmicas em C 23:33

Tendo em vista que a Linguagem C proporciona mecanismos de alocação dinâmica de memória, porque limitar a lista a um vetor de tamanho definido?

Tornasse interessante o fato de utilizar a memória disponível do computador para montarmos uma lista.

Para que isto seja possível temos que ter em mente algumas coisinhas:

1. Não vamos precisar de um vetor para a estrutura de dados da lista.
2. Cada item da lista terá um ponteiro para o próximo item.
3. Acessaremos a lista a partir do início dela (cabeça). Este item estará em um ponteiro.
4. Para modificarmos a lista, devemos passar o primeiro item por referência, para que toda alteração nele reflita no contexto geral. Logo teremos um ponteiro de ponteiro.
5. Se a lista esta vazia o ponteiro da cabeça será nulo.
6. O último elemento terá o ponteiro nulo, pois não há próximo item. Para isso damos o nome de Terra.

Graficamente, podemos representar uma lista assim:

Como havia dito, teremos apenas um ponteiro para a cabeça, sendo assim, observe a figura a seguir e acompanhe o raciocínio já proposto:

Então é fundamental estar bem afiado em ponteiros para implementar uma estrutura de dados desta. Vamos à uma breve implementação de uma lista dinâmica:

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

struct Item
{
    int numero;
    struct Item *proximo;
};

bool Inserir(Item **cabeca, int valor)
{
    Item *novo, *anterior, *atual;

    // -> Aloca memória para o novo item
    novo = (Item *)malloc(sizeof(Item));

    // -> Checa se foi alocado memória corretamente.
    if (novo != NULL)
    {    
        // -> Define e inicializa os valores.
        novo->numero = valor;
        novo->proximo = NULL;
        anterior = NULL;
        atual = *cabeca; // -> Atual é o ponteiro para o item da cabeça

        // -> Ordenação
        //    Verifica se a posição atual não é nula (início ou fim)
        //    Verifica se o valor é maior do que o número do item.
        while (atual != NULL && valor > atual->numero)
        {
            anterior = atual;           
            atual = atual->proximo;       
        }
        // -> Se não há posição anterior, então o novo item será a cabeça.
        if (anterior == NULL)
        {
            novo->proximo = *cabeca; // -> recebe o que já tem na cabeça.
            *cabeca = novo; // ->  cabeça nova.
        }
        else // -> Arranjando posição no meio da lista... Remanejando.
        {
            // -> Elemento anterior aponta para o novo.
            anterior->proximo = novo;
            // -> Novo elemento aponta para o resto da lista.
            novo->proximo = atual;
        }

        return true;
    }
    else   
    {
        return false;
    }
}   

bool Remover(Item **cabeca, int valor)
{
    Item *anterior, *atual, *itemRemover;

    anterior = NULL;
    atual = *cabeca;

    // -> Procura o valor.
    while(atual != NULL && atual->numero != valor)
    {
        anterior = atual;
        atual = atual->proximo;
    }
    // -> Quando encontra o valor.
    if(atual != NULL)
    {
        itemRemover = atual;

        if(anterior != NULL)
        {
            // -> Encurta o caminho.
            anterior->proximo = atual->proximo;
        }
        else // -> Quando o item é a cabeça.
        {
            // -> Ela recebe o próximo do primeiro item.
            *cabeca = (*cabeca)->proximo;
        }

        // -> Libera da memória o item excluído.
        free(itemRemover);

        return true;
    }

    return false;
}

bool EstaVazia(Item *cabeca)
{
    return cabeca == NULL;
}

void Listar(Item *cabeca)
{
    if (EstaVazia(cabeca))
    {
        printf( " A lista esta vazia.\n\n" );
    }
    else
    {
        printf( "Listando... \n");

        while(cabeca != NULL)
        {
            printf("%i --> ", cabeca->numero);
            cabeca = cabeca->proximo;
        }

        printf("NULL\n\n");
    }
}

void Menu()
{
    printf( "Digite a sua escolha: \n"
        "    1 para inserir um elemento na lista \n"
        "    2 para remover um elemento da lista \n"
        "    3 para finalizar \n"
        "? ");
}

void main()
{   
    Item *cabeca = NULL;
    int opcao;
    int numero;

    Menu();
    scanf("%i", &opcao);

    while (opcao != 3)
    {

        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);

                Inserir(&cabeca, numero);

                Listar(cabeca);

                break;
            case 2:
                if (!EstaVazia(cabeca))
                {
                    printf( " Digite o numero a ser removido: ");
                    scanf( "\n%i", &numero);

                    if (Remover(&cabeca, numero))
                    {
                        printf("%i removido. \n", numero);

                        Listar(cabeca);
                    }
                    else
                    {
                        printf(" %c não encontrado. \n\n", numero);
                    }
                }
                else
                {
                    printf("A Lista está vazia. \n\n");
                }

                break;

            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }

        scanf("%i", &opcao);   
    }
    printf("Fim do programa.\n");
}

OK, concordo que não foi tão breve assim…

Mas, este é o exemplo de uma lista de inteiros ordenada!

Antes de tudo temos um novo operador, o: –>

Este operador é um indicador, ou seja, indica direto para o dado dentro do ponteiro, sem o uso do “*”. Ele é o equivalente a fazermos: (*novo).numero = valor;

Explicando então este código:

• Como precisamos de uma estrutura que contenha o dado e um ponteiro para o próximo dado, criei então uma struct Item.
• O booleano Inserir() retorna o sucesso da inserção do elemento na lista.
• Ele também insere de forma a deixar a lista sempre ordenada.
• O booleano Remover() também retorna o sucesso da operação.
• Ambos recebem o primeiro item (cabeça) por referência, por isto temos um ponteiro de ponteiro (já que o primeiro item já é um ponteiro).
• Para saber se a lista está vazia, basta chegar se a cabeça é nula.
• Para listar, basta ir de próximo em próximo item, até encontrar o terra (nulo).

Qualquer dúvida, entrem em contato. Divirtam-se:

1. Retorne o número de elementos da lista;
2. Verifique se um nome está ou não na lista;
3. Retorne a média de números da lista;

:)

Alocação de Dinâmica de Memória em C 21:59

Quando falamos em listas, uma das soluções plausíveis para implementar esta estrutura de dados é dada usando vetores. Porém temos que alocar uma capacidade máxima para este vetor, o que, de certa forma, torna a aplicação limitada.

A linguagem C permite a alocação dinâmica de memória. Um dos responsáveis por isso é a função malloc(). Essa função permite alocar uma determinada quantidade de bytes e retorna o ponteiro para esta região alocada na memória. É interessante trabalhar a alocação dinâmica de memória usando os três conceitos a seguir:

• malloc(): Função que aloca memória de um determinado tamanho e retorna o ponteiro para ela.
• free(): Libera a memória alocada dinamicamente, bastando informar o ponteiro dela.
• sizeof(): Mede o tamanho de um determinado tipo, inclusive de uma struct.

A memória que o malloc() aloca é da Heap. A Heap é uma porção e memória que o SO dedica ao aplicativo para esta natureza de alocação.

Uma consideração importante sobre o malloc() está no quesito de conversão explicita (cast), pois quando alocamos memória, o malloc() retorna um ponteiro, mas não se sabe do que é este ponteiro. Então podemos explicitar de que tipo de trata o ponteiro.

Para compreender melhor, acompanhe os exemplos a seguir:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

void main()
{
    int *inteiro = (int *)malloc(sizeof(int)); 

    *inteiro = 10;

    printf("\n tamanho de mem0ria alocado %i", sizeof(int));
    printf("\n endereco de memoria %x", inteiro);
    printf("\n valor dentro do endereco de memoria %i", *inteiro);

    free(inteiro);

    getch();
}

Primeiramente, notamos que obrigatoriamente temos usar um ponteiro, pois é isso que o malloc() retorna.

O cast (conversão explicita) fica por conta do: (int *) – onde indicamos que o ponteiro na verdade é um ponteiro para um inteiro.

Utilizamos também o sizeof() para medir o tamanho, em bytes, que um inteiro ocupa na memória. Podemos definir este valor “na unha”, caso necessário. Podemos inclusive montar um array dinâmico, multiplicando o sizeof() pelo tamanho desejado.

Antes de testarmos mais a alocação de memória temos de dar extrema importância ao free(). Esta função que é responsável por liberar memória. Portanto: lembre-se de usá-la. É importante para um uso otimizado de memória.

Bastante deve ser o cuidado ao liberar a memória, pois devemos ter certeza de liberar o conteúdo do ponteiro sem mais utilizá-lo.

Lembrando que se você acha ruim que seu browser/navegador, ou algum outro programa, consuma muita memória, aqui está o culpado… avise os programadores deste produto para lembrarem do free().

Mais um cuidado na alocação de memória: verificar se a mesma foi alocada corretamente! Como? verificando se o ponteiro não é nulo.

Vejamos mais um exemplo que explora os conceitos já citado:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

void main()
{
    int *numero = (int *)malloc(2 + 2); 

    if(numero != NULL)
        *numero = 10;
    else
        printf("\n erro ao alocar memoria");

    printf("\n endereco de memoria %x", numero);
    printf("\n valor dentro do endereco de memoria %i", *numero);

    free(numero);

    getch();
}

Reparem que eu aloquei 4 bytes de memória (somando 2 mais 2), sem usar o sizeof(). Além disso verifiquei se o ponteiro não é nulo, para garantir que a memória foi alocada.

E no final liberei a memória utilizada… Logicamente.

Espero que tenham gostado. Até mais… E aloquem isso em suas memórias :)

Parâmetros, Argumentos e Referência 15:56

Você sabe qual a diferença de argumentos e parâmetros?

Em subprogramação, ou seja, quando criamos funções ou métodos, podemos passar valores para a função/método.

Com isso em mente, podemos explorar as definições:

• Parâmetros: são as variáveis que estão na assinatura da função/método.
• Argumentos: são os valores que são passados para as funções/métodos.

Acompanhe o esquema da figura abaixo:

Lembre-se que em C toda chamada de uma função deve preencher completamente a assinatura dela, ou seja, se ela pede dois parâmetros, devem ser passados dois argumentos.

É possível também que se passe variáveis como argumentos:

Veja que agora passamos variáveis, ao invés de constantes, como argumentos. Sendo assim, podemos passar de duas maneiras as variáveis:

• Por Valor: É copiado o valor do argumento para o parâmetro.
• Por Referência: É feita a referência para onde a variável esta armazenada.

Na figura anterior, a passagem foi Por Valor, ou seja, os valores foram copiados para a função e as variáveis que estão dentro do main() não irão ter qualquer interferência da manipulação da função.

Se anotarmos o parâmetro com um &, daí dizemos que estamos passando a referência desta variável, veja o exemplo:

void Incrementar(int &i)
{
    i++;
}

void main()
{
    int i = 1;
    Incrementar(i);
    printf("%i", i);
    getch();
}

A saída deste algoritmo é:

Percebemos então que, quando passamos uma variável para uma função por referência (usando o & na definição do parâmetro), as ações que, neste caso, a função Incrementar() realizou no parâmetro, refletiram na variável da função main().

Então a passagem de parâmetros para uma função por referência ocorre quando alterações nos parâmetros formais, dentro da função, alteram os valores dos parâmetros que foram passados para a função.

O C, por padrão, faz chamadas por valor. Isto é bom quando queremos usar os parâmetros formais à vontade dentro da função, sem termos que nos preocupar em estar alterando os valores dos parâmetros que foram passados para a função.

Mas isto também pode ser ruim às vezes, porque podemos querer mudar os valores dos parâmetros fora da função também. Então podemos usar o &, um recurso de programação, para podemos usar uma chamada por referência.

Ficam alguns exercícios de fixação:

1. Faça uma calculadora em C (Somar, Dividir, Subtrair e Multiplica) que retorne o resultado por referência.
2. Inclua na calculadora, mais uma função para calcular o quadrado de um número, retornando o valor por referencia e tendo apenas um parâmetro em sua assinatura.

Obrigado e até + :)

Listas Especializadas: Fila 13:41

Quando você vai em um Cinema, pode ser que você enfrente uma fila, não é verdade? Nas filas, o última que entrar na fila, será o último a comprar o ingresso e/ou entrar no cinema.

E é exatamente assim que a estrutura de Fila funciona em um programa. Trata-se de uma lista onde é imposta uma política de acesso:

• Todo elemento tem que ser inserido no final da lista.
• Todo elemento que for excluído, deve ser excluído do início da lista.

As pilhas são definidas em Inglês como Queue, ou FIFO (First In First Out =  Primeiro que Entra é o Primeiro que Sai).

Para compreender sua aplicação na informática imagine a seguinte situação: Seu computador executa várias tarefas “ao mesmo tempo” (escutar música, navegar na Internet etc.) com um único processador. Para dar conta de tudo isso o processador escalona as tarefas, ou seja, processa um pouco uma tarefa, depois um pouco uma outra tarefa e assim por diante. Para decidir a ordem da tarefa que será processada, o processador organiza as tarefas em filas, por “ordem de chegada”.

O esquema de imagens abaixo, representa o funcionamento de uma fila:

Estruturalmente os dados se comportam assim:

Já deu para perceber que temos que criar uma estrutura que controle o início e final da fila, além de ter uma inserção e exclusão de elementos diferenciada. Acompanhe uma implementação básica em C:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

const int MAX = 100;

struct Aluno
{
    int ra;
    char nome[50];
};

struct Fila{
    Aluno dados[MAX];
    int inicio;
    int fim;
};

void IniciarFila(Fila &fila)
{
    fila.inicio = 0;
    fila.fim = 0;
}

bool FilaEstaVazia(Fila &fila)
{
    int resultado = fila.fim - fila.inicio;
    return resultado == 0;
}

bool FilaEstaCheia (Fila &fila)
{
    return fila.fim == MAX;
}

bool Enfileirar(Fila &fila, Aluno &aluno)
{
    if (!FilaEstaCheia(fila))   
    {
        fila.dados[fila.fim] = aluno;
        fila.fim++;
        return true;
    }
    else
    {
        return false;
    }
}

void Retirar(Fila &fila, Aluno &alunoRetirado)
{
    alunoRetirado = fila.dados[fila.inicio];
    fila.inicio++;
}    

void Listar(Fila fila)
{
    printf("\nListando...\n");

    while (!FilaEstaVazia(fila))
    {
        Aluno alunoRetirado;
        Retirar(fila, alunoRetirado);
        printf("\n%i - %s", alunoRetirado.ra, alunoRetirado.nome);
    }

    getch();
}

void main()
{
    char opcao;
    Fila fila;

    // -> Inicializando a Fila.
    IniciarFila(fila);

    do
    {
        system("cls");
        printf("Escolha a opcao desejada:");
        printf("\n 1- Enfileirar um Aluno");
        printf("\n 2- Retirar um Aluno da Fila");
        printf("\n 3- Listar todos os elementos da Fila");
        printf("\n 0- Sair do programa\n");
        printf("\n Opcao: ");

        opcao = getchar();

        switch(opcao)
        {
            case '1':
                Aluno aluno;

                printf(" \nDigite um nome para o Aluno: ");
                scanf("%s", &aluno.nome);

                printf(" \nDigite um RA para o Aluno: ");
                scanf("%i", &aluno.ra);

                Enfileirar(fila, aluno);

                break;
            case '2':
                Aluno alunoRetirado;
                Retirar(fila, alunoRetirado);
                printf(" \nAluno %i - %s retirado", alunoRetirado.ra, alunoRetirado.nome);
                getch();

                break;
            case '3':
                Listar(fila);

                break;
            case '0':
                return;
        }
    } while(opcao != 0);
}

Acompanhe o resultado das movimentações na fila:

Vamos para a diversão:

1) Implemente o exemplo dado anteriormente usando ponteiros.

2) Implemente uma função que retorne o número de posições livres da fila, para as duas implementações (referência e ponteiros).

3) Implemente uma função que localize um dado específico (cujo nome for igual a...) para as duas implementações da fila (referência e ponteiros). A função deve retornar na tela a posição do dado no vetor bem como as informações armazenadas sobre ele.

Espero que gostem :)

Listas Especializadas: Pilha 22:59

A pilha é uma lista! Porém ela tem uma disciplina de acesso: A inserção de um novo item, ou a remoção de um item já existente, se dá em uma única extremidade (topo), exatamente como uma pilha de pratos de cozinha.

… Ou seja: o último prato que empilhamos é o primeiro a ser lavado, ou utilizado.

Enfim, o último elemento que entrou na pilha é sempre o primeiro a sair e o primeiro que entrou é sempre o último a sair da pilha, acompanhe o funcionamento na figura:

Após esta imagem já percebemos que a exclusão de um elemento é tratada de forma diferenciada.

As pilhas são conhecidas em inglês como Stack ou LIFO (Last In First Out = Último que Entra é o Primeiro que Sai).

Reforçando: Uma pilha estática é uma lista estática em que todas as inserções, remoções e geralemente os acessos são realizados em apenas um extremo da lista: o topo.

Suas aplicações são diversas: já pensou como o sistema operacional organiza a ordem das janelas abertas? Ou como um algoritmo recursivo funciona?

Veja um exemplo de sua implementação na linguagem C:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

const int MAX = 10;

struct Aluno
{
    int ra;
    char nome[50];
};

struct Pilha
{
    Aluno alunos[MAX];
    int topo;
};

void IniciarPilha(Pilha &pilha)
{
        pilha.topo = 0;
}

bool PilhaEstaVazia(Pilha &pilha)
{
    return pilha.topo == 0;
}

bool PilhaEstaCheia(Pilha &pilha)
{
    return pilha.topo == MAX;
}

bool Empilhar(Pilha &pilha, Aluno &item)
{
    if (!PilhaEstaCheia(pilha))
    {
        pilha.alunos[pilha.topo] = item;
        pilha.topo++;
        return true;
    }
    else
    {
        return false;
    }
}

void Desempilhar(Pilha &pilha, Aluno &alunoDesempilhado)
{
    pilha.topo--;
    alunoDesempilhado = pilha.alunos[pilha.topo];
}

void Listar(Pilha pilha)
{
    printf("\nListando...\n");

    while (!PilhaEstaVazia(pilha))
    {
        Aluno alunoDesempilhado;
        Desempilhar(pilha, alunoDesempilhado);
        printf("\n%i - %s", alunoDesempilhado.ra, alunoDesempilhado.nome);
    }

    getch();
}

void main()
{
    char opcao;
    Pilha pilha;

    // -> Inicializando a pilha.
    IniciarPilha(pilha);

    do
    {
        system("cls");
        printf("Escolha a opcao desejada:");
        printf("\n 1- Empilhar um Aluno");
        printf("\n 2- Desempilhar um Aluno");
        printf("\n 3- Listar todos os elementos da pilha");
        printf("\n 0- Sair do programa\n");
        printf("\n Opcao: ");

        opcao = getchar();

        switch(opcao)
        {
            case '1':
                Aluno aluno;

                printf(" \nDigite um nome para o Aluno: ");
                scanf("%s", &aluno.nome);

                printf(" \nDigite um RA para o Aluno: ");
                scanf("%i", &aluno.ra);

                Empilhar(pilha, aluno);
                break;
            case '2':
                Aluno alunoDesempilhado;
                Desempilhar(pilha, alunoDesempilhado);
                printf(" \nAluno %i - %s desempilhado", alunoDesempilhado.ra, alunoDesempilhado.nome);
                getch();
                break;
            case '3':
                Listar(pilha);
                break;
            case '0':
                return;
        }
    }while(opcao != 0);
}

Com estes algoritmos montamos uma pilha com uma estrutura baseada na figura abaixo:

Acompanhe as saídas de exemplo:

Hora de refletir e se divertir:

1) Implemente o exemplo dado anteriormente com ponteiros.

2) Implemente uma função que retorne o número de posições livres da pilha, para as duas implementações (referência e ponteiros).

3) Implemente uma função que localize um dado específico (cujo nome for igual a...) para as duas implementações da pilha (referência e ponteiros). A função deve retornar na tela a posição do dado no vetor bem como as informações armazenadas sobre ele.

Boa diversão :)

Estudando Listas Estáticas 21:34

Uma lista é uma coleção ordenada de componentes(variáveis, estruturas, objetos etc.) do mesmo tipo, como por exemplo a lista telefone, com seus nomes e números em ordem alfabética.

As listas podem ser estáticas ou dinâmicas. As estáticas são baseadas em vetores (arrays), ou seja, seu tamanho máximo fica limitado ao tamanho da declaração do vetor. Já as dinâmicas alocam memória dinamicamente a cada novo item inserido, fazendo seu vinculo de um item com o outro ao armazenar o endereço de memória do próximo item da lista.

Suas aplicações são diversas, como, guardar em memória informações lidas de um arquivo de texto, xml e até mesmo consulta de banco de dados.

Podemos manipular as listas de várias maneiras, como:

• Acessar, inserir ou retirar itens da lista;
• Concatenar/intercalar duas listas para formar uma lista única;
• Partir uma lista em duas ou mais listas.

A lista pode existir mesmo estando vazia. Suas propriedades estruturais respondem questões como:

• Qual é o primeiro elemento da lista?
• Qual é o último elemento?
• Quais elementos precedem ou seguem um determinado elemento?
• Quantos elementos existem na lista?

Há dois tipos de representação dos dados de uma lista: Sequencial e Encadeada.

No caso das listas sequenciais o sucessor de um elemento da lista ocupa posição física subsequente. Então devemos tomar cuidado tanto na ao inserir um item, quanto na remoção de um mesmo, pois devemos deslocar os item, mantendo-os sempre aninhados e ordenados.

Acompanhe um exemplo da implementação de uma lista e das suas operações:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

const int MAX = 10;

int Procurar(int elementoProcurado, int tamanho, int lista[])
{
    int i = 0;

    while ((lista[i] != elementoProcurado) && (i < tamanho))
        i++;

    // -> Se oe elemento não for encontado é retornado o indece -1
    if (lista[i] != elementoProcurado)
        return -1;
    return i;
}

void Adicionar(int elemento, int *tamanho, int lista[])
{
    if (*tamanho < MAX)
    {
         if (Procurar(elemento, *tamanho, lista) == -1)
         {
             lista[*tamanho] = elemento;
             *tamanho = *tamanho + 1;
         }
         else
         {
             printf("\nEste elemento já foi inserido na lista!");
         }
    }
    else
    {
        printf("\nO tamanho máximo da lista foi excedido!");
    }
}

void Remover(int elemento, int *tamanho, int lista[])
{
    int posicao = Procurar(elemento, *tamanho, lista);

    if (posicao != -1)
    {
        for(int i = posicao; i < (*tamanho - 1); i++)
            lista[i] = lista[i+1];

        *tamanho = *tamanho - 1;
    }
    else
    {
        printf("\nEste elemento não existe!");
    }
}

void Listar(int tamanho, int Lista[])
{
    if (tamanho !=0)
    {
        printf("\nListando...\n");

        for(int i = 0; i < tamanho; i++)
            printf("\n%i", Lista[i]);
    }
    else
    {
        printf("\n\nA lista está vazia!");
    }

    getch();
}

void main()
{
    int Lista[MAX];
    int tamanho = 0;
    int numero;
    char opcao;

    // -> Inicializando a lista.
    for(int i = 0; i < MAX; i++)
        Lista[i] = 0;

    do
    {
        system("cls");
        printf("Escolha a opcao desejada:");
        printf("\n 1- Inserir elemento na lista");
        printf("\n 2- Excluir elemento da lista");
        printf("\n 3- Listar todos os elementos da lista");
        printf("\n 0- Sair do programa\n");
        printf("\n Opcao: ");

        opcao = getchar();

        switch(opcao)
        {
            case '1':
                printf(" \nDigite um elemento para inserido: ");
                scanf("%i", &numero);
                Adicionar(numero, &tamanho, Lista);
                break;
            case '2':
                printf(" \nDigite o elemento a ser excluido: ");
                scanf("%i",&numero);
                Remover(numero, &tamanho, Lista);
                break;
            case '3':
                Listar(tamanho, Lista);
                break;
            case '0':
                return;
        }
    }while(opcao != 0);
}

Após algumas operações conseguiremos listar os elementos, como no mostrado abaixo:

Vamos fazer uma reflexão, e ficam estes exercícios para serem implementados:

1) Considerando a implementação de uma lista estática para a seguinte struct:

const MAX=20;
struct TPAgenda {
       int cód;
       char nome[50];
       char fone[14];
} Agenda[MAX];

• Implemente uma função que retorne o número de posições livres na agenda;
• Implemente uma função que ordene todos os dados em ordem de código;
• Implemente uma função que inclui um dado já em ordem alfabética;
• Implemente uma função que localize um dado específico (cujo nome for igual a ...). A função deve retornar -1 se o dado não existir, ou a sua posição caso ele exista; (Busca Sequencial, partindo da primeira posição do vetor).
• Implementa uma função que localize um dado específico (cujo nome for igual a ...) utilizando a busca binária. A função deve retornar -1 se o dado não existir, ou a sua posição caso ele exista;

Espero que gostem, pois escrevi isto no aeroporto de Curitiba/PR esperando um voo para São Paulo/SP.