MAC 324 Estruturas de Dados para Engenharia
Departamento de Ciência da Computação - USP
Segunda Lista de Exercícios
Prazo de Entrega: 22/maio/2000
Prof. Ronaldo Fumio Hashimoto
Para resolver os exercícios a seguir, considere as estruturas
de dados apresentadas em sala de aula:
-
lista circularmente ligada com cabeça de lista:
-
lista duplamente ligada circular:
-
lista duplamente ligada circular com cabeça de lista:
Questão 1 (2.0 pontos): Faça uma função
que receba uma lista ligada ini contendo números inteiros
e constrói duas listas, par e ímpar
, contendo respectivamente os lementos pares e ímpares de
ini.
Questão 2 (2.0 pontos): Faça uma função
que receba dois conjuntos A e B, armazenados
em listas ligadas circulares com cabeça de lista e constrói
uma lista para
A U B.
Questão 3 (2.0 pontos): Escreva uma função
que receba uma lista duplamente ligada apontada por dir e
esq
e um elemento x e insere x de forma que o número
de elementos à direita e à esquerda de x seja
igual, ou com diferença de no máximo 1.
Questão 4 (2.0 pontos): Escreva para cada uma das estruturas
mencionadas acima, uma função que remove o elemento do fim,
isto é,
-
lista ligada: último elemento
-
circularmente ligada: elemento antes de atual
-
circularmente ligada com cabeça de lista: antes da cabeça
-
duplamente ligada: antes de dir
-
duplamente ligada com cabeça de lista: antes da cabeça
Questão 5 (2.0 pontos): Considere uma matriz esparsa (ou seja, uma
matriz em que a maior parte das posições é preenchida
com zeros) implementada através de listas duplamente ligadas com
cabeças de listas para suas linhas e colunas. Além disso,
as cabeças das listas das linhas e colunas estão interligadas
em listas duplamente ligadas com cabeças de listas. Veja a figura
no exemplo a seguir.
Por exemplo, dada a matriz,
| 3 |
0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
0 |
-2 |
| 0 |
0 |
0 |
0 |
0 |
| -1 |
1 |
0 |
0 |
4 |
| 4 |
-2 |
0 |
0 |
1 |
cada célula da estrutura tem o formato
onde,
-
cant: apontador para o elemento anterior na mesma coluna;
-
cprox: apontador para o próximo elemento na mesma coluna;
-
lant: apontador para o elemento anterior na mesma linha;
-
lprox: apontador para o próximo elemento na mesma linha.
e a matriz estará implementada como a seguir:
-
Faça uma função que receba uma matriz esparsa
A
e imprime o conteúdo da matriz na forma tradicional;
-
Faça uma função que receba A e
B
e calcula a matriz A+B;
-
Faça uma função que receba A e acha
o elemento máximo de A.