Stawer Fórum
Seja bem-vindo ao Stawer Fórum,
Aqui você encontra tudo oque precisa, desde Games à Informática.
Para melho visualização do conteúdo do fórum, Registre-se!

Atenciosamente,
Administração Stawer Fórum.
Stawer Fórum
Últimos assuntos
» Template More Create [Blogger]
Dom Set 14, 2014 4:27 pm por artursk

» Banner Editável !
Dom Set 07, 2014 7:57 pm por raposa

» Template ATR Habbo - Plataforma Blogger
Ter Nov 12, 2013 6:17 pm por -Crash

» Fundo blog
Sex Out 04, 2013 4:40 pm por Universal

» apresentaçao
Qui Jul 18, 2013 6:07 pm por digitalradio

» [TEMPLATE] Cria Habbos [TEMPLATE]
Sab Abr 27, 2013 10:55 am por Abusado

» Template do HabbMenta
Seg Mar 18, 2013 6:35 pm por Lolinaa

» Codigo selecione o fundo para blog 2013
Sab Jan 05, 2013 9:22 am por loko-poko

» Template blog habbo editado pelo the pixelando
Qua Jan 02, 2013 11:05 am por loko-poko

Os membros mais ativos do mês


Você não está conectado. Conecte-se ou registre-se

[tuto][estrutura de dados]lista encadeada.

Ver o tópico anterior Ver o tópico seguinte Ir em baixo  Mensagem [Página 1 de 1]

#1 [tuto][estrutura de dados]lista encadeada. em Qui Out 13, 2011 3:40 pm

Tuto de listas (linear e ordenada) encadeadas.

Difículdade:
Básico

Índice:
1. Lista linear
2. Vantagens e desvantagens
3. Lista ordenada
4. Nodo ou Nó
5. Sources

Lista linear

Lista linear é uma estrutura de dados dinâmica cujos elementos estão organizados de maneira seqüencial. São estruturas flexíveis , que podem crescer ou diminuir durante a execução do programa, de acordo com a demanda.

Operações mas freq
üentes em listas:
°Iniciar/Criar/Instanciar uma lista linear vazia.
°Verificação do estado da lista: vazia ou cheia.
°Inclusão de elemento em uma posição específica;
°Remoção e retorno do elemento em uma posição específica;
°Consulta a um elemento em uma posição específica
°Alteração de um elemento de uma posição específica
°Busca de um elemento na lista
°Ordenação dos elementos da lista
°Fazer uma cópia da lista
°Mostrar a lista


Tipos de implementações de Listas:
1. Implementação seq
üencial:
um
vetor é utilizado para armazenar os elementos da estrutura. Vemos
abaixo a representação gráfica de uma lista com 4 elementos armazenada
em um vetor de capacidade para até 10 elementos.

Expandir esta imagemReduzir esta imagem Ver em tamanho real

2. Implementação encadeada
Os
elementos são armazenados em nodos que têm um campo que aponta para o
próximo elemento da lista. Vemos abaixo a representação gráfica de uma
lista vazia e de uma lista com 4 elementos encadeados.

Expandir esta imagemReduzir esta imagem Ver em tamanho real


Vantagens e desvantagens do encadeamento em relação á implementação sequencial:

°Desvantagens
1. Acesso indireto aos elementos
2. Tempo variável para acessar os elementos (depende da posição do elemento)
3. Gasto de memória maior pela necessidade de um novo campo para o ponteiro

°Vantagens
1. A inserção e remoção de elementos podem ser feitas sem deslocar os itens seguintes da lista
2.Não há necessidade de previsão do número de elementos da estrutura,o espaço necessário é alocado em tempo de execução
3. Facilita o gerenciamento de várias listas (fusão,divisão,...)

Listas ordenadas

São
listas lineares onde os elementos estão ordenados segundo um critério
preestabelecido. As remoções são realizadas de qualquer posição,mas as
inserções são feitos de modo que cada novo elemento a ser inserido
ocupará a posição que mantenha os elementos ordenados.Essa ordenação é
mantida para facilitar a busca de elementos na lista.

