Trabalho de aed

Prévia do material em texto

Trabalho de AED 
 
Pedro Henrique Carvalho de Oliveira 
 
1 – Crie na CLista o método void InsereAntesDe(Object ElementoAInserir, Object 
Elemento) que insere o ElementoAInserir na posição anterior ao Elemento passado 
por parâmetro. 2 
public void InsereAntesDe(Object ElementoAInserir, Object Elemento) 
 { 
 bool achou = false; 
 CCelula aux = Primeira; 
 while (aux.Prox != null && !achou) 
 { 
 achou = aux.Prox.Item.Equals(Elemento); 
 if (achou) 
 aux.Prox = new CCelula(ElementoAInserir, aux.Prox); 
 else 
 aux = aux.Prox; 
 } 
 } 
 
 
2 – Crie na CLista o método void InsereDepoisDe(Object ElementoAInserir, Object 
elemento) que insere o ElementoAInserir na posição posterior ao Elemento passado 
por parâmetro.*/ 
 
 public void InsereDepoisDe(Object ElementoAInserir, Object Elemento) 
 { 
 bool achou = false; 
 CCelula aux = Primeira.Prox; 
 while (aux != null && !achou) 
 { 
 achou = aux.Item.Equals(Elemento); 
 if (achou) 
 aux.Prox = new CCelula(ElementoAInserir, aux.Prox); 
 else 
 aux = aux.Prox; 
 } 
 if (Ultima != null) 
 Ultima = Ultima.prox; 
 } 
 
 
 
 
3 – Crie na CLista o método void InsereOrdenado(int ElementoAInserir) que insere 
ElementoAInserir em ordem crescente.*/ 
 
 public void InsereOrdenado(int ElementoAInserir) 
 { 
 CCelula aux = Primeira; 
 CCelula aux2 = Primeira.Prox; 
 
 while (aux.Prox != null && (int)aux.Prox.Item <= ElementoAInserir) 
 { 
 aux = aux.Prox; 
 aux2 = aux2.Prox; 
 } 
 } 
 
 
 
4 – Crie a função CListaDup Concatena(CListaDup L1, CListaDup L2) que concatena as 
listas L1 e L2 passadas por parâmetro, retornando uma lista duplamente encadeada. 
 
 public static CListaDup Concatenar(CListaDup L1, CListaDup L2) 
 { 
 CListaDup L3 = new CListaDup(); 
 
 foreach (int i in L1) 
 L3.InsereFim(i); 
 foreach (int i in L2) 
 L3.InsereFim(i); 
 return L3; 
 } 
 
 static void Main(string[] args) 
 { 
 CListaDup a = new CListaDup(); 
 CListaDup b = new CListaDup(); 
 CListaDup c = new CListaDup(); 
 
 for (int i = 0; i < 5; i++) 
 { 
 a.InsereFim(i); 
 } 
 for (int i = 5; i < 10; i++) 
 { 
 b.InsereFim(i); 
 } 
 Console.Write("\n Elementos a: "); 
 foreach(int i in a) 
 Console.Write(i+", "); 
 
 
 Console.Write("\n\n Elementos b: "); 
 foreach (int i in b) 
 Console.Write(i + ", "); 
 
 c = Concatenar(a, b); 
 
 Console.Write("\n\n Elementos b: "); 
 foreach (int i in c) 
 Console.Write(i + ", "); 
 
 Console.ReadKey(); 
 } 
 
 
