4.1 Listas Encadeadas

4.1.1 Modelagem de Dados
4.1.2 Listas Encadeadas: Modelagem de Dados Genérica
4.1.3 Modelagem Funcional

• Algoritmo CriaLista
• Algoritmo ListaVazia
• Algoritmo AdicionaNoInício
• Algoritmo RetiraDoInício
• Algoritmo EliminaDoInício
• Exemplo simplificado: Programa Principal
• Algoritmo AdicionaNaPosição
• Algoritmo RetiraDaPosição
• Modelagem do Tipo Info
• Algoritmo AdicionaEmOrdem
• Algoritmo DestroiLista
• Algoritmos Restantes

4.0 Listas com Vetores: Desvantagens

• Tamanho máximo fixo
• Mesmo vazias ocupam espaço grande de memória
• Mesmo que utilizemos um vetor de ponteiros, se quisermos prever uma lista de 10.000 elementos, teremos 40.000 bytes desperdiçados.
• Operações podem involver muitos deslocamentos de dados:
• Inclusão em uma posição ou no início
• Exclusão em uma posição ou no início

4.1 Listas Encadeadas

• São listas onde cada elemento contido em uma lista está armazenado em um TAD chamado elemento de lista.
• Cada elemento de lista referencia o próximo e só é alocado dinamicamente quando é necessário
• Para referenciar o primeiro elemento utilizamos um TAD cabeça de lista.

4.1.1 Modelagem de Dados

Cabeça de Lista

• Necessitamos:
• Um ponteiro para o primeiro elemento da lista.
• Um inteiro para indicar quantos elementos a lista possue.
• Pseudo-código:

Elemento de Lista

Necessitamos:

• Um ponteiro para o próximo elemento da lista.
• Um campo do tipo da informação que vamos armazenar.
• Pseudo-código:
 
tipo Elemento {
    Elemento *próximo;
    tipo-que-eu-vou-usar-nesta-aplicação info;
};

4.1.2 Listas Encadeadas: Modelagem de Dados Genérica

• Para tornar todos os algoritmos da lista mais genéricos, fazemos o campo info ser um ponteiro para um elemento de informação.

Modelagem: Elemento de Lista II

• Pseudo-código II:

• Razões para a modelagem do TipoInfo:
• Vamos na maioria dos algoritmos trabalhar com algum elemento de infomação.
• Se este elemento é somente um ponteiro para um TipoInfo, não importando o que este seja, teremos algoritmos totalmente genéricos.
• Posso usar o mesmo código de lista para muitas aplicações diferentes simplesmente recompilando.
• Desvantagens:
• O algoritmo de destruição da lista torna-se mais complexo.

4.1.3 Modelagem Funcional

• Aspecto Funcional: Três Grupos de Funções
• Colocar e retirar dados da lista.
• Testar se a lista está vazia e outros testes.
• Inicializa-la e garantir a ordem dos elementos.


Modelagem da Lista

Operações: Colocar e retirar dados da lista:

• Adiciona(lista, dado)
• AdicionaNoInício(lista, dado)
• AdicionaNaPosição(lista, dado, posição)
• AdicionaEmOrdem(lista, dado)

 
• Retira(lista)
• RetiraDoInício(lista)
• RetiraDaPosição(lista, posição)
• RetiraEspecífico(lista, dado)


Operações: Testar a lista e outros testes:

• ListaVazia(lista)
• Posicao(lista, dado)
• Contem(lista, dado)
Operações: Inicializar ou limpar:
• CriaLista()
• DestroiLista(lista)

---

Algoritmo CriaLista

Algoritmo ListaVazia

• Um algoritmo ListaCheia não existe aqui.
• Verificar se houve espaço na memória para um novo elemento será responsabilidade de cada operação de adição.

Algoritmo AdicionaNoInício

• Procedimento:
• Testamos se é possível alocar um elemento.
• Fazemos o próximo deste novo elemento ser o primeiro da lista.
• Fazemos a cabeça de lista apontar para o novo.
• Parâmetros:
• O tipo info (dado) a ser inserido.
• Lista.

---

Algoritmo RetiraDoInício

• Procedimento:
• Testamos se há elementos.
• Decrementamos o tamanho.
• Liberamos a memória do elemento.
• Devolvemos a Informação.
• Parâmetros:
• Lista.

TipoInfo* FUNÇÃO retiraDoInício( Lista *aLista )

"Elimina o 1. Elemento de uma lista.
 Retorna a informação do elemento eliminado ou NULO."
variáveis Elemento *saiu; "Var. auxiliar para o 1. elemento"
TipoInfo *volta; "Var. auxiliar para o dado retornado" início SE (listaVazia(aLista)) ENTÃO RETORNE( NULO ); SENÃO saiu <- aLista->dados;
volta <- saiu->info;
aLista->dados <- saiu->proximo;
aLista->tamanho <- aLista->tamanho - 1;
LIBERE(saiu);
RETORNE(volta); FIM SE fim;

---

Algoritmo EliminaDoInício

• Observe que a linha libere(saiu->info) possui um perigo:
• Se o tipoInfo for por sua vez um conjunto estruturado de dados com referências internas através de ponteiros (outra lista, p.ex.), a chamada à função libere(saiu->info) só liberará o primeiro nível da estrutura (aquele apontado diretamente).
• Tudo o que for referenciado através de ponteiros em info permanecerá em algum lugar da memória, provavelmente inatingível (garbage).
• Para evitar isto pode-se criar uma função destroi(info) para o TipoInfo que será chamada ao invés de libere.

