Estrutura de dados - di.ubi.ptcbarrico/Disciplinas/AlgoritmosEstruturas... · Estrutura de dados: Notas: - depois de um elemento ser eliminado da lista, é necessário libertar o

1

LISTAS SIMPLES - ARMAZENAMENTO NÃO SEQUENCIAL COM VETORES

Estrutura de dados:

- Lista é um vetor em que cada componente (nodo) é composto por 2 campos:

- Elemento (informação a tratar), que pode ser um tipo de dados

- não estruturado básico (inteiro, real, caracter, ...), ou

- estruturado (vetor, matriz, registo, ...); se o tipo de dados é um registo, então é

composto por um ou mais subcampos (dependendo do volume de informação a tratar)

em que um deles pode funcionar como Chave (valor que caracteriza cada elemento e

que é base da ordenação e da pesquisa na lista);

- Prox (índice do nodo que o segue na lista; isto é, o sucessor), que é um número inteiro;

- InicioLista (índice do nodo que contém o primeiro elemento da lista).

- Representação de um nodo da lista:

Nodo

Elemento Informação

Prox Sucessor

2

Exemplo 1: Lista com 6 nodos, em que o elemento de cada nodo é um inteiro.

Representação gráfica:

Lista

16 • 29 • 14 • 18 • 36 • 23 •

Estrutura de dados:

Lista(k) = struct { Elemento, Prox }, k = 1, ..., 6

Lista é um tipo de dados estruturado, mais especificamente um registo (estrutura);

Elemento é um tipo de dados não estruturado básico (inteiro).

InicioLista = 3

Lista 1 2 3 4 5 6

Elemento 29 23 16 14 36 18

Prox 4 0 1 6 2 5

Implementação em MatLab:

Lista(3).Elemento = 16; Lista(3).Prox = 1; (InicioLista = 3)

Lista(1).Elemento = 29; Lista(1).Prox = 4;




Lista(2).Elemento = 23; Lista(2).Prox = 0; (último, logo sem sucessor)

3

Exemplo 2: Lista com 3 nodos, em que o elemento de cada nodo contém o número e o

nome de um estudante, e a nota final obtida pelo estudante em AED.


Lista

Numero: 34624

Nome: Luis Marques

NotaFinal:15.6

•

Numero: 25267

Nome: Carlos Lopes

NotaFinal: 14.9

•

Numero: 36254

Nome: Isabel Paiva

NotaFinal: 18.7

•

Estrutura de dados:

Lista(k) = struct { Elemento, Prox }, k = 1, ..., 3

Elemento = struct { Numero, Nome, NotaFinal }

Lista é um tipo de dados estruturado, mas especificamente um registo (estrutura).

Elemento é um tipo de dados estruturado, mas especificamente um registo (estrutura).

InicioLista = 2

Lista 1 2 3

Elemento Numero: 25267

Nome: Carlos Lopes

NotaFinal: 14.9

Numero: 34624

Nome: Luis Marques

NotaFinal:15.6

Numero: 36254

Nome: Isabel Paiva

NotaFinal: 18.7

Prox 3 1 0

4

Representação computacional:

Lista 1 2 3

Elemento Numero: 25267

Nome: Carlos Lopes

NotaFinal: 14.9

Numero: 34624

Nome: Luis Marques

NotaFinal:15.6

Numero: 36254

Nome: Isabel Paiva

NotaFinal: 18.7

Prox 3 1 0

Implementação em MatLab:

Primeiro elemento (InicioLista = 2):

Lista(2).Elemento.Numero = 34624; Lista (2).Elemento.Nome = 'Luis Marques';

Lista (2).Elemento.NotaFinal = 15.6;

Lista (2).Prox = 1; % segundo elemento da lista (índice 1)

Segundo elemento (índice 1)

Lista (1).Elemento.Numero = 25267; Lista (1).Elemento.Nome = 'Carlos Lopes';


Lista (1).Prox = 3; % terceiro elemento da lista (índice 3)

Terceiro elemento (índice 3)

Lista (3).Elemento.Numero = 36254; Lista (3).Elemento.Nome = 'Isabel Paiva';


Lista (3).Prox = 0; (não tem sucessor, logo é último da lista)

5

Operações básicas sobre uma lista:

- Criar um nodo de uma lista (a partir de um elemento)

- Criar uma lista (com um elemento)

- Libertar/destruir um nodo de uma lista

- Verificar se uma lista está vazia

- Listar/mostrar os elementos de uma lista (início para fim; fim para início)

- Determinar o tamanho (número de elementos) de uma lista

- Consultar um elemento numa lista

- Pesquisar um elemento numa lista (não ordenada; ordenada)

- Inserir um elemento numa lista (início; fim; por ordem)

- Remover um elemento de uma lista

Outras operações sobre uma lista:

- Determinar o maior elemento de uma lista

- Alterar/atualizar os dados de um elemento de uma lista

- Trocar dois elementos de uma lista

6

Criar um nodo de uma lista (a partir de um elemento)


Nodo

Elem •

Estrutura de dados (representação):

Nodo

Elemento Elem

Prox 0

Parâmetros:

Entrada: informação referente a um elemento (Elem)

Saída: um nodo isolado composto pelo elemento dado e sem sucessor (Nodo)

Função implementada em MatLab (iterativa):

function [Nodo] = CriarNodo (Elem)

Nodo.Elemento = Elem;

Nodo.Prox = 0;

7

Criar uma lista (com um elemento)


Lista

Elem •

Estrutura de dados (representação):

Lista 1

Elemento Elem

Prox 0

Parâmetros:

Entrada: informação referente a um elemento (Elem)

Saída: lista com um só nodo (Lista) e início da lista (InicioLista)


function [Lista, InicioLista] = CriarLista (Elem)

nodo = CriarNodo(Elem);

Lista(1) = nodo;

InicioLista = 1;

8

Libertar um nodo de uma lista

Representação gráfica: libertar o nodo com Elem3 (já retirado da Lista)

