Estrutura de Dados I
Listas Lineares - Parte II
Listas Estáticas
Prof. Othon M. N. Batista
Mestre em Informática
Roteiro
Fundamentos
Operações Usuais
Implementação com Vetor
Fundamentos
Uma lista linear estática é uma sequência de
zero ou mais elementos
L : [a1, a2, ..., an], n ≥ 0.
ai é um elemento do mesmo tipo, 1 ≤ i ≤ n
n é o tamanho da lista
Fundamentos
Os elementos têm uma relação de ordem na
lista:
a1 é o primeiro elemento de L;
an é o último elemento de L;
ak, 1 < k < n, é precedido pelo elemento ak-1
e seguido por ak+1 em L.
Fundamentos
Exemplo:
var Lista : Array [1 .. 10] of String;
...
Lista [1] := 'Fulano de Tal';
...
Lista [11] := 'Essa linha tem um erro';
Roteiro
Fundamentos
Operações Usuais
Implementação com Vetor
Operações Usuais
Operações sobre listas:
Iniciar ou criar uma lista vazia;
Combinar duas listas;
Dividir uma lista em duas ou mais;
Copiar uma lista.
Operações Usuais
Operações sobre elementos da lista:
Inserir um novo elemento no final da lista;
Pesquisar um elemento na lista;
Alterar um elemento da lista;
Remover um elemento da lista;
Ordenar os elementos da lista.
Operações Usuais
Inicia uma Lista (Função):
descrição: cria uma lista vazia;
parâmetro: tipoLista L;
resultado: lista L vazia.
Operações Usuais
Teste de Lista Vazia (Função):
descrição: testa se a lista está vazia;
parâmetro: tipoLista L;
resultado: retorna TRUE se a lista está
vazia, caso contrário retorna FALSE.
Operações Usuais
Inserir um Elemento na Lista (Procedimento):
descrição: insere um elemento após o último da
lista;
parâmetros: TipoItem x; TipoLista L; Boolean
flag
teste: a lista L tem n ≥ 0 e n < MAXIMO
resultado: insere x em L e retorna TRUE em
flag ou não insere e retorna FALSE em flag
Operações Usuais
Como descrever outras operações???
Remover um elemento da lista;
imprimir um elemento da lista.
Roteiro
Fundamentos
Operações Usuais
Implementação com Vetor
Implementação com Vetor
Implementação com Vetor
Componentes da lista:
quantidade de elementos na lista;
vetor de elementos;
tamanho da lista.
Implementação com Vetor
Constantes em Pascal
Const
MAXTAM = 50;
MSG_SUCESSO = 1;
MSG_LISTACHEIA = 2;
MSG_LISTAVAZIA = 3;
MSG_POSINVALIDA = 4;
Implementação com Vetor
Constantes em C
#define MAXTAM 50
#define MSG_SUCESSO
#define MSG_LISTACHEIA
#define MSG_LISTAVAZIA
#define MSG_POSINVALIDA
1
2
3
4
Implementação com Vetor
Tipos em Pascal
Type
TipoElemento = Integer;
TipoLista = Record
Total: Integer;
Memo: Array [1 .. MAXTAM] of TipoElemento;
End;
Implementação com Vetor
Tipos em C
typedef int TipoElemento;
typedef struct STipoLista
{
int Total;
TipoElemento Memo [MAXTAM];
} TipoLista, *APTipoLista;
Implementação com Vetor
Criar Lista em Pascal
Procedure CriaLista (Var Lista: TipoLista);
Begin
Lista.Total :=0;
End;
Implementação com Vetor
Criar Lista em C
void CriaLista (APTipoLista Lista);
Begin
Lista -> Total =0;
End;
Implementação com Vetor
Inserir no Fim da Lista em Pascal
Procedure InsereNoFim (Var Lista : TipoLista;
Numero : TipoElemento; Var Flag : Bolean);
Begin
If (Lista.Total = MAXTAM)
Then Flag := MSG_LISTACHEIA
Else Begin
Lista.Total := Lista.Total + 1;
Lista.Memo[Lista.Total] := Numero;
Flag := MSG_SUCESSO;
End;
End;
Implementação com Vetor
Inserir no Fim da Lista em C
int InsereNoFim (APTipoLista Lista, TipoElemento Numero)
{
int
Flag;
If (Lista -> Total == MAXTAM)
Flag = MSG_LISTACHEIA
Else
{
Lista -> Total ++;
Lista -> Memo[Lista.Total] = Numero;
Flag = MSG_SUCESSO;
}
return Flag;
}
Implementação com Vetor
Inserir no Início da Lista em Pascal
Function IncluiInicio (Var Lista: TipoLista; Numero: TipoElemento) : Integer;
Var
Retorno,
i : Integer;
Begin
If (Lista.Total = MAXTAM) Then Retorno := MSG_LISTACHEIA
Else Begin
Lista.Total := Lista.Total + 1;
For i := Lista.Total Downto 2 Do
Lista.memo [i] := Lista.memo [i-1];
Lista.memo [1] := Numero;
Retorno := MSG_SUCESSO;
End;
IncluiInicio := Retorno;
End;
Implementação com Vetor
Inserir no Início da Lista em C
int IncluiInicio (APTipoLista Lista, TipoElemento Numero)
{
int
Retorno,
i : Integer;
if (Lista -> Total == MAXTAM) Retorno = MSG_LISTACHEIA
Else {
Lista -> Total ++;
for (i = Lista -> Total - 1; i > 0; -- i)
Lista -> memo [i] = Lista -> memo [i-1];
Lista -> memo [0] = Numero;
Retorno = MSG_SUCESSO;
}
return Retorno;
}
Exercício
Implemente as operações listadas com a estrutura de
dados definida nestes slides:

inserir um elemento em uma posição específica;

pesquisar um elemento pelo valor do elemento;

remover um elemento do final da lista;

remover um elemento do início da lista;

ordenar uma lista.