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