lista dinamica

[brian_e]

debo hacer un nuevo proyecto, reproductor.

en los requerimientos de programacion me han restringido el uso de vectores estaticos y objetos que permitan manejar arreglos dinamicos.

como seria un vector estatico y un arreglo dinamico??

bueno, y para reemplazar esto el enunciado dice que debo usar exclusivamente lista dinamica...

podria darme alguien un ejemplo de cada uno de estos...

[Sk9ITk5Z]

como seria un vector estatico y un arreglo dinamico??

sencillo un vector estatico es aquel que no puedes modificar su tamaño osea como lo decalraas esa longitud va tener y el vector dinamico es aquel que puedes modificar su tamaño osea que se le puede asignar memoria dinamica de la pc...
estatico

Código [Seleccionar] Expandir


int v[5];
int i;
for (i=0 ; i<5 ; i++)
{
    v[i] = 2*i;
}



Dinamico

Código [Seleccionar] Expandir



#include <vector>

vector<int> v; // Si no se especifica el tamaño inicial es 0

for (int i=0 ; i<5 ; i++)
{
    v.push_back(2*i);
}


[juancho77]

Con lista dinamica se me ocrçurre que deben hacer referencia a Lista Enlazadas. Estas son TDA's organizados como si fuera un arreglo, pero en forma de nodos interconectados. Cada nodo mantiene una referencia de posesion y posicion, y asi se mantienen ordenados en la lista "simulada". Como son nodos, puede agregar cuantos quieras (el poder lo limita la memoria de la pc) y puedes agrandar, achicar, agregar, remover, editar, dinamicamente (en ejecucion)
Consulta un libro de Estructuras de Datos para Java o C++ (generalmente se llaman Data Structures and Algorithms y los encuentras en la biblioteca de la universidad).

[brian_e]

muchas gracias por sus respuestas...al final he entendido esto de crear nodos.

bueno he aqui el codigo que he generado

Lista.java

Código [Seleccionar] Expandir


/**
*@author Brian Estrada - USAC Guatemala
*/
import java.util.*;

public class Lista{
private Nodo lista;
private int tamano;

public Lista(){
lista = new Nodo();
tamano = 0;
}

public int getTamano(){
return tamano;
}

public void agregar(Object objeto){
Nodo padre = lista;
Nodo nuevo = new Nodo();

for (int i = 0;i<tamano;i++)
padre = padre.getHijo();

nuevo.setObjeto(objeto);
nuevo.setPadre(padre);
nuevo.getPadre().setHijo(nuevo);
tamano++;
}

public void agregar(Object objeto, int indice) throws NullPointerException{
Nodo padre = lista;
Nodo nuevo = new Nodo();

for (int i = 0;i<indice;i++)
padre = padre.getHijo();

nuevo.setObjeto(objeto);
nuevo.setPadre(padre);
nuevo.setHijo(padre.getHijo());
nuevo.getHijo().setPadre(nuevo);
nuevo.getPadre().setHijo(nuevo);
tamano++;
}

public void agregar(Lista lista){
if (lista.getTamano()>0){
Nodo padre = this.lista;

for (int i = 0;i<tamano;i++)
padre = padre.getHijo();

padre.setHijo(lista.getLista().getHijo());
padre.getHijo().setPadre(padre);

tamano += lista.getTamano();
}
}

public void agregar(Lista lista, int indice){
if (lista.getTamano()>0){
Nodo padre1 = this.lista;
Nodo padre2 = lista.getLista();

for (int i=0;i<indice;i++)
padre1 = padre1.getHijo();

for (int i=0;i<lista.getTamano();i++)
padre2 = padre2.getHijo();

padre2.setHijo(padre1.getHijo());
padre1.setHijo(lista.getLista().getHijo());
tamano += lista.getTamano();
}
}

public Object getObjeto(int indice) throws NullPointerException{
Nodo padre = lista;
for (int i=0;i<indice;i++)
padre = padre.getHijo();

return padre.getHijo().getObjeto();
}

public Nodo getLista(){
return lista;
}

public void setLista(Nodo lista, int tamano){
this.lista = lista;
this.tamano = tamano;
}

public Lista getSubLista(int indice, int tamano)throws Exception{
Lista lista = new Lista();
Nodo padre = this.lista;
Nodo aux;

for (int i = 0;i<indice;i++)
padre = padre.getHijo();

aux = (Nodo)padre.clone();
aux.setPadre(null);

padre = aux;

for (int i=0;i<tamano;i++)
padre = padre.getHijo();

padre.setHijo(null);

lista.setLista(aux,tamano);
return lista;
}

public void remover(int indice){
Nodo padre = lista;

for (int i = 0;i<indice;i++)
padre = padre.getHijo();

if (indice<(tamano-1)){
padre.getHijo().setObjeto(padre.getHijo().getHijo().getObjeto());
padre.getHijo().setHijo(padre.getHijo().getHijo().getHijo());
}
else
padre.setHijo(null);
--tamano;
}
public void remover(int indice,int tamano){
Nodo padre1 = lista;
Nodo padre2;

for (int i = 0;i<indice;i++)
padre1 = padre1.getHijo();

padre2 = padre1;

for (int i=0;i<tamano;i++)
padre2  = padre2.getHijo();

padre1.setHijo(padre2.getHijo());
this.tamano -= tamano;
}
public void removerTodo(){
lista.setHijo(null);
tamano = 0;
}
public void barajar(){
Random rnd = new Random();
Lista nuevaLista = new Lista();
int i;
while(tamano>0){
i = rnd.nextInt(tamano);
nuevaLista.agregar(getObjeto(i));
remover(i);
}
agregar(nuevaLista);
}


public void setOrden(Lista orden){
int posicion;
Lista lista = new Lista();
for (int i = 0;i<tamano;i++){
posicion = ((OrdenLista)orden.getObjeto(i)).getIndice();
lista.agregar(getObjeto(posicion));
}
removerTodo();
setLista(lista.getLista(),lista.getTamano());
}
}


