Lista3_Listas_Encadeadas

Prévia do material em texto

IBILCE UNESP Departamento de Ciências de Computação e Estatística 
Disciplina Estrutura de Dados 
Curso Bacharelado em Ciências da Computação 
Profa. Dra. Inês Ap.Gasparotto Boaventura 
Lista de Exercícios sobre Listas Encadeadas 
 
Exercícios sobre Listas Encadeadas 
 
9. Suponha uma nova forma de representar uma lista ligada onde é mantido um nó 
chamado cabeça da lista. O valor do campo de informação desse nó não faz parte da 
lista, e seu campo próximo aponta para o primeiro elemento da lista. O nó cabeça é 
chamado de sentinela e evita o caso de uma lista vazia. 
 
 
 
Assuma uma lista ligada de números inteiros usando essa estrutura: 
Nolista<int> *header 
(a)Escreva uma função para inserir um nó no início da lista. 
 (b)Escreva uma função para remover o nó do início da lista. 
 
10. Escreva a função 
 Template <class T> 
 Intint Nolista<T> contelem(nolista<T> *p); 
Que conta a número de vezes que o elemento ocorre na lista 
 
11. Considere uma lista L de números inteiros. Escreva uma função 
 Void OddEven(lista<int>*L, lista<int>* L1, lista<int>*L2); 
que dado a lista L, cria duas novas listas L1 e L2 , onde L1 contém os nós pares de 
L e L2 contém os nós ímpares de L. 
12. Uma lista circular pode ser definida da seguinte forma 
 
 
 
 
 onde é a representação de lista vazia 
 
 Defina e implemente a classe nocirc , e defina a classe listacir, 
 com funções para inserir elementos em uma lista circular ordenada, remover 
elementos da lista circular, verificar se a lista está vazia, e Imprimir a lista circular. 
Cabeça 
3 5 8 
 5 8 10 L 
L 
13. Use a classe nocirc do exercício anterior e desenvolva uma implementação da classe 
lista, conforme ilustração abaixo. Declare um nó cabeça como um elemento private da 
classe e realize inserções e remoções como segue: 
insert: inserir após o nó final da lista. 
delete: Remover após o nó cabeça. Verificar para não remover elementos de uma lista 
vazia. 
 
 
 
 
 
 
 
 
 
 
 
14. Pode-se implementar a classe conjunto com elementos do tipo T armazenando 
elementos de dados únicos em uma lista encadeada. Implemente as duas funções: 
Template <class T> 
Lista<T> uniao(Lista<T> *x, Lista<T>, Lista<T> *y); 
 
Template <class T> 
Lista<T>interseccao(Lista<T> *x, Lista<T> *y); 
15. Um polinômio de grau n é uma expressão da forma: 
F(x) = anxN+an-1xn-1+ ... + a1x1+a0x0, onde os termos ai são chamados de coeficiente. 
Utilize a classe lista encadeada para resolver esse exercício onde os nós dessa lista 
deverá conter informações referentes ao coeficiente e ao expoente de X para cada 
termo. 
 Struct Term { 
 Double coef; 
 Int expoente; 
} 
O programa deverá ler um polinômio como uma série de pares de coeficientes e 
expoentes. Armazene cada par coeficiente/ expoente em uma lista encadeada 
ordenada pelo expoente. Escreva uma função que avalia o polinômio no ponto x e 
retorna o resultado dessa avaliação. 
 Double poli(lista<Term> *p); 
 
Lista Vazia 
início
 
final início 
final