MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3818 6140

E-MAIL cef@ime.usp.br

MONITOR: MARCIO C. CABRAL

MAC 122 - Princípios de Desenvolvimento de Algoritmos

Segundo semestre de 2000

Lista de Exercícios - Listas Ligadas

1.

Escreva uma função para converte uma lista ligada em um vetor.

2.

Escreva uma função que recebe uma lista ligada apontada por inicio e uma dada informação X e remove da lista todos os elementos com este conteúdo.

3.

Escreva funções para as seguintes operações:

(a)

acrescentar um elemento ao começo de uma lista ligada;

(b)

acrescentar um elemento no fim de uma lista ligada;

(c)

imprimir os conteúdos de todos os elementos de uma lista ligada.

4.

Discuta vantagens e desvantagens de vetores (arrays) em relação a listas ligadas (implementadas num vetor ou com pointers). Dê atenção especial às questões de quantidade de memória, velocidade de inserção, remoção e acesso.

5.

Escreva um procedimento que inverte uma lista ligada dada (o primeiro elemento da nova lista é o último da lista dada, o segundo é o penúltimo da lista dada, e assim por diante. Exemplo:

6.

Escreva um procedimento para intercalar duas listas ligadas cujas informações estão arranjadas em ordem crescente. Exemplo:

7.

Discuta vantagens e desvantagens de vetores (arrays) em relação a listas ligadas (implementadas num vetor ou com pointers). Dê atenção especial às questões de quantidade de memória, velocidade de inserção, remoção e acesso.

8.

Dada uma lista ligada que armazena números inteiros escreva um procedimento que transforma a lista dada em duas listas ligadas: a primeira contendo os elementos cujo conteúdo é par e a segunda cujo conteúdo é ímpar. O seu procedimento deve manipular somente os apontadores e não o conteúdo das células (i.e. não vale ficar copiando os conteúdo de um lado para o outro, só vale alterar os apontadores). Exemplo: