Estructuras dinámicas
Las estructuras dinámicas de datos son estructuras que cuya dimensión puede crecer o disminuir durante la ejecución del programa. Una estructura dinámica de datos es una colección de elementos llamados nodos. Al contrario que un array, que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa.
Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos:
Lineales: listas enlazadas, pilas, colas
No lineales: árboles , grafos
Las estructuras dinámicas de datos son de gran utilidad para almacenar datos del mundo real, que están cambiando constantemente. Por ejemplo si tenemos almacenados en un array los datos de los alumnos de un curso, los cuales estan ordenados de acuerdo al promedio, para insertar un nuevo alumno seria necesario correr cada elemento un espacio: Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del alumno se pueden insertar fácilmente.
Lineales: listas enlazadas, pilas, colas
No lineales: árboles , grafos
Las estructuras dinámicas de datos son de gran utilidad para almacenar datos del mundo real, que están cambiando constantemente. Por ejemplo si tenemos almacenados en un array los datos de los alumnos de un curso, los cuales estan ordenados de acuerdo al promedio, para insertar un nuevo alumno seria necesario correr cada elemento un espacio: Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del alumno se pueden insertar fácilmente.
Listas Enlazadas
Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo.
El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.
El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo.
El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.
El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
La lista enlazada se muestra en la siguiente figura:
Cabecera
Las operaciones que normalmente se ejecutan con listas incluyen:
Las operaciones que normalmente se ejecutan con listas incluyen:
- Recuperar información de un nodo específico.
- Encontrar el nodo que contiene una información específica.
- Insertar un nuevo nodo en un lugar específico.
- Insertar un nuevo nodo en relación a una información particular.
- Borrar un nodo existente.
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
class nodo
{int num;
nodo *sgte;
public:
nodo(){sgte=NULL;}
void apns(nodo *n);
nodo *rpns();
void ingresar();
int mostrar();
};
void nodo::apns(nodo *n)
{sgte=n;}
nodo *nodo::rpns()
{return sgte;}
void nodo::ingresar()
{cin>>num;}
int nodo::mostrar()
{return num;}
/////////////////////////////////////////
class lista
{nodo *cab;
public:
lista(){cab=NULL;}
void insertar_i();
void insertar_f();
void eliminar_nodo();
void mostrar_lista();
void eliminar_i();
void eliminar_f();
void eliminar_lista();
};
void lista::insertar_f()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
{cab=a;}
else
{nodo *temp,*temp1,*temp2;
temp=cab;
while(temp2!=NULL)
{temp1=temp->rpns();
temp2=temp1->rpns();}
temp->rpns();
temp->apns(a);
}
}
void lista::insertar_i()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
cab=a;
else
{nodo *temp;
temp=cab;
cab=a;
cab->apns(temp);
}
}
void lista::mostrar_lista()
{nodo *t;
if (cab==NULL)
cout<<"La lista esta vacia";
else
{t=cab;
while(t!=NULL)
{//t=t->rpns();
cout<<t->mostrar();
t=t->rpns();
}
}
}
void lista::eliminar_nodo()
{nodo *temp,*temp1,*temp2;
temp1=cab;
int numero;
cout<<"ingrese numero a borrar";
cin>>numero;
if(temp1->rpns()==NULL)
cout<<"no hay elementos";
else
{do
{temp=temp1;
temp1=temp1->rpns();
if(temp1->mostrar()==numero)
{temp2=temp1->rpns();
temp->apns(temp2);
delete temp1;
}
}while(temp!=NULL); /////
}}
void lista::eliminar_i()
{if(cab==NULL)
cout<<"\nno existen nodos";
else
{nodo *temp;
temp=cab;
cab=cab->rpns();
delete temp;
}
}
void lista::eliminar_f()
{if(cab==NULL)
cout<<"\nno existen nodos";
else
{nodo *ptr1, *ptr2;
ptr2=cab;
ptr1=NULL;
while(ptr2->rpns()!=NULL)
{ptr1=ptr2;
ptr2=ptr2->rpns();
}
if(ptr1==NULL)
{delete cab;
cab=NULL;
}
else
{delete ptr2;
ptr1->apns(NULL);
}
}
}}
void lista::eliminar_lista()
{nodo *temp;
while(cab!=NULL)
{temp=cab;
cab=cab->rpns();
delete temp;
}
}
void main()
{int op;
lista b;
clrscr();
for(;;)
{
cout<<"\n\n<1> insertar al inicio";
cout<<"\n<2> insertar al final";
cout<<"\n<3> eliminar nodo";
cout<<"\n<4> mostrar lista";
cout<<"\n<5> eliminar inicio";
cout<<"\n<6> eliminar final";
cout<<"\n<7> eliminar lista";
cout<<"\n<8> salir\n";
op=getch();
switch(op)
{case '1': b.insertar_i();break;
case '2': b.insertar_f();break;
case '3': b.eliminar_nodo(); break;
case '4': b.mostrar_lista();break;
case '5': b.eliminar_i();break;
case '7': b.eliminar_lista();break;
case '8': exit(0);
}
}
}
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
class nodo
{int num;
nodo *sgte;
public:
nodo(){sgte=NULL;}
void apns(nodo *n);
nodo *rpns();
void ingresar();
int mostrar();
};
void nodo::apns(nodo *n)
{sgte=n;}
nodo *nodo::rpns()
{return sgte;}
void nodo::ingresar()
{cin>>num;}
int nodo::mostrar()
{return num;}
/////////////////////////////////////////
class lista
{nodo *cab;
public:
lista(){cab=NULL;}
void insertar_i();
void insertar_f();
void eliminar_nodo();
void mostrar_lista();
void eliminar_i();
void eliminar_f();
void eliminar_lista();
};
void lista::insertar_f()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
{cab=a;}
else
{nodo *temp,*temp1,*temp2;
temp=cab;
while(temp2!=NULL)
{temp1=temp->rpns();
temp2=temp1->rpns();}
temp->rpns();
temp->apns(a);
}
}
void lista::insertar_i()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
cab=a;
else
{nodo *temp;
temp=cab;
cab=a;
cab->apns(temp);
}
}
void lista::mostrar_lista()
{nodo *t;
if (cab==NULL)
cout<<"La lista esta vacia";
else
{t=cab;
while(t!=NULL)
{//t=t->rpns();
cout<<t->mostrar();
t=t->rpns();
}
}
}
void lista::eliminar_nodo()
{nodo *temp,*temp1,*temp2;
temp1=cab;
int numero;
cout<<"ingrese numero a borrar";
cin>>numero;
if(temp1->rpns()==NULL)
cout<<"no hay elementos";
else
{do
{temp=temp1;
temp1=temp1->rpns();
if(temp1->mostrar()==numero)
{temp2=temp1->rpns();
temp->apns(temp2);
delete temp1;
}
}while(temp!=NULL); /////
}}
void lista::eliminar_i()
{if(cab==NULL)
cout<<"\nno existen nodos";
else
{nodo *temp;
temp=cab;
cab=cab->rpns();
delete temp;
}
}
void lista::eliminar_f()
{if(cab==NULL)
cout<<"\nno existen nodos";
else
{nodo *ptr1, *ptr2;
ptr2=cab;
ptr1=NULL;
while(ptr2->rpns()!=NULL)
{ptr1=ptr2;
ptr2=ptr2->rpns();
}
if(ptr1==NULL)
{delete cab;
cab=NULL;
}
else
{delete ptr2;
ptr1->apns(NULL);
}
}
}}
void lista::eliminar_lista()
{nodo *temp;
while(cab!=NULL)
{temp=cab;
cab=cab->rpns();
delete temp;
}
}
void main()
{int op;
lista b;
clrscr();
for(;;)
{
cout<<"\n\n<1> insertar al inicio";
cout<<"\n<2> insertar al final";
cout<<"\n<3> eliminar nodo";
cout<<"\n<4> mostrar lista";
cout<<"\n<5> eliminar inicio";
cout<<"\n<6> eliminar final";
cout<<"\n<7> eliminar lista";
cout<<"\n<8> salir\n";
op=getch();
switch(op)
{case '1': b.insertar_i();break;
case '2': b.insertar_f();break;
case '3': b.eliminar_nodo(); break;
case '4': b.mostrar_lista();break;
case '5': b.eliminar_i();break;
case '7': b.eliminar_lista();break;
case '8': exit(0);
}
}
}
Listas Doblemente Enlazadas
Hasta ahora se han manejado listas que se recorren en un asola dirección. En algunas aplicaciones es práctico o hasta indispensable poder recorrer una lista en ambas direcciones. Para estos casos se tienen las lista doblemente enlazadas. Esta propiedad implica que cada nodo debe tener dos apuntadores, uno al nodo predecesor y otro al nodo sucesor.
Hasta ahora se han manejado listas que se recorren en un asola dirección. En algunas aplicaciones es práctico o hasta indispensable poder recorrer una lista en ambas direcciones. Para estos casos se tienen las lista doblemente enlazadas. Esta propiedad implica que cada nodo debe tener dos apuntadores, uno al nodo predecesor y otro al nodo sucesor.
Cabecera
Listas Circulares
Una lista circular es una lista en la cual el último nodo es enlazado al primer elemento de la lista. La ventaja de este tipo de estructura es que siempre se puede llegar a cualquier nodo siguiendo los enlaces. La desventaja es que si no se tiene cuidado una búsqueda puede resultar en un bucle infinito. Esto se puede evitar al determinar a un nodo como nodo-cabeza o nodo inicial.
Listas Circulares
Una lista circular es una lista en la cual el último nodo es enlazado al primer elemento de la lista. La ventaja de este tipo de estructura es que siempre se puede llegar a cualquier nodo siguiendo los enlaces. La desventaja es que si no se tiene cuidado una búsqueda puede resultar en un bucle infinito. Esto se puede evitar al determinar a un nodo como nodo-cabeza o nodo inicial.
Pilas
Una pila es un tipo especial de lista lineal en la cual un elemento sólo puede ser añadido o eliminado por un extremo llamado cima. Esto significa que los elementos se sacan de la pila en orden inverso al que se pusieron en ella.
Las dos operaciones básicas asociadas a las pilas son:
-Poner: es añadir un elemento a la pila.
-Sacar: es extraer un elemento de la pila.
Una pila es un tipo especial de lista lineal en la cual un elemento sólo puede ser añadido o eliminado por un extremo llamado cima. Esto significa que los elementos se sacan de la pila en orden inverso al que se pusieron en ella.
Las dos operaciones básicas asociadas a las pilas son:
-Poner: es añadir un elemento a la pila.
-Sacar: es extraer un elemento de la pila.
La pila es una estructura con numerosas analogías en la vida real: una pila de platos, una pila de monedas, una pila de bandejas, etc.
La representación consiste en un vector con espacio para un máximo de elementos y un contador que indica el número de elementos válidos almacenados en el vector.
La representación consiste en un vector con espacio para un máximo de elementos y un contador que indica el número de elementos válidos almacenados en el vector.
Colas
Una cola es una lista en las que las supresiones se realizan solamente solamente al principio de la lista y las inserciones al final de la misma. Al igual que en el caso de las pilas, hay que prever un vector para almacenar el máximo número de elementos que puedan presentarse en el programa. A diferencia de las pilas, no basta con añadir un simple contador, tal que indique el número de elementos válidos; sino hay que prever dos índices que indiquen la posición del comienzo y del final de la cola. Si la cola no está vacía, en CABEZA está el primer elemento, y si la cola no está llena, en FIN es el lugar donde se copia el siguiente elemento que se incorpora a la misma.
Las colas se usan para almacenar datos que necesitan ser procesados según el orden de llegada. En la vida real se tienen ejemplos numerosos de colas: la cola de un cine, la cola de un banco, etc; en todas ellas el primer elemento que llega es el primero que sale.
Una cola es una lista en las que las supresiones se realizan solamente solamente al principio de la lista y las inserciones al final de la misma. Al igual que en el caso de las pilas, hay que prever un vector para almacenar el máximo número de elementos que puedan presentarse en el programa. A diferencia de las pilas, no basta con añadir un simple contador, tal que indique el número de elementos válidos; sino hay que prever dos índices que indiquen la posición del comienzo y del final de la cola. Si la cola no está vacía, en CABEZA está el primer elemento, y si la cola no está llena, en FIN es el lugar donde se copia el siguiente elemento que se incorpora a la misma.
Las colas se usan para almacenar datos que necesitan ser procesados según el orden de llegada. En la vida real se tienen ejemplos numerosos de colas: la cola de un cine, la cola de un banco, etc; en todas ellas el primer elemento que llega es el primero que sale.
ESTRUCTURAS DINAMICAS.- Existen 2 tipos:
a) Simples
DINAMICAS LINEALES: 1. Listas enlazadas-- b) Dobles
2. Pilas c) Circulares
3. Colas
4. Bicolas
Las Dinámicas Lineales simulan la funcionalidad del vector, como su nombre lo dice son lineales, unas van seguida de otras.
1 2 3
|
|
|
· AB
a) Arboles Binarios-- * ABB
DINAMICA NO LINEAL: 1. Arboles b) Arboles Binarios de Busqueda
2. Grafos
Arbol: Es una lista enlazada a conjuntos de Nodos
UNIDAD: Nodos
Class Nodo Simple{
|
}
Nodo SimpleDato Enlace
|
}
|
}
1.Public Nodo(Object, obj){
This Obj null;
}
2. Public Nodo(Object, Obj, Nodo Sis){
Dato=Obj;
Enlace=Sis; // enlazado
}
3. Public getDato(){return dato;} //fin
La Estructura Dinámica de Datos son aplicable a la vida real.
LISTAS ENLAZADAS
a) Simples
E.D Lineales: 1. Listas -- b) Dobles
2. Pilas c) Circulares
3. Colas
4. Bicolas
Unid.Class Nodo{ // PARA LISTAS NO VACIAS
Object dato;
Nodo Sis; Object getDato(){
Nodo(Object 0) return dato;
Dato=0; }
Sig=null;
} Nodo getEnlace(){-----}
//________________
Nodo(Object 0, Nodo n){
Dato=0;
Sis=n;
}
La lista Enlazada es un vector Dinámico empieza desde el punto de vista estructurado.
OPERACIONES
Constructor{
Lista vacia
Constructor
Public lista(Striing N){
Nombre=n;
Pow=null;
}
Public boolear
Return()
}
INSERCIONESa) Insertar al frente Lista vacia
Lista vacia lista n
|
|
|
Null nullPri null
pri ult
Algoritmo;
Crear Nodo;
lista Algoritmo
|
nuevo if (lista vacia())pri ult pri=ult =new N;
//uso el primer constructor else
De la clase nodo//
Pri= new Nodo(Obj=pri)
}
Public class lista simple{
Private Nodo pri;
Private Nodo ult;
Private String nombre;
}
-----------------------------------------
Public lista simple(){
Pri=ult=null;
Nombre=””; }
METODOS INSERTAR:
- Public void insFrente(Object Obj){ }
- Public void insPosterior(Object Obj){ }
- Public void insposicion(Object Obj){ }
- Public Object delFrente(Object Obj){ }
- Public Object del posterior(Object Obj){ }
ELIMINACIONES
- Obtener dato
- Eliminar dato
- Mostrar dato
1. DEL FRENTE Lista vacia
Lista vaciaLista vacia lista n
|
|
|
Null nullPri null
pri ult
Algoritmo
Retornar Error:
Mensaje; Dato a remover = pri.dato; //obj1
Excepcion; actual=pri;
Objeto; pri=pri.sig;
Retornar dato a remover
_Lista vacia ------------------------------------------------
|
Dato a remover=pri.dato; If(pri.Esquals(ult));
Pri ult pri=Ult =null;
Retornar dato;
Public object DelFrente(){
If (Lista vacia()) trows Exepcion
Object dato a remover=pri.dato;
If(pri.equals(ult))
Pri=ult=null;
Else{
Nodo actual=pri;
Pri=pri.sig;
Actual.sig=null;
}
Return dato A remover
}
2. DEL POSTERIOR
_ Lista vaciaLista vacia lista x
|
|
|
|
Null nullPri null
pri ult
Algoritmo
Retornar null:
error; Dato a remover = ult.dato; //obj1
Excepcion; While(Actual.sig!=ult)
Objeto; Actual=Actual.sig;
Ult=Actual.nulll;
Return dato a remover;
------------------------------------------------
ALGORITMO
Dato a remover=ult.dato;
If(pri.Equals(ult));
pri=Ult =null;
Retornar dato;
Public object DelPosterior(){
If (Lista vacia()) trows Exepcion;
Object dato a remover=ult.dato;
If(pri.equals(ult))
Pri=ult=null;
Else{
Nodo actual=pri;
While(actual.sig!=ult)
Actual.actual.sig;
Ult=actual;
Ult.sig=null;
}
Return dato A remover
}
3. DEL POS N
_ Lista vacia 1 elemLista vacia
lista x
 |
Lista x 
Null pri ultPri null
Algoritmo
Retornar null:
error; Dato a remover = pri.dato;
Excepcion; if(pri.equals.ult && pos==1)
Objeto;
pri=ult=nulll;
Return dato a remover;
------------------------------------------------
Public object DelPos-n(int pos){
If (Lista vacia()) return;
If(pos==1)Delfrente();
If(pos==Nro. elem)DelPosterior();
Object dato a remover=ult.dato;
Else{
If(pri.equals(ult)){
Pri=ult=null;
Return dato a remover;
}
Else{
Nodo actual=pri;
For(int i; i<pos; i++)
Actual=actual.sig;
Nodo a borrar= actual.sig;
Dato a remover= (actual.sig).dato;
actual.sig=( actual.sig;).sig;
a Borrar.sig=null;
return dato a remover;
}
}
}
