Slide aula 9

Prévia do material em texto

2019.2
ESTUTURAS DE DADOS
CCT0637
Aula 9
PROFESSOR: EDIBERTO MARIANO
1
2019.2
CONTEÚDOS
2
Lista
Listas Encadeadas (parte II)
Listas Duplamente Encadeadas
Listas Circulares Simples
2019.2
Listas Encadeadas
3
Duplamente encadeada
podem ser usadas quando várias operações de inserção e remoção de 
elementos são necessárias.
2019.2
Listas Encadeadas
4
Duplamente encadeada
Vantagem da utilização de lista duplamente encadeada sobre a lista
simplesmente encadeada
Facilita a realização de operações (inclusão e remoção), diminui a
quantidade de variáveis auxiliares necessárias.
Estrutura de dados usada na implementação do método Round Robin do sistema 
operacional UNIX 
Todos os elementos dispersos na memória RAM, mas ligados através da
definição, dentro da estrutura de cada um destes elementos, de um campo que
guarda o endereço de cada elemento subsequente da lista, e de outro campo
que guarda o endereço de cada elemento anterior na lista.
Na lista simplesmente encadeada maior facilidade para 
navegação, que na lista duplamente encadeada.
2019.2
Listas Encadeadas
5
Duplamente encadeada
Vantagem da utilização de lista duplamente encadeada sobre a lista
simplesmente encadeada
A principal vantagem É o ganho em
desempenho em termos de velocidade nas
inclusões e remoções de elementos.
Em uma lista contígua é
necessário mover todos os
elementos da lista para uma
nova lista para realizar essas
operações.
Esta estrutura é mais adequada para listas
com centenas ou milhares de nós.
Em uma inserção ou remoção em uma lista
contígua representará uma perda notável no
desempenho do processamento.
2019.2
Listas Encadeadas
6
Duplamente encadeada
protótipo de um elemento da lista
typedef struct dl_elementoLista {
char *dado;
struct dl_elementoLista *anterior;
struct dl_elementoLista *seguinte;
}dl_elemento;
protótipo - controle da lista
typedef struct dl_ListaDetetada {
dl_elemento *início;
dl_elemento *fim;
int tamanho;
}dl_Lista; 
2019.2
Listas Encadeadas
7
Duplamente encadeada Rotinas de Manipulação 
Inserção:
As inserções podem ser no começo, no meio ou no fim da lista.
Sendo p um ponteiro que aponta para um dos nodos da lista, pode-se afirmar que: 
As operações removem o nodo apontado pelo ponteiro p.
2019.2
Listas Encadeadas
8
Duplamente encadeada Rotinas de Inserção 
Sintaxe
nodupla *inserir(nodupla *p, int
codigo, string autor) {
nodupla *novo;
novo = new nodupla;
novo->codigo = codigo;
novo->autor = autor;
novo->dlink = p;
novo->elink = NULL;
if (p != NULL)
p->elink = novo;
p = novo;
return p;
}
2019.2
Listas Encadeadas
9
Duplamente encadeada Rotinas de Manipulação 
Remoção:
As operações removem o nodo apontado pelo ponteiro p
2019.2
Listas Encadeadas
10
Duplamente encadeada Rotinas de Exclusão 
Sintaxe
Lista2* lst2_retira (Lista2* l, char 
v[]){
Lista2* p; 
p= lst2_busca(l,v); 
if (p==NULL){ 
printf("Cidade nao encontada.\n"); 
return l; 
} 
else printf("Cidade retirada.\n"); 
if (l==p) 
l=p->prox; 
else p->ant->prox=p->prox; 
if (p->prox!=NULL) 
p->prox->ant=p->ant; 
free(p); 
return l; 
} 
2019.2
Listas Encadeadas
11
Duplamente encadeada Rotinas de Impressão 
Sintaxe
struct nodupla {
int dado;
struct nodupla *dlink, //aponta para o nó à direita
*elinlk; //aponta para o nó à esquerda
};
e uma lista duplamente encadeada, cujo primeiro nó é apontado 
por p, sendo nodupla *p;
void imprimir(nodupla *p)
{ while (p != NULL)
{
cout << " " << p->dado;
p = p->dlink;
}
}
2019.2
Listas Encadeadas
12
Duplamente encadeada Exemplo
2019.2
Listas Encadeadas
13
Duplamente encadeada Exemplo
2019.2
Listas Encadeadas
14
Duplamente encadeada Exemplo
2019.2
Listas Encadeadas
15
Circulares simples
O algoritmo de busca em uma lista encadeada pode ser melhorado se modificarmos a lista de
modo que ela passe a ser circular
Ao término do algoritmo a chave é sempre
encontrada, e pode-se descobrir se ela pertencia
ou não a lista pelo ponteiro que foi dado como
resposta. Caso o ponteiro termine apontando
para o nó cabeça, podemos afirmar que o
elemento não se encontra na lista.
2019.2
Listas Encadeadas
16
Circulares simples
protótipo de um elemento da lista
typedef struct ElementoLista {
char dado;
struct ElementoLista seguinte;
}Elemento; 
O ponteiro seguinte será obrigatoriamente do
mesmo tipo que o elemento, caso contrário
ele não poderá apontar para o elemento.
typedef struct ListaDetectada {
Elemento início;
Elemento fim;
int tamanho;
}Lista; 
protótipo controlar a lista
Para controlar a lista, é melhor salvar certos elementos:
Para tanto, outra estrutura vai ser utilizada (isso não é
imprescindível, as variáveis podem ser utilizadas).
O primeiro elemento, o último elemento, o número de 
elementos.
2019.2
Listas Encadeadas
17
Circulares simples Operações
Inicialização
Protótipo da função: void inicialização (Lista lista); 
Função:
void inicialização (Lista lista){
lista -> início = NULL;
lista -> fim = NULL;
tamanho = 0;
} 
2019.2
Listas Encadeadas
18
Circulares simples Operações
Inserção de um elemento na lista
Declaração de elementos a serem inseridos
Alocação da memória para o novo elemento
Preenchimento do conteúdo do campo de dados
A atualização dos ponteiros com alvo no primeiro e no último elemento, 
se necessário.
Caso especial: em uma lista com um único elemento, o primeiro também 
é o último.
Atualização do tamanho da fila
2019.2
Listas Encadeadas
19
Circulares simples Operações
Inserção em uma lista vazia
Protótipo da função: int ins_lista_circ_vazia(Lista lista, char dado); 
A função volta em -1 com falha, se não ela retorna 0.
Passos :
Alocação da memória para o novo elemento
Os ponteiros início e de fim apontarão para o novo elemento
Preenchimento do campo de dados do novo elemento
O ponteiro seguinte do novo elemento apontará para ele mesmo (é a
etapa que torna a lista circular)
O tamanho é atualizado
2019.2
Listas Encadeadas
20
Circulares simples Operações
Inserção em uma lista vazia
Função:
2019.2
Listas Encadeadas
21
Circulares simples Operações
Inserção em uma lista não vazia
Protótipo da função: int ins_lista_circ(Lista lista, Elementoemandamento, char dado); 
A função exibe-se novamente -1 em caso de falha, se não ela retorna 0.
A inserção será efetuada no final da lista.
Alocação da memória para o novo elemento
Preenchimento do campo de dados do novo elemento
O ponteiro seguinte do novo elemento aponta para o endereço do primeiro elemento 
(manter a lista circular)
O ponteiro início não muda
O ponteiro fim aponta para o novo elemento
O tamanho é incrementado com uma unidade
2019.2
Listas Encadeadas
22
Circulares simples Operações
Inserção em uma lista não vaziaFunção:
2019.2
Listas Lineares
23
Listas Duplamente Encadeadas e Circulares simples - Exercícios
01 – Considere uma lista duplamente encadeada de livros em que cada nó ou nodo é do tipo 
nodupla definido a seguir
struct nodupla {
int codigo;
string autor;
struct nodupla *dlink; // aponta para o nó à direita
struct nodupla *elink; // aponta para o nó à esquerda
};
sendo nodupla *p; //ponteiro para o início da lista, que pode estar vazia
Escreva uma função em C++ para inserir um novo livro no início da lista. Para isso, 
considere o seguinte protótipo : 
nodupla *inserir(nodupla *p, int codigo, string autor); 
2019.2
Listas Lineares
24
Listas Duplamente Encadeadas e Circulares simples - Exercícios
02 – Ao criarmos uma rotina para inserir um dado em uma LISTA de dados duplamente 
encadeada e circular, nos deparamos com as seguintes cuidados:
[ ] Só poderei inserir no começo ou no fim, mas não no meio.
[ ] Posso inserir no começo, no meio ou no fim.
[ ] Só poderei inserir no final da lista e nunca no começo ou no meio.
[ ] Só poderei inserir no final da lista e no começo somente se ela estiver vazia.
[ ] Só poderei inserir no final da lista e no começosomente se ela estiver cheia.
03 - Nas estruturas dinâmicas a alocação de memória ocorre em tempo de execução, assim 
pode-se controlar durante a execução do programa o tamanho da estrutura. Entretanto, é 
imprescindível o uso de ponteiros nestas estruturas, explique o porquê.
2019.2
Listas Lineares
25
Listas Duplamente Encadeadas e Circulares simples - Exercícios
04 - Em uma lista duplamente encadeada, seus nodos são compostos por campos cujos tipos 
podem ser de diferentes naturezas, entretanto dois de seus campos devem ser ponteiros para 
o mesmo tipo do nodo, são estes os ponteiros ant e prox, que apontam, respectivamente, para 
o nodo anterior e para o próximo nodo. Esta característica permite que a estrutura seja 
percorrida em ambos os sentidos. Assim analisando as operações a seguir:
p->ant->prox=p->prox;
p->prox->ant=p->ant;
Sendo p um ponteiro que aponta para um dos nodos da lista, pode-se afirmar que:
[ ] As operações removem o nodo apontado pelo ponteiro p.
[ ] As operações inserem novo nodo, após o nodo apontado pelo ponteiro p.
[ ] As operações possibilitam a busca de um nodo apontado pelo ponteiro p.
[ ] As operações possibilitam o percurso do ponteiro p da direita para esquerda.
[ ] As operações possibilitam o percurso do ponteiro p da esquerda para direita.
2019.2
Listas Lineares
26
Listas Duplamente Encadeadas e Circulares simples - Exercícios
05 - Considere o tipo nodupla assim definido :
struct nodupla {
int dado;
struct nodupla *dlink, //aponta para o nó à direita
*elinlk; //aponta para o nó à esquerda
};
e uma lista duplamente encadeada, cujo primeiro nó é apontado por p, sendo
nodupla *p;
Pede-se : Sabendo-se que a função imprimir dada abaixo possui um ou mais erros, acerte-
a, reescrevendo-a inteiramente de forma correta.
imprimir(nodupla *p)
{
while (p != NULL)
{
cout << " " << p->dado;
}
}
2019.2
Listas Lineares
27
Listas Duplamente Encadeadas e Circulares simples - Exercícios
06 - Os registros também conhecidos como estruturas, são estruturas de dados do tipo 
heterogêneo, ou seja, permitem que valores de tipos diferentes possam ser armazenados em 
uma mesma estrutura. Analisando a estrutura abaixo, a mesma pode ser utilizada para qual 
tipo de estrutura de dados, marque a alternativa correta.
struct nomeRegistro{
int info;
struct nomeRegistro* ant;
struct nomeRegistro* prox;
};
typedef struct nomeRegistro NOMEREGISTRO;
[ ] Lista encadeada
[ ] Lista duplamente encadeada
[ ] Fila
[ ] Pilha
[ ] Matriz
2019.2
Listas Lineares
28
Listas Duplamente Encadeadas e Circulares simples - Exercícios
07 - Qual a estrutura de dados usada na implementação do método Round Robin do sistema 
operacional UNIX ?
[ ] Lista duplamente encadeada
[ ] Lista simplesmente encadeada
[ ] Pilha 
[ ] Fila
[ ] Arvore
08 - A partir da definição de lista simplesmente encadeada, implementar uma função que 
insira um novo valor inteiro no inicio da lista simplesmente encadeada. Protótipo : void 
InserirIni (pont *L, int x);
2019.2
Listas Lineares
29
Listas Duplamente Encadeadas e Circulares simples - Exercícios
09 - Diga o que faz a função Descobrir, que recebe um ponteiro para o último nó de uma lista circular 
simplesmente encadeada, que pode ser vazia. Considere o tipo no assim definido :
struct no{
int dado;
struct no *link; };
no *Descobrir(no *a, int valor) {
no *aux;
aux = new no;
aux->dado = valor;
if (a == NULL) {
a = aux;
a->link = a;
}else {
aux->link = a->link;
a->link = aux;
}
return a;
} // fim da função
2019.2
Listas Lineares
30
Listas Duplamente Encadeadas e Circulares simples - Exercícios
10 - Defina uma Lista Simplesmente Encadeada Circular.
11 - Defina uma Lista Duplamente Encadeada.
12 - Considere uma lista duplamente encadeada não circular de livros, sendo que cada livro possui código e 
preço. Escreva as instruções necessárias, na main, para criar um nó desta lista sabendo que cada nó é do 
tipo noDupla definido a seguir :
struct noDupla {
int codigo;
float preco;
struct noDupla *dlink, //aponta para o nó à direita
*elink; //aponta para o nó à esquerda
};
13 - Meu filho precisa trabalhar com a estrutura de dados fila, mais especificamente, fila sequencial circular com 
contador. Para isso, o 1º. passo é inicializar a fila. Sabendo que
struct Fila {
int inicio, fim, contador;
float v[100];
};
modela f que é do tipo Fila, ajude meu filho a inicializar a fila f, implementando uma função com o seguinte protótipo :
Fila inicializar(Fila f);
2019.2
Listas Lineares
31
Listas Duplamente Encadeadas e Circulares simples - Exercícios
14 - Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada 
nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa 
estrutura.
[ ] para estabelecer a ligação entre um nó já pertencente a uma lista e um novo nó, basta fazer com que o
novo nó referencie no, campo next, o nó que anteriormente era referenciado pelo nó original, desde que
esse campo não tenha o valor nulo.
[ ] a existência de um ponteiro apontando para o 1º elemento e outro para o fim da lista permite que a
inserção ou deleção de dados de um nó que esteja no meio da lista seja rapidamente executada.
[ ] enquanto a entrada que determina o topo da lista é mantida em um nó descritor dessa lista, a entrada
que marca o fim da lista é mantida fora do descritor. 
[ ] o armazenamento de uma lista requer uma área contígua de memória para permitir a otimização no
processamento de criação e remoção de nós da lista.
[ ] o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas
dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.
2019.2
Listas Lineares
32
Listas Duplamente Encadeadas e Circulares simples - Exercícios
15 - Em relação às estruturas de dados, considere: I. Um tipo abstrato de dados está desvinculado de sua 
implementação, ou seja, a sua definição visa a preocupação com o que ele faz e não como ele faz. II. A 
lista duplamente encadeada além de saber o próximo nó, cada elemento também conhece o nó anterior a 
ele na lista, o que facilita a remoção de um elemento e a exibição dos elementos na ordem inversa. III. A 
implementação dinâmica de pilhas possui as mesmas vantagens que as listas dinâmicas, ou seja, não é 
necessário saber a quantidade máxima de elementos que serão armazenados. IV. Lista, pilha, fila e array 
são casos típicos de estruturas lineares, enquanto grafo e heap são casos típicos de estruturas não 
lineares. É correto o que se afirma em: 
[ ] I e IV, apenas.
[ ] I, II e III, apenas.
[ ] II, III e IV, apenas.
[ ] I, II, III e IV.
[ ] II e III, apenas.
2019.2
Listas Lineares
33
Listas Duplamente Encadeadas e Circulares simples - Exercícios
16 - Faça uma função em C++ para imprimir todos os dados de uma lista duplamente encadeada não 
vazia de alunos. Considere
struct nodupla {
int matricula;
float media;
struct *dlink, //ponteiro para o nó à direita
*elink; //ponteiro para o nó à esquerda
};
e o seguinte protótipo : void mostrar(nodupla *p);
17 - Faça uma função em C++ para criar uma lista duplamente encadeada com apenas um nó e armazenar 
neste nó a matrícula 100 e a média 9.0. Deverá ser retornado o ponteiro para o nó criado. Considere
struct nodupla {
int matricula;
float media;
struct *dlink, *elink;
};
e o seguinte protótipo : nodupla *cria();
2019.2
Listas Lineares
34
Listas Duplamente Encadeadas e Circulares simples - Exercícios
18 - Uma lista simplesmente encadeada pode ser transformada em uma lista duplamente encadeada em 
tempo O(1), porque para transformar uma lista simplesmente encadeada em duplamente encadeada basta 
fazer uma cópia invertida de cada ponteiro (o destino do novo ponteiro passa a ser a origem do ponteiro 
original e vice-versa) e existe um número constante e limitado de cópias a fazer.Analisando as afirmações 
acima, conclui-se que: 
[ ] As duas afirmações são verdadeiras e a segunda justifica a primeira.
[ ] As duas afirmações são verdadeiras e a segunda não justifica a primeira.
[ ] Primeira afirmação é verdadeira e a segunda é falsa.
[ ] A primeira afirmação é falsa e a segunda é verdadeira.
[ ] As duas afirmações são falsas.