Listas (Lists)

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Listas (Lists)

Mensagem por Evandro Abu Kamel em Sex 18 Set 2009, 20:51

Olá pessoa, já estava na hora de eu postar algum códgo aqui no fórum de AED.
Vou disponibilizar aqui os códigos que fiz das implementações das listas simplesmente encadeadas (LSE) e as listas simplesmente encadeadas circulares (LSEC).
Espero que vocês tentem fazer antes, tentem entender estes códigos, estudem, comparem, analizem, pois isso é matéria de prova.


Lista Simplesmente Encadeada (LSE)

Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace Lab06_LSE
{
   class Node
   {
      public int value;
      public Node prox;

      public Node(int value, Node prox)
      {
         this.value = value;
         this.prox = prox;
      }

      public Node()
      {
         value = 0;
         prox = null;
      }
   }

   class Lista
   {
      private Node primeiro, pos, ultimo;
      /* O primeiro node da lista sempre tera value = 0;
       * pos percorre a lista e ultimo aponta para o ultimo elemento.
       */

      public Lista()
      {
         // construtor padrao, aponta os tres nodes para um unico nulo
         primeiro = new Node();
         pos = primeiro;
         ultimo = primeiro;
      }

      public bool isEmpty()
      {
         // verifica se a lista esta vazia
         return (primeiro.prox == ultimo.prox);
      }

      public void insere(int x)
      {
         // insere um node no fim da lista
         Console.WriteLine("Inserindo {0} no final ", x);

         Node novo = new Node(x, null);
         pos = ultimo;
ultimo.prox = novo;
         ultimo = novo;
      }

      public void retira(int x)
      {
         // retira o node cujo value e igual x da lista
         if (!isEmpty())
         {
            Node q = primeiro;
            while (q.prox != null && q.prox.value != x)
            {
               q = q.prox;
            }

            if (q.prox != null)
            {
               Console.WriteLine("Retirando elemento {0}!", x);
               q.prox = q.prox.prox;

               if (q.prox == null)
                  ultimo = q;
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public void inserePrimeiro(int x)
      {
         //insere elemento na primeira posicao da lista (na frente)
         Console.WriteLine("Inserindo {0} no inicio ", x);

         Node novo = new Node(x, primeiro.prox);
         primeiro.prox = novo;
      }

      public int retiraPrimeiro()
      {
         //retira elemento da ultima posicao da lista e o retorna
         val = -1;
         if (!isEmpty())
         {
            val = primeiro.prox.value;
            Console.WriteLine("\nRetirando primeiro elemento: {0}", val);
            primeiro.prox = primeiro.prox.prox;
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void retiraTodos(int x)
      {
         // remove todas as ocorrencias de x da lista
         Node p = primeiro;
         Node q = primeiro.prox;

         if (!isEmpty())
         {
            Console.WriteLine("\nRemovendo todos os valores {0}", x);
            while (q != null)
            {
               if (q.value == x)
               {
                  p.prox = q.prox;
                  q = q.prox;
               }
               else
               {
                  p = p.prox;
                  q = q.prox;
               }
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public int pesquisa(int x)
      {
         // pesquisa se um elemento esta na lista.
         // caso afirmativo, retorna o elemento. Caso contrario, retorna -1.
         int val = -1;
         if (!isEmpty())
         {
            pos = primeiro.prox;
            do
            {
               if (this.pos.value == x)
                  val = pos.value;
               pos = pos.prox;
            } while (pos != null);
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public int proximo()
      {
         //retorna o ultimo elemento da lista
         int val = -1;
         if (!isEmpty())
         {         
            val = ultimo.value;
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void imprime()
      {
         //imprime a lista
         if (!isEmpty())
         {
            Console.WriteLine("\nA lista esta assim:\n ");
            pos = primeiro.prox;
            do
            {
               Console.Write("  {0}", pos.value);
               pos = pos.prox;
            } while (pos != null);
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Lista L = new Lista();

         L.insere(6);
         L.insere(5);
         L.insere(8);
         L.insere(34);
         L.insere(56);
         L.insere(98);
         L.insere(6);
         L.retira(5);
         L.retira(56);
         L.retira(8);
         L.insere(20);
         L.inserePrimeiro(33);
         L.insere(77);
         L.insere(6);

         L.imprime();
         Console.ReadLine();

         Console.WriteLine("\nUltimo item da lista: " + L.proximo());
         L.retiraPrimeiro();
         Console.WriteLine("\nElemento pesquisado: " + L.pesquisa(98));
         L.retiraTodos(6);
         L.imprime();

         Console.WriteLine("\n");
         Console.ReadLine();
      }
   }
}

Lista Simplesmente Encadeada Circular (LSEC)

Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace Aula_LSEC
{
   class Node
   {
      public int value;
      public Node prox;

      public Node(int value, Node prox)
      {
         this.value = value;
         this.prox = prox;
      }

      public Node()
      {
         value = 0;
         prox = null;
      }
   }

   class Lista
   {
      private Node sentinel, ultimo;

      public Lista()
      {
         // construtor padrao, inicializa sentinel e aponta ultimo para sentinel
         sentinel = new Node();
         ultimo = this.sentinel;
      }

      public bool isEmpty()
      {
         // verifica se a lista esta vazia
         return (this.sentinel.prox == this.sentinel);
      }

      public void insere(int x)
      {
         // insere um node no fim da lista
         Console.WriteLine("Inserindo {0} no final ", x);

         Node novo = new Node(x, this.sentinel);
         ultimo.prox = novo;
         ultimo = novo;
      }

      public void retira(int x)
      {
         // retira o node cujo value e igual x da lista
         if (!isEmpty())
         {
            Node q = sentinel;
            while (q.prox != sentinel && q.prox.value != x)
            {
               q = q.prox;
            }

            if (q.prox != this.sentinel)
            {
               Console.WriteLine("Retirando elemento {0}!", x);
               q.prox = q.prox.prox;
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public void inserePrimeiro(int x)
      {
         //insere elemento na primeira posicao da lista (na frente)
         Console.WriteLine("Inserindo {0} no inicio ", x);

         Node novo = new Node(x, sentinel.prox);
         sentinel.prox = novo;
      }

      public int retiraPrimeiro()
      {
         //retira elemento da ultima posicao da lista e o retorna
         int val = -1;
         if (!isEmpty())
         {
            val = sentinel.prox.value;
            Console.WriteLine("\nRetirando primeiro elemento: {0}", val);
            sentinel.prox = this.sentinel.prox.prox;
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void retiraTodos(int x)
      {
         // remove todas as ocorrencias de x da lista
         Node p = sentinel;
         Node q = sentinel.prox;

         if (!isEmpty())
         {
            Console.WriteLine("\nRemovendo todos os valores {0}", x);
            while (q != this.sentinel)
            {
               if (q.value == x)
               {
                  p.prox = q.prox;
                  q = q.prox;
               }
               else
               {
                  p = p.prox;
                  q = q.prox;
               }
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public int pesquisa(int x)
      {
         // pesquisa se um elemento esta na lista.
         // caso afirmativo, retorna o elemento. Caso contrario, retorna -1.
         Console.WriteLine("\nPesquisando elemento {0}... ", x);
         int val = -1;         
         if (!isEmpty())
         {
            Node q = sentinel;
            while (q.prox != sentinel && q.prox.value != x)
            {
               q = q.prox;
            }

            if (q.prox != sentinel)
               Console.WriteLine("Elemento {0} encontrado!", x);
            else
               Console.WriteLine("Elemento nao encontrado!", x);

         }
         else
            Console.WriteLine("A lista esta vazia!");
         return val;
      }

      public int final()
      {
         //retorna o ultimo elemento da lista
         int val = -1;
         if (!isEmpty())
         {         
            val = ultimo.value;
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void imprime()
      {
         //imprime a lista
         if (!isEmpty())
         {
            Console.WriteLine("\nA lista esta assim:\n ");
            Node p = sentinel;
            while (p.prox != sentinel)
            {
               Console.Write("  {0}", p.prox.value);
               p = p.prox;
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Lista L = new Lista();

         L.insere(6);
         L.insere(5);
         L.insere(8);
         L.insere(34);
         L.insere(56);
         L.insere(98);
         L.insere(6);
         L.retira(5);
         L.retira(56);
         L.retira(8);
         L.insere(20);
         L.inserePrimeiro(33);
         L.insere(77);
         L.insere(6);

         L.imprime();
         Console.ReadLine();

         Console.WriteLine("\nUltimo item da lista: " + L.final());
         L.retiraPrimeiro();
         L.pesquisa(98);
         L.pesquisa(79);
         L.retiraTodos(6);
         L.imprime();

         Console.WriteLine("\n");
         Console.ReadLine();
      }
   }
}

Lista Duplamente Encadeada Circular (LDEC)

Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace Aula_LDEC
{
   class Node
   {
      public int value;
      public Node prev, next;

      public Node(int v, Node p, Node n)
      {
         value = v;
         prev = p;
         next = n;
      }

      public Node criaLista()
      {
         // construtor padrao, inicializa sentinel
         Node sentinel = new Node(0, null, null);
         sentinel.prev = sentinel;
         sentinel.next = sentinel;
         return sentinel;
      }

      public bool isEmpty(Node sentinel)
      {
         // verifica se a lista esta vazia
         return (sentinel.prev == sentinel && sentinel.next == sentinel);
      }

      public void insereFinal(Node sentinel, int x)
      {
         // insere um node no fim da lista
         Console.WriteLine("Inserindo {0} no final ", x);

         Node novo = new Node(x, sentinel.prev, sentinel);
         sentinel.prev.next = novo;
         sentinel.prev = novo;
      }

      public void insereOrdenado(Node sentinel, int x)
      {
         // insere um node ordenadamente
         Console.WriteLine("Inserindo {0} em ordem ", x);
         Node p = sentinel.next;
         while (p != sentinel && p.value < x)
            p = p.next;

         Node novo = new Node(x, p.prev, p);
         p.prev.next = novo;
         p.prev = novo;
      }

      public void inserePrimeiro(Node sentinel, int x)
      {
         //insere elemento na primeira posicao da lista (na frente)
         Console.WriteLine("Inserindo {0} no inicio ", x);

         Node novo = new Node(x, sentinel, sentinel.next);
         sentinel.next.prev = novo;
         sentinel.next = novo;
      }

      public void remove(Node sentinel, int x)
      {
         // retira o node cujo value e igual x da lista
         if (!isEmpty(sentinel))
         {
            Node q = sentinel.next;
            while (q != sentinel && q.value != x)
               q = q.next;

            if (q != sentinel)
            {
               Console.WriteLine("Retirando elemento {0}!", x);
               Node a = q.prev;
               Node b = q.next;
               a.next = b;
               b.prev = a;
            }
            else
               Console.WriteLine("Elemento {0} nao existe!", x);
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public int removePrimeiro(Node sentinel)
      {
         //retira elemento da ultima posicao da lista e o retorna
         int val = -1;
         if (!isEmpty(sentinel))
         {
            val = sentinel.next.value;
            Console.WriteLine("\nRetirando primeiro elemento: {0}", val);
            sentinel.next = sentinel.next.next;
            sentinel.next.prev = sentinel;
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void removeTodos(Node sentinel, int x)
      {
         // remove todas as ocorrencias de x da lista
         Node p = sentinel;
         Node q = sentinel.next;

         if (!isEmpty(sentinel))
         {
            Console.WriteLine("\nRemovendo todos os valores {0}", x);
            while (q != sentinel)
            {
               if (q.value == x)
               {
                  p.next = q.next;
                  q.prev = p;
                  q = q.next;
               }
               else
               {
                  p = p.next;
                  q = q.next;
               }
            }
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }

      public int pesquisa(Node sentinel, int x)
      {
         // pesquisa se um elemento esta na lista.
         // caso afirmativo, retorna o elemento. Caso contrario, retorna -1.
         Console.WriteLine("\nPesquisando elemento {0}... ", x);
         int val = -1;
         if (!isEmpty(sentinel))
         {
            Node q = sentinel;
            while (q.next != sentinel && q.next.value != x)
               q = q.next;

            if (q.next != sentinel)
               Console.WriteLine("Elemento {0} encontrado!", x);
            else
               Console.WriteLine("Elemento nao encontrado!", x);
         }
         else
            Console.WriteLine("A lista esta vazia!");
         return val;
      }

      public int final(Node sentinel)
      {
         //retorna o ultimo elemento da lista
         int val = -1;
         if (!isEmpty(sentinel))
         {
            val = sentinel.prev.value;
            Console.WriteLine("\nUltimo item da lista: " + val);
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
         return val;
      }

      public void imprime(Node sentinel)
      {
         //imprime a lista
         if (!isEmpty(sentinel))
         {
            Console.WriteLine("\nA lista esta assim:\n ");
            Node p = sentinel.next;
            while (p != sentinel)
            {
               Console.Write("  {0}", p.value);
               p = p.next;
            }
            Console.WriteLine("");
         }
         else
            Console.WriteLine("\nA lista esta vazia!");
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Node lista = new Node(0, null, null);
         lista = lista.criaLista();

         lista.insereOrdenado(lista, 6);
         lista.insereOrdenado(lista, 5);
         lista.insereOrdenado(lista, 8);
         lista.insereOrdenado(lista, 34);
         lista.insereOrdenado(lista, 56);
         lista.insereOrdenado(lista, 98);
         lista.insereOrdenado(lista, 6);
         lista.insereOrdenado(lista, 20);
         lista.insereOrdenado(lista, 33);
         lista.insereOrdenado(lista, 77);
         lista.insereOrdenado(lista, 6);

         lista.imprime(lista);
         Console.ReadLine();

         lista.remove(lista, 8);
         lista.remove(lista, 5);

         lista.imprime(lista);
         Console.ReadLine();

         lista.removePrimeiro(lista);
         lista.pesquisa(lista, 98);
         lista.pesquisa(lista, 79);
         lista.removeTodos(lista, 6);
         lista.imprime(lista);

         Console.WriteLine("\n");
         Console.ReadLine();
      }
   }
}

Qualquer dúvida, postem aqui no fórum, procurem monitoria ou me chamem no MSN.
Aproveitem.

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Ajuda para o trabalho de Listas

Mensagem por Evandro Abu Kamel em Sex 09 Out 2009, 20:03

Olá pessoal, estou ouvindo muita gente com dificuldades em relação ao TP02.
Então vou dar umas dicas rápidas sobre os exercícios para LSEC e LDEC.
E vale lembrar que é bom verificar, antes de executar estas operações, se a lista está ou não vazia, pois se ela estiver vazia, não é possível fazer nada (a não ser inserir elementos).
Vamos lá...


-> LSEC:

- Verificar se a lista está em ordem crescente:

Primeiramente, devemos usar uma variável booleana que armazenará o estado da lista, ordenada ou não.
Vamos pressupor que ela esteja ordenada, "estado = true"; vamos percorrer a lista até o final ou enquanto o estado da lista for ordenado. Dentro dessa repetição, vamos verificar se o valor de um nodo é maior que seu próximo; caso isso aconteça, a lista já estará desordenada, então mudaremos o valor da variável de estado para "false", logo a lista não será mais percorrida. Ao final é só retornar a variável de estado.


- Imprime os valores dos elementos com valor maior que seu antecessor:

Esse é bem simples, apenas percorrer a lista até o penúltimo nodo e, dentro da repetição, imprimir uma mensagem qualquer caso o valor que está sendo percorrido for menor que seu sucessor.


- Inverter a ordem dos elementos da lista:

Agora sim! Muita gente está quebrando a cabeça pra fazê-lo. Smile
Uma das formas de se fazer isso é usando o conceito de pilhas e aquele exercícios que fizemos sobre Pilha e Fila.
A lógica é a seguinte: repetir os passos a seguir até que a lista original esteja vazia. Criamos um nodo temporário e a ele atribuímos o primeiro elemento da lista original, removendo-o da mesma; em seguida, inserimos esse nodo temporário no início de uma nova lista temporária, assim, essa a cada inserção, os elementos já inseridos serão empurrados para o final, e a lista temporária está na ordem inversa a original.
Mas a forma como isso será feito é por conta de vocês, quebrem a cabeça mais um pouco, para evitar cópias e suas consequências.


-> LDEC:

- Verificar se a lista está em ordem crescente: Vide explicação anterior.


- Remover os elementos cujo valor seja igual a soma dos valores de seu antecessor com seu sucessor:

Começaremos percorrendo a lista a partir do segundo nodo depois do sentinela até o penúltimo. Dentro da repetição, caso o valor atual seja igual a soma de seu antecessor com seu sucessor, removeremos esse nodo atual apenas encadeando (nos dois sentidos) seu antecessor com seu sucessor através de seus apontadores.


- Inverte a ordem dos elementos da lista:

Pode ser feito da mesma forma que na LSEC, mas quem achar alguma forma melhor, fique a vontade.


- Remover os elementos ímpares e retornar a lista invertida:

A lógica dele é bem simples. Podemos criar uma lista "resultado" dentro do método e percorrer a lista original normalmente até o final. Caso o nodo atual seja par, vamos inseri-lo na primeira posição da lista "resultado", assim ela terá nenhum elemento ímpar e está invertida.


- Remove a ultima ocorrência do maior elemento:

Este já é um pouco mais complexo. Nosso nodo "p" que percorre a lista deve começar com o primeiro elemento após o sentinela, e precisaremos de mais dois nodos auxiliares "axuA" e "auxB", e, é claro, uma variável inteira "maior" que receberá o maior valor da lista, ela começará com 0.
Antes da repetição, iremos criar os dois nodos auxiliares e a eles atribuir "p.prev" e "p.next" respectivamente. Agora sim vamos percorrer a lista até o final. Dentro da repetição vamos verificar se o valor de "p" é maior ou igual ao valor da variável "maior" (pois assim chegaremos ao último maior elemento), e as variáveis auxiliares receberão os mesmos valores com que foram iniciadas, "p.prev" e "p.next" respectivamente.
Fora da comparação, mas ainda dentro da repetição, avançamos o nodo "p" para o próximo nodo da lista (como de costume).
Agora sim, fora da repetição, os nodos auxiliares estão apontando para o último maior elemento pelos dois lados (sentidos), assim, é só fazer o encadeamento entre eles e exibir o valor retirado ("maior") numa simples mensagem de texto. E é isso. Smile


Bom pessoal, espero que isso ajude quem está com dúvidas ou que não faz idéia de como fazer.
Quem precisar pode me chamar na sala ou aqui no fórum mesmo.
Já estou livre dos trabalhos de AED. Cool
Depois escrevo sobre o TP03 no tópico Algoritmos de Ordenação.

Até mais.

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum