Índice > Lista > Generalizada

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

Lista Generalizada

Problema

  • uma lista típica em LISP é da forma L1 = (a,(b,c)) e
  • uma lista típica em Prolog é da forma L2 = [a, [b,c]].

    • Ambas as listas contêm dois elementos:

  • o primeiro elemento é o atomo a e
  • o segundo elemento é a lista formada pelos elementos b e c.

    • Para representar essas listas, precisamos de uma estrutura que permita dizer quando um elemento é um átomo ou um ponteiro para outra lista

    Listas Generalizadas

    Uma lista generalizada é aquela que pode ter como elemento ou um átomo ou uma outra lista (sub-lista).
    Toda lista pode ser representada usando-se a estrutura de nó onde:
  • CABEÇA (CAR) é um atomo ou um ponteiro para uma outra lista
  • CAUDA (CDR) ligação para a cauda da lista ('próximo elemento')
  • TAG é 0 (CABEÇA é atomo) ou é 1 (CABEÇA é ponteiro)

    • Exemplo:

    L1 = (a, (b, c) )

    L2 = (a, b, c)

    L3 = ( (a, b), (c, d), e)

    Este tipo de estrutura nos permite manipular também Listas Compartilhadas e Listas Recursivas.

    Implementação de Listas Generalizadas

    Utilizam o Recurso do Pascal (record variante) 
      Type
    pont_no = ^no;
    no = record
           cauda: pont_no;
           case tag: boolean of
             true: (pont: pont_no);
             false: (atomo: tipo_elem);
         End;
     Lista = pont_no;

    Operações em Listas Generalizadas

    Exercícios

    Lista

    Índice