Folha prática - Listas ligadas simples
1
Listas ligadas com ligações simples
A. Considere as declarações de Nodo e PNodo (adaptada dos apontamentos) seguintes:
struct Nodo {
int Elemento;
struct Nodo *Prox;
};
typedef struct Nodo *PNodo;
Considere as funções relacionadas com a Estrutura Abstrata de Dados Lista com armazenamento
não sequencial usando memória dinâmica (que constam em Capítulo 3 - Estruturas de Dados
sequenciais com armazenamento não sequencial www.di.ubi.pt/~cbarrico –> Programação
III/Estruturas de Dados -> Apontamentos) adaptadas às declarações anteriores.
- Copiar e adaptar todas as funções associadas às operações básicas de uma EAD Lista de
inteiros com ligações simples estudadas nas aulas teóricas para um ficheiro denominado
“ListasLigadasSimples.h”, as quais se encontram descritas nos apontamentos disponibilizados
na página web da disciplina.
- Elaborar um programa que inclua o ficheiro anterior e resolva as questões colocadas a seguir,
usando, sempre que possível, as funções/operações básicas mencionadas.
1. Implementar uma função para preencher uma lista ligada L com valores inteiros positivos,
inseridos a partir do teclado.
2. Implementar uma função para determinar a soma dos elementos duma lista ligada L com
valores inteiros positivos.
3. Implementar uma função para determinar a quantidade de elementos duma lista ligada L
com valores inteiros positivos maiores ou iguais a um valor K.
4. Implementar uma função que, dados uma lista ligada L com valores interios positivos e um
inteiro X, remova um elemento da lista L com valor igual a X, caso exista.
5. Implementar uma função que, dados uma lista ligada L com valores interios positivos e um
inteiro X, remova todos os elementos da lista L com valores iguais a X, caso existam.
6. Implementar uma função que, dados uma lista ligada L com valores inteiros positivos e um
número inteiro positivo N, remova da lista L os seus N primeiros elementos e retorne a lista
resultante. Caso N seja maior do que o comprimento da lista, todos os seus elementos
devem ser removidos e o resultado deve ser uma lista vazia.
7. Implementar uma função que receba como parâmetro uma lista L de valores inteiros
positivos e um número inteiro positivo M e divida a lista em duas, de tal forma que a
segunda lista comece com o elemento logo após o elemento com valor igual a M.
Programação III / Estruturas de Dados
Folha prática - Listas ligadas simples
2
8. Implementar uma função que determine o maior valor associado a um elemento de uma lista
ligada L com valores inteiros positivos.
9. Implementar uma função que remova todos os elementos de uma lista ligada L com valores
inteiros positivos, cujos elementos sejam iguais ao maior valor da lista L (usar a função
implementada no exercício anterior).
10. Implementar uma função que modifique uma lista ligada L com valores inteiros positivos, tal
que os valores pares são multiplicados por K1 e os ímpares por K2.
11. Implementar um função que construa uma lista ligada L com valores inteiros positivos, os
quais estão ordenados crescentemente.
12. Implementar uma função que, dados uma lista ligada L com valores interios positivos
ordenados crescentemente e um inteiro X, remova todos os elementos da lista L com valores
iguais a X, caso existam.
13. Implementar uma função que, dados uma lista ligada L com valores interios positivos
ordenados crescentemente e um inteiro X, remova todos os elementos da lista L com valores
superiores ou iguais a X, caso existam.
14. Implementar uma função para determinar a soma dos elementos duma lista ligada L com
valores inteiros positivos maiores do que K1 e menores do que K2.
15. Implementar uma função para alterar a lista ligada L com valores inteiros positivos, tal que
aos elementos da primeira metade da lista L são acrescentados o valor K1 e aos restantes
são acrescentados o valor K2.
16. Implementar uma função para determinar o menor elemento duma lista ligada L de valores
inteiros positivos, com valor maior ou igual ao valor K.
17. Implementar uma função para alterar uma lista ligada L valores inteiros positivos, tal que
aos primeiros e últimos K elementos da lista L são acrescentados o valor Y1 e aos restantes
são acrescentados o valor Y2.
18. Construa uma função para determinar o maior elemento duma lista ligada L de valores
inteiros positivos menor do que o valor Y.
19. Implementar uma função que dada uma lista ligada L com valores inteiros positivos,
determine o segundo maior elemento da lista, percorrendo-a apenas uma vez.
20. Implementar uma função que dado duas listas ligadas L1 e L2 com valores inteiros positivos,
construa uma lista L resultante da concatenação de L1 com L2 (L = L1.L2)
21. Implementar uma função que dada uma lista ligada L1 com valores inteiros positivos,
construa uma lista L2 com elementos de L1, na mesma sequência mas sem valores
repetidos. (Ex: L1 = [15 31 23 15 75 23 41 15 31 85] => L2 = [15 31 23 75 41 85])
Programação III / Estruturas de Dados
Folha prática - Listas ligadas simples
3
22. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, remova
todos os elementos repetidos (ex: L = [15 31 23 15 75 23 41 15 31 85]  L = [15 31 23 75
41 85]).
23. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, remova
todos os elementos pares (ex: L = [15 32 24 11 75 26 41 18 31]  L = [15 11 75 41 31]).
24. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, remova o
primeiro e o último elementos da lista.
25. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, remova
todos os elementos de L com exceção do primeiro e do último elemento.
26. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, insira
elementos iguais junto dos elementos pares (ex: L = [15 32 24 11 17 42]  L = [15 32 32
24 24 11 17 42 42]).
27. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, transfira
o último elemento para a segunda posição da lista (ex: L = [15 32 24 11 17 42]  L = [15
42 32 24 11 17]).
28. Implementar uma função que dada uma lista ligada L de valores inteiros positivos liberte
todos os nodos desta lista.
29. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, inverta a
lista L de modo que o último elemento se torne o primeiro, e assim sucessivamente.
30. Implementar uma função que dada uma lista ligada L de valores inteiros positivos, elimine o
último elemento da lista L.
31. Implementar uma função que dada uma lista ligada L de valores inteiros positivos e um
número inteiro N, elimine o N-ésimo elemento da lista L.
32. Implementar uma função que dadas duas listas ligadas ordenadas L1 e L2 de valores
inteiros positivos, junte as duas listas numa única lista também ordenada.
33. Implementar uma função que dadas duas listas ligadas L1 e L2, construa uma lista contendo
a intersecção dos elementos de duas listas.
B. Outras problemas
34. Implementar uma função para verificar se um número inteiro positivo N é capicua (número
que ao ser lido da esquerda para a direita ou vice-versa é o mesmo; ex: 12321 ), usando
uma lista ligada.
35. Implementar uma função que dadas duas lista ligadas com valores binários (0/1), L1 e L2, e
um valor inteiro k (k > 0), construa duas listas ligadas L3 e L4, em que L3 é formado pelos
primeiros k valores de L1 e os últimos de L2, e L4 é formado pelos primeiros k valores de
Programação III / Estruturas de Dados
Folha prática - Listas ligadas simples
4
L2 e os últimos de L1 (ex: L1 = [1 1 0 1 0 1], L2 = [0 1 0 1 1 0] e k = 2 => L3 = [1 1 0 1
1 0] e L4 = [0 1 0 1 0 1]).
36. Seja um polinómio de grau n:
P(x) = anxn + an-1xn-1 + ... + a1x1 + a0x0
onde an ≠ 0, exceto possivelmente no caso n = 0.
a) Construa uma função para determinar o valor de P(x).
b) Construa uma função para efetuar a soma de dois polinómios: P(x) + P(y).
c) Construa uma função para efetuar o produto de dois polinómios: P(x) x P(y).
Sugestão: Criar uma lista ligada com três campos, um para o coeficiente (a n), outro para o
expoente (n) e o outro para a ligação ao próximo elemento.
Programação III / Estruturas de Dados