TRABALHO N2 AEDI

Prévia do material em texto

INSTITUTO FEDERAL DE EDUCAÇÃO – IFCE
PROF: HÉRLON CORTEZ
TURMA: ALGORITMOS E ESTRUTURA DE DADOS I
ALUNOS:
JOÃO VICTOR CORDEIRO DE NORÕES
JOSIANA FRANCISCA DE SOUZA SILVA
(1 Ponto) - Qual a diferença entre alocação sequencial e alocação encadeada?
Na alocação sequencial cada dado é colocado em uma posição da estrutura de forma que para
se encontrar um dado basta saber sua posição, já na alocação encadeada cada dado fica alocado
em um link ou nó da estrutura e aponta através de uma referência para o próximo nó, de modo
que a ligação dessa estrutura é construída por meio desse relacionamento, assim para se saber
onde está um determinado dado, é preciso encontrar o dado que aponta para ele.
2. (1 Ponto) - Quais as vantagens de se utilizar alocação encadeada para um conjunto de elementos? E
quais as possíveis desvantagens?
Algumas vantagens são o acesso e manipulação rápidos a elementos no começo da lista, mais
eficiência no processo de adicionar ou remover elementos, visto que será necessário apenas
mudar as referências aos nós ao invés de mover eles de lugar como é no caso de vetores, e
também o uso eficiente de memória por conta da implementação dinâmica dessa estrutura, de
modo que não exige que se predetermine quanto será usado de memória.
3. (2 Pontos) - Dado o estado inicial das pilhas p1, p2 e p3 na figura abaixo, mostre (desenhe as pilhas) o
estado final dessas mesmas pilhas após as operações descritas no código abaixo. Considere que p1,
p2 e p3 sejam instâncias da classe Pilha:
int temp = p1.Retira();
p2.Insere(temp);
p3.Insere(p1.Retira());
p2.Insere(p1.Retira());
temp = p1.Retira();
p3.Insere(temp);
(1 Ponto) - Faça diagramas ilustrando uma pilha encadeada e explique sucintamente o funcionamento.
Como exemplificado acima nas pilhas encadeadas o primeiro elemento adicionado é o último a ser
retirado, visto que a remoção se da pelo último elemento adicionado, existem assim duas
operações:
● Empilhar: adiciona dados no início.
● Desempilhar: retira dados do início.
Diferentemente de uma estrutura estática na dinâmica para acessarmos um elemento temos um
ponteiro no qual aponta sempre para o próximo elemento da pilha.
5. (1 Ponto) - Faça diagramas ilustrando uma fila encadeada e explique sucintamente o funcionamento.
A fila encadeada é um representação de uma fila da vida real, diferente das pilhas, aqui o primeiro
que entrou é o primeiro a sair, dado que os elementos são incluídos no fim da fila e removidos no
começo da fila, temos assim as operações básicas:
● Incluir: no fim da fila.
● Retirar: no começo da fila.
Para acessarmos um elemento temos um ponteiro no qual aponta sempre para o próximo elemento
da fila.
6. (2 Pontos) - Especifique um problema que é melhor de ser resolvido com uma representação estática e
sequencial e outro que seja melhor resolvido com uma representação dinâmica e encadeada. Justifique.
Como estruturas estáticas necessitam de se pré determinar quanto espaço será necessário elas
podem ser usadas em casos que se sabe exatamente ou aproximadamente quanto de memória será
usado, assim, um problema que pode ser melhor resolvido usando isso é a criação de um registro
que possua campos já determinados e que provavelmente não mudarão a cada registro (ex. uma
ficha de cadastro contendo nome de até n caracteres, idade que será um inteiro de 2 bytes, etcs).
Um exemplo de problema que é melhor resolvido com uma estrutura dinâmica seria o
armazenamento de cadastros de usuário, visto que é um número que pode crescer dependendo das
demandas do sistema.
7. Implemente uma fila em um vetor circular, sem armazenar o número total de elementos (sugestão:
nunca deixe que o indicador “fim” alcance o indicador “início”, ainda que seja necessário perder uma
posição do vetor.
public class Fila {
int primeiro;
int ultimo;
int capacidade;
int[] fila;
// Na implementação desta fila os espaços do vetor ocupados com 0 serão
// considerados vazios.
public Fila(int capacidade) {
this.capacidade = capacidade;
fila = new int[capacidade];
this.primeiro = this.ultimo = 0;
}
public boolean vazia() {
if (fila[primeiro] == 0) {
return true;
}
return false;
}
public boolean cheia() {
if (contElem() == capacidade) {
return true;
}
return false;
}
/**
* Este método caso a fila esteja vazia começa a adicionar os elementos a partir
* da posição 0
* Caso esteja cheia não poderá adicionar nenhum elemento e retornará false
*/
public boolean adicionar(int valor) {
if (vazia()) {
fila[0] = valor;
primeiro = 0;
return true;
} else if (!cheia()) {
boolean vazio = false;
int n = 0;
while (!vazio) {
if (fila[n] == 0) {
vazio = true;
fila[n] = valor;
ultimo = n;
}
if (n == capacidade - 1)
n = 0;
else
n++;
}
return true;
}
return false;
}
/**
* Este método remove o elemento na primeira posição e então a segunda posição
* será a primeira
* Caso o primeiro passe a ser a última posição e seja removido então a primeira
* posição será novamente 0
*/
public void remover() {
fila[primeiro] = 0;
if (primeiro + 1 < capacidade)
primeiro = primeiro + 1;
else
primeiro = 0;
}
public void percorre() {
String stringFila = "[ ";
for (int i = 0; i < capacidade; i++) {
stringFila += fila[i];
}
stringFila += " ]";
System.out.println(stringFila);
}
/**
* Este método conta quantos elementos tem na fila, percorrendo-a
* do primeiro ao último caso não esteja vazia
*/
public int contElem() {
int cont; // variável que vai guardar a quantidade de elementos
if (primeiro == 0 && ultimo == 0 && fila[primeiro] == 0)
cont = 0;
else {
cont = 0;
int c = primeiro;
while (c != ultimo) {
cont++;
c++;
if (c == capacidade)
c = 0;
}
cont += 1; // pequeno ajuste por conta que a repetição encerra sem contar a
// posição do último
}
return cont;
}
}