Estructura de datos I

17:59 |


ESTRUCTURAS  DINAMICAS

Dinámicas Lineales.-
     -> Listas Enlazadas.- Simples, Dobles, Circulares
-> Pilas
-> Cola
-> Biloca

Dinámicas No Lineales.-
-> Arboles.-Binarios, Binarios De Búsqueda
-> Grafos

La lista enlazada es una estructura de datos dinámicas formada por un conjunto de nodos, conectados atreves de uno enlace (sig.);
Queda definida básicamente al  x Nombre,  enlaza al 1 nodo (elemento) y 1 enlace al último Nodo (elem).
Lista enlazada puede ser movida sobre la memoria y también ser rápidamente serializada para almacenarla en un disco o transferirla sobre una red.
Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista.
Especialmente para una lista pequeña, los arrays indexados pueden ocupar mucho menos espacio que un conjunto de punteros.
La localidad de referencia puede ser mejorada guardando los nodos juntos en memoria y siendo reordenados periódicamente.



Public Class Nodo {
     Object Dato;
     Nodo Enlace;
}
Val1
        Object Dato;
        Nodo Enlace;
}
Val1
        Object Dato;
        Nodo Enlace;
}
Val1
    

1
Public Nodo (Object obj) {
This (obj; null); // SOLO
}
2
Public nodo (Object obj, Nodo sig){
     Dato=obj;
Enlace=sig; // ENLAZADO
}
3
Public getDato () {return Dato ;}
}//fin


Obj

        Object Dato;
        Nodo Enlace;
}
Obj


        Object Dato;
        Nodo Enlace;
}
Obj


        Object Dato;
        Nodo Enlace;
}
Obj

        Object Dato;
        Nodo Enlace;
}
                                                                       Siguiente
                                                           …..     
                 Null



Clase nodo {
Object dato;
0

      Object Dato;
      Nodo Enlace;
}
Nodo sig; // Lista vacia         Dato
Nodo (Object 0) {
Dato = 0;
Sig = null;
}
//-------------------------------------------------------------
Nodo (Object 0, Nodo n) {
Dato = 0;
Sig = n;
} //Lista no vacia
Object getDato () {
Return Dato;
}
Nodo getEnlace () {-}

OPERACIONES.
-INSERTAR
-ELIMINAR
-BUSCAR
-ORDENAR

-Operaciones
-> Constructor
-> Lista Vacia

Constructor
Public Lista (String n) {
     Nombre = n;
     Pri = ult = null;
}
Public boolean ListaVacia () {
     Return ( pri == null);
}

INSERCIONES.-
Frente
Posterior
Pos_n