Lista indNodo

Elem1 • Elem2 • Elem3 • Elem4 • Elem5 • Elem6 •

Estrutura de dados:

Notas:

- depois de um elemento ser eliminado da lista, é necessário libertar o seu nodo do vetor;

- no cálculo do tamanho da lista, este elemento já não é contabilizado, apesar do seu nodo

ainda estar no vetor (tamanho lista = tamanho vetor - 1);

- o nodo a libertar tem o seu campo Prox = -1;

- a libertação do nodo consiste em removê-lo do vetor da lista e depois atualizar os valores

do campo "Prox" de forma que não haja valores fora da dimensão do vetor;

- este processo consiste em 3 passos:

1º) "eliminar" o nodo do vetor da lista e atualizar a sua dimensão,

2º) atualizar os índices dos sucessores dos nodos da lista (os que forem necessários),

3º) atualizar o inicio da lista (se for necessário).

9

Representação: libertar o nodo com Elem3, já retirado da lista mas não do vetor da lista

tamanho da lista = 5 (tamanho do vetor = 6)

InicioLista = 3 (índice do nodo inicial da lista)

indNodo = 4 (índice do nodo a libertar; campo Prox = -1)

Início:

Lista 1 2 3 4 5 6

Elemento Elem2 Elem6 Elem1 Elem3 Elem5 Elem4

Prox 6 0 1 -1 2 5

1º passo:

Lista 1 2 3 4 5

Elemento Elem2 Elem6 Elem1 Elem5 Elem4

Prox 6 0 1 2 5

2º passo: (note-se que o nodo 4 não é sucessor de qualquer nodo e o nodo 6 é sucessor de 1)

Lista 1 2 3 4 5


Prox 5 0 1 2 4

3º passo: (como o inicio da lista está antes do nodo 4, então não sofre alteração)

InicioLista (=3) < indNodo (=4) ==> InicioLista = 3 (não sofre alteração)

10

Parâmetros:

Entrada: lista (Lista) e início da lista (InicioLista)

Saída: lista sem o nodo libertado (Lista) e início da lista atualizado (InicioLista)

Algoritmo (iterativo):

Determinar o tamanho da lista (tam)

Se a lista está vazia (tam = 0) Então

Sair (o nodo a libertar está no fim do vetor da lista − índice 1)

Senão

Determinar o índice do nodo a libertar (indNodo)

Se o nodo a libertar está na última posição do vetor ou não existe (indNodo > tam) Então

Eliminar o nodo da posição indNodo do vetor e atualizar a sua dimensão

Sair (o nodo a libertar é o último do vetor)

Senão

Eliminar o nodo da posição indNodo do vetor e atualizar a sua dimensão

Atualizar os campos Prox dos nodos com valores maiores do que indNodo

Atualizar o início da lista (se for um valor superior a indNodo)

11


function [Lista, InicioLista] = LibertarNodoLista (Lista, InicioLista)

tam = TamanhoLista(Lista, InicioLista);

if tam == 0

return;

end;

% determinar o nodo a libertar (indNodo), percorrendo todo o vetor da lista

% o nodo a libertar tem o seu campo Prox = -1

indNodo = 1;

while indNodo <= tam & Lista(indNodo).Prox ~= -1

indNodo = indNodo + 1; % passar ao índice seguinte do vetor

end;

% verificar se o índice do nodo a libertar é o último índice do vetor

if indNodo > tam

Lista(indNodo) = []; % eliminar o nodo da posição indNodo do vetor

return; % não existe nodo a libertar ou já está no fim do vetor (está libertado)

end;

12

% a lista tem um elemento a menos, mas o vetor da lista mantém o nodo;

% assim, este nodo deve ser libertado do vetor (isto é, removido)

% primeiro: eliminar o nodo da posição indNodo do vetor e atualizar a sua dimensão

Lista(indNodo) = []; % vetor e dimensão são automaticamente atualizados

% segundo: atualizar os campos Prox dos nodos com valores maiores que indNodo

for i = 1:tam

if Lista(i).Prox > indNodo

Lista(i).Prox = Lista(i).Prox - 1;

end;

end;

% terceiro: atualizar o início da lista, InicioLista, se for um índice superior a indNodo

if InicioLista >= indNodo

InicioLista = InicioLista - 1;

end;

13

Verificar se uma lista está vazia

Parâmetros:

Entrada: início da lista (InicioLista)

Saída: 1, se a lista está vazia, ou 0, se a lista não está vazia (vazia)


Se início da lista é 0 Então

Atribuir ao resultado o valor 1 (a lista está vazia)

Senão

Atribuir ao resultado o valor 0 (a lista não está vazia)


function [vazia] = ListaVazia (InicioLista)

if InicioLista == 0

vazia = 1;

else

vazia = 0;

end;

14

Determinar o tamanho (número de elementos) de uma lista

Parâmetros:


Saída: tamanho (quantidade de elementos) da lista (tamLista)


Atribuir ao tamanho inicial da lista o valor 0 (tamLista ← 0)

Atribuir a k o índice do primeiro elemento da lista (k ← InicioLista)

Enquanto o valor de k é índice de um elemento da lista (k ≠ 0) Fazer

Atualizar o tamanho da lista (tamLista) incrementando-lhe 1 unidade

Atribuir a k o índice do elemento seguinte (k ← índice do seu sucessor)


function [tamLista] = TamanhoLista (Lista, InicioLista)

k = InicioLista;

tamLista = 0;

while k ~= 0

tamLista = tamLista + 1;

k = Lista(k).Prox;

end;

15

Algoritmo (recursivo):

Se a lista está vazia (InicioLista = 0) Então

% lista vazia - caso terminal/paragem

tamLista ← 0

Senão

% lista não vazia - caso geral (processo recursivo)

tamLista ← 1 + tamanho da sublista com início no segundo elemento da lista

Função implementada em MatLab (recursiva):

