Fecha y hora actual: Sábado 01 Nov 2014 14:54
Índice del Foro

Foros de programación informática, diseño gráfico y Web

En esta comunidad intentaremos dar soporte de programación a todos los niveles, desde principiantes a profesionales de la informática, desarrollo de programas, programación web y mucho más.

Programando desde 0: 49- Listas encadenadas "El regreso

Responder al Tema Ir a página 1234Siguiente

Índice del Foro > Programación en general > Programando desde 0: 49- Listas encadenadas "El regreso

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Miércoles 07 Mar 2012 18:12

Título del mensaje: Programando desde 0: 49- Listas encadenadas "El regreso

Responder citando

Listas encadenadas

Esta estructura ya es super conocida por ustedes. La hemos venido trabajando desde los finales del curso de Pascal en su implementación de Lista Encadenada Simple. Hasta el momento es lo único que sabemos respecto a esta estructura.
Una lista encadenada simple (también conocida como lista enlazada o lista simplemente encadenada) no es más que un conjunto de nodos enlazados por punteros. Cada nodo tiene un puntero hacia el siguiente. La lista está dada entonces por un único puntero que apunta al nodo inicial. Esta estructura es, obviamente, lineal y en este caso tiene un único sentido de recorrida, es decir, solo podemos avanzar hacia delante, no hay otra forma porque dado un nodo solo podemos conocer el siguiente:



Si bien hemos visto las ventajas de esta estructura, también tenemos desventajas como la que acabo de mencionar (recorrido en un solo sentido). Para los ejemplos que hemos visto nos han solucionado la vida, sin embargo existen otras formas de listas encadenadas que sirven para otro tipos de problemas. En este apartado veremos tres variaciones de Listas Encadenadas que se sumarán a la implementación de Listas Encadenadas Simples. De este modo conocerán cuatro implementaciones diferentes para esta estructura. Tendrán muchos ejercicios para hacer y luego, en un proyecto bastante pesado, tendrán ustedes mismos que decidir qué tipo de estructuras les conviene más usar para tal o cual problema.

A continuación verán descripciones de las variantes de listas encadenadas, pero no tendrán mucho código fuente porque estoy totalmente convencido de que ustedes ya son capaces de implementarlas por sí mismos, y justamente es lo que les pediré en los ejercicios que tendrán luego de estas descripciones.

===============================================

Lista Doblemente Encadenada:

Esta variante permite recorrer una lista encadenada en ambos sentidos ya que cada nodo tendrá un puntero al siguiente nodo de la lista y otro al anterior. De esta manera, el primer nodo de la lista tendrá como puntero al nodo anterior el valor NIL y el último nodo tendrá como siguiente al valor NIL. Gráficamente tendríamos esto:



De este modo, si la lista está ordenada por ejemplo, recorrerla es mucho más sencillo que en el caso de una lista simplemente encadenada. No hace falta volver siempre al inicio de la misma para hacer una búsqueda, o iterar con dos punteros para tener el nodo que buscamos y a su inmediato anterior.
Entonces, esta implementación tiene las mismas ventajas que una lista simplemente encadenada y agrega otras más, por tanto uno podría pensar que es mejor, sin embargo esto dependerá de varias cosas.

===============================================

Lista Encadenada Circular:

Esta variante representa a una lista que no tiene un último elemento. Dicho más claramente, el último elemento tiene como nodo siguiente al primer elemento de la lista, de este modo la recorremos circularmente porque al llegar al final, si seguimos, volvemos a empezar. Gráficamente es así:



Como ven entonces, no hay nodo que tenga NIL. Sin embargo, siempre tenemos nuestro puntero l que indica cuál es el inicio de la lista. No es la variante más utilizada pero tiene algunas aplicaciones interesantes.
Nos permiten, por ejemplo, dado cualquier nodo, recorrer toda la lista. De este modo, no siempre tenemos que pasar el puntero l, sino que cualquier otro puntero que esté apuntando a cualquier nodo de la lista servirá igualmente para poder recorrerla completamente.

Este tipo de lista también puede ser doblemente encadenada, donde el anterior nodo al primero sería el último y el siguiente al último sería el primero:



Pueden resultar muy útiles en ciertas circunstancias.

==============================================

Listas Encadenadas Indizadas:

Esta es una variante que, me atrevería a decir, solo encontrarán en este manual y en ningún otro lado, por lo que pueden sentirse afortunados de conocerla aquí (claro que, si estudian ingeniería del software, aprenderán esto y mucho más).

Dentro de esta variante hay dos sub-variantes:

  • Listas Indizadas Implícitamente.
  • Listas Indizadas Explícitamente.


_________________

Indizado Implícito:

En esta variante tenemos una lista encadenada (simple o doble) y además tenemos un puntero que apunta a la última posición en la que se hizo algún cambio. Es mediante este puntero que se hacen inserciones, eliminados y búsquedas sobre la lista, es decir, será nuestro iterador.
Si nuestra estructura es simple encadenada, entonces nuestro puntero iterador solo podrá avanzar hacia delante; si es doble encadenada podrá avanzar hacia delante o hacia atrás. En cualquiera de estos casos las recorridas son circulares, es decir, nuestro iterador volverá al inicio de la lista una vez que llegó al final y se quiere avanzar más allá, o bien, volverá al final si llegó al inicio y se quiere retroceder más allá (esto último solo para listas doble encadenadas). A pesar de que de esta manera se recorre la lista circularmente, no estamos hablando de una lista circular ya que el último nodo no apuntará al primero ni viceversa.

Hay que tener muchísimo cuidado a la hora de pensar en esta implementación, porque NO significa que cada nodo tiene un puntero hacia la última posición usada, sino que significa que tenemos la lista y además un puntero hacia la última posición usada. Gráficamente, para una lista simple encadenada es así:



En este ejemplo tenemos nuestra posición implícita marcada por el puntero p. Como ven, la última posición en la que se hizo algo fue la segunda. Aquí, p puede avanzar solo hacia delante, por lo cual al llegar al último nodo y querer avanzar una posición más debe regresar al primer nodo de la lista.

La operación de borrado de un nodo en este ejemplo será complicada, pero ya verán ustedes el por qué cuando tengan que hacer ejercicios.
Les dejo aquí un código fuente de cómo se implementaría esta estructura para listas de enteros:

Código:
TYPE
   ListaIndizadaEnteros= POINTER TO ElemLista;
   ListaEnteros= POINTER TO NodoLista;
   NodoLista=   RECORD
                  numero: INTEGER;
                  sig: ListaEnteros;
               END;
   ElemLista=   RECORD
                  lista: ListaEnteros;
                  actual: ListaEnteros;
               END;


Es difícil de comprender al principio. Básicamente lo que hacemos primero es definir una lista encadenada de enteros tal como lo hemos hecho siempre. En este caso dicha lista se llama ListaEnteros la cual no es más que un puntero a algo del tipo NodoLista. Eso ya lo conocen. Ahora bien, teniendo entonces el tipo ListaEnteros debemos definir un registro con dos punteros al tipo ListaEnteros, uno para indicar el inicio de mi lista indizada y otro que será el iterador. Teniendo dicho registro llamado ElemLista, me declaro entonces el tipo ListaIndizadaEnteros como puntero a ese registro.

El resto al respecto de esta implementación lo verán ustedes solos con los ejercicios.

_____________________

Indizado Explícito:

Esta variante puede implementarse de varias maneras. La idea es que los nodos tengan un número que indica su posición en la lista, tomando como posición 0 a la primera posición. Una forma puede ser que cada nodo tenga un entero que indica esta posición. Parecería aceptable, pero al momento de quitar un nodo intermedio habría que actualizar el índice de todos los nodos posteriores a ese, lo cual es muy costoso. Lo mismo a la hora de insertar algo en una posición intermedia.

Otra forma es tener una implementación como la anterior, es decir, implícita, pero habría que tener un entero que indique la cantidad de nodos totales en la lista y otro entero que indique la posición a la que apunta el puntero iterador. Esto mejoraría bastante algunas cosas respecto a las búsquedas, sin embargo, quedará como tarea de ustedes el implementarlo.

A continuación les dejo ejercicios para que apliquen todo lo que hemos hablado sobre listas más lo que ya conocen desde antes.

_________________________________

Ejercicios sobre listas encadenadas:

Primera parte: accediendo directamente a la representación.

Ejercicio 1
Consideren la siguiente representación para una Lista Encadenada de Naturales:

Código:
TYPE
      LNat = POINTER TO NodoLista;
      NodoLista = RECORD
                    elem : CARDINAL;
                    sig : LNat;   
              END;

Implementen las siguientes operaciones, en forma iterativa y sin usar procedimientos auxiliares, utilizando la representación anterior.
Para la operación IsIncluded consideren la siguiente definición: L1 está incluida en L2 si y sólo sí existen dos listas, L3 y L4, tal que cumplen que L2 = L3L1L4.

Código:
1. PROCEDURE Last(l : LNat) : CARDINAL;
(* Retorna el último elemento, si la lista l es no vacía. *) 
2. PROCEDURE Average(l : LNat) : REAL;
(* Retorna el promedio de sus elementos, si la lista l es no vacía. *) 
3. PROCEDURE Insert(x : CARDINAL; l : LNat) : LNat;
(* Dada la lista l ordenada, inserta a x en l ordenadamente *) 
4. PROCEDURE Snoc(x : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x al final de la lista l *)
5. PROCEDURE Remove(x : CARDINAL; l : LNat) : LNat;
(* Elimina un natural dado x de la lista l *) 
6. PROCEDURE IsIncluded(l, p : LNat) : BOOLEAN;
(* Verifica si la lista l está incluida en la lista p *)

Las estructuras que devuelve su solución: ¿comparten memoria con los parámetros? En caso afirmativo: ¿qué problemas puede acarrear esto?

------------------------------------------------------------------------------------

Ejercicio 2

Utilizando la representación para Lista Encadenada de Naturales del ejercicio 1 implementen las siguientes operaciones, en forma iterativa, sin usar procedimientos auxiliares y sin que las soluciones retornadas compartan memoria con los parámetros:

Código:
1. PROCEDURE Take(i : CARDINAL; l : LNat) : LNat;
(* Retorna la lista resultado de tomar los primeros i elementos de    l *) 
2. PROCEDURE Drop(i : CARDINAL; l : LNat) : LNat;
(* Retorna la lista resultado sin los primeros i elementos de l *) 
3. PROCEDURE Merge(l, p : LNat) : LNat;
(* Genera una lista intercalando ordenadamente las  listas l y p,    que vienen ordenadas *) 
4. PROCEDURE Append(l, p : LNat) : LNat;
(* Retorna una lista que contiene a los elementos de l y luego a    los elementos de p, en el mismo orden. *)


-------------------------------------------------------------------------------------

Ejercicio 3

Utilizando la representación para Lista Encadenada de Naturales del ejercicio 1 implementen las siguientes operaciones, en forma iterativa y sin usar procedimientos auxiliares:

Código:
1. PROCEDURE Insert(x : CARDINAL; VAR l : LNat);
(* Dada la lista l ordenada, inserta a x en l ordenadamente *) 
2. PROCEDURE Snoc(x : CARDINAL; VAR l : LNat);
(* Inserta el elemento x al final de la lista l *)
3. PROCEDURE Remove(x : CARDINAL; VAR l : LNat);
(* Elimina el natural x de la lista l *) 


¿Qué diferencias encuentran entre las soluciones de este ejercicio y las del ejercicio 1?

-------------------------------------------------------------------------------------

Ejercicio 4

Una variante a la implementación clásica de listas encadenadas es la llamada Lista Doblemente Encadenada de la cual ya hablamos.
Dar una representación e implementar las siguientes operaciones para Listas Doblemente Encadenadas de Naturales:

Código:
1. PROCEDURE Null() : LNat;
(* Crea la lista vacía *) 
2. PROCEDURE Cons(x : CARDINAL; l : LNat) : LNat;
(* Inserta un elemento al principio de la lista *)
3. PROCEDURE IsEmpty( l : LNat) : BOOLEAN;
(* Verifica si la lista está vacía *) 
4. PROCEDURE IsElement(x : CARDINAL; l : LNat) : BOOLEAN;
(* Verifica si un natural pertenece a la lista *) 
5. PROCEDURE Remove(x : CARDINAL; l : LNat) : LNat;
(* Elimina todas las ocurrencias del natural x en la lista l *) 
6. PROCEDURE Insert(x : CARDINAL; l : LNat) : LNat;
(* Inserta ordenadamente x en l, asumiendo que l está ordenada *)

----------------------------------------------------------------------------------

Ejercicio 5

Otra variante a las implementaciones clásicas de listas encadenadas es la llamada Lista Encadenada Circular de la cual también ya hablamos.
Dar una representación e implementar las siguientes operaciones para Listas Encadenadas Circulares de Naturales:

Código:
1. PROCEDURE Null() : LNat;
(* Crea la lista vacía *)
2. PROCEDURE IsEmpty( l : LNat) : BOOLEAN;
(* Verifica si la lista está vacía *) 
3. PROCEDURE Tail(l : LNat) : LNat;
(* Retorna la lista sin su primer elemento, si la lista no es    vacía *) 
4. PROCEDURE Last(l : LNat) : CARDINAL;
(* Retorna el último elemento de l, si la lista no es vacía *) 
5. PROCEDURE Insert(x : CARDINAL; l : LNat) : LNat;
(* Inserta ordenadamente x en l, asumiendo que l está ordenada *)

-------------------------------------------------------------------------------------

Ejercicio 6

Una tercer variante a las implementaciones clásicas de listas encadenadas es la llamada Lista Doblemente Encadenada y Circular.
Dar una representación e implementar las siguientes operaciones para Listas Doblemente Encadenadas Circulares de Naturales:

Código:
1. PROCEDURE Null() : LNat;
(* Crea la lista vacía *) 
2. PROCEDURE Cons(x : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x al principio de la lista l *) 
3. PROCEDURE Snoc(x : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x al final de la lista l *)
4. PROCEDURE IsEmpty( l : LNat) : BOOLEAN;
(* Verifica si la lista l está vacía *)


------------------------------------------------------------------------------------

Ejercicio 7

Una variante importante de listas son las Listas Indizadas. En éstas, se manipula la lista mediante posiciones, generalizando la idea de los arreglos para estructuras no acotadas. Las posiciones se pueden manejar de forma explícita o implícita.

Dar una representación e implementar las siguientes operaciones que se corresponden con el manejo explícito de posiciones en una lista:

Código:
1. PROCEDURE Null() : LNat;
(* Genera la lista vacía *) 
2. PROCEDURE IsEmpty( l : LNat) : BOOLEAN;
(* Verifica si la lista está vacía *) 
3. PROCEDURE IsDefined(p : CARDINAL; l : LNat) : LNat;
(* Dado un natural p, retorna TRUE si, y solamente  si, la lista    está definida en la posición p, considerando a las posiciones a    partir de 0 *)
4. PROCEDURE Insert(x : CARDINAL; p : CARDINAL; l : LNat) : LNat;
(* Inserta un elemento x en la posición p de la lista,    considerando a las posiciones a partir de 0. Si la lista tiene    longitud m, con m-1 menor a p, lo inserta en la posición m. Si la    lista tiene longitud m, con m-1 mayor o igual a p, inserta x en la
posición p y desplaza en una posición los elementos que estuvieran    en las posiciones siguientes *)   
5. PROCEDURE Element(p : CARDINAL; l : LNat) : CARDINAL;
(* Retorna el elemento que se encuentra en la posición p de l, si    p está definida en l *) 
6. PROCEDURE Delete(p : CARDINAL; l : LNat) : LNat;
(* Dado un entero p, elimina de la lista el elemento que se    encuentra en la posición p. Si la posición no está definida, la    operación no tiene efecto. Si la posición está definida, elimina    el elemento en dicha posición y desplaza en una posición los    elementos que estuvieran en las posiciones posteriores a p    (contrae la lista) *)


Dar una representación e implementar las siguientes operaciones que se corresponden con el manejo implícito de posiciones en una lista:

Código:
1. PROCEDURE Null() : LNat;
(* Crea la lista vacía *) 
2. PROCEDURE IsEmpty(l : LNat) : BOOLEAN;
(* Verifica si la lista está vacía *) 
3. PROCEDURE Start(VAR l : LNat);
(* Coloca la posición actual al inicio de la lista *) 
4. PROCEDURE Next(VAR l : LNat);
(* Mueve la posición actual al siguiente nodo (elemento). En caso    de que la posición actual sea el final de la lista, coloca la    posición actual al inicio de la lista (tiene un comportamiento    circular) *) 
5. PROCEDURE End(l : LNat) ) : BOOLEAN;
(* Verifica si la posición actual es la posición final *) 
6. PROCEDURE Insert(x : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x luego de la posición actual en la lista.    La posición actual pasa a ser el elemento (nodo) recién insertado.    Si la lista l está vacía, el resultado es la lista unitaria que    contiene a x, siendo este elemento la posición actual en la lista    resultado *) 
7. PROCEDURE Element(l : LNat) : CARDINAL;
(* Retorna el elemento en la posición actual, si la lista no está    vacía *) 
8. PROCEDURE Delete(l : LNat) : LNat;
(* Elimina de la lista el elemento en la posición actual, si la    lista no está vacía. La posición actual pasa a ser la siguiente al    elemento eliminado. Si l tenía un único elemento, la lista    resultante es la lista vacía *)