class OrdenLista{
private int indice;
private int valor;
public OrdenLista(int valor,int indice){
this.indice =indice;
this.valor = valor;
}
public int getIndice(){
return indice;
}
public int getValor(){
return valor;
}

public static void ordenar(Lista lista,int inicio,int fin){
//quicksort
int i = inicio - 1;
int j = fin;
OrdenLista aux;

if (i>=j)
return;

int pivote = ((OrdenLista)lista.getObjeto(fin)).getValor();
while (true){
while (i<fin && ((OrdenLista)lista.getObjeto(++i)).getValor() < pivote);
while (j>inicio && ((OrdenLista)lista.getObjeto(--j)).getValor() > pivote);
if (i<j){
aux = (OrdenLista)lista.getObjeto(i);
lista.agregar(lista.getObjeto(j),i);
lista.remover(i+1);
lista.agregar(aux,j);
lista.remover(j+1);
}
else break;
}
aux = (OrdenLista)lista.getObjeto(i);
lista.agregar(lista.getObjeto(fin),i);
lista.remover(i+1);
lista.agregar(aux,fin);
lista.remover(fin+1);

ordenar(lista,inicio,i-1);
ordenar(lista,i+1,fin);
}
}



Nodo.java

Código [Seleccionar] Expandir


/**
*@author Brian Estrada - USAC Guatemala
*/
public class Nodo implements Cloneable {
private Nodo padre;
private Nodo hijo;
private Object objeto;

public Nodo(){
padre = null;
hijo = null;
objeto = null;
}
public Object getObjeto(){
return objeto;
}
public void setObjeto(Object objeto){
this.objeto = objeto;
}
public Nodo getPadre(){
return padre;
}
public void setPadre(Nodo padre){
this.padre = padre;
}
public Nodo getHijo(){
return hijo;
}
public void setHijo(Nodo hijo){
try{
if (hijo!=null)
this.hijo = (Nodo)hijo.clone();
else
this.hijo = null;
}
catch(CloneNotSupportedException e){
System.out.println("error en nodo");
}
}
public Object clone() throws CloneNotSupportedException{
Nodo clone = (Nodo)super.clone();
return clone;
}
}



Ejemplo:

Código [Seleccionar] Expandir


