Estructuras de datos

Memoria Dinámica 

Nodo:
cada nodo sera una estructura o registro que dispondrá de varios campos y al menos uno de esos campos sera un puntero hacia otro nodo.
1. en un lenguaje que implementa POO los nodos son instancias de una clase osea objetos, dado que una clase pude ser intanciada muchas veces, se puede trabajar los nodos como estructuras utilizando la sentencia Struct de c++ pero como se puede observar es mucho mas fácil trabajarlo con objetos.


c++
ejemplo de crear una estructura en c++
esta estructura llamada Nodo contendrá los campos necesarios para el registro y parte de eso contendrá una apuntador o mas dependiendo de la estructura a realizar, en este caso para crear una puntero en c++ se hace de la siguiente forma struct persona *sig;


Codigo struct Nodo{
  int carnet;
  string nombre;
  string apellido;
  string direccion;
  int telefono;
  int edad;
  string sexo;
  struct persona *sig;
};


java y C#
ejemplo de crear una estructura en java
como java es totalmente orientada a objetos vamos a utilizar es ventaja
Codigo class Nodo{
  int codigo
  tring nombre;
  string apellido;
  Nodo sig;
  void Nodo(){
    // aqui vamos a inicial izar las variables
    codigo=0;
    nombre="";
    apellido="";
  }
  // en esta parte pueden ir los metodos que modificaran los campos
  // por ejemplo
  public Nodo dar_siguiente(){
    return sig;
  }
}
PHP
recuerden que en php las variables no tiene un tipo especifico estas aceptan de cualquier tipo

Codigo class Nodo{
var $codigo;
var $nombre;
var $apellido;
Nodo $sig;
    funtion Nodo(){
      codigo=0;
      nombre='';
      apellido='';
    }
funtion dar_siguiente(){
return $sig;
}
}



Lista simplemente ligada
      figura 1
este tipo de lista es la mas simple porque solamente tiene un apuntador hacia siguiente Nodo, claro es muy fácil implementarla, pero como todo tiene sus ventajas y desventajas este tipo de estructura es muy deficiente a la ora de la búsqueda de un registro, suponga que que tenemos una lista de 5,000,000 de registros y el registro que estamos buscando esta en la posición 4,999,999 eso quiere decir que tenemos que comparar 4,999,998 registros ?no se ve tan eficiente verdad? por la razón que primer nodo de la lista es la cabeza desde esa dirección comenzamos la búsqueda.
las ventajas se pueden apreciar a corto plazo, por ejemplo cuando manejamos bases de datos suele suceder que la base se satura por múltiples entradas, una solución seria almacenar al información entrante en una lista simple  luego de cierto tiempo mandar esa colección de datos a la base de datos eso reduciría las operaciones de la base de datos como tal. y asi como estas hay muchas mas funciones.

Crear un nuevo registro o nodo
 c++

Codigo


void insertar(int carnet,string nombre,string apellido,string direccion,int telefono,int edad,string sexo){

    cout << "dato ingresado\n";

    struct Nodo *aux; // asignando un apuntador

    aux=cabeza;  // en te momento temos que ver donde comieza  aux lo          inicializamos con cabeza 

    nuevo = new Nodo; // estamos creando un nuevo nodo  

    nuevo->carnet=carnet; // modificando el valor del campo

    nuevo->nombre=nombre;

    nuevo->apellido=apellido;
    nuevo->direccion=direccion;
    nuevo->telefono=telefono;
    nuevo->sexo=sexo;
    nuevo->edad=edad;
    if(cabeza==NULL){   // preguntamos si cabeza es null si lo es eso significa que la lista esta vacia 
        cabeza=nuevo; // asignamos cabeza como nuevo
        cabeza->sig=NULL; // indicamos que el siguiente de cabeza es null
    }
    else{   // de lo contrario si cabeza no el null eso significa que la lista no esta vacia y tiene que buscar
        // el utlimo nodo ingresado
        do{   
            if(aux->sig==NULL){ // pregunto si ya llego al final de lista
                aux->sig=nuevo;   // le asigno el siguiente del nodo aux a nuevo
                nuevo->sig=NULL;  // indicamos que el siguiente de nuevo es nulo
            } 
            aux= aux->sig;  // decimos que aux va ser igual a el siguiente de el mismo.
        }while(aux!=NULL);   // el while se va repetir mientras aux no sea igual a nulo
    }
}