7 - A classe RandomQueue é uma Fila que retorna elementos aleatórios ao invés de 
sempre retornar o primeiro elemento. Crie a classe RandomQueue com os seguintes 
métodos: 
 
 
public class RandomQueue 
 { 
 private CCelula Frente; 
 private CCelula Tras; 
 private int Qtde = 0; 
 
 
 public RandomQueue() 
 { 
 Frente = new CCelula(); 
 Tras = Frente; 
 
 
 public bool IsEmpty() 
 { 
 return Frente == Tras; 
 } 
 public void Enqueue(Object item) 
 { 
 Tras.Prox = new CCelula(item); 
 Tras = Tras.Prox; 
 Qtde++; 
 } 
 public Object Dequeue() 
 { 
 Object Item = null; 
 Random amostra = new Random(); 
 int count = 1, indice = amostra.Next(1, Qtde); 
 CCelula auxiliar = Frente; 
 while (auxiliar != null) 
 { 
 if (count == indice) 
 { 
 Item = auxiliar.Item; 
 } 
 count++; 
 auxiliar = auxiliar.Prox; 
 } 
 if (Frente != Tras) 
 { 
 CCelula aux = Frente; 
 bool achou = false; 
 while (aux.Prox != null && !achou) 
 { 
 achou = aux.Prox.Item.Equals(Item); 
 if (!achou) 
 aux = aux.Prox; 
 } 
 if (achou) 
 { 
 aux.Prox = aux.Prox.Prox; 
 if (aux.Prox == null) 
 Tras = aux; 
 Qtde--; 
 } 
 } 
 return Item; 
 
 
 } 
 
 public Object Sample() 
 { 
 Random amostra = new Random(); 
 int count = 1, indice = amostra.Next(1, Qtde); 
 for (CCelula aux = Frente.Prox; aux != null; aux = aux.Prox) 
 { 
 if (count == indice) { return aux.Item; } 
 count++; 
 } 
 return null; 
 } 
 
 public Object Peek() 
 { 
 if (Frente != Tras) 
 return Frente.Prox.Item; 
 else 
 return null; 
 } 
 } 
 
 
 
8 – Crie na CListaDup o método int PrimeiraOcorrenciaDe(Object elemento) que busca 
e retorna o índice da primeira ocorrência do elemento passado por parâmetro. Caso o 
elemento não exista, sua função deve retornar um valor negativo. 
 
 public int PrimeiraOcorrenciaDe(Object elemento) 
 { 
 int n=-1, pos = 0; 
 
 
 if(Primeira != Ultima) 
 { 
 bool achou = false; 
 CCelulaDup aux = Primeira.Prox; 
 
 while (aux != null && !achou) 
 { 
 achou = aux.Item.Equals(elemento); 
 aux = aux.Prox; 
 pos++; 
 } 
 
 if (achou == true) 
 n = pos; 
 } 
 return n; 
 } 
 
 
 
10– Deque (Double-ended-queue) é um Tipo Abstrato de Dados (TAD) que funciona 
como uma Fila e como uma Pilha, permitindo que itens sejam adicionados em 
ambos os extremos. Implemente a classe Deque, usando duplo encadeamento, 
com os seguintes métodos: 
 
 
public class Deque 
 { 
 private CCelulaDup Topo = null; 
 private int Qtde = 0; 
 public Deque() { } 
 public bool IsEmpty() 
 { 
 return Topo == null; 
 } 
 public int Size() 
 { 
 return Qtde; 
 } 
 public void Esquerda(Object item) 
 { 
 if (IsEmpty()) 
 { 
 Topo = new CCelulaDup(item); 
 } 
 else 
 { 
 Topo = new CCelulaDup(item, null, Topo); 
 } 
 } 
 public void Direita(Object item) 
 { 
 CCelulaDup aux = Topo; 
 if (IsEmpty()) 
 { 
 Topo = new CCelulaDup(item); 
 } 
 else 
 { 
 while (aux != null) 
 { 
 if (aux.Prox == null) 
 { 
 aux.Prox = new CCelulaDup(item,aux, null); 
 return; 
 } 
 aux = aux.Prox; 
 } 
 } 
 } 
 
 public Object PopLeft() 
 { 
 Object Item = null; 
 if (Topo != null) 
 { 
 Item = Topo.Item; 
 Topo = Topo.Prox; 
 Qtde--; 
 } 
 return Item; 
 } 
 public Object PopRight() 
 { 
 Object item = null; 
 CCelulaDup aux = Topo; 
 while (aux != null) 
 { 
 if (aux.Prox == null) 
 { 
 item = aux.Item; 
 aux = aux.Ant; 
 aux.Prox = null; 
 break; 
 } 
 aux = aux.Prox; 
 } 
 return item; 
 } 
 public void Print() 
 { 
 CCelulaDup aux = Topo; 
 Console.WriteLine(); 
 while (aux != null) 
 { 
 Console.Write(aux.Item + " "); 
 aux = aux.Prox; 
 } 
 } 
 } 
 
 
 
 
16 - Crie na CLista o método Object[] CopiaParaVetor() que copia todos os elementos 
da Lista para um vetor. 
 
 public Object[] CopiaParaVetor(CLista x) 
 { 
 object []vet = new object[x.Qtde]; 
 
 Console.WriteLine("\n"); 
 for (int i = 1, j=0; i <= x.Qtde; i++, j++) 
 { 
 vet[j] = x.RetornaIndice(i); 
 } 
 
 return vet; 
 } 
 
 
 
32 -Crie a classe CListaSimples que é uma lista simplesmente encadeada sem célula 
cabeça e que possui apenas os métodos definidos na interface abaixo. Atenção: 
não podem ser acrescentados novos atributos ou métodos às classes 
CListaSimples e/ou CCelula abaixo. 
 
class CCelula 
 { 
 public Object item; 
 public CCelula prox; 
 } 
 private CCelula primeira, ultima; 
 public CListaSimples() 
 { 
 
 primeira = null; 
 ultima = primeira; 
 } 
 
 public bool Vazia() { return primeira == null; } 
 public void InsereComeco(Object valorItem) 
 { 
 
 if (primeira == null) 
 { 
 primeira = new CCelula(); 
 primeira.item = valorItem; 
 ultima = primeira.prox; 
 } 
 else 
 { 
 CCelula aux = primeira; 
 primeira = new CCelula(); 
 primeira.item = valorItem; 
 primeira.prox = aux; 
 if (primeira.prox == null) { ultima = primeira.prox; } 
 } 
 } 
 public Object RemoveComeco() 
 { 
 
 if (primeira != null) 
 { 
 CCelula aux = primeira; 
 primeira = aux.prox; 
 return aux.item; 
 } 
 else { return null; } 
 } 
 
 
 
 public Object RemoveFim() 
 { 
 CCelula aux = primeira; 
 Object item = null; 
 while (aux != null) 
 { 
 if (aux.prox == null) 
 { 
 item = aux.item; 
 ultima = aux; 
 return item; 
 } 
 aux = aux.prox; 
 } 
 return item; 
 } 
 public void Fim(Object valorItem) 
 { 
 CCelula aux = primeira; 
 while (aux != null) 
 { 
 if (aux.prox == null) 
 { 
 aux.prox = new CCelula(); 
 aux.prox.item = valorItem; 
 ultima = aux.prox.prox; 
 return; 
 } 
 aux = aux.prox; 
 } 
 } 
 
 
 public void Imprime() 
 { 
 
 for (CCelula aux = primeira; aux != null; aux = aux.prox) 
 { 
 Console.Write(aux.item + " "); 
 } 
 } 
 public bool Contem(Object elemento) 
 { 
 
 CCelula aux = primeira; 
 bool existe = false; 
 while (aux != null && !existe) 
 { 
 existe = aux.item.Equals(elemento); 
 aux = aux.prox; 
 } 
 return existe; 
 } 
 }