Lista lista = new Lista();
    lista.agregar(new Cancion(1,"A"));
    lista.agregar(new Cancion(3,"B"));
    lista.agregar(new Cancion(2,"C"),1);
    lista.agregar(new Cancion(4,"D"));
   
    lista.barajar();
   
    Lista orden = new Lista();   
    for(int i=0;i<4;i++)
    orden.agregar(new OrdenLista(((Cancion)lista.getObjeto(i)).getDuracion(),i));
       
    OrdenLista.ordenar(orden,0,orden.getTamano()-1);
   
    for (int i = 0;i<lista.getTamano();i++)
    System.out.println(((Cancion)lista.getObjeto(i)).getTitulo());
   
    System.out.println();
   
    lista.setOrden(orden);
   
    System.out.println();
    for (int i = 0;i<lista.getTamano();i++)
    System.out.println(((Cancion)lista.getObjeto(i)).getTitulo());
   
  lista.remover(0,2);
 
  System.out.println();
    for (int i = 0;i<lista.getTamano();i++)
    System.out.println(((Cancion)lista.getObjeto(i)).getTitulo());



Explicacion:

Lista
Antes...
•   El tamaño esta dado desde 1, esto quiere decir que si contiene 5 elementos el tamaño será 5.
•   El índice inicia en 0, por lo tanto si contiene 5 elementos, para tener acceso al primero se hará con el índice 0 y para tener acceso al ultimo con índice 4.
agregar(Object objeto)
Se agregara el objeto al final del listado.
agregar(Object objeto,int indice)
Se agregara el objeto en el índice especificado.
agregar(Lista lista)
Se agrega una lista al final de la lista en la que se emplea este método.
agregar(Lista lista,int indice)
Se agrega una lista en el índice seleccionado de la lista en la que se emplea este método.
getObjeto(int indice)
Retorna el objeto que se encuentra en el índice seleccionado, y hace un retorno de tipo objeto al cual solo se le debe hacer un cast para poder emplearlo. Retorna Object.
getLista()
   Retorna el nodo lista donde se almacena toda la información. Retorna Nodo.
setLista(Nodo lista,int tamano)
Asigna a lista global la lista, y tamaño de la lista. Otra forma de agregar una lista que reemplaza a otra. Tienen un mejor desempeño.
getSubLista(int indice,int tamaño)
Retorna una sublista de la lista en la que se llama este método que va desde índice hasta índice+tamaño. Retorna tipo Lista.
remover(int índice)
   Remueve el objeto que ocupa la posición índice.
remover(int índice,int tamaño)
   Remueve todos los objetos comprendidos entre índice e índice+tamaño.
removerTodo()
   Elimina todos los objetos.
barajar()
   Reordena los objetos de forma aleatoria.
setOrden()
   Ordena los objetos como lo indique la clase OrdenLista.
 
OrdenLista
Antes...
•   El ordenamiento se efectúa de forma ascendente.
•   valor -  es el valor que se tomara como criterio de ordenamiento
•   índice - contiene el valor de índice que lleva el orden
ordenar(Lista lista, int inicio, int fin)
        Ordena la lista con el algoritmo de quicksort en versión de recursión.
 

les debo la explicacion de nodo, porque ya es muy tarde y tengo sueño...

aprovechenlo bien por favor, me tomo 2 dias de quebradera de cabeza....

[er_rafael_rafi]

Todo eso lo hace la clase de JAVA LinkedList...pero asi te has enterado bien de como funcionan(yo tambien tengo mi lista propia con las modificaciones que me parecieron)...

Saludos

[brian_e]

  gracias por la informacion seguramente en el futuro me servira.

En realidad tuve que hacerlo de esta manera pues me pedian como requisito de programacion que yo creara mi propia lista dinamica.

[juancho77]

Todo eso lo hace la clase de JAVA LinkedList...pero asi te has enterado bien de como funcionan(yo tambien tengo mi lista propia con las modificaciones que me parecieron)...

Saludos

En la universidad hay toda una materia llama Estructuras de Datos dedicada al estudio de eso que Java ya manda creado. 

[er_rafael_rafi]

Si claro, las Listas, Pilas y Colas, donde en java se llaman LinkedList, Stack(Pila), Queoe(o algo asi para las Colas), todo ello contenido en el paquete java.util

Saludos

[thurgrim]

También es muy util la clase vector (del mismo paquete, java.util). Es como una array normal (se accede igual a los elementos), solo que cuando se llena, reserva más memoria dinámicamente de forma automática.