Cuando señalas insertar (al inicio o al final), no debieras imprimir la lista, eso haría inecesario en el menú, la opción imprimir... (que yo añadiría esa opción al menú) bien que mientras diseñas si tengas activa esa línea para ir verificando que las operaciones se realizan correctamente...
entonces lo pondrías tras la llamada en el menú, antes del Break...
El nombre de 'Final', no es para nada ilustrativo de su funcionalidad. Insertar, siempre es añadir delante de algún item, OK, pero al final puedes llamarlo simplemente Añadir... sin más expecificaciones, al añadir, siempre se añade al final.
Por último, no veo que lleves la cuenta de la cantidad de ítems en la lista... es más eficiente preguntar que 'Si Items=0', que 'Si Lista es null', y añadir al comienzo puede indicarse con un 0 y añadir al final con -1, y Añadir en cualquier otra posición (insertar), con cualquier otro valor entre 1 e ítems -2
Un control de la cuenta de nodos en la lista, aunque no es imprescindible, si es más que aconsejable, simplifica la lógica y funcionalidad de la misma a cambio de algo de código extra.
Y ahora yendo a tus dudas:
- Tu función 'Final' no está bien implementada... Trato de explicarte con un sencillo ejemplo, sea una lista con varios elementos, consideremos estos 3: Marte -> Jueves -> domingo
vemos que domingo.anterior = jueves
y vemos que Jueves.siguiente = domingo
Ahora insertemos un elemento en medio, por ejemplo viernes.
Las operaciones a realizar serán 4, verás:
viernes.siguiente = domingo
domingo.anterior = viernes
Viernes.anterior = jueves
Jueves.siguiente = viernes
Es decir se necesita apuntar desde el nuevo elemento a los extremos donde se inserta, y se necesita apuntar desde los extremos donde se inserta al nuevo elemento. Siempre son 4 asignaciones (si está en medio)
Si el nodo a añadir es un extremo, solo necesita 2 asignaciones (si la lista doblemente enlazada no es circular)...
Modifico tu código a pseudocódigo para hacerlo más legible:
Esta función está bien, salvo la redundancia de establecer nulos, donde ya los hay y no llevar cuenta de ítems que tiene la lista.
if (lista = Nulo)
lista = q //OK
q.sig = Nulo //Innecesario
q.ant = Nulo //Innecesario
else
q.sig = lista //OK
q.ant = lista.ant; //Innecesario
lista.ant = q //OK
}
¿No cuentas los items que lleva la lista.... por qué?
Así tu función externa podría ser:
Funcion Añadir(dato, posicion)
nodo n
n.Dato = dato
// o bien como en tu caso operas por consola, desde aquí solicitas la entrada del dato, 1 solo sitio para las 3 funciones internas (y retiras el parámetro dato de la funcion)
Si (posicion=0) ó (Items=0) luego
AñadirAlComienzo(n)
PeroSi (posicion menor que 0) ó (posicion mayor o igual que Items-1) luego
AñadirAlFinal(n)
Sino
Insertar(n, posicion)
Fin si
actual =n
Fin funcion
Y tus funciones internas serían ahora: AñadirAlFinal, AñadirAlComienzo, Insertar
Fíjate que ahora insertar exigirá localizar el ítem en la posición pedida. al caso actual es una buena estrategia, porque recordando su posición, puede partirse desde 0 hasta actual desde actual hasta 0, desde actual hasta último, desde último hasta actual, según quede más cerca de un nodo u otro de los 3 implicados: primero, actual ó último...
Reviso tu función 'Final' (Añadir):
Simplifico tu código hacia pseudocódigo, más sencillo de ver así...
funcion Final
...
if(lista = Nulo)
lista = q
q.sig = Nulo //Innecesario
q.ant = Nulo //Innecesario
else
//3 líneas 3 errores...
q.sig = lista.sig //Innecesario, asignar nulo al final de la lista no es preciso, el nodo recién creado ya tiene su .siguiente en nulo. Pero además es un error.
lista.sig = q //NO lista.sig apunta al segundo nodo, no al último.
q.ant = lista //NO, le estás diciendo que el anterior a este nodo es el primer nodo.
}
¿Igual que la otra, no llevas cuenta de los ítems, por qué?
Fin funcion
Esta función te falla... porque
Una lista, basta que tenga el nodo 'inicial, pero si tienes una lista doblemente enlazada, debieras mantener referencia al primer y último elemento.
Cuando apuntas a lista (tu nodo lista), estás apuntando al primero nodo en ella, entonces lista.siguiente apunta al siguiente nodo en la lista, es decir al segundo nodo, no al último. Será el último solo si la lista tiene 2 ítems...
Entonces tu función Final, está insertando nodos incorrectamente... usa nombre días o de meses y haz las asignaciones en papel para ver como va quedando concada inserción, para entender el problema.
La implementación debe mantener referencia al primer y último nodo, y deja de llamar lista al primer nodo, porque eso te 'nubla la vista'.
Aquí una sencilla implementación con referencias al primero, último y actual nodos, además lleva la cuenta de ítems...
Estos son los miembros en la clase, debajo los métodos...
nodo Primero //primer nodo de la lista.
nodo Ultimo // Ultimo nodo de la lista.
nodo Actual // Nodo actual, también podría ser el primero y el último
entero ixActual // indice que ocupa el nodo en la lista.
entero Items // Cantidad de nodos que contiene la lista actualmente.
Función externa para añadir nodos...
Con cada añadido, se hace actual al nodo añadido, y se conserva su posición.
Funcion Añadir(Posicion)
nodo n
entero dato
dato = PedirDatoAlUsuario
Si (Items=0) luego
CrearLista(n)
ixActual=0
Sino
Si (posicion=0) luego
AñadirAlComienzo(n)
ixActual=0
PeroSi ((posicion < 0) ó (posicion >(Items-2))) luego
AñadirAlFinal(n)
ixActual= items
Sino
Insertar(n, posicion)
ixActual= posicion
Fin si
Fin Si
actual = n
Items +=1
Fin Funcion
Añade el primer nodo a la lista.
funcion CrearLista (nodo n)
primero = n
ultimo = n // vuando solo hay 1 nodo en la lista, es el primero y también el último.
Fin funcion
Añade un nodo al comienzo de la lista.
Funcion AñadirAlComienzo(nodo n)
n.siguiente = primero
primero.anterior = n
primero = n
Si (items=1) luego
ultimo.anterior = n //el primero
fin si
Fin funcion
Añade un nodo al final de la lista.
Funcion AñadirAlFinal(nodo n)
n.anterior = ultimo
ultimo.siguiente = n
ultimo = n
Si (items = 1) luego
primero.siguiente = n // el ultimo
Fin si
Fin si
Insertar un nodo en posiciones distintas del último y el primero.
Funcion Insertar(nodo n, entero posicion)
nodo busca
busca = BuscarNodo(posicion)
n.anterior = busca.anterior
n.siguiente = busca
busca.anterior.siguiente = n
busca.anterior = n
Fin funcion
Busca desde el primero hasta hallar el nodo en la posición pedida.
nodo = funcion BuscarNodo(entero posicion)
nodo n
entero k
n= primero
mientras (k < posicion)
n = n.siguiente
k +=1
repetir
devolver n
Fin funcion
Búsqueda optimizada, basada en el actual... para una lista con pocos elementos no se nota, cuanto más crece la lista, más útil resulta...
nodo = funcion BuscarNodo(entero posicion)
nodo n
entero k, s
Si (posicion <= ixactual) luego //está entre el primero e ixactual
Si ((posicion-ixactaul) < (ixActual /2)) luego //si está más cerca de ixActual que de 0...
n = ixactual
k = ixactaul
s = -1
Sino
n = primero
k = 0
s = 1
fin si
Sino //está entre ixactual y el último
k = (items-ixActual)
Si ((k/2) => (k - (posicion-ixactaual))) luego // si está más cerca de ixActual que del final
n = ixactual
k = ixactaul
s = 1
Sino
n = ultimo
k = Items-1
s = -1
fin si
Fin si
Si (s = 1) luego //busca hacia arriba (itera sobre siguiente
mientras (k < posicion) // <> es distintode
n = n.siguiente
k +=1
repetir
Sino //busca hacia abajo (itera sobre anterior)
mientras (k>posicion)
n = n.anterior
k -=1
repetir
devolver n
Fin funcion
Dejo a tu cargo Imprimir(DesdePosicion, HastaPosicion), con valores Imprimir(0,-1) debería imprimir toda la lista.
Autor
En línea