Operações mas frequentes em listas:
°Iniciar/Criar uma lista linear vazia (Construtor)
°Verificação do estado da lista: Vazia ou Cheia
°Inclusão de elemento
°Remoção e retorno do elemento em uma posição específica
°Busca de um elemento na lista (Busca Binária só na implementação sequencial)
°Fazer uma cópia da lista
°Mostrar Lista

Implementação sequencial de uma lista ordenada
Representação gráfica

Expandir esta imagemReduzir esta imagem Ver em tamanho real

Implementação encadeada de uma lista ordenada (encadeamento com nodos cabeça e sentinela)

Expandir esta imagemReduzir esta imagem Ver em tamanho real

Não há possibilidades de eu terminar esse tuto sem explicar o "esqueleto" da encadeação.

Nodo ou Nó

Um
nodo ou nó representa cada ponto de inter-conexão com uma estrutura ou
rede,independente da função do equipamento representado por ele. Em
ciência da computação,nodo ou nó também pode representar um elemento de
uma árvore de busca binária ou um vértice de um grafo (BY WIKIPÉDIA)
Resumindo de uma forma bem vulgar,nodo é um elemento da lista encadeada.

Nodo cabeça:
Um
nodo cabeça é um nodo extra,mantido sempre na primeira posição de uma
lista encadeada.Ele não é usado para armazenar um elemento da
lista,tendo como único objetivo simplificar as funções de inserção e
remoção da lista. No caso de uma lista numérica ele pode ser usado para
, por exemplo, armazenar o número de elementos na lista

Nodo Sentinela
Um
nodo sentinela também é um nodo extra,mantido na última posição com o
mesmo objetivo do nodo cabeça.Seu valor não faz parte da lista.Muitas
vezes ele armazena o maior valor (HV - High Value) para o tipo
armazenado.Isso simplifica,Ainda mas,os processos de inserção e remoção

