Lista de Exercícios
Estrutura de Dados
Profa. Susana Marrero Iglesias
Estruturas dinâmicas. Listas Linearmente Ligadas, Listas Circulares e Listas
duplamente enlaçadas.
1. Usando a notação de sala de aula para listas simples ligadas (node(p), info(p),
next(p), freenode, getnode). Escreva algoritmos para:
a. Incluir um elemento no final de uma lista
b. Concatenar duas listas
c. Liberar todos os nós de uma lista
d. Inverter uma lista de modo que o último elemento se torne o primeiro e
assim por diante.
e. Eliminar o último elemento de uma lista
f. Eliminar o enésimo elemento de uma lista
g. Combinar duas listas ordenadas numa única lista ordenada
h. Formar uma lista contendo a união dos elementos de suas listas
i. Formar uma lista contendo a intersecção dos elementos de duas listas
j. Inserir um elemento depois do enésimo elemento de uma lista
k. Eliminar cada segundo elemento de uma lista ordenada crescente
l. Colocar os elementos de uma lista em ordem ascendente
m. Retornar a soma dos inteiros de uma lista.
n. Retornar o número de elementos de uma lista
o. Deslocar node(p) n posições à frente numa lista
p. Criar uma segunda cópia de uma lista.
2. Escreva algoritmos para executar as operações do exercício 1 pressupondo que
cada lista contenha um nó cabeçalho com o número de elementos da lista.
3. Implemente as rotinas empty, push e pop e popandtest para a implementação
dinâmica de pilha com listas ligadas linear, implemente a estrutura e funções
necessárias (getnode e freenode)
4. Implemente uma fila com uma lista linearmente ligada , implemente as rotinas
empty, insert e remove.
5. Escreva rotinas em C para a implementação de lista linear ligada para as
operações do exercício 1.
6. Escreva uma rotina em C para intercambiar os elementos m e n de uma lista
ligada.
7. Suponha que um string de caracteres seja representado por uma lista de caracteres
individuais. Escreva um conjunto de rotinas que para manipular estas listas como
segue (l1 e l2 são ponteiros para um nó de cabeçalho e uma lista representando
um string de carateres, str é um vetor de caracteres e i1 e i2 dois inteiros)
a. strcnvcl(str) para converter a string de caracteres, str numa lista. Essa
função retorna um ponteiro para o nó cabeçalho da lista.
b. strcnvlc(list, str) para converter uma lista em um string de caracteres.
c. strpsl(l1, l2) para executar a função strpos sobre duas strings. Essa função
retorna um inteiro.
1
d. strvfyl(l1, l2) para determinar a primeira posição da string representada
por l1 que não esteja contida em l2. Essa função retorna um inteiro.
e. strcmpl(l1, l2) para comparar duas strings de caracteres, representadas por
listas. Essa função retorna -1 se a string representada por l1 é menor que a
string representada por l2; 0 se são iguais, e 1 se a string representada por
l1 é maior.
8. Escreva um algoritmo e uma rotina em C para efetuar cada uma das operações do
Exercício 1, com listas circulares.
9. Reescreva a função place que vimos na sala de aula para listas ligadas lineares de
modo a inserir um novo item numa lista circular ordenada.
10. Escreva uma função em C que faça a soma de dois inteiros representados por uma
lista circular.
11. Como um polinômio em três variáveis (x, y e z ) pode ser representado por uma
lista circular? Cada nó deve representar um termo e deve conter as potencias de x,
y e z, bem como o coeficiente desse termo. Escreva funções em C para
a. Somar dos polinômios
b. Multiplicar dois polinômios
c. Avaliar o polinômio para valores de x, y e z
d. Imprimir a representação desse polinômio.
2