function [tamLista] = TamanhoListaRec (Lista, InicioLista)

if InicioLista == 0

% lista vazia - caso terminal

tamLista = 0;

else

% lista não vazia - caso geral

tamLista = 1 + TamanhoListaRec(Lista, Lista(InicioLista).Prox);

end;

16

Pesquisar um elemento numa lista (não ordenada)

Notas:

- A informação contida no elemento fornecido para consulta basta incidir sobre um dos seus

campos, normalmente o que serve de Chave (valor que caracteriza o elemento).

- Estratégia: efetuar a pesquisa sequencial na lista (e não no vetor, pois os elementos estão

guardados de forma sequencial na lista mas não no vetor), até encontrar um nodo com o

elemento a pesquisar (existe naquee nodo) ou chegar ao fim da lista (não existe).

Parâmetros:

Entrada: elemento a pesquisar (Elem), lista (Lista) e início da lista (InicioLista)

Saída: índice do nodo com Elem, se Elem existe na lista, ou 0, caso contrário (indNodo)


Se a lista está vazia Então

Atribuir ao resultado o valor 0 (o elemento a pesquisar não pertence à lista)

Senão % percorrer sequencialmente a lista até encontrar um nodo com Elem ou chegar ao fim da lista

k ← início da lista (índice do primeiro elemento da lista)

Enquanto k é índice de um nodo da lista (k ≠ 0) e não tem o elemento a pesquisar Fazer

k ← índice do seu nodo sucessor (passar ao próximo elemento da lista)

Atribuir ao resultado o valor de k

17


Nota: CompararElementos é uma operação específica do problema

function [indNodo] = PesquisarElementoLista (Elem, Lista, InicioLista)

if InicioLista == 0 % se a lista está vazia,

indNodo = 0; % então Elem não pertence à lista

return;

end;

indNodo = InicioLista; % a lista não está vazia

while indNodo ~= 0 & CompararElementos(Lista(indNodo).Elemento, Elem) ~= 0

indNodo = Lista(indNodo).Prox;

end; % indNodo = 0 (Elem não está na lista); indNodo ≠ 0 (Elem está na lista)

18



% caso terminal/paragem

Atribuir ao resultado o valor 0, pois aquele elemento não está na lista

Senão

Se o nodo inicial tem o elemento a pesquisar Então

% caso terminal/paragem

Atribuir ao resultado o valor do início da lista (índice do primeiro nodo da lista)

Senão

% caso geral - processo recursivo

Pesquisar aquele elemento da sublista com início no segundo nodo

19


function [indNodo] = PesquisarElementoListaRec (Elem, Lista, InicioLista)


if InicioLista == 0

% Elem não pertence à lista

indNodo = 0;

return;

end;


if CompararElementos(Lista(InicioLista).Elemento, Elem) == 0

% se são iguais, então Elem pertence à lista

indNodo = InicioLista;

else

% procurar na restante lista, a partir do sucessor do nodo inicial atual

indNodo = PesquisarElementoListaRec(Elem, Lista, Lista(InicioLista).Prox);

end;

20

Pesquisar um elemento numa lista (ordenada crescentemente)

Notas:

- Estratégia: efetuar a pesquisa sequencial na lista (não no vetor), até encontrar um nodo com

o elemento a pesquisar (existe naquele nodo), ou um elemento maior que o elemento a

pesquisar ou chegar ao fim da lista (não existe).

Parâmetros:

Entrada: elemento a pesquisar (Elem), lista (Lista) e início da lista (InicioLista)

Saída: índice do nodo com Elem, se Elem existe na lista, ou 0, caso contrário (indNodo)


Se a lista está vazia (InicioLista = 0) Então

indNodo ← 0 (Elem não pertence à lista)

Senão

k ← InicioLista (índice do primeiro elemento da lista)

Enquanto k é índice de um nodo da lista (k ≠ 0) e o elemento no seu nodo ≤ Elem Fazer

k ← índice do seu nodo sucessor (passar ao próximo elemento da lista)

Se k é índice de um nodo da lista (k ≠ 0) e o seu nodo tem o elemento a pesquisar Então

indNodo ← k (Elem pertence à lista e está na posição k)

Senão

indNodo ← 0 (Elem não pertence à lista)

21



function [indNodo] = PesquisarElementoListaOrdenada (Elem, Lista, InicioLista)

if InicioLista == 0

% como a lista está vazia, então Elem não pertence à lista

indNodo = 0;

return;

end;

% a lista não está vazia

indNodo = InicioLista;

while indNodo ~= 0 & CompararElementos(Lista(indNodo).Elemento, Elem) <= 0

indNodo = Lista(indNodo).Prox;

end;

% se indNodo = 0, então o Elem não está na lista

if indNodo ~= 0 & CompararElementos(Lista(indNodo).Elemento, Elem) ~= 0

% o Elemento do nodo indNodo não é igual (é maior) a Elem, logo não existe

indNodo = 0;

end;

22

Listar/mostrar os elementos de uma lista (do início para o fim)

Notas:

- Estratégia: percorrer todos os elementos da lista e mostrar cada um deles individualmente.

Parâmetros:


Saída: mostrar os elementos da lista no monitor


k ← inicio da lista (k é o índice do nodo inicial)

Enquanto k ≠ 0 (k = 0 quanto chegar ao sucessor do nodo do fim da lista)

Mostrar o elemento contido no nodo atual (com índice k)

k ← sucessor do nodo atual (com índice k)


Nota: MostrarElemento é uma operação específica do problema

function [] = ListarListaInicioFim (Lista, InicioLista)

k = InicioLista;

while k ~= 0

MostrarElemento(Lista(k).Elemento);

k = Lista(k).Prox;

end;

23



{ caso terminal/paragem }

Terminar

Senão

{ caso geral }

Mostrar o elemento que se encontra no início da lista atual

Listar sublista com início no sucessor do início da lista atual


function [] = ListarListaInicioFimRec (Lista, InicioLista)