Sources
Lista sequencial
Spoiler:class ListaDeInteiros {
private
int nel;
private
int ele[];

public
ListaDeInteiros() {
nel = 0;
ele = new int[10];
}

public
ListaDeInteiros(int cap) {
nel = 0;
if(
cap < 10)
ele = new int[10];
else
ele = new int[cap];
}

public
ListaDeInteiros(ListaDeInteiros lis)
{
nel = lis.nel;
ele = new int[lis.ele.length];
System.arraycopy(lis.ele, 0, ele, 0, nel);
}

public
boolean estaVazia()
{
return
nel == 0;
}

public
boolean estaCheia()
{
return
nel == ele.length;
}

public
int getNel() {
return
nel;
}

public
void insereNoFinal(int val)
{
ele[nel++] = val;
}

public
void insereNoInicio(int val)
{
for(
int i=nel; i>0; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[0] = val;
nel++;
}

public
void insereNoIndice(int val, int ind)
{
for(
int i=nel; i>ind; i--) // Deslocamento de dados
ele[i] = ele[i-1];
ele[ind] = val;
nel++;
}

public
int removeDoFinal()
{
return
ele[--nel];
}

public
int removeDoInicio()
{
int res = ele[0];
for(
int i=0; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return
res;
}

public
int removeDoIndice(int ind)
{
int res = ele[ind];
for(
int i=ind; i<nel-1; i++)
ele[i] = ele[i+1];
nel--;
return
res;
}

public
int busca(int val)
{
for(
int i=0; i<nel; i++)
if(
ele[i] == val)
return
i;
return -
1;
}

public
void remove(int val)
{
int rb = busca(val);
if(
rb > -1)
removeDoIndice(rb);
}

public
void removeTodos(int val)
{
int i = 0;
while(
i < nel)
{
if(
ele[i] == val)
removeDoIndice(i);
else
i++;
}
}

@
Override
public String toString() {
if(
estaVazia()) return "[]";
String res = "[";
for(
int i=0; i<nel-1; i++)
res += ele[i]+", ";
return
res+ele[nel-1]+"]";
}

}



Lista encadeada
Obs: por motivos de preguiça,tempo e burrice (no final do tópico explico porque da burrice) está sem nodo cabeça e sentinela
Spoiler:public class ListaEncadeada<E extends Object & Comparable> {
private
Nodo<E> lis;

/**
* Construtor padrão da classe. Cria uma
* lista vazia.
*/
public ListaEncadeada()
{
lis = null;
}

public
boolean estaVazia()
{
return
lis == null;
}

public
boolean estaCheia()
{
return
false;
}

public
int getNel()
{
Nodo<E> p = lis;
int res = 0;
while(
p != null)
{
res++;
p = p.pro;
}
return
res;
}

public
void insereNoInicio(E val)
{
Nodo<E> nn = new Nodo<E>(val, lis);
//nn.pro = lis;
lis = nn;
}

public
void insereNaPosicao(E val, int pos)
{
if(
pos == 1)
insereNoInicio(val);
else
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(
pos > 2)
{
p = p.pro;
pos--;
}
nn.pro = p.pro;
p.pro = nn;
}
}

public
void insereNoFinal(E val)
{
Nodo<E> nn = new Nodo<E>(val);
Nodo p = lis;
while(
p.pro != null)
{
p = p.pro;
}
nn.pro = p.pro;
p.pro = nn;
}

public
E removeDoInicio()
{
E res = lis.val;
lis = lis.pro;
return
res;
}

public
E removeDaPosicao(int pos)
{
if(
pos == 1)
return
removeDoInicio();
else
{
Nodo<E> p = lis;
while(
pos > 2)
{
p = p.pro;
pos--;
}
E res = p.pro.val;
p.pro = p.pro.pro;
return
res;
}
}

public
Nodo<E> busca(E val)
{
Nodo<E> p = lis;
while(
p != null)
{
if(
p.val.compareTo(val) == 0)
return
p;
p = p.pro;
}
return
null;
}

public
void remove(E val)
{
if(
lis.val.compareTo(val)== 0)
{
lis = lis.pro;
}
else
{
Nodo<E> p = lis;
while(
p.pro != null && p.pro.val.compareTo(val) != 0)
p = p.pro;
if(
p.pro != null)
p.pro = p.pro.pro;
}
}

public
void removeTodos(E val)
{
while(
busca(val) != null)
remove(val);
}

public
void ordena()
{
Nodo<E> i = lis;
while(
i.pro != null)
{
Nodo<E> pm = i;
Nodo<E> j = i.pro;
while(
j != null)
{
if(
j.val.compareTo(pm.val) < 0)
pm = j;
j = j.pro;
}
E aux = i.val;
i.val = pm.val;
pm.val = aux;
i = i.pro;
}

}

@
Override
public String toString() {
if(
estaVazia())
return
"[]";
String res = "[";
Nodo p = lis;
while(
p.pro != null)
{
res += p.val + ", ";
p = p.pro;
}
return
res + p.val + "]";
}
}



Nodo
Spoiler:public class Nodo<T> {
public
T val;
public
Nodo<T> pro;

public
Nodo(T v)
{
val = v;
pro = null;
}

public
Nodo(T v, Nodo p)
{
val = v;
pro = p;
}
}



Fim.

Observações gerais:
*Tutorial usando como referencia NetBeans
*Algumas coisas do tuto fizeram no word e depois passou para cá,porque algumas formatações de texto não sei fazer aqui xd
*Desculpa ser tiver qualquer erro de português
*Qualquer dúvida relacionada ao tópico estárei respondendo =]

**Ahh,
sobre a burrice(citada no tópico) é que estáva fazendo o tuto e sem
querer fechei a página e perdi tudo u.u então fui fazer tudo denovo e
pra agilizar coloquei essa source sem nodo cabeça e sentinela

Espero que tenha ajudado vocês

Créditos: Totalmente de lipinf o/

To aqui para ajudar as pessoas e não para críticar!

Ver perfil do usuário

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo  Mensagem [Página 1 de 1]


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