Insertar al frente.-
La Inserción al Principio básicamente busca si existe algún lugar disponible en el arreglo Info. Y lo agrega como primer Nodo si es que es posible.
Public void InsertarFrente (Object obj){
If (ListaVacia ())
       Prim = ult = null (obj);
Else
Prim=new Nodo (obj, pri);
}
Insertar Posterior.-
La Inserción después de un Nodo Determinado básicamente hace lo mismo que la inserción al principio, la única diferencia es que este recibe la posición del nodo en la que será Insertada. Este Algoritmo se usa para Inserción Ordenada que más adelante
Public void InsPosterior (Object obj) {
If (listaVacia ())
       Prim=ult=new nodo (obj);
Else
       Ult=ult.sig=new nodo (obj);
}
-CONTAR NODO DE UNA LISTA
Public int contnodos () {
  Nodo Actual=Prim; int cont=0;
       While (Actual != null) {
            Cont++;
           Actual=Actual.sig;//avanza
}
Return cont;
  }
}
Insertar Pos_n
Public void insPos_n (object obj, int pos) {
       If (ListaVacia ())
            InsertaFrente ();
       Else {
            If (pos==1){insertaFrente();}
            If (pos==ContElem ()){insertaPosterior;
Else {
           Nodo Actual=Prim;
                For (int i = 0; i <= pos_n; i++){
                Actual=Actual.sig;
                }
                Nodo Nuevo=new Nodo (obj, Actual.sig)
                Actual sig=nuevo;
}
}
}
Public class lista simple {
Private nodo prim;
Private nodo ult;
Private string nombre;
}
Public lista Simple (){
Prim=ult=null;
Nombre=””;
}
Public lista simple (string n){
  Prim = ult = null;
  Nombre = n;
}
Public Boolean ListaVacia () {
  Return prim==null;
}
Public void InsFrente (Object obj) {}
Public void Insposterior (Object obj) {}
Public void insposicion (Object obj, int pos) {}


ELIMINACIONES.-
Eliminar al Frente
Public object DelFrente () {
       If (Listavacia ()) trows excepcion
            Object datoARemover = prim.dato;
       If (prim.equals cult)
            Prim=ult=null;
       Else {
Nodo Actual = prim;
Prim = prim.sig;
Actual.sig=null;
}
Return datoARemover;
}
Eliminar Posterior
     1
If (listaVacia ())
Object DatoARemover = ult.dato;
     2
         If (prim.equals (null))
         Prim=ult=null;
     3
         Else {
              Nodo Actual=pri;
              While (Actual.sig != ult)
                   Actual=Actual.sig;
}
Eliminar Pos_n
     Public void ElemPos_n (Object, int Pos)
         If (listaVacia ()) {ElimFrente () ;}
         Else {
              If (pos==1) {ElimFrente () ;}
              If (pos==cantElem ()) ;{ elemPost () ;}
          Else {
Nodo=Actual=prim;
For (int i=1; i<=Pos_n; i++) {
Actual=Actual.sig;
datoARemover=Pos.Dato;
}
Return DatoaRemover;
}
//PARA ELIMINAR ENTRE MEDIO Y ENLAZAR AL SIGUIENTE
Public object DelPos (int Pos) {
     If (ListaVacia)
     If (Pos == 1) DelFrente () {
          If (Pos == numElemen) DelPosterior ();
          Else {
               Object DatoARemoer
              If (prim.equals (ult)) {
                  Prim = ult = null;
                   Return DatoARemover;
}
Else {
Nodo actual = prim;
For (int i = 1; i <= pos; i++) {
                   Actual = actual.sig;
                  DatoARemover = (actual.sig).Dato
                   (aBorrar.Dato)
                   Actual.sig = (actual.sig).sig;
                   (aBorrar.sig);
                   aBorrar.sig = null;
                   Return DatoARemover;
}
}
}
}
}
//MODIFICACIONES AL FRENTE
Algoritmo completo
Public void update frente (object obj new)
If (listaVacia ())
Else
Prim.Dato = obj new;

//MODIFICACIONES POSTERIOR
Algoritmo completo
Public void update post (object obj)
If (listaVacia ())
Else
ult.Dato = obj;

//MODIFICA LA POSICION
a) Lista Vacia
Lista X
     Null
Algoritmo
System(error)

b) No Vacia
pos  new  elemento
        <>, y <> new  element
Algoritmo
Si  pos = new elem => update  pos (obj  new)<

Actual.dato = object  new;

 Algoritmo completo
Public void update pos (object obj new, int pos) {
If (listaVacia ()) //ERROR
If (pos == 1) updateFrente (obj new);
If (pos == numElemen) update post (object new);
Else {
nodo.actual = prim;
For (int i = 1; I <= pos; i++)
     Actual = actual.sig;
     actual.dato = obj new;
}
}
//MOSTRAR LISTA
Public void mostrarLista () {
     Nodo. Actual = prim;
     While (actual != null)
     Joptionpane (actual.dato)
     Actual = actual.sig;
}


//PILA (STACK)
Una Pila es un lugar donde se almacenan datos, pero una Pila tiene una filosofía de entrada y salida de datos  ultimo en entrar, primero en salir. Esta estructura de datos tiene muchas aplicaciones debido a su simplicidad.
Las pilas suelen emplearse en los siguientes contextos:

Evaluación de expresiones en notación postfija (notación polaca inversa).
Reconocedores sintácticos de lenguajes independientes del contexto
Implementación de recursividad.