if InicioLista == 0


return;

else


MostrarElemento(Lista(InicioLista).Elemento); % mostrar elemento do início

ListarListaInicioFimRec(Lista, Lista(InicioLista).Prox); % mostrar sublista restante

end;

24

Listar/mostrar os elementos de uma lista (do fim para o início)

Notas:

- Estratégia: ir até ao último elemento e mostrá-lo; voltar ao início da lista, ir até ao

penúltimo elemento e mostrá-lo; e assim sucessivamente até mostrar o primeiro elemento.

Parâmetros:


Saída: mostrar os elementos da lista no monitor


fim ← 0 (fim é o índice do sucessor do último elemento da lista)

Enquanto fim ≠ início da lista

k ← início da lista

ant ← 0 (ant é o índice do antecessor do fim, ou seja, o último elemento)

Enquanto não chega ao fim da lista (k ≠ fim)

Atualizar ant

Avançar para o próximo elemento da lista (k ← sucessor(k))

Mostrar o último elemento (com o índice ant)

Atualizar o fim com o antecessor do último elemento (fim ← ant)

25


Nota: MostrarElemento é uma operação específica do problema

function [] = ListarListaFimInicio (Lista, InicioLista)

fim = 0; % fim é o sucessor do último elemento da lista

while fim ~= InicioLista

k = InicioLista;

ant = 0; % ant é o antecessor do fim (o último)

while k ~= fim

ant = k;

k = Lista(k).Prox;

end;

MostrarElemento(Lista(ant).Elemento); % ant é o última (o que se quer mostrar)

fim = ant; % atualizar fim com o último, que é o ant

end;

26



{ caso terminal/paragem }

Terminar sem mostrar nada

Senão

{ caso geral }

Listar sublista com início no segundo elemento da lista (sucessor do primeiro)

Mostrar o elemento que se encontra no início da lista


function [] = ListarListaFimInicioRec (Lista, InicioLista)

if InicioLista == 0


return;

else


ListarListaFimInicioRec(Lista, Lista(InicioLista).Prox); % mostrar sublista sem início

MostrarElemento(Lista(InicioLista).Elemento); % mostrar elemento do início

end;

27

Consultar um elemento de uma lista

Notas:

- A informação contida no elemento fornecido para consulta basta incidir sobre um dos seus


Parâmetros:

Entrada: elemento a consultar (Elem), lista (Lista) e início da lista (InicioLista)

Saída: mostra os dados do elemento da lista com a mesma Chave de Elem (se existe na lista)


Determinar o índice do nodo que contém o elemento a consultar (indNodo)

Se não existe um nodo com aquele elemento (indNodo ≠ 0) Então

Mostrar uma mensagem indicando que o elemento a consultar não existe na lista

Senão

Alterar a informação do elemento do nodo corrente (o nodo a consultar)

28


Nota: CompararElementos e MostrarElemento são operações específicas do problema

function [] = ConsultarElementoLista (Elem, Lista, InicioLista)

% indNodo é índice do nodo com Elem (se não existe, indNodo = 0)

indNodo = PesquisarElementoLista(Elem, Lista, InicioLista);

if indNodo == 0

% Elem não pertence à lista

disp('Elemento nao pertence a lista!');

else

% Elem pertence à lista

MostrarElemento(Lista(indNodo).Elemento);

end;

29

Inserir um elemento no início de uma lista

Representação gráfica (inserir um nodo com Elem): listas inicial e final

Novo Lista

Elem • Elem1 • Elem2 • Elem3 • Elem4 •

Lista

Elem • Elem1 • Elem2 • Elem3 • Elem4 •

Estruturas de dados:

Nota: um nodo é sempre inserido na nova/última posição do vetor

Representação: inserir um nodo com Elem na lista (listas inicial e final)

InicioLista = 3 (lista inicial)

Lista 1 2 3 4 Novo

Elemento Elem2 Elem4 Elem1 Elem3 Elem

Prox 4 0 1 2 0

Lista 1 2 3 4 5

Elemento Elem2 Elem4 Elem1 Elem3 Elem indNovo = 5

Prox 4 0 1 2 3

InicioLista = 5, após atualização do início da lista (lista final)

30

Parâmetros:

Entrada: elemento a inserir (Elem), lista (Lista) e início da lista (InicioLista)

Saída: lista com mais um nodo (Lista) e início da lista atualizado (InicioLista)


Criar um novo nodo com o elemento a inserir

Aumentar em uma unidade o tamanho do vetor da lista

Acrescentar o novo nodo ao vetor da lista, colocando-o na última posição do vetor

Ligar o novo nodo ao nodo inicial

Atualizar o início da lista, que passa a ser o novo nodo


function [Lista, InicioLista] = InserirInicioLista (Elem, Lista, InicioLista)

Novo = CriarNodo(Elem); % construir um nodo usando Elem

indNovo = TamanhoLista(Lista, InicioLista) + 1; % índice do novo nodo na lista

Lista(indNovo) = Novo; % acrescentar o novo nodo da lista

Lista(indNovo).Prox = InicioLista; % ligar o novo nodo à lista

InicioLista = indNovo; % atualizar o início da lista

31

Inserir um elemento no fim de uma lista

Representação gráfica (inserir o nodo com Elem): listas inicial e final

Lista Ultimo Novo

Elem1 • Elem2 • Elem3 • Elem4 • Elem •

Lista

Elem1 • Elem2 • Elem3 • Elem4 • Elem •


Notas: um nodo é sempre inserido na nova/última posição do vetor

Representação (inserir um nodo com Elem): listas inicial e final

InicioLista = 3

Lista 1 2 3 4 Novo


Prox 4 0 1 2 0

Lista 1 2 3 4 5

Elemento Elem2 Elem4 Elem1 Elem3 Elem pUltimo = 2

Prox 4 5 1 2 0 pNovo = 5

InicioLista = 3, pois o início da lista só sofre alteração se a lista inicial for vazia (lista final)

32