=============================================

Segunda parte: utilizando operaciones primitivas.

Ejercicio 8

Llamaremos a las operaciones que se describen a continuación operaciones primitivas sobre Listas Encadenadas de Naturales.

Código:
PROCEDURE Null() : LNat;
(* Crea la lista vacía *) 
PROCEDURE Cons(x : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x  al principio de la lista l *) 
PROCEDURE IsEmpty(l : LNat) : BOOLEAN;
(* Verifica si la lista l está vacía *) 
PROCEDURE Head(l : LNat) : CARDINAL;
(* Retorna el primer elemento de la lista, si la lista l no es vacía *) 
PROCEDURE Tail(l : LNat) : LNat;
(* Retorna la lista sin su primer elemento, si la lista l no es vacía *)


Utilizando solamente este conjunto minimal de operaciones es posible implementar cualquier otra operación sobre listas sin acceder a, ni conocer, la representación de LNat. Esto responde a los Tipos Abstractos de Datos, ya que justamente la idea es comenzar a ver a las listas encadenadas como tipos abstractos de datos.

Utilicen las operaciones anteriores para implementar las siguientes:

Código:
1. PROCEDURE Length(l : LNat) : CARDINAL;
(* Retorna la cantidad de elementos de la lista l *) 
2. PROCEDURE Append(l, p : LNat) : LNat;
(* Agrega la lista p al final de la lista l *)
3. PROCEDURE Reverse(l : LNat) : LNat;
(* Invierte la lista l *) 
4. PROCEDURE Sort(l : LNat) : LNat;
(* Ordena la lista l *) 
5. PROCEDURE HowMany(x : CARDINAL; l : LNat) : CARDINAL;
(* Cuenta las ocurrencias del natural x en la lista l *) 
6. PROCEDURE Max(l : LNat) : CARDINAL ;
(* Retorna el máximo elemento de la lista l, si l no es vacía *) 
7. PROCEDURE IsSorted(l : LNat) : BOOLEAN;
(* Verifica si la lista l  esta ordenada *) 
8. PROCEDURE Change(x, y : CARDINAL; l : LNat) : LNat;
(* Retorna la lista resultado de cambiar el elemento x (cada vez que    aparece) por el elemento y en la lista l *) 
9. PROCEDURE InsBefore(x, y : CARDINAL; l : LNat) : LNat;
(* Inserta el elemento x inmediatamente antes de la primera ocurrencia    del elemento y en la lista l, si x está en l *) 
10. PROCEDURE Equals(l, p : LNat) : BOOLEAN;
(* Verifica si las listas l y p son iguales *) 
11. PROCEDURE Merge(l, p : LNat) : LNat;
(* Genera una lista ordenada intercalando ordenadamente las listas l y p,    que vienen ordenadas *)


Muchísima suerte con todos estos ejercicios. Les recomiendo, como siempre, que los hagan ya que es la única forma de aprender realmente. Con todo esto, sabrán manejar los punteros al máximo nivel y podrán trabajar con estructuras dinámicas muy fácilmente.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
sr floyd
Usuario Activo


Registrado: 05 Sep 2011
Mensajes: 196

Mensaje Publicado: Jueves 25 Oct 2012 12:47

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Excelente itinerario de ejercicios !! Intentaré resolver algunos, gracias Kyshuo!!

Ok

Volver arriba
Ver perfil del usuario Enviar mensaje privado MSN Messenger
sr floyd
Usuario Activo


Registrado: 05 Sep 2011
Mensajes: 196

Mensaje Publicado: Martes 30 Oct 2012 16:26

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Profe qué ventajas trae declarar al tipo ElemLista con dos campos del tipo ListaEnteros en lugar de declarar solo dos punteros del tipo ListaEnteros?
tiendo a pensar que se requiere de más memoria declarado de esa manera, de seguro hay una ventaja pero no estoy seguro de reconocerla
Cita:
ElemLista= RECORD
lista: ListaEnteros;
actual: ListaEnteros;
END;