java

Codigo

void insertar(int carnet,string nombre,string apellido,string direccion,int telefono,int edad,string sexo){

 aux=cabeza;  // en te momento temos que ver donde comieza  aux lo inicializamos con cabeza 

    Nodo nuevo = new Nodo; // estamos creando un nuevo nodo  

      nuevo.cambiar_carnet(carnet); // modificando el valor del campo

      nuevo.cambiar_nombre(nombre);

      nuevo.cambiar_apellido(apellido);

      ...
 ...
 ...
    if(cabeza==NULL){   // preguntamos si cabeza es null si lo es eso significa que la lista esta vacia 
       cabeza=nuevo; // asignamos cabeza como nuevo
       cabeza.cambiar_siguiente(null); // indicamos que el siguiente de cabeza es null
     
    }
    else{   // de lo contrario si cabeza no el null eso significa que la lista no esta vacia y tiene que buscar
                // el utlimo nodo ingresado
        do{   
          if(aux.dar_siguiente()==NULL){ // pregunto si ya llego al final de lista
           aux.cambiar_siguiente(nuevo);   // le asigno el siguiente del nodo aux a nuevo
           nuevo.cambiar_siguiente(NULL);  // indicamos que el siguiente de nuevo es nulo
          } 
           aux= aux.dar_siguiente();  // decimos que aux va ser igual a el siguiente de el mismo.
        }while(aux!=NULL);   // el while se va repetir mientras aux no sea igual a nulo
    }
        
    
}



     figura 2
esto seria el recorrido del apuntador auxiliar(aux)

hasta hora hemos visto código por separado de algunos lenguajes de programación pero con el fin de implementar las buenas practicas vamos a comenzar a trabajar con sudocodigo para poder implementarlos en cualquier lenguaje.

Buscar un registro
para buscar un registro se tiene que recorrer la lista comparando cada uno de los registros con un campo en especifico de registro con otro ingresado por el usuario, pare esto hacemos uso de la figura 2  en la cual se muestra el uso de un apuntador auxiliar que es el que recorre las lista.

Codigo aux=cabeza
hacer{
    si (CampoIngresado= =aux.campo){ //dependiendo que tipo de dato se
                                                            // este comparando asi cambia
                                                              // el método de comparación.
        // imprimir resultado


}

aux=aux.singuiente;
}mientras (aux != null)

nota:
CampoIngresado: el dato que el usuario ingresa como parámetro de busqueda
aux.campo: es el dato que se obtiene al momento analiza un registro o nodo.

Eliminar Registro
pare eliminar una registro se utiliza el método de búsqueda mencionado anteriormente con ligeras modificaciones
inicioCodigo
Codigo
hacer{
    si (CampoIngresado= =aux.campo){ 
       si (aux==cabeza){
cabeza= cabeza.siguiente
cabeza.siguiente=null
cabeza=null;
        }
de_lo_contrario{
ant.siguiente= aux.siguiente
aux.siguiente=null
aux = null
}


}  
ant=aux // ant es un apuntador anterior solo para saber nodo anterior 
aux=aux.singuiente;


}mientras (aux != null) 



    figura 3


 figura 4

La figura 3 muestra el borrado de un registro que es la cabeza
La figura 4 muestra el borrado de un registro al centro  de la lista cualquier parte menos la cabeza

modificación de una registro
la modificación también utiliza como base la búsqueda

  hacer{
    si (CampoIngresado= =aux.campo){ 
       
     // campos a modificar
}  

aux=aux.singuiente;

}mientras (aux != null) 

si entendieron las listas simples el resto de listas solo es manejo de apuntadores con exactamente los mismo códigos, talvez algunos cambios pero no bruscos 


siguientes temas por completar....


lista simplemente ligada circular


crear clase nodo en java

Codigo
class Nodo{
    int codigo
    string nombre;
    string apellido;
    Nodo sig;
    void Nodo(){
        // aqui vamos a inicial izar las variables
        codigo=0;
        nombre="";
        apellido="";
    }
    // en esta parte pueden ir los metodos que modificaran los campos
    // por ejemplo
    public Nodo dar_siguiente(){
        return sig;
    }
}

