public class ListaSimple {
String nombre;
Nodo pri;
Nodo ult;
public ListaSimple(String n){
pri=ult=null;
nombre=n;
}
public ListaSimple(){
this("Lista");
}
public Boolean ListaVacia(){
return pri==null;
}
public void InsFrente(Object obj){
if (ListaVacia())
pri=ult=new Nodo(obj);
else
pri=new Nodo(obj);
}
public void InsPosterior(Object Elem){
if(ListaVacia()){
pri=ult=new Nodo(Elem);
}
else{
ult=ult.siguiente=new Nodo(Elem);
}
}
public int ContElem(){
Nodo Actual=pri;
int cont=0;
while(Actual!=null){
cont++;
Actual=Actual.siguiente;
}
return cont;
}
public void InsPosicion_n(Object obj,int Pos){
Nodo Actual =pri;
Nodo Nuevo;
if(ListaVacia())
InsFrente(obj);
else{
if(Pos==1)
InsFrente(obj);
if( Pos==ContElem())
InsPosterior(obj);
else{
for( int i=0;i<=Pos-1;i++){
Actual=Actual.siguiente;
Nuevo=new Nodo(obj);
Actual.siguiente=Nuevo;
}
}
}
}
public Object DelFrente(){
if(ListaVacia())
System.out.println("La lista esta vacia");
Object DatoARemover=pri.dato;
if(pri.equals(ult))
pri=ult=null;
else{ Nodo Actual=pri;
pri=pri.siguiente;
Actual.siguiente=null;
}
return DatoARemover;
}
public Object DelPosterior(){
if(ListaVacia())
System.out.println("La lista esta vacia");
Object DatoARemover = ult.dato;
if(pri.equals(ult))
pri=ult=null;
else{ Nodo Actual = pri;
while(Actual.siguiente != ult){
Actual = Actual.siguiente;
ult = Actual;
ult.siguiente = null;
}
}
return DatoARemover;
}
public void MostrarLista(){
Nodo Actual=pri;
if(ListaVacia()){
System.out.println("La "+nombre+" Vacia");
}
else{
System.out.println("La "+nombre+": ");
while (Actual != null){
System.out.println(""+Actual.dato+"");
Actual = Actual.siguiente;
}
}
}
public void ModificarFrente(Object obnuevo){
if (ListaVacia())
System.out.println("Ocurrio un error");
else{
pri.dato = obnuevo;
}
}
public void ModificarPos(Object obj){
if (ListaVacia())
System.out.println("Ocurrio un error");
else{
ult.dato = obj; }
}
public static void main(String[] args) {
// TODO code application logic here
ListaSimple ls = new ListaSimple();
ls.InsFrente(" Juan ");
ls.InsPosterior(" Carlos ");
ls.InsPosicion_n(" Alejandra ", 2);
ls.MostrarLista();
System.out.println("Eliminar el primero");
ls.DelFrente(); ls.MostrarLista();
System.out.println("Modificamos el Primero es Carlos por Rosario"); ls.ModificarFrente(" Rosario ");
ls.MostrarLista();
System.out.println("Modificamos el ultimo q es Alejandra por es Eduar2"); ls.ModificarPos(" Eduar2 ");
ls.MostrarLista();
}
}
public class Nodo {
protected Object dato;
public Nodo siguiente;
public Nodo (Object obj){
dato =obj; siguiente= null;
}
public Object getElemento(){return dato;}
public Nodo getAnt(){return siguiente; }
}
public class Pila {
public Nodo tope;
public Pila(){ tope=null; }
public boolean vacia (){
return tope == null;
}
public void apilar(Object dato){
Nodo p=new Nodo(dato);
p.dato=dato;
p.siguiente=tope; tope=p;
}
public Object desApilar(){
Object dat;
Nodo p=tope;
dat=p.dato;
tope=tope.siguiente;
p=null;
return dat;
}
public void eliminar(){
while(tope!=null)
desApilar();
}
public void imprimir(){
if (vacia()){
System.out.println("La pila esta vacia...");
}
else{
Nodo Actual=tope;
do{
System.out.print(Actual.getElemento().toString()+" "); Actual=Actual.siguiente;
}
while(Actual != null);
System.out.println();
//imprime un salto de linea
}
}
public static void main(String[] args) {
// TODO code application logic here
Pila p=new Pila();
System.out.println("La Pila Original es");
p.apilar(" 100 ");
p.apilar(" 200 ");
p.apilar(" 300 ");
p.imprimir();
System.out.println("En La Pila ultimo q llega primero en salir");
p.desApilar();
p.imprimir();
p.desApilar();
p.imprimir();
}
}
public class Cola {
public Pila pilaCola;
private Pila pilaCola2;
public Cola(){
pilaCola=new Pila();
pilaCola2=new Pila();
}
public void insertar(Object dato){
pilaCola.eliminar();
//se reinica la pila,para q no guarde los valores del anterior orden
pilaCola2.apilar(dato);
Nodo Actual=pilaCola2.tope;
//se invierte la pila
while(Actual!=null){
pilaCola.apilar(Actual.getElemento());
Actual=Actual.siguiente;
}
}
public void sacar(){
pilaCola.desApilar();
}
public void Mostrar(){
pilaCola.imprimir();
}
public static void main (String [] args){ Cola p=new Cola();
System.out.println("La Cola Original es ");
p.insertar(" 100 ");
p.insertar(" 200");
p.insertar(" 300 ");
p.Mostrar();
System.out.println("En la Cola el Primero q llega Primero q sale");
p.sacar();
p.Mostrar();
p.sacar();
p.Mostrar();
}
}
public class ListaDobleCircular {
NodoDoble ultimo;
String Nombre;
public ListaDobleCircular(String s){
Nombre=s;
ultimo=null;
}
public ListaDobleCircular(){
this ("Lista");
}
public boolean VaciaLista (){
return ultimo == null;
}
//Mostramos la lista
public void MostrarLista(){
if (VaciaLista()){
System.out.println("Vacia" + Nombre);
}
else{
System.out.print("La "+Nombre + " es: ");
NodoDoble Actual=ultimo.sig;
System.out.print(ultimo.datos.toString()+" ");
while(Actual != ultimo){
System.out.print(Actual.datos.toString()+" ");
Actual=Actual.sig; } System.out.println();
System.out.println();
}
}
//Inserta un Elemento al ultimo de la Lista
public void InsertaUltimo (Object ElemInser){
if (VaciaLista()){
ultimo = new NodoDoble(ElemInser);
ultimo.sig=ultimo; ultimo.ant=ultimo;
}
else{
NodoDoble nuevo=new NodoDoble(ElemInser);
nuevo.sig=ultimo.sig;
nuevo.ant=ultimo;
ultimo.sig.ant=nuevo;
ultimo.sig=nuevo;
ultimo=nuevo; }
}
//Inserta un Elemento en una posición dada
public void InsertaPos_n (Object ElemInser,int Posicion){
if(Posicion>=(Contador()))
InsertaUltimo(ElemInser);
else{
NodoDoble Aux = ultimo;
int i = 2;
while ((i != Posicion) & (Aux.sig != ultimo)){
i++;
Aux = Aux.sig;
}
NodoDoble Nuevo = new NodoDoble(ElemInser);
Nuevo.sig = Aux.sig;
Aux.sig =Nuevo;
Nuevo.ant=Aux;
Aux.sig.ant=Nuevo;
}
}
//Eliminar en el primer elemento
public void EliminaPrimero(){
if (VaciaLista())
System.out.println ("No hay elementos");
else{
if (ultimo==ultimo.sig)
ultimo= null;
else{
ultimo.ant.sig=ultimo.sig;
ultimo.sig.ant=ultimo.ant;
ultimo=ultimo.sig;
}
}
}
//Eliminar al ultimo
public void EliminaUltimo (){
if (VaciaLista())
System.out.println ("No hay elementos");
else{
if (ultimo==ultimo.sig)
ultimo= null;
else{
ultimo.ant.ant.sig=ultimo;
ultimo.ant=ultimo.ant.ant;
}
}
}
// Longitud de la lista
public int Contador(){
int con =1;
if(!VaciaLista()){
NodoDoble aux=ultimo.sig;
while (aux != ultimo){
con++;
aux =aux.sig;
}
}
System.out.println ( "La Longitud de la Lista es: "+ con);
return con;
}
}
class ListaDobleCircularA{
public static void main(String[] args) {
// TODO code application logic here
ListaDobleCircular l=new ListaDobleCircular();
//Crea la lista
l.InsertaUltimo(" Eduar ");
l.InsertaUltimo(" Yoni ");
l.InsertaUltimo(" Rosa ");
l.InsertaUltimo(" Indira ");
l.InsertaUltimo("Richar ");
l.InsertaPos_n("Eduar2",4);
l.MostrarLista();
System.out.println("Eliminamos el Primer elemento");
l.EliminaPrimero();
l.MostrarLista();
System.out.println("Eliminamos el Ultimo elemento");
l.EliminaUltimo();
l.MostrarLista();
}
}
public class NodoDoble {
Object datos;
NodoDoble sig;
NodoDoble ant;
NodoDoble(Object valor){
datos =valor;
sig =ant= null;
}
NodoDoble(Object valor, NodoDoble signodo){
datos = valor;
sig = signodo;
}
Object getObject(){return datos; }
NodoDoble getnext() {return sig; }
}
Dinámicas no Lineales:
Arboles:
• Es una estructura dinámica no Lineal que consta de un conjunto de Nodos
Y no un conjunto de rama
En teoría de grafos, un árbol es un grafo conectado acíclico. Un árbol con raíz es como un grafo con un vértice seleccionado como la raíz. En ese caso, sólo dos vértices conectados con el lado heredan una relación de padre- hijo. Un grafo acíclico con múltiples componentes conectados o un conjunto de árboles con raíz se llama bosque.
Operaciones comunes en arboles son:
•
Enumerar todos los elementos
•
Buscar un elemento
•
Añadir un nuevo ítem en una cierta posición del árbol
•
Borrar un elemento
•
Remover una sección completa de un árbol.
•
Añadir una sección completa a un árbol.
•
Encontrar la raíz de cualquier nodo
Usos comunes de los árboles son:
•
Manipular datos jerárquicos
•
Para hacer la información fácilmente
•
Manipular listas ordenadas de datos.
Árbol binario de búsqueda
La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles, tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para construir los algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual efectuaremos las búsquedas. En las implementaciones que presentaremos sólo se considerará en cada nodo del árbol un valor del tipo Elemento aunque en un caso general ese tipo estará compuesto por dos: una clave indicando el campo por el cual se realiza la ordenación y una información asociada a dicha clave o visto de otra forma, una información que puede ser compuesta en la cual existe definido un orden.
Un árbol binario de búsqueda(ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x ,y todos los elementos almacenados en el subárbol derecho de x son mayores que el elemento almacenado en x.
La figura de abajo muestra dos ABB construidos en base al mismo conjunto de
enteros:
Nodo Padre: Nodo que contiene un puntero al nodo actual. En un árbol
un nodo solo puede tener un nodo padre.. X es padre de Y sí y solo sí el nodo X apunta a Y, también se dice que X es antecesor de Y. En la figura B es padre de E y F.
•
Nodo Hijo: Cualquiera de los nodos apuntados por uno de los nodos del
aŕbol. Un nodo puede tener varios hijos.. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. En la figura: E es hijo de B.
•
Hermano: Dos nodos serán hermanos si son descendientes directos de
un mismo nodo. En la figura E y F son hermanos.
Conceptos básicos en cuanto a la posición dentro del árbol:
•
Nodo Raíz: Es el único nodo del árbol que no tiene padre. Este es el
nodo que usaremos para referirnos al árbol. En la figura A es el nodo
raíz.
•
Nodo Hoja: Nodo que no tiene hijos. Se llama hoja o terminal a aquellos
nodos que no tienen ramificaciones ( hijos ). En la figura .. N es un nodo
hoja.
•
Nodo Interior: Es un nodo que no es raíz ni hoja. En la figura .. D es un
nodo interior.
•
Orden: Es el número potencial de hijos que puede tener cada elemento
de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. Podríamos decir que nuestro árbol de ejemplo es de orden tres.
•
Grado: El número de hijos que tiene el elemento con más hijos dentro
del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto A como
D tienen tres hijos, y no existen elementos con más de tres hijos.
•
Nivel: Se define para cada elemento del árbol como la distancia a la
raíz, medida en nodos. El nivel de la raíz es cero, el de sus hijos uno y asi sucesivamente. En el ejemplo, el nodo D tiene nivel 1, el nodo G tiene nivel 2 y el nodo N nivel 3.
•
Rama: Es el camino desde el nodo raíz a una hoja. En el ejemplo A-B-E-
K y A-B-F son ramas.
Altura: La altura de un árbol se define como el nivel del nodo de mayor
nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, tambien podemos hablar de altura de ramas, el máximo número de nodos que hay que recorrer para llegar de la raíz a una de las hojas. El árbol de la Figura tiene altura 3, la rama B tiene altura 2, la rama G tiene altura 1 y la N cero.
•
Peso: Es el número de nodos del árbol sin contar la raíz.
•
Camino: Es una consecuencia de nodos, en el que dos nodos
consecutivos cualesquiera son padre e hijo. En el ejemplo A-D-H y A-C-
G-M son caminos.
•
Longitud de camino: Es el número de arcos que deben ser recorridos
para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. En nuestro árbol de ejemplo G tiene longitud de camino 3 y N tiene longitud de camino 4
