Programação C/C++
Exercício - Avaliação de uma implementação
O objetivo deste exercício é testar e avaliar uma solução, de outro colega, para o exercício apresentado a seguir.
Você receberá uma folha com a resposta que um de seus colegas criou para o problema. Digite o código e teste.
Faça comentários em cada parte do código. Caso haja erros de sintaxe
simples como falta de ponto-e-vírgula, você pode corrijir e
desconsiderá-lo. Para outros erros, como falta de declaração de
variáveis, falta de parâmetros ou erros de lógica, você deve igualmente
corriji-los mas deve anotar do código que havia um erro.
Ao final, gere um relatório com um parecer sobre o a solução apresentada.
Lista Encadeada de Inteiros
Definir uma classe que
represente uma lista de
inteiros.
Esta classe deve armazenar os dados em um vetor de inteiros de tamanho
10.
Deve existir um vetor auxiliar de que indique, na posição
Vaux[i], qual o próximo elemento da lista após o elemento
que está na posição 'i'.
Na figura abaixo, considere que a lista inicia na posição
3.
No vetor auxiliar, o valor -1 indica que a posição
correspondente no vetor 'dados' está vazia. Por sua vez, o
valor -2 indica que a posição correspondente no vetor
'dados' é o último elemento da lista.
| Índice |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Dados |
10 |
1 |
VAZIO |
9 |
VAZIO |
11 |
34 |
VAZIO |
VAZIO |
VAZIO |
VAZIO |
| Vetor
Auxiliar(próximo) |
5 |
6 |
-1 |
0 |
-1 |
1 |
-2 |
-1 |
-1 |
-1 |
-1 |
Ao ser impressa, esta lista deve apresentar os seguintes valores: 9,
10, 11, 1, 34.
A classe de deve ter métodos para:
-
Inserção:
este método deve inserir um dado (int) na lista,
após o último dado inserido. Este método deve
retornar 1 quando conseguir inserir e 0 quando não houver mais
espaço na lista. Internamente, a inserção deve ser
feita no primeiro espaço livre do vetor de dados;
-
Remoção:
Remover um elemento da lista
dado seu valor. Este método deve
retornar 1 quando conseguir remover e 0 quando o dado não
existir na lista;
-
Impressão:
Imprime os dados na lista na ordem que foram inseridos.
void
ListaEncadeadaComVetor::imprimeLista()
{
int pos = inicio;
cout << "Lista: ";
cout << "Inicio: " << pos << endl;
for(int i=0; i< TAM; i++)
{
cout << Dados[pos] << "(" << pos << ")";
pos = Aux[pos];
if (pos == -2)
break;
else cout << ", ";
}
cout << endl;
}
Sugestão para definição da classe:
#include <iostream>
using namespace std;
const int TAM = 10;
class ListaEncadeadaComVetor{
int inicio;
int Dados[TAM];
int Aux[TAM];
int achaPosUltimo();// Este método faz a busca do último a partir dos dados da lista e não a partir do vetor auxiliar
int achaPosLivre(); // Este método faz a busca de um espaço livre a partir do vetor auxiliar
public:
ListaEncadeadaComVetor ();
int insereDado(int D);
int removeDado(int D);
void imprimeLista();
};
