CMP1054 - Exercicios - Lista Simplesmente Encadeada

Prévia do material em texto

CMP1054 - Estrutura de Dados I
3
a
Lista de Exercícios - Listas simplesmente encadeadas
Max Gontijo de Oliveira
• Todas as funções criadas nas questões deverão ser testadas em um programa principal (main).
• Caso haja necessidade, crie parâmetros adicionais para as funções recursiva além dos explicitamente solicitados nas questões.
• Quando não estiver explícito na questão, o aluno poderá escolher entre criar um algoritmo iterativo ou recursivo.
• Considere em todas as questões o uso da seguinte estrutura nos elementos da lista:
c l a s s Node {
pub l i c :
i n t x ;
Node ∗prox ;
} ;
• Considere que o ponteiro do início da lista é declarado como variável global, inicializado com o valor NULL e com o nome lst, exatamente como segue:
Node ∗ l s t = NULL;
• Considere ainda que a lista lst é uma lista ordenada.
1. Crie uma função em C++ que receba por parâmetro um valor int e insira-o na lista lst de forma
ordenada. Utilize um algoritmo iterativo.
2. Crie uma função em C++ que receba por parâmetro um valor int e insira-o na lista lst de forma
ordenada. Utilize um algoritmo recursivo.
3. Crie uma função em C++ que some todos os valores ÍMPARES da lista lst e retorne o valor dessa
soma. Utilize um algoritmo recursivo.
4. Crie uma função em C++ que receba por parâmetro dois valores int (a e b) e remova da lista
lst todos os elementos cujo valor esteja entre a e b.
5. Crie uma função em C++ que receba por parâmetro um valor int que representa o índice de
um elemento da lista lst. A função deverá retornar o endereço do elemento referente ao índice
informado (tal como em um vetor) ou retornar NULL caso o índice informado seja maior ou igual ao
tamanho da lista ou menor que 0. Considere que o primeiro elemento (aquele apontado por lst)
é o elemento na posição 0
6. Crie uma função em C++ que receba por parâmetro dois ponteiros para listas distintas e retorne
TRUE caso as duas listas tenham o mesmo conteúdo ou FALSE caso contrário. Considere que as
duas listas estejam ordenadas.
7. Crie uma função em C++ que receba por parâmetro dois valores int (a e b). A função deverá
procurar na lista lst a localização do elemento cujo valor é a e substituir esse valor por b. Note
que, após a troca de valor, poderá ser necessária a mudança de lugar do nó alterado para manter a
lista ordenada.
8. Crie uma função em C++ que receba por parâmetro um ponteiro para uma outra lista ordenada
(não é a mesma lista lst) e adicione todos os elementos dessa outra lista à lista lst por meio de
intercalação.
9. Crie uma função em C++ que receba por parâmetro dois ponteiros para duas listas ordenadas
distintas. A função deverá CRIAR uma nova lista contendo os mesmos valores das duas listas
passadas por parâmetro mas sem alterar as listas originais. Em outras palavras, novos objetos
Node deverão ser criados para compor essa nova lista. Aproveite que as duas listas são ordenadas e
utilize intercalação. Por fim, a função deverá retornar o endereço do início dessa nova lista criada.
Caso ambas as listas passadas por parâmetro sejam vazias, a função deverá retornar NULL.
10. Crie uma função em C++ que receba por parâmetro uma lista ordenada e retorne TRUE caso os
elementos da lista representem valores sequenciais a partir do início da série de Fibonacci (0, 1, 1,
2, 3, 5, 8, 13...). Caso haja algum elemento na lista que quebre a série, a função deverá retornar
FALSE. Se a lista estiver vazia, deverá também retornar FALSE.