Parâmetros:






O novo nodo passa a ser o único da lista, logo o nodo inicial

Senão

Posicionar-se no último elemento da lista (indUltimo)

Aumentar em 1 unidade o tamanho do vetor da lista


Ligar o último nodo da lista ao novo nodo

33


function [Lista, InicioLista] = InserirFimLista (Elem, Lista, InicioLista)


if InicioLista == 0 % lista vazia, logo Elem é o primeiro e único da lista

Lista(1) = Novo;

InicioLista = 1;

return;

end;

% lista não vazia - posicionar-se no último nodo da lista (indUltimo)

indUltimo = InicioLista;

while Lista(indUltimo).Prox ~= 0

indUltimo = Lista(indUltimo).Prox;

end;

% inserir o nodo com o Elem como sucessor do último nodo da lista

indNovo = TamanhoLista(Lista, InicioLista) + 1; % posição do novo nodo na lista

Lista(indUltimo) = Novo;

Lista(indUltimo).Prox = indNovo;

34


Como a função recursiva necessita do tamanho da lista (operação básica), antes de efetuar a

inserção do elemento, usa-se uma função iterativa para realizar estas duas ações:

1ª) Determinar o tamanho da lista, usando uma função básica (recursiva ou não);

2ª) Inserir o novo elemento no fim da lista (usando uma função recursiva local).


function [Lista, InicioLista] = InserirFimListaRec (Elem, Lista, InicioLista)

tamL = TamanhoListaRec(Lista, InicioLista); % 1ª ação

[Lista, InicioLista] = InserirFimListaR (Elem, Lista, InicioLista, tamL); % 2ª ação

35

function [Lista, InicioLista] = InserirFimListaR (Elem, Lista, InicioLista, tamL)

if InicioLista == 0 % lista original vazia, então inserir Elem


Lista(1) = Novo;

InicioLista = 1; % o novo nodo ficou no início, logo InicioLista é alterado (só aqui)

return;

end;

if Lista(InicioLista).Prox == 0 % é o último da lista, então inserir Elem


Lista(tamL + 1) = Novo;

Lista(InicioLista).Prox = tam+1;

return;

end;

% como o início da lista (InicioLista) não sofre alteração, não se pode indicar como parâmetro de

saída, pelo que deve usar-se outro identificador (InicioL)

[Lista, InicioL] = InserirFimListaR(Elem, Lista, Lista(InicioLista).Prox, tamL);

36

Inserir um elemento numa lista ordenada por ordem crescente

Representação gráfica: inserir o nodo com Elem entre os nodos com Elem3 e Elem4

Lista ant

Inicial Elem1 • Elem2 • Elem3 • X Elem4 •

2 1

Novo Elem •

Lista

Final Elem1 • Elem2 • Elem3 • Elem • Elem4 •

Estrutura de dados:

Notas: um nodo é sempre inserido na nova/última posição do vetor

Representação: inserir o nodo Elem entre os nodos Elem3 e Elem4 (listas inicial e final)

InicioLista = 3

Lista 1 2 3 4 Novo


Prox 4 0 1 2 0

Lista 1 2 3 4 5

Elemento Elem2 Elem4 Elem1 Elem3 Elem ant = 4

Prox 4 0 1 5 2 pNovo = 5

37

Parâmetros:






O novo nodo passa a ser o único da lista, logo o nodo inicial

Atualizar o início da lista com o índice 1 (é o único)

Senão

Procurar local de inserção, posicionando-se no nodo anterior ao local de inserção (ant)

Aumentar em 1 unidade o tamanho do vetor da lista


Se o local de inserção é o início da lista (ant = 0) Então

Ligar o novo nodo ao nodo inicial atual (o sucessor do novo nodo é o atual inicial)

Atualizar o início da lista com o novo nodo

Senão

Se o local de inserção é no fim da lista Então

Ligar o último nodo (ant = índice do último nodo) ao novo nodo

Senão { inserir o novo nodo entre 2 nodos e como sucessor do nodo ant }

Ligar o novo nodo ao sucessor do ant (o sucessor de novo é o sucessor de ant)

Ligar o nodo ant ao novo nodo (o sucessor de ant é o novo)

38


function [Lista, InicioLista] = InserirListaOrdenadaCrescente (Elem, Lista, InicioLista)


if InicioLista == 0 % se lista vazia, então Elem é o primeiro

Lista(1) = Novo;

InicioLista = 1;

return;

end;

% procurar local de inserção, procurando o nodo anterior ao local de inserção (ant)

ant = 0;

atual = InicioLista;

while atual ~= 0 & CompararElementos(Lista(atual).Elemento, Elem) < 0

ant = atual;

atual = Lista(atual).Prox;

end;

39

indNovo = TamanhoLista(Lista, InicioLista) + 1;

Lista(indNovo) = Novo;

if ant == 0 % inserir Novo no início da lista

Lista(indNovo).Prox = InicioLista;

InicioLista = indNovo;

return;

end;

if atual == 0 % inserir Novo no fim e ant = posição do último nodo

Lista(ant).Prox = indNovo;

return;

end;

% inserir entre 2 nodos

Lista(indNovo).Prox = Lista(ant).Prox;

Lista(ant).Prox = indNovo;

40

Remover um elemento de uma lista

Representação gráfica: todos os casos possíveis de remoção de um elemento

Remoção do primeiro nodo (Elem1): listas inicial e final

Lista

Elem1 • Elem2 • Elem3 • Elem4 • Elem5 •

atual Lista


Remoção de um nodo entre dois nodos (Elem3): listas inicial e final

Lista


Lista ant atual


Remoção do último nodo (Elem5): listas inicial e final

Lista


Lista ant atual


41


Notas:

- Depois de removido um elemento de uma lista, é necessário libertar o nodo que lhe está

associado no vetor associado à lista.

- A informação contida no elemento fornecido para consulta basta incidir sobre um dos

seus campos, normalmente o que serve de Chave (valor que caracteriza o elemento).

