2.2 Estrutura de Dados Lista - Definição

• Este conjunto de dados pode possuir uma ordem intrínseca (Lista Ordenada) ou não.
• Este conjunto de dados pode ocupar espaços de memória fisicamente consecutivos, espelhando a sua ordem, ou não.
• Se os dados estiverem dispersos fisicamente, para que este conjunto seja uma lista, ele deve possuir operações e informações adicionais que permitam que seja tratado como tal (Lista Encadeada).

• De que forma estão organizados os dados, qual a sua estrutura.
• Quais procedimentos atuam sobre estes dados, que operações podem ser realizadas sobre eles.
• Vamos ver agora estes aspectos para as listas.

2.2.1 Listas usando Vetores: Modelagem de Listas utilizando Programação Estruturada

• Modelaremos a Estrutura de Dados Lista utilizando a técnica da Programação Estruturada e como forma de armazenamento um Vetor (Array).
• Veremos somente algoritmos.
• Veremos algoritmos tanto para uma lista cronológica como para uma lista ordenada.
• Procedimento Didático:
• Modelagem da Lista e de seus algoritmos usando a técnica estruturada.
• Exercícios

• Aspecto Estrutural:
• Necessitamos de um vetor para armazenar as informações.
• Necessitamos de um indicador da posição atual do ultimo elemento da lista.
• Necessitamos de uma constante que nos diga quando a lista está cheia e duas outras para codificar erros.

• Pseudo-código:

• Aspecto Funcional:

1. Colocar e retirar dados da lista.
2. Testar se a lista está vazia ou cheia e outros testes.
3. Inicializa-la e garantir a ordem dos elementos.

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

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

• Operações: Inicializar ou limpar:

Algoritmo InicializaLista

• Procedimento:
• Testamos se há espaço.
• Incrementamos o último.
• Adicionamos o novo dado.
• Parâmetros:
• O dado a ser inserido.
• Lista (global).

• Procedimento:
• Testamos se há elementos.
• Decrementamos o último.
• Devolvemos o último elemento.
• Parâmetros:
• Lista (global).

Algoritmo AdicionaNoInício

• Procedimento:
• Testamos se há espaço.
• Incrementamos o último.
• Empuramos tudo para trás.
• Adicionamos o novo dado na primeira posição.

• Parâmetros:
• O dado a ser inserido.
• Lista (global).

• Procedimento:
• Testamos se há elementos.
• Decrementamos o último.
• Salvamos e primeiro elemento.
• Empuramos tudo para a frente.
• Parâmetros:
• Lista (global).

• Procedimento:
• Testamos se há espaço e se a posição existe.
• Incrementamos o último.
• Empuramos tudo para trás a partir da posição.
• Adicionamos o novo dado na posição dada.

• Parâmetros:
• O dado a ser inserido.
• A posição onde inserir.
• Lista (global).

• Procedimento:
• Testamos se há elementos e se a posição existe.
• Decrementamos o último.
• Salvamos elemento na posição.
• Empuramos tudo para frente até posição.

• Parâmetros:
• O dado a ser inserido.
• A posição onde inserir.
• Lista (global).

• Procedimento:
• Necessitamos de uma função para comparar os dados (maior)
• Testamos se há espaço.
• Procuramos pela posição onde inserir comparando dados.
• Chamamos adicionaNaPosição.

• Parâmetros:
• O dado a ser inserido.
• Lista (global).


Preâmbulo: Algoritmo Maior
 

Booleano FUNÇÃO maior(inteiro dado1, dado2)
início SE (dado1 > dado2) ENTÃO RETORNE(Verdade) SENÃO RETORNE(Falso); FIM SE fim;

• Observação: Quando o dado a ser armazenado em uma lista for algo mai scomplexo do que um inteiro, a comparação de precedênci não será mais tão simples (ex.: Empregado1 > Empregado2) e será resultado de um conjunto mais complexo de operações.

Para deixar os algoritmos de operações sobre lista independentes do tipo de dado específico armazenado na lista, usamos uma função deste tipo.

Algoritmo AdicionaEmOrdem

• Retira um dado específico da lista.
• Procedimento:
• Testamos se há elementos.
• Testamos se o dado existe e qual sua posição.
• Necessitamos de uma função Posição(dado)
• Chamamos RetiraDaPosição.
• Parâmetros:
• O dado a ser retirado.
• Lista (global).

Preâmbulo: Algoritmo Posição

• As seguintes funções:
booleano Contem(dado)
booleano Igual(dado1, dado2)
booleano Menor(dado1, dado2)

Ficam por conta do aluno.
 

• Obrigatório: Utilize os algoritmos implementados nesta aula para desenvovler um pequeno programa em "C" que leia números inteiros e os insira/delete de uma lista. Este programinha deve ter um pequeno menu (em ASCII) que oferece todas as opções (funções) acima (menos a de criar uma lista). Numere as opções e permita ao usuário entrar com o número da função a ser executada, passando à execução em seguida. Pesquise a utilização do comando switch em "C" para a implemntação deste menu em um laço.
• Observe que será necessário que você implemente ainda uma função que mostra o conteúdo (todos os elementos em ordem) da lista, pois esta função não foi dada em aula mas é necessária ao trabalho.
• Entrega: terca feira.

 

 

• Opcional: Para melhorar o seu domínio de "C" tente, depois que você implementou a lista para números interios, implementá-la para strings de tamanho máximo 30 caracteres.
• Observe que para definir um vetor de strings de no máximo 30 caracteres, voce deve em "C" definir uma matriz de caracteres

tipo Lista {
    caracter    dados[Maxlista][31];
    inteiro     ultimo;
}
• Observe que você pode referenciar um string na posição 3 da lista simplesmente utilizando aLista.dados[3] e omitindo o segundo índice. O resultado será um ponteiro para string (char *).
• As suas funções de manipulação de listas devem refletir o fato de que voce agora está trabalhando com uma matriz.
• Observe também que o tamanho é 31 para cada linha da matriz, pois "C" utiliza o caracter ASCII 0 (zero) para indicar o fim de um string e um string de 30 caracteres ocupará 31 bytes.