Volver arriba
Ver perfil del usuario Enviar mensaje privado MSN Messenger
Emirona07
Usuario Iniciado


Registrado: 10 Mar 2013
Mensajes: 11

Mensaje Publicado: Viernes 22 Mar 2013 04:46

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Buenas.

Una consulta, ¿sería posibles que explicaras más detalladamente el tema de Listas Indizadas Implícitas?

Leí tus teorías y necesito realizar una serie de ejercicios con este tema (entre ellos varios de los que tú posteaste) pero no termino de entender cómo una de las entradas del segundo registro apunta al primero y cómo la otra apunta al campo "actual" (es decir, cómo Modula sabe cuál debe apuntar a cada uno).

Me interesaría saber bien cómo aplicar un procedimiento para recorrer la lista hasta el final y luego obtener la primer celda de la lista (según lo que entendí esta es la única forma de lograrlo).

El procedimiento Start creo que sería un buen ejemplo para demostrar cómo hacerlo, aunque agradecería acompañarlo de una explicación. Disculpa por tantos pedidos.

Muchas gracias desde ya.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Viernes 22 Mar 2013 16:21

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

En primer lugar no es molestia, en segundo lugar, debes manejar bien el tema de listas encadenadas simples, si no es así entonces repasa eso primero.

El centro de tu duda está en cómo se define el tipo ListaIndizada. Como viste en el dibujo que hice, hay dos punteros, uno que apunta al inicio de la lista y otro al nodo actualmente usado:



Si te fijas bien, dentro de esa estructura tenemos una lista encadenada común y corriente. Entonces lo primero que hacemos es definirnos eso en Modula, una lista encadenada:

Código:
  1. ListaEncadenada= POINTER TO NodoListaEncadenada;
  2. NodoListaEncadenada= RECORD
  3. elem: CARDINAL;
  4. sig: ListaEncadenada;
  5. END;


Como dije, si manejas el tema de listas encadenadas esto será sencillo porque lo que acabo de definir allí es justamente una lista encadenada simple, en este caso de NATURALES. No me extenderé en explicarte eso porque está dado en lecciones de Pascal y en las de Modula.

Ahora tenemos que definir la lista indizada. Esta debe contener un puntero al primer nodo de la lista encadenada y otro al actual. Entonces su definición queda así:

Código:
  1. ListaInd= POINTER TO NodoInd;
  2. NodoInd= RECORD
  3. primero: ListaEncadenada;
  4. actual: ListaEncadenada;
  5. END;


Esto resultará dificil de digerir, no es para nada sencillo. El nodo de la lista indizada tiene dos elementos del tipo ListaEncadenada, uno llamado primero y el otro actual.

El tipo ListaInd no es más que un puntero a ese registro.

En primera instancia hay que definirse la lista vacía, es decir ¿cómo está dada? Podría ser un puntero a NIL o bien, que tanto el primero como el actual sean NIL, o bien, solo conque el primero sea NIL basta. Eso lo decides tú. Yo prefiero que ambos sean NIL porque en sí uno siempre trabajará desde el puntero actual.

Ahora, por ejemplo, si tu quieres que actual vuelva al inicio de la lista no haces más que:

Código:
  1. actual:= primero


Analiza esto y si tienes más dudas, o bien, si no te aclaré nada, dímelo.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Emirona07
Usuario Iniciado


Registrado: 10 Mar 2013
Mensajes: 11

Mensaje Publicado: Viernes 22 Mar 2013 19:09

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Estoy entendiendo, estoy entendiendo...

Una de mis dudas es cómo el programa detecta cuál de los dos campos apunta al primero y cuál al actual. Tengo bien entendidos los temas de punteros y listas encadenadas simples tanto en Pascal como en Modula.

La pregunta que yo me hago es, si por ejemplo, tengo un módulo o procedimiento auxiliar y a ese procedimiento le paso una lista encadenada simple que no esté apuntando actualmente al primer elemento. Por ejemplo, si dentro de mi programa principal recorro la lista hasta cierto punto, y una vez llegado a ese punto (la mitad de la lista, por ejemplo) se la mando al procedimiento. ¿Cómo haría mi procedimiento para saber qué valor tiene el campo "Primero" y qué valor tiene el campo "Actual"?