Representação: todos os casos possíveis de remoção de um elemento


Remoção do primeiro nodo (Elem1): listas inicial e final

Lista 1 2 3 4 5


Prox 4 0 1 5 2

Lista 1 2 3 4 5


Prox 4 0 -1 5 2

InicioLista = Lista(3).Prox = 1 (lista final) — sofre alteração, pois o nodo removido é o

inicial

42

Remoção de um nodo entre dois nodos (Elem3): listas inicial e final

Lista 1 2 3 4 5


Prox 4 0 1 5 2

Lista 1 2 3 4 5


Prox 5 0 1 -1 2

InicioLista = 3 (lista final) — sem alteração, pois o nodo removido não é o primeiro

Remoção do último nodo (Elem5): listas inicial e final

Lista 1 2 3 4 5


Prox 4 0 1 5 2

Lista 1 2 3 4 5


Prox 4 -1 1 5 0

InicioLista = 3 (lista final) — sem alteração, pois o nodo removido não é o primeiro

43

Parâmetros:

Entrada: elemento a remover (Elem), lista (Lista) e início da lista (InicioLista)

Saída: lista com menos um nodo (Lista) e início da lista atualizado (InicioLista)


Determinar o índice do nodo que contém o elemento a alterar (indNodo)

Se existe um nodo com aquele elemento (indNodo ≠ 0) Então

Se a lista tem apenas um elemento Então

Lista fica vazia (início da lista = 0)

Senão

Procurar o elemento que está antes do elemento a remover (ant)

Se o elemento a remover está no nodo da primeira posição Então

Atualizar o início da lista (passa a ser o seu sucessor)

Senão { o elemento a remover está num nodo entre dois nodos ou no fim da lista }

Ligar o nodo antecessor (ant) ao sucessor do nodo com o elemento removido

Libertar o nodo com o elemento removido da lista

44



function [Lista, InicioLista] = RemoverElementoLista (Elem, Lista, InicioLista)


if indNodo == 0

return; % Elem não está na lista, logo sair (a lista não sofre alteração)

end;

% o elemento Elem está na lista

if Lista(InicioLista).Prox == 0 % se a lista tem apenas um elemento, então fica vazia

% libertar o nodo que contém o elemento removido, que está na posição 1

Lista(InicioLista).Prox = -1; % isolar e marcar o nodo a libertar

InicioLista = 0;

return;

end;

45

% a lista tem mais do que um elemento

% procurar o elemento que está antes do elemento a remover (ant)

ant = 0; % ant é o índice do nodo cujo sucessor tem o índice atual; no início é 0

atual = InicioLista; % atual é o índice do nodo corrente

while atual ~= indNodo

ant = atual;

atual = Lista(atual).Prox;

end;

if ant == 0 % o Elem está no nodo da primeira posição

atual = InicioLista; % atual contém o índice do nodo a remover

InicioLista = Lista(InicioLista).Prox; % atualizar o início da lista

else % o Elem está num nodo entre dois nodos ou no fim da lista

% ligar o nodo que está antes de Elem (ant) ao sucessor deste (atual)

Lista(ant).Prox = Lista(atual).Prox;

end;

Lista(atual).Prox = -1; % marcar o nodo a libertar

% libertar o nodo com o elemento removido

[Lista, InicioLista] = LibertarNodoLista(Lista, InicioLista);

46


Como a libertação do nodo que contém o elemento removido deve ser realizada e feita

depois do elemento ser retirado da lista, usa-se uma função não recursiva para realizar estas

duas ações:

1ª) Retirar o elemento fornecido da lista (usando uma função recursiva local);

2ª) Libertar o nodo que contém o elemento removido.


function [Lista, InicioLista] = RemoverElementoListaRec (Elem, Lista, InicioLista)

[Lista, InicioLista] = RemoverElementoListaR(Elem, Lista, InicioLista); % 1ª ação

[Lista, InicioLista] = LibertarNodoLista(Lista, InicioLista); % 2ª ação

47

function [Lista, InicioLista] = RemoverElementoListaR (Elem, Lista, InicioLista)

if InicioLista == 0 % a lista está vazia

return; % logo sair sem efetuar qualquer alteração

end;

if CompararElementos(Lista(InicioLista).Elemento, Elem) == 0

atual = InicioLista; % Elem está na primeira posição da lista

InicioLista = Lista(InicioLista).Prox; % só aqui é que InicioLista sofre alteração

Lista(atual).Prox = -1; % isolar e marcar o nodo a libertar

return; % neste caso, o nodo está automaticamente libertado

end;

seg = Lista(InicioLista).Prox; % se o sucessor do atual nodo contem Elem (é o nodo a remover)

if Lista(InicioLista).Prox ~= 0 & CompararElementos(Lista(seg).Elemento, Elem) == 0

atual = Lista(InicioLista).Prox;

Lista(InicioLista).Prox = Lista(atual).Prox; % ant = InicioLista

Lista(atual).Prox = -1; % isolar e marcar o nodo a libertar

else

% como o início da lista (InicioLista) não sofre alteração, não se pode indicar como parâmetro de

% saída; usar InicioL para a chamada à função estar correta em número de parâmetros

[Lista, InicioL] = RemoverElementoListaR(Elem, Lista, Lista(InicioLista).Prox);

end;

48

Determinar o maior elemento de uma lista

Notas:

- Estratégia: assumir no início que o maior elemento da lista é o primeiro elemento; depois,

percorrer toda a lista e atualizar o maior elemento sempre que apareça um elemento maior

do que ele.

Parâmetros:


Saída: o maior elemento da lista (maiorElem)


Maior elemento ← primeiro elemento da lista

k ← índice do primeiro elemento da lista

Enquanto o valor de k é índice de um elemento da lista (k ≠ 0) Fazer

Maior elemento ← máximo (Maior elemento, elemento da posição k da lista)

k ← índice do sucessor do elemento da posição k da lista

49


