Definição:

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;

• elemento: é um nó da lista, normalmente manipulado na forma de um ponteiro para este nó:
  (elem = pont_no), ou alternativamente como o próprio nó (elem = no).
  
  
• valor: é o conteúdo de um determinado elemento. É o objeto armazenado pela lista individualmente. Então, valor = tipo_elem.
  
  
• ponteiro externo: é um ponteiro que NÃO é elemento de uma lista.
  
  
• ponteiro interno: é um ponteiro que faz parte de uma lista, como elemento dela. (isto é, armazenado no campo pont).

Operações usuais em Lista Generalizada

Algumas operações típicas de Lista Generalizada são:

Obs: retorno das operações em itálico.

cabeça (lista,valor)

    Fornece o valor do primeiro elemento de lista (a cabeça).

cauda (lista1,lista2)

    Fornece a lista obtida removendo-se do primeiro elemento de lista (a cabeça) -

       isto é, o ponteiro para a cauda.

primeiro (lista, elem)

    Retorna o elemento correspondente à cabeça da lista.

info (elem, valor)

    Retorna o valor correspondente ao elemento elem.

próximo (elem, proxElem)

    Retorna o elemento seguinte ao elemento elem da lista.

tipo_nó (elem,tipo)

    Retorna o tipo do elemento, isto é, se ele é lista ou átomo.

define_cabeça (lista, x:no)

    Substitui a cabeça da lista pelo elemento dado por x.

insere_início (lista, x:no, lista1)

    Insere um elemento no início da lista, mas não altera a cabeça da lista.

    Retorna um ponteiro para essa 'nova' lista em lista1.

define_próximo (elem1, elem2)

    Substitui o próximo elemento a elem1 por elem2. Como tudo em elem2 fica intacto,

    essa operação é equivalente a trocar todo o restante da lista que contem elem1, a

    a partir do próximo elemento.

define_cauda (l, list1)

    Define a lista list1 como sendo a cauda da lista l.

define_info (elem, valor)

    Atribui valor ao conteúdo do elemento elem.

vazia (list)

    Determina se a lista list está vazia

inicializa (list)

    Inicializa list como uma lista vazia.

esvazia (list)

    Torna a lista vazia.

Algoritmos Baseados nas Operações Acima

Suponha que se deseja criar as seguintes listas:

Lista 1

Lista 2

Qual a sequência das operações acima para construção da lista acima?

-> Refazer a sequência de operações após definir as operações, isto é, definindo os

  comandos Pascal para construção da lista.

Definição de algumas operações: supondo implementação sem cabeçalho

Function primeiro (lista:pont_no): pont_no;

Begin

    primeiro:=lista;

End;

-> Perguntas: Por que, em Pascal, é necessário retornar o ponteiro?

              Porque é razoável contruir a Function primeiro, se ela retorna a

                própria lista?

Procedure próximo (elem: pont_no; VAR proxElem:pont_no);

Begin

    proxElem:= pont_no^.cauda;

End;

Procedure info_el (elem:pont_no; Var valor:tipo_elem);

Begin

    if (not elem^.tag) then valor:=elem^.atomo

    else valor:= valorNulo;

End;

Procedure info_l (elem:pont_no; Var lista:pont_no);

Begin

    if (elem^.tag) then lista:=elem^.pont

    else valor:= pontNulo;

End;

-> Necessidade de determinar um elemento nulo - > usuário

-> Se o registro do elemento, na definição do início da página, fosse feita mais

adequadamente, seria possível retornar a informação de um nó por uma única operação,

info, que retornaria o conteúdo (ponteiro ou átomo) e o tipo do conteúdo.

Procedure define_cabeça (lista: pont_no; x:no)

var p:pont_no;

Begin

    x^.cauda = lista^.cauda;

    lista^:=x;

End;

Function insere_início (lista:pont_no, x:no): pont_no;

var p:pont_no;

Begin

    new(p);

    p^:=x;

    p^.cauda := lista;

    insere_início := p;

End;

Procedure define_próximo (elem1, elem2:pont_no);

var p:pont_no;

Begin

    p:= elem1^.cauda;

    elem1^.cauda:=elem2;

   -> -> O que fazer com a antiga cauda, isto é, o resto da lista a partir de elem1?

End;

Procedure define_cauda (l, list1: pont_no);

Begin

    define_próximo (l,list1);

End

Procedure define_info (elem: pont_no, valor:no);

-> Atenção. Aqui, seria melhor se o objeto da lista estivesse definido como

        conteúdo (atomo ou lista+tag) e cauda, em dois campos separados.

Begin

    valor^.cauda = elem^.cauda;

    elem^:=valor;

End;

Procedure tipo_nó (elem:no): boolean;

-> Aqui seria melhor se o tipo do elemento fosse definido por enumeração.

Begin

    tipo_nó:= elem^.tag;

End;

-> Completar a definição das operações acima

-> Fazer as alterações sugeridas acima para o tipo lista, e re-fazer todas as

operações para o novo tipo. As alterações sugeridas são:

            . Usar tipo enumerado, ao invés de boolean, para definir o

                conteúdo de um nó.

            . Separar o registro referente a um elemento da lista em dois, um

                contento o conteúdo (ou info), que contém tag e valor (seja ele

                ponteiro ou atomo), e o outro contendo o ponteiro para o próximo

                (ou cauda).

            Lembre-se de definir uma única operação info.

-> Considerar condições de erro, pré-condições e pós-condições das operações

    definidas acima.

-> Re-fazer as operações, considerando que lista tem um cabeçalho.

-> Fazer busca

-> Extrair o TAD, e implementar as operações de interface do mesmo.

-> Implementar as demais operações

Exercícios

Listas Generalizadas