¿Y cómo podría hacer para pararme dentro del procedimiento auxiliar en la primera celda de la lista encadenada simple (la primera de la lista original, no la celda con la cual llamé al procedimiento)?

Creo que tengo que recorrer toda la lista y cuando llego al final recorrer uno más para que vuelva al principio, pero evidentemente si estoy en NIL (el final) no voy a poder hacer un l := l^.Sig;

¿Se entiende más o menos cuál es mi problema?

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Sábado 23 Mar 2013 01:15

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Vamos por partes: Imagina primero que tenemos una referencia L de tipo ListaIndizada:

Código:
  1. VAR L: ListaIndizada;


Aquí haré todo directo, no me basaré en TADs ni módulos independientes, así que imagina que todo esto lo hacemos directo sobre el módulo principal. En alguna parte del código inicializo a L como lista vacía:

Código:
  1. NEW(L);
  2. L^.primero:=NIL;
  3. L^.actual:=NIL;


Como ves, mi definición de lista vacía es que ambo punteros sean NIL.

Ahora imagina que vamos a agregar un objeto de tipo ListaEncadenada (justamente primero y actual son de ese tipo). Supón que nuestro nuevo elemento ha sido inicializado así:

Código:
  1. NEW(miElem);
  2. miElem^.elem:= 10; (*Un numero cualquiera*)
  3. miElem^.sig:= NIL;


O sea, es un nodo con el número 10. Debemos agregarlo a la lista indizada, como está vacía es el primer elemento y por tanto actual y primero apuntarán al mismo:

Código:
  1. L^.primero:= miElem;
  2. L^.actual:= miElem;


Si fueras ahora a agregar un nuevo elemento a la lista, suponiendo que este debe ir al final ¿cómo harías? Ten en cuenta que primero no debe ser modificado porque siempre apuntará al primero nodo, así que todo lo haces con actual.

Piensalo un poco y luego vemos tus otras dudas. Seguramente con esto ya se irán evacuando.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Emirona07
Usuario Iniciado


Registrado: 10 Mar 2013
Mensajes: 11

Mensaje Publicado: Sábado 23 Mar 2013 02:19

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Supongo que debería crear un NEW(L^.actual^.sig), avanzar el actual al siguiente (L^.actual := L^.actual^.sig), asignarle el próximo valor (L^.actual^.elem := VALOR) y luego apuntarlo a NIL (L^.actual^.sig := NIL).

¿Estoy muy errado?

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Sábado 23 Mar 2013 21:40

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Pues no, no estás errado, eso está bien, suponiendo (como en este caso) que ya estás sobre el final de la lista.

Con eso digamos que deberías aclarar tu duda de como Modula "sabe" cuál es el primero y cual el actual. En realidad Modula no lo sabe, Modula solo apunta punteros a distintos lugares, tú eres quien lo sabe y simplemente dice a donde hay que apuntar ¿me explico?

Siendo que primero apunta siempre al primer nodo porque justamente tú te encargas de eso en las inserciones, hacer que actual vuelva a esa posición es hacer

Código:
  1. actual:= primero;


Si tienes más dudas al respecto de esto pues solo comenta. Me da la sensación de que estas dudas te surgen para implementar la tarea de Prog2 de este año ¿estoy en lo cierto?

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Emirona07
Usuario Iniciado


Registrado: 10 Mar 2013
Mensajes: 11

Mensaje Publicado: Domingo 24 Mar 2013 05:38

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Sí, entiendo. En realidad me expresé mal y no tengo la duda de cómo módula sabe cuál es la primera celda en el procedimiento principal, mi duda viene cuando me mandan una lista en la cual ya recorrieron la mitad de las celdas (por ejemplo) y mi procedimiento la agarra ya "empezada". Yo debo volver a la primera celda, pero me parece que estoy interpretando mal la tarea, porque al no poder declarar variables en el programa principal no creo que sea posible tener un respaldo de cuál es la primera celda.

Sí, mi problema nace de uno de los procedimientos de la tarea de este año. Me mandan una lista y me piden que me posicione en la primera ubicación, por lo que yo interpreté que me podrían mandar la lista recorrida hasta X ubicación. ¿Estoy interpretando mal?

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Domingo 24 Mar 2013 22:10

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Pues no, no interpretas mal pero hay algo que te confunde. La lista enlazada está representada por un TAD, en concreto este TAD se llama Ruta (en la tarea). Imagina que tenemos un TAD diferente, al que llamamos de forma MUY ORIGINAL ListaIndizada, y que esta lista indizada es de naturales (porque es fácil trabajar con ellos).

