2ª Lista de exercícios
Estrutura de Dados 1
Verão-2011
Centro de Ciências Agrárias
Universidade Federal do Espírito Santo
Departamento de Engenharia Rural
Observação: Aproveite os códigos-fonte disponibilizados para resolver as questões
que exigirem codificação.
1) Suponha que lis é o endereço do primeiro nó de uma lista encadeada que termina
com NULL. Eu gostaria de somar 1 ao item de cada nó. O trecho de código abaixo
faz o serviço?
PNo t;
for (t = lis; t->prox != NULL; t = t->prox)
t->info++;
2) Crie uma função que receba uma lista simplesmente encadeada com descritor e
inverta a ordem do encadeamento de seus elementos (a lista deverá estar
invertida ao fim da execução da função).
Para os exercícios 3, 4 e 5 considere a seguinte declaração de uma lista
simplesmente encadeada sem descritor:
typedef struct noLista* PNo;
typedef struct noLista {
int info;
PNo prox;
}TNoLista;
3) Escreva uma função que, dada uma lista l do tipo PNo, desloque uma vez os
elementos de l, de acordo com n. Se n é ímpar, o elemento que está na última
posição passa a ser o primeiro quando a lista é deslocada. Caso n seja par, o
elemento que está na primeira posição passa a ser o último. O protótipo desta
função é o seguinte: void desloca (PNo* l, int n).
4) Faça uma função que receba como parâmetro um ponteiro para um nó qualquer
de uma lista simplesmente encadeada sem descritor e verifique se esta lita é
circular. (O ponteiro não aponta necessariamente para o primeiro nó da lista, a
função não deve acessar a informação de qual é o primeiro nó da lista).
5) Escreva uma função que aceite como entrada uma lista l simplesmente
encadeada circular sem descritor, um valor inteiro n e faça o seguinte:
a) A partir do primeiro nó, percorrer as ligações (campo prox) dos nós até
que se tenha passado por n ligações, retornando ao nó inicial sempre que
se atinge o último nó, isto é, quando n for maior ou igual ao número de nós
da lista. Nesta questão, vamos considerar o ato de seguir uma ligação
como um salto.
b) Calcule e retorne: i) quantas voltas foram dadas na lista (considerar uma
volta completa quando o processo atingir o nó inicial - apontado por l) (0
volta quando não se completar uma volta) ii) quantos saltos são
necessários para completar uma volta a partir do nó em que o processo
parou.
Exemplos (considerar a lista encadeada ilustrada na figura 1):
i – fornecendo esta lista e o valor n = 3 para a função, o processo irá encerrar no
nó de informação Pedro e a função deverá informar como saída que foi realizada
“0 volta” e que é necessário 1 “salto” para completar uma volta.
ii – fornecendo a mesma lista e o valor 4 (o processo deverá encerrar no nó
João): foi dada 1 volta e serão necessários 4 “saltos” para completar uma volta.
Professor: Bruno Vilela Oliveira
1 de 2
2ª Lista de exercícios
Estrutura de Dados 1
Verão-2011
Centro de Ciências Agrárias
Universidade Federal do Espírito Santo
Departamento de Engenharia Rural
iii – fornecendo a mesma lista e o valor 9 (o processo deverá encerrar no nó
Maria): foram dadas 2 voltas e serão necessários 3 saltos para completar uma
volta.
Figura 1 – Lista Simplesmente Encadeada Circular
6) Escreva as funções necessárias para que, dadas duas listas (l1 e l2) que
armazenam números inteiros, faça a concatenação das mesmas ao final de l1. O
protótipo da função é o seguinte: void juntaListas (PNo* l1, PNo l2).
a) Considerando que as listas sejam simplesmente encadeadas sem descritor
b) Considerando que as listas sejam simplesmente encadeadas com descritor
c) Considerando que as listas sejam duplamente encadeadas sem descritor
d) Considerando que as listas sejam simplesmente encadeadas e circulares,
sem descritor.
7) Elabore uma função para remoção de todos os nós cuja informação (número
inteiro) do campo info seja igual a um valor v fornecido como entrada. A lista a ser
considerada é duplamente encadeada com descritor.
Professor: Bruno Vilela Oliveira
2 de 2