Estruturas de Dados - Tipo Abstrato de Dados - Listas - Parte 1 (Dibio)

Prévia do material em texto

dibio@unb.br
Roteiro
 Dados Simples e Compostos
 Tipo Abstrato de Dados (TAD) 
 Ex: Ponto em R2
 Ex: Números racionais
 Listas (Conceituação)
 Listas Encadeadas
 O TAD de uma Lista Encadeada
 Ex: Implementação na linguagem C
dibio@unb.br
Dados Simples
Referência a um elemento, com domínio e 
conjunto de operações pré­definido
●  Dados numéricos (e.g. inteiro, real)
●  Dados simbólicos (e.g. caracteres)
dibio@unb.br
Dados Compostos 
Referência a um conjunto de elementos com domínio 
e conjunto de operações a ser estabelecido
● Homogêneos (e.g. vetor, matriz, cadeia de
caracteres (“string”))
● Não necessariamente homogêneo (e.g. Estrutura)
● Conjuntos, formas de inclusão, acesso,
organização, algoritmos eficientes para uso em
conjuntos e organizações diversas. (e.g.
Sequências, prioridade, hierárquicos, fluxos)
dibio@unb.br
Tipo Abstrato de Dados (TAD)
● Modelo Matemático
● Implementa em um conjunto de elementos:
–  Operações específicas
–  Semântica Especial
– A implementação usa as estruturas básicas de uma 
linguagem de programação formando uma nova 
estrutura
●  Abstrai detalhes após implementação, ou seja, 
realiza um encapsulamento do modelo matemático
dibio@unb.br
Exemplos de Modelos 
matemáticos que poderiam ser 
implementados como TADs
● ponto, segmento de reta, círculo, números
racionais, números complexos
dibio@unb.br
Ex: Construindo um TAD para 
ponto (Celes, W.; Cerqueira, R. & Rangel, J.L.   
Introdução a Estruturas de Dados, Campus, RJ, 2004.)
dibio@unb.br
dibio@unb.br
Ex: cont. em um arquivo ponto.c
dibio@unb.br
Ex: cont. em um arquivo ponto.c
dibio@unb.br
Exemplo: números racionais
dibio@unb.br
Exemplo em C
dibio@unb.br
Exemplo em C
dibio@unb.br
Exemplo em C
dibio@unb.br
Trabalhando com Conjuntos
dibio@unb.br
Listas
● Uma lista é uma estrutura flexível que pode 
aumentar ou diminuir seu tamanho sob demanda
● Elementos podem ser acessados, inseridos, 
apagados, em qualquer posição da lista
● Listas podem ser concatenadas ou repartidas em 
sub­listas
dibio@unb.br
Listas
● Matematicamente uma lista é uma sequência de 
0 ou mais elementos de um tipo específico
● O número n de elementos da lista é o seu tamanho
● n sendo igual a 0 (zero) temos uma lista vazia
● Uma posição após o último elemento da lista é 
referido como o fim da lista
dibio@unb.br
Como formar um TAD de Listas?
● Definições de uma lista?
● Qual o conjunto básico de operações de uma lista?
– Inserir (x, p, L): inserir x na posição p da lista L 
– Deletar (p, L): deletar o elemento na posição p da lista L
– ListaVazia(L): criar lista vazia
● outras operações?
– Localizar (x, L)
– Posterior (p, L), Anterior(p, L)
– Primeiro (L)
– ImprimirLista (L)
dibio@unb.br
Lista Encadeada, ou Ligada
dibio@unb.br
Lista Encadeada, ou Ligada
dibio@unb.br
Representação de Listas Encadedas
dibio@unb.br
Listas com Cabeça, e sem Cabeça
● Com Cabeça: o conteúdo da primeira célula é 
irrelevante, serve apenas para marcar o início da 
lista. A primeira célula é a cabeça da lista.
● Sem Cabeça: o conteúdo da primeira célula é tão 
relevante quanto das demais (* Usada aqui)
dibio@unb.br
Criando Listas Vazias
dibio@unb.br
Inserindo elementos em uma lista
● No começo da Lista
dibio@unb.br
Inserindo elementos em uma lista
dibio@unb.br
Inserindo elementos em lista
dibio@unb.br
Impressão de listas 
dibio@unb.br
Verificar se lista está vazia
dibio@unb.br
Busca de elemento em listas
dibio@unb.br
Removendo elementos de listas 
dibio@unb.br
Removendo elementos de listas
dibio@unb.br
Liberando listas encadeadas
dibio@unb.br
Comparação de listas encadeadas
dibio@unb.br
Exemplos: listas de inteiros
dibio@unb.br
Exemplos: listas de inteiros
dibio@unb.br
Implementação Recursiva de Listas
dibio@unb.br
Implementação Recursiva de Listas
dibio@unb.br
Implementação Recursiva de Listas
dibio@unb.br
Implementação Recursiva de Listas
dibio@unb.br
Implementação Recursiva de Listas
dibio@unb.br
Exercícios
● Escreva uma função que receba uma lista 
encadeada e devolva o endereço de um nó que 
esteja o mais próximo possível do meio da lista. 
Faça isso sem contar explicitamente o número de 
nós da lista. 
● Escreva uma função que encontre uma célula de 
conteúdo mínimo. Faça duas versões: uma 
iterativa e uma recursiva. 
● Escreva uma função que copie um vetor para uma 
lista encadeada. Faça duas versões: uma iterativa e 
uma recursiva. 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40