Pongámosle solo estas operaciones al TAD:

  • CrearLista: Crea la lista vacía
  • InsertarNumero(num: CARDINAL; VAR lista: ListaIndizada): Inserta un número en la posición actual.
  • Siguiente(VAR lista: ListaIndizada): Mueve la posición actual al siguiente nodo, si no hay siguiente nodo la posiciona al inicio.
  • Inicio(VAR lista: ListaIndizada): Mueve la posición actual al inicio.


Estas operaciones se hacen dentro del TAD ListaIndizada y reciben como argumento elementos de ese tipo. Es dentro de él que puedes hacer lo que quieras. Por ejemplo, la operación Inicio recibe por referencia un elemento lista de tipo ListaIndizada, entonces esa operación puede hacer:

Código:
lista^.actual:= lista^.inicio:


Si estás, por ejemplo, en el módulo principal y tienes un objeto de tipo ListaInidizada llamado miLista y quieres que su posición actual regrese al inicio haces

Código:
Inicio(miLista);


Y listo.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Emirona07
Usuario Iniciado


Registrado: 10 Mar 2013
Mensajes: 11

Mensaje Publicado: Martes 26 Mar 2013 01:59

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Bien, ya entendí casi todo (creo). Cualquier otra cosa te vuelvo a preguntar, muchas gracias.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
lulus



Registrado: 28 Mar 2013
Mensajes: 3

Mensaje Publicado: Jueves 28 Mar 2013 17:40

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

Podrías citar un ejemplo de como destruir una listaindizada implicitamente?, porque no me queda del todo claro!!gracias!

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 905

Mensaje Publicado: Jueves 28 Mar 2013 18:49

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

No tiene mucha dificultad... básicamente si lo que tienes que hacer es destruirla toda te olvidas que es indizada y la tratas como una lista encadenada normal ya que en sí es lo que es.

Destruyes la lista encadenada nodo a nodo (ya verás tu si lo haces iterativamente o recursivamente) y luego liberas el nodo de lista indizada. Piensalo un momento. A partir del nodo INICIAL puedes recorrer absolutamente toda la lista sin siquiera usar el ACTUAL. También puedes usarlo si lo regresas al inicio y te basas en él para ir eliminando nodos.

Te pido que lo pienses un poco y si no lo logras publicaré un pseudocódigo para darte una mano.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
lulus



Registrado: 28 Mar 2013
Mensajes: 3

Mensaje Publicado: Jueves 28 Mar 2013 19:05

Título del mensaje: Re: Programando desde 0: 49- Listas encadenadas "El reg

Responder citando

ah, muchas gracias por la pronta respuesta!,es lo que estaba pensando, pero teóricamente no llegaba a ver (en términos de memoria) el porque al destruir la indizada no se destruían las encadenadas!

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Responder al Tema Ir a página 1234Siguiente
Mostrar mensajes anteriores:   
Ir a:  
Todas las horas están en GMT + 2 Horas

Temas relacionados

Tema Autor Foros Respuestas Publicado
El foro no contiene ningún mensaje nuevo

Base de datos mysql desde Vb 6

Fleki Visual Basic y VBA 0 Viernes 05 Sep 2014 23:02 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Crear web con contenido generado por usuarios (...

Antirreni91 Programación Web en general 4 Viernes 05 Sep 2014 16:08 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Exception in thread "main"

SeñorDelMostacho Java 13 Jueves 10 Jul 2014 15:48 Ver último mensaje
El foro no contiene ningún mensaje nuevo

No puedo abrir archivo desde macro al cambiar l...

Calcetinesdepuntitos Visual Basic y VBA 1 Jueves 03 Jul 2014 19:23 Ver último mensaje
El foro no contiene ningún mensaje nuevo

problema renombrar carpeta "entrada" ...

willer Temas generales 0 Sábado 28 Jun 2014 14:06 Ver último mensaje
Panel de Control
No puede crear mensajes, No puede responder temas, No puede editar sus mensajes, No puede borrar sus mensajes, No puede votar en encuestas,