Estudando Listas Estáticas

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.