function [maiorElem] = MaiorElementoLista (Lista, InicioLista)

maiorElem = Lista(InicioLista).Elemento;

k = Lista(InicioLista).Prox;

while k ~= 0

if maiorElem > Lista(k).Elemento

maiorElem = Lista(k).Elemento;

end;

k = Lista(k).Prox;

end;

50


Se a lista só tem um elemento (inicio da lista não tem sucessor) Então

% a lista só com um elemento - caso terminal/paragem

Maior elemento ← primeiro elemento da lista

Senão

% a lista tem mais do que um elemento - caso geral (processo recursivo)

maior ← maior elemento da sublista com início no segundo elemento da lista

Maior elemento ← máximo (maior, primeiro elemento da lista)


function [maiorElem] = MaiorElementoListaRec (Lista, InicioLista)

if Lista(InicioLista).Prox == 0


else

maior = MaiorElementoListaRec(Lista, Lista(InicioLista).Prox);

if maior > Lista(InicioLista).Elemento

maiorElem = maior;

else


end;

end;

51

Alterar/atualizar um elemento de uma lista

Notas:

- A informação contida no elemento fornecido para atualizar basta incidir sobre um dos seus


Parâmetros:

Entrada: elemento a consultar (Elem), lista (Lista) e início da lista (InicioLista)

Saída: lista atualizada com a nova informação sobre o Elem (Lista)


Determinar o índice do nodo que contém o elemento a alterar (indNodo)

Se existe um nodo com aquele elemento (indNodo ≠ 0) Então

Alterar a informação do elemento do nodo corrente (o nodo a alterar)


Nota: AlterarElemento é uma operação específica do problema

function [Lista] = AlterarElementoLista (Elem, Lista, InicioLista)


if indNodo ~= 0

Lista(indNodo).Elemento = AlterarElemento(Lista(indNodo).Elemento);

end;

52

Trocar dois elementos de uma lista

Notas:

- A troca de dois elementos de uma lista pode ser feita segundo duas estratégias:

a) trocar apenas o conteúdo do campo Elemento dos nodos (e não os nodos);

b) trocar os próprios nodos.

- A informação contida nos elementos fornecidos para troca basta incidir sobre um dos seus

campos, normalmente o que serve de Chave (valor que caracteriza cada elemento).

Trocar os elementos contidos em dois nodos:

Representação gráfica: troca de Elem2 com Elem4 (lista inicial e final)

Lista ind1 ind2


Lista


Operações realizadas:

1) aux = ind1→Elemento

2) ind1→Elemento = ind2→Elemento

3) ind2→Elemento = aux

53


Representação: troca de Elem2 com Elem4 (lista inicial e final)


ind1 = 3; % índice do nodo que contém Elem2


Lista 1 2 3 4 5


Prox 4 0 1 5 2

Lista 1 2 3 4 5


Prox 4 0 1 5 2

InicioLista = 1 (lista final) — não sofre alteração, pois apenas se trocam os elementos,

sendo que agora os nodo inicial contém Elem4 e não Elem2


1) aux = Lista(ind1).Elemento

2) Lista(ind1). Elemento = Lista(ind2). Elemento

3) Lista(ind2). Elemento = aux

54

Parâmetros:

Entrada: elementos a trocar (Elem1 e Elem2), lista (Lista) e início da lista (InicioLista)

Saída: lista com os nodos trocados (Lista) e início da lista atualizado (InicioLista)


Determinar o índice do nodo com Elem1 (indNodo1)

Determinar o índice do nodo com Elem2 (indNodo2)

Se ambos os elementos existem na lista Então

Trocar os elementos dos nodos cujos índices são indNodo1 e indNodo2


function [Lista, InicioLista] = TrocarElementosSimples (Elem1, Elem2, Lista, InicioLista)

% pesquisar os índices dos nodos com as mesmas Chaves de Elem1 e Elem2

ind1 = PesquisarElementoLista(Elem1, Lista, InicioLista);

ind2 = PesquisarElementoLista(Elem2, Lista, InicioLista);

if ind1 ~= 0 & ind2 ~= 0

% Elem1 e Elem2 pertencem à lista

aux = Lista(ind1).Elemento;

Lista(ind1).Elemento = Lista(ind2).Elemento;

Lista(ind2).Elemento = aux;

end;

55

Trocar dois nodos:


Elementos consecutivos: troca dos nodos com Elem3 e Elem4

Inicial: 3 1

Lista ant1 ind1 ind2

Elem1 • Elem2 • 3 Elem3 • 1 Elem4 • 2 Elem5 • Elem6 •

2

Final:

Lista



1) ind1→Prox = ind2→Prox

2) ind2→Prox = ind1

3) ant1→Prox = ind2

56

Elementos não consecutivos: troca dos nodos com Elem2 e Elem5

Inicial:

3 1

Lista ind1 seg1 ant2 ind2

Elem1 • 3 Elem2 • 1 Elem3 • Elem4 • 4 Elem5 • 2 Elem6 •

ant1 2

4

Final:

Lista



1) ind1→Prox = ind2→Prox

2) ind2→Prox = seg1



57


Representação: todos os casos possíveis de troca de dois nodos


Elementos consecutivos (nodos com Elem3 e Elem4): listas inicial e final



ant1 = 1; % índice do nodo anterior ao nodo que contém Elem3

Lista 1 2 3 4 5 6


Prox 4 5 1 6 0 2

Lista 1 2 3 4 5 6


Prox 6 5 1 2 0 4

InicioLista = 3 (lista final) — sem alteração, pois um dos nodos trocados não é o primeiro


1) Lista(ind1).Prox = Lista(ind2).Prox

2) Lista(ind2).Prox = ind1

3) Lista(ant1).Prox = ind2

58

Elementos não consecutivos (nodos com Elem2 e Elem5): listas inicial e final





seg1 = 4; % índice do nodo seguinte ao nodo que contém Elem2

Lista 1 2 3 4 5 6