---

Exemplo simplificado: Programa Principal

#inclua listaEnc.h

variáveis
    Lista *devedores, *credores, *listaEscolhida;
    TipoInfo *dado;
    caracter opção;

1 Programa Principal
2     início
3         devedores <- criaLista();
4         credores <- criaLista();
5         opção <- ´´;
6         ENQUANTO (opção ~= ´f´) ENTÃO
7             escreveMenu();
8             leia(opção);
9             CASO opção SEJA
10             ´c´: listaEscolhida <- credores;
11             ´d´: listaEscolhida <- devedores;
12             ´i´: dado <- leiaInfo(); "P/tipoInfo leitura espec."
13                  adicionaNoInício(listaEscolhida,dado);
--             - - - -
--             - - - -
--             FIM CASO
--         FIM ENQUANTO
--    fim;
 
 

Memória logo após  o início do programa,  quando o fluxo de execução  do programa se encontra na  linha #2.
Memória logo após as  2 chamadas às funções  criaLista(), quando o  fluxo de execução do  programa se encontra  na linha #5.
Memória imediatamente  antes de retornar de uma  chamada à função  adicionaNoInício(),  quando a listaEscolhida  é a dos credores e o  fluxo de execução do  programa se encontra  na última linha da função  adicionaNoInício e retornará  ao programa principal para a  linha #13.

 

---

Algoritmo AdicionaNaPosição

• Procedimento:
• Testamos se a posição existe e se é possível alocar elemento.
• Caminhamos até a posição.
• Adicionamos o novo dado na posição.
• Incrementamos o tamanho.
• Parâmetros:
• O dado a ser inserido.
• A posição onde inserir.
• Lista.


Inteiro FUNÇÃO adicionaNaPosição( Lista *aLista, TipoInfo *info, inteiro posição )

"Adiciona novo elemento na posição dada.
 Retorna a novo numero de elementos da lista ou erro."
variáveis
Elemento *novo, *anterior; "Ponteiros auxiliares"
início SE (posição > aLista->tamanho + 1) ENTÃO RETORNE( ErroPosição ) SENÃO SE (posição = 1) ENTÃO RETORNE(adicionaNoInício(aLista, info); SENÃO novo <- aloque(Elemento);
SE (novo = NULO) ENTÃO RETORNE( ErroListaCheia ); SENÃO anterior <- aLista->dados;
REPITA (posição - 2) VEZES anterior <- anterior->proximo; novo->proximo <- anterior->proximo;
novo->info <- info;
anterior->proximo <- novo;
aLista->tamanho <- aLista->tamanho + 1;
RETORNE(aLista->tamanho); FIM SE FIM SE FIM SE fim;

---

Algoritmo RetiraDaPosição

• Procedimento:
• Testamos se a posição existe.
• Caminhamos até a posição.
• Retiramos o dado da posição.
• Decrementamos o tamanho.
• Parâmetros:
• A posição de onde retirar.
• Lista.


 TipoInfo* FUNÇÃO retiraDaPosição( Lista *aLista, inteiro posição )

"Elimina o Elemento na posição posição de uma lista.
 Retorna a informação do elemento eliminado ou NULO."
variáveis
Elemento *anterior, *eliminar; "Var. auxiliar para elemento"
TipoInfo *volta; "Var. auxiliar para o dado retornado"
início
SE (posição > aLista->tamanho) ENTÃO
    RETORNE( NULO );
SENÃO
    SE (posição = 1) ENTÃO
        RETORNE( retiraDoInício(aLista) );
    SENÃO
        anterior <- aLista->dados;
        REPITA (posição - 2) VEZES
            anterior <- anterior->proximo;
        eliminar <- anterior->proximo;
        volta <- eliminar->info;
        anterior->proximo <- eliminar->proximo;
        aLista->tamanho <- aLista->tamanho - 1;
        LIBERE(eliminar);
        RETORNE(volta);
    FIM SE
FIM SE
fim;

---

Modelagem do Tipo Info

• Para inserção em ordem e para achar um elemento determinado, necessitamos da capacidade de comparar informações associadas aos elementos.
• Estas operações de comparação fazem parte do TAD TipoInfo e não da lista.
• Devem ser implementadas como tal.
• Operações: Testar AS INFORMAÇÕES:
• Igual(dado1,dado2)
• Maior(dado1,dado2)
• Menor(dado1,dado2)

---

Algoritmo AdicionaEmOrdem

• Procedimento:
• Necessitamos de uma função para comparar os dados (maior)
• Procuramos pela posição onde inserir comparando dados.
• Chamamos adicionaNaPosição.
• Parâmetros:
• O dado a ser inserido.
• Lista.

variáveis
    Elemento *atual; "Variável auxiliar para caminhar"
    inteiro posição;
início

SE (listaVazia(aLista)) ENTÃO
    RETORNE(adicionaNoInício(aLista, dado));
SENÃO
    atual <- aLista->dados;
    posição <- 1;
    ENQUANTO (atual->proximo ~= NULO E maior(dado, atual->info)) FAÇA
        "Encontrar posição para inserir"
        atual <- atual->proximo;
        posição <- posição + 1;
    FIM ENQUANTO
    SE maior(dado, atual->info) ENTÃO "Parou porque acabou lista"
        RETORNE(adicionaNaPosição(aLista, dado, posição + 1));
    SENÃO
        RETORNE(adicionaNaPosição(aLista, dado, posição));
    FIM SE
FIM SE

fim;

---

Algoritmo DestroiLista

---

Algoritmos Restantes