Lista circular doble

UNIVERSIDAD PERUANA UNIÓN
FACULTAD DE INGENIERÍA
EAP Ing. Sistemas

MONOGRAFIA
Lista Circular doble enlazada
Monografía presentada en cumplimiento parcial de la
Asignatura Algoritmos y Estructura de datos

Autores:
Arnold Tapia Gutiérrez
Alejandro Gutiérrez González
Carla Rodríguez Moreno
Frank Albites Loa

Profesor:
Alex Chire

Lima, Noviembre de 2011

INDICEIntroducción ----------------------------------------------------------------------------------------------------- 02
Resumen-------------------------------------------------------------------------------------------------------- 03
Listas doblemente circular---------------------------------------------------------------------------------- 04
Programación enJava--------------------------------------------------------------------------------------- 06

INTRODUCCIÓN
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden serhechas desde cualquier punto de acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntando que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Listas Doblemente Circular
Implementar en Java una clase de listascirculares de enteros doblemente encadenadas. En concreto, la práctica contendrá la siguiente clase de nodos:

class nodo
{ int valor;
nodo ant;
nodo sig;
}
y también ha de contener la clase de listas con las operaciones siguientes:
public class L_circular
{ nodo acceso=null;
public void insertar(int N)
{
//código de insertar
}
public void suprimir()
{
//código de suprimir
}
publicboolean buscar(int N)
{
//código de buscar
}
}
Más concretamente, la estructura de datos a implementar ha de tener una forma como la siguiente:acceso

La referencia acceso ha de apuntar a un nodo cualquiera de la lista. La operación insertar, dado un número N, ha de insertar un nodo con el valor N en la posición siguiente a la apuntada por acceso. La operación suprimir ha de eliminar el nodoapuntado por acceso.
Finalmente, la operación buscar nos debe contestar si un elemento N está o no en la lista y, en caso en que esté, nos ha de dejar a acceso apuntando al nodo que contiene a N..

Sol·lució:
Nota: la sol·lució té diversos errors.
class nodo
{
int valor;
nodo ant;
nodo sig;
}
public class L_circular
{
nodo acceso=null;

public void insertar(int N)
/*dado un nmeroN, ha de insertar un nodo con el valor
*N en la posicion� siguiente a la apuntada por acceso.*/
{
nodo nuevo = new nodo();
nuevo.valor = N;
if (acceso == null){
nuevo.sig = nuevo;
nuevo.ant = nuevo;
acceso = nuevo;
} else {
nuevo.sig = acceso.sig;
nuevo.ant = acceso;
acceso.sig.ant = nuevo;
acceso.sig = nuevo;
}
}

public void suprimir()
/*eliminar el nodo apuntado por acceso.Acceso apunta al
*siguiente nodo*/
{
if (acceso != null){ //hay como minimo un nodo nodo
if (acceso.sig == acceso){ //solo hay un nodo
acceso = null;
} else {//hay mas de un nodo
acceso.sig.ant= acceso.ant;
acceso.ant.sig = acceso.sig;
acceso = acceso.sig;
}
}
}

public boolean buscar(int N)
/*nos debe contestar si un elemento N est�o no en la lista
*y, en caso en que est�nos ha de dejar a acceso apuntando
*al nodo que contiene a N.*/
{
nodo original = new nodo();
boolean b = false;
if (acceso != null){//si al menos hay un nodo
original = acceso;
if (acceso.valor == N){
b=true;
}else{
acceso=acceso.sig;
}
while (!b && acceso != original){
if (acceso.valor != N){ //encontrado
acceso=acceso.sig;
}else{
b=true;
}
}
}
return b;
}
}...