Prox 4 5 1 6 0 2

Lista 1 2 3 4 5 6


Prox 5 4 2 6 0 1

InicioLista = 3 (lista final) — sem alteração, pois um dos nodos trocados não é o primeiro


1) Lista(ind1).Prox = Lista(ind2).Prox

2) Lista(ind2).Prox = seg1



59

Parâmetros:

Entrada: elementos a trocar (Elem1 e Elem2), lista (Lista) e início da lista (InicioLista)

Saída: lista com os nodos trocados (Lista) e início da lista atualizado (InicioLista)


function [Lista, InicioLista] = TrocarElementosLista (Elem1, Elem2, Lista, InicioLista)

ind1 = PesquisarElementoLista(Elem1, Lista, InicioLista); % índice do nodo com Elem1

ind2 = PesquisarElementoLista(Elem2, Lista, InicioLista); % índice do nodo com Elem2

if ind1 == 0 | ind2 == 0

return; % Elem1 e/ou Elem2 não pertencem à lista

end;

k = InicioLista; % os dois pertencem à lista; ind1 deve estar associado ao elemento que está antes

while k ~= ind1 & k ~= ind2

k = Lista(k).Prox;

end;

if k == ind2 % se o Elem2 está antes de Elem1, então trocar ind1 com ind2

aux = ind1;

ind1 = ind2;

ind2 = aux;

end;

60

if Lista(ind1).Prox == ind2 % os dois elementos são consecutivos

if ind1 == InicioLista % o nodo em ind1 é o primeiro da lista

Lista(ind1).Prox = Lista(ind2).Prox;

Lista(ind2).Prox = ind1;

InicioLista = ind2;

else % o nodo em ind1 não é o primeiro da lista

ant1 = InicioLista; % procurar o nodo anterior ao que está em ind1

while Lista(ant1).Prox ~= ind1

ant1 = Lista(ant1).Prox;

end;


Lista(ind2).Prox = ind1;

Lista(ant1).Prox = ind2;

end;

return;

end;

61

% os dois elementos não são consecutivos

if ind1 == InicioLista

% o nodo em ind1 é o primeiro da lista

% procurar o nodo anterior ao que está em ind2

ant2 = Lista(ind1).Prox;



end;

% determinar o índice do nodo sucessor ao que está em ind1 (seg1)

seg1 = Lista(ind1).Prox;


Lista(ind2).Prox = seg1;


InicioLista = ind2;

else

62

% o nodo em ind1 não é o primeiro da lista

% procurar os índices dos nodos anteriores (ant1 e ant2) aos que estão em ind1 e ind2

ant1 = InicioLista;



end;

ant2 = Lista(ind1).Prox; % são nodos não consecutivos



end;

% determinar o índice do nodo sucessor ao que está em ind1 (seg1)

seg1 = Lista(ind1).Prox;


Lista(ind2).Prox = seg1;



end;

63

Exemplo 1: Lista em que o elemento de cada nodo é um inteiro.

Estrutura de dados:

Lista(k) = struct { Elemento, Prox }, k = 1, ...

Lista é um tipo de dados estruturado (neste caso, do tipo registo);

Elemento é um tipo não estruturado básico (neste caso, do tipo inteiro).

Operações específicas deste problema a implementar (funções em MatLab):

function [Elem] = CriarElemento ()

Elem = input('Inserir um inteiro: ');

function [] = MostrarElemento(Elem)

disp(Elem);

function [Elem] = AlterarElemento (Elem)

disp(Elem);

sim = input('Pretende alterar este valor (1 = sim; 0 = nao) ? ');

if sim == 1

Elem = input('Inserir um inteiro: ');

end;

64

% comparar dois elementos considerando para comparação os valores dos elementos

function [comp] = CompararElementos (Elem1, Elem2)

if Elem1 > Elem2

comp = 1;

elseif Elem1 == Elem2

comp = 0;

else

comp = -1;

end;

65

Exemplo 2: Lista em que o elemento de cada nodo contém o número, o nome e a nota

obtida na disciplina de AED por um estudante.

Estrutura de dados:

Lista(k) = struct { Elemento, Prox }, k = 1, ...

Elemento = struct { Numero, Nome, NotaFinal },

Lista é um tipo estruturado de dados (neste caso, do tipo registo).

Elemento é um tipo estruturado de dados (neste caso, do tipo registo).

Operações específicas deste problema a implementar (funções em MatLab):

function [Elem] = CriarElemento ()

Elem.Numero = input('Insira o numero de estudante: ');

Elem.Nome = input('Insira o nome do estudante: ', 's');

Elem.NotaFinal = input('Insira nota final do estudante: ');

function [] = MostrarElemento(Elem)

disp(Elem.Numero);

disp(Elem.Nome);

disp(Elem.NotaFinal);

66

function [Elem] = AlterarElemento (Elem)

disp(Elem.Numero);

sim = input('Pretende alterar o numero (1 = sim; 0 = nao) ? ');

if sim == 1

Elem. Numero = input('Inserir um inteiro: ');

end;

disp(Elem.Nome);

sim = input('Pretende alterar o nome (1 = sim; 0 = nao) ? ');

if sim == 1

Elem.Nome = input('Inserir um nome: ', 's');

end;

disp(Elem.NotaFinal);

sim = input('Pretende alterar a nota final (1 = sim; 0 = nao) ? ');

if sim == 1

Elem.NotaFinal = input('Inserir a nota final: ');

end;

67

% comparar dois elementos considerando para comparação apenas o campo Numero

function [comp] = CompararElementos (Elem1, Elem2)

if Elem1.Numero > Elem2.Numero

comp = 1;

elseif Elem1.Numero == Elem2.Numero

comp = 0;

else

comp = -1;

end;

Documents

Estrutura de dados - di.ubi.ptcbarrico/Disciplinas/AlgoritmosEstruturas... · Estrutura de dados: Notas: - depois de um elemento ser eliminado da lista, é necessário libertar o