Pila (insPosterior, delPosterior)
Class  pila  extends  listaSimple{
     Public  pila() {super (“Pila”);{
     Public  void  push ( object  obj) {
         Inserter  posterior ( obj);
     }
Public  object  pop () { //eliminar
          Return  del  posterior ();
}
Public  void  mostrarPila (){
          mostrarLista ();
}//ultimo  en  entrar  y  primero  en  salir
}


Class  prueba{
     Main () {
          Pila  p=new  pila (“Pila X”);
         p.push (“Ana”);
         p.push (“Juan”);
         p.pop (); // Juan
         p.pop (); //Ana
     }
}
Class  cola  extends  ListaSimple{
     Public  cola () {super (“cola”) ;{  // insertar
         Insertar  posterior (obj);
     }
     Public  object  decolar () {// eliminar
         Return  del  frente ();
     }
     Public  void  mostrar cola (){
         mostrarLista ();
}//  Primero en  entrar  y  primero  en  salir
}


Class  prueba {
     Public  static  void  main(…){
       Cola  c = new cola(“X”);
         c.  encolar  (“Juana”); 
               c.  encolar  (“Ana”); 
                 c.  encolar  (“Pepe”);
                   c.  encolar  (); 
                     c.  encolar  ();


ListaSimple  Lista  X = new  ListaSimple (“ ”);
     // Llenado  de  la  lista  se  asume
     Pila  Lista1 = new  Pila (“P”); 
     Cola  Lista2 = new  Cola (“C”);
     While (object  lista X.ListaVacia ()) {
         Object  obj = ListaX.Del frente ();
         If (obj.estado == “Bueno”)
         Lista1.push (obj);  //insertar  pila
         Else
         Lista2.encolar (obj); // insertar  cola
}
En  el  main  principal
     Int  cod = in….(jop…(“cod”)) ;
     String =b jop…(“Nombre”)
listaEnlazada  L1 = new  ListaEnlazada(“Lista X”)
L1.insfrente (new Estudiante (cod, nom))//insfrente  un objeto
Estudiante  obj:
Obj = (Estudiante) L1.deleteFrente(); //delete frente retorna un objecto
          System…(obj.getcod+obj.getnombre);
*Se  decea  registrar  los  datos  de  10  vendedores
   Nombre, apellido, dirección, fono

Main  principal
     Lista enlazada  L1 = new.ListaEnlazada (“Lista X”);
        For (  int  i = 1; i <= 0; i++){
     String nombre = joption.pane(“Nombre”);
     String apellido = joption.pane(“Apellido”);
     String direccion = joption.pane(“Direccion”);
     String telefono = joption.pane(“Telefono”);

L1.insposterior(new  vendedor (nombre, apellido, direccion, telefono))
     }
}
Vendedor  obj;
For(int  i = 1; i <= 10; i++){
     Obj = (vendedor) L1.deleteposterior();
System.out.println(obj.getnombre()+obj.getapellido()+obj.getdireccion()+
obj.gettelefono());


LISTA DOBLE CIRCULAR
   4
  3
   2
  1
                Sig               sig              sig                         
                             Ant             ant            ant

Realizar el siguiente recorrido
1:  1-2-3-2    = (actual.sig.sig).ant
2:  2-3-4-1-4       = (((actual.sig).sig).sig).ant
3:  1-2-1-4    = (((actual.sig).ant).sig)
Recorrido optimo
4:  1-4       = actual.ant
5:  3-1       = (actual.ant).ant
6:  2-4       = (actual.sig ).sig

Lista Circular
Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.

Class nodoDoble{
     Object  Dato ;
     Nodo sig;
     Nodo ant;
     Public nodoDato () { }
}

Class listaDobleCircular{
     String Nombre;
     Nodo ultimo;
     Nodo actual; // OPCIONAL
}
INSERCIONES
InsUltimo
     Nuevo.sig = ultimo.sig;
     Nuevo.ant = ultimo;
     Ultimo.sig.ant = Nuevo;
     Ultimo.sig = Nuevo;
     Ultimo = Nuevo;
InsPos_n
     Nuevo.sig = actual.sig;
     Nuevo.ant = actual;
     Actual.sig.ant = Nuevo;
     Actual.sig = Nuevo;
Eliminaciones
DeleteUltimo
1 actual.sig = ultimo.sig;
2 actual.sig.ant = actual;
3 ultimo = null;
Ultimo.ant = ultimo.sig = null;
DeletePrimero
     1 actual sig.ant = ultimo;
     2 ultimo.sig = actual.sig;
     3 actual.sig = actual.ant =null;
Del Pos_n
     Aux.sig = actual.sig;
     Actual.sig.ant = aux;
     Actual.sig = actual.ant = null;

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS
Publicado por beverly

1 comentarios:

Liliana Arggiro Soruco dijo...

Trabajo corregido

27 de julio de 2011 a las 13:30

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)