crear un nuevo registro o nodo
la diferencia entre una lista simplemente ligada y una lista simple ligada circular es el apuntador del ultimo registro de la lista que en lugar de apuntar a hacia null va a apuntar hacia la cabeza el codigo siguiente el el mismo que hicimos en para la lista simplemente ligada.  los cambios va a estar resaltados como amarillo


void insertar(int carnet,string nombre,string apellido,string direccion,int telefono,int edad,string sexo){
 aux=cabeza;  // en te momento temos que ver donde comieza  aux lo inicializamos con cabeza 
    Nodo nuevo = new Nodo; // estamos creando un nuevo nodo  
      nuevo.cambiar_carnet(carnet); // modificando el valor del campo
      nuevo.cambiar_nombre(nombre);
      nuevo.cambiar_apellido(apellido);
      ...
  ...
  ...
    if(cabeza==NULL){   // preguntamos si cabeza es null si lo es eso significa que la lista esta vacia 
       cabeza=nuevo; // asignamos cabeza como nuevo
       cabeza.cambiar_siguiente(cabeza); // indicamos que el siguiente de cabeza va apuntar a cabeza
     
    }
    else{   // de lo contrario si cabeza no el null eso significa que la lista no esta vacia y tiene que  
               //  buscar
                // el utlimo nodo ingresado
        do{   
          if(aux.dar_siguiente()==NULL){ // pregunto si ya llego al final de lista
           aux.cambiar_siguiente(nuevo);   // le asigno el siguiente del nodo aux a nuevo
           nuevo.cambiar_siguiente(cabeza);  // indicamos que el siguiente de nuevo apunta a cabeza
          } 
           aux= aux.dar_siguiente();  // decimos que aux va ser igual a el siguiente de el mismo.
        }while(aux!=cabeza);   // el while se va repetir mientras aux no sea igual a cabeza
    }
        
    
}

eliminar un registro


hacer{
    si (CampoIngresado= =aux.campo){ 
       si (aux==cabeza){
 cabeza= cabeza.siguiente
 cabeza.siguiente=null
 cabeza=null;
        }
de_lo_contrario{
ant.siguiente= aux.siguiente
aux.siguiente=null
aux = null
}


}  


búsqueda de un registro



aux=cabeza
hacer{
    si (CampoIngresado= =aux.campo){ //dependiendo que tipo de dato se
                                                            // este comparando asi cambia
                                                              // el método de comparación.
        // imprimir resultado


}
aux=aux.singuiente;
}mientras (aux != cabeza)




modificación de un registro

hacer{
    si (CampoIngresado= =aux.campo){ 
       
     // campos a modificar
}  

aux=aux.singuiente;

}mientras (aux != cabeza) 





lista doblemente ligada
link tutorial: Tutorial de Lista doblemente Ligada


lista doblemente ligada circular
La lista circular es exactamente igual a la lista doblemente ligada con la unica diferencia que la cabeza de la lista el "apuntador Anterior" apunta hacia el ultimo nodo de la lista y igualmente el ultimo nodo "apuntador siguiente" apunta hacia la cabeza.




Matriz Ortogonal













he visto casos que piden hacer una matriz ortogonal dentro de otra en este tipo de casos es muy facil de resolver normalmete una matriz ortogonal tiene cutro apuntadores "arriba" "abajo" "Derecha" "Izquierda" pero cuando un nodo puede tener una matriz interna entonces se crea un quinto apuntador que es la cabeza principal de la matriz interna en este caso "i" y se coloca como un apuntador más, asi como se dice apunta hacia la direccion de la cabeza principal de la matriz interna.
un ejemplo de clase nodo:

Codigo class Nodo{
    Nodo arriba;
    Nodo abajo;
    Nodo derecha;
    Nodo izquierda;
    Nodo CabezaPrincipal;
    /*este es el quinto apuntador que es la cabeza principal de matriz interna
    esto quiere decir que cada nodo va terner definido un apuntador CabezaPrincipal aunque no la utilice*/
    Nodo(){
        arriba=null;
        abajo=null;
        derecha=null;
        izquierda=null;
        CabezaPrincipal=null;
    }
}



arboles binario
Dado que el arbol binario es facil de enteder desde cualquier texto entonces vamos vamos a poner el siguiente link: Arbol Binario

arboles AVL
Suscribirse a: Entradas (Atom)