TAD Lista

Instituto de Ciências Matemáticas e de Computação 
Departamento de Computação e Estatística 
SCE182 - Algoritmos e Estruturas de Dados 1 
Profs. Resp.: Graça Pimentel, Maria Cristina e Rosane Minghim

Tipo Abstrato de Dado

Lista Ordenada

Uma lista pode ser ordenada ou não-ordenada. As operações referentes a elas dependem da organização, pois o tipo de manipulação de uma lista ordenada não é o mesmo de uma lista desordenada. Um exemplo é a inserção de um novo elemento. Numa lista ordenada sob algum critério, a inserção só pode ocorrer num determinado lugar, enquanto que numa lista desordenada, ela pode ocorrer  em qualquer lugar. Abaixo, exemplificamos as operações para um tipo abstrato de dados Lista ordenada:

Operações :

Inicialização
        Objetivo Cria uma lista vazia.
        Nome da Operação: Cria_Lista
        Parâmetros: A lista (e/s)

Inserir Elemento
        Objetivo Insere um novo elemento na lista ordenada, mantendo a ordenação.
        Nome da Operação: Insere
        Parâmetros: A lista (e/s), Flag de sucesso(s), elemento a ser inserido (e)

Buscar Elemento
        Objetivo Localiza um elemento dentro de uma lista
        Nome da Operação: Busca
        Parâmetros: A lista (e), Flag de sucesso(s), Posição (s), Informações associadas ao elemento procurado (e).

Acessar Elemento
        Objetivo Fornece o conteúdo de um elemento da lista.
        Nome da Operação: Acessar
        Parâmetros: A lista (e), Posição (e), Flag de sucesso(s), Informações associadas ao elemento procurado (s).
        Pós-condição: A operação retorna o conteúdo da lista na posição fornecida pelo usuário.
                            A lista não é alterada.
                            No caso da posição não existir, a flag de sucesso é falsa.

Eliminar Elemento
        Objetivo Retira um elemento específico da lista, mantendo a ordenação dos demais.
        Nome da Operação: Exclui
        Parâmetros: A lista (e/s), Flag de sucesso(s), referência do elemento a ser eliminado (e)

Tamanho da Lista
        Objetivo Encontra o número de elementos da lista
        Nome da Operação: Tamanho
        Parâmetros: A lista (e), número de elementos da lista (s)

Destruição da Lista
        Objetivo Destroi a lista
        Nome da Operação: Destroi
        Parâmetros: A lista (e/s).
        Pós-condição: A lista é destruída e está vazia. Seus elementos não são mais acessíveis.

-> * Incluir nesse TAD, uma operação de Diferença, que toma duas listas e devolve uma outra lista que contém somente os elementos que não estão em nenhuma delas. Fazer a implementação dessa operação supondo: alocação estática sequencial, alocação estática encadeada, e alocação dinâmica encadeada.

Índice
Lista