Seguimos buscando a Arshak. Ayudanos compartiendo!
Encuesta no oficial de docentes
Resultados de la encuesta no oficial de docentes
Probaste el SIGA Helper?

Donar $100 Donar $200 Donar $500 Donar mensualmente


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
[ALGORITMOS] Ayuda con punteros y nodos
Autor Mensaje
H3rnst Sin conexión
Secretario de la SAE
Overlord
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 644
Agradecimientos dados: 243
Agradecimientos: 112 en 49 posts
Registro en: Sep 2010
Mensaje: #1
[ALGORITMOS] Ayuda con punteros y nodos Dudas y recomendaciones Algoritmos y Estructuras de Datos
Bueno, la consulta es puntualmente sobre el funcionamiento de este algoritmo:
[Imagen: listaAgregar2.jpg]

Lo que hace el procedimiento es:
1) Crear un nodo
2) Asignarle el valor que viene como parámetro
3) Agregarlo al final de la lista, (el puntero que apunta a esta lista, también es parámetro)

En un momento se llega a la condición de si la lista está vacía o no. Si está vacía, directamente se le hace apuntar al nuevo nodo, pero si no está vacía entonces se crea un puntero 'aux' que apunta a la lista, y luego se empieza a recorrer buscando el último nodo. Cuando lo encuentra, le asigna al campo 'sig' la dirección del nuevo nodo que creamos más arriba.

Ahora, esto me genera dos preguntas:
1) El puntero 'lst', ¿No sigue apuntando a la misma lista de siempre? Osea, a la que no tiene al nuevo nodo.
2) El puntero 'aux', al finalizar el procedimiento, ¿No está apuntando a una lista que contiene únicamente dos nodos? (es decir, el último de la lista que pasé como parámetro y el nuevo que agregé ahora) Digo porque ¿Los anteriores no los fué perdiendo con cada iteración del while?

Desde ya gracias por la ayuda. Hace banda que no toco esta materia y me da bronca porque son cosas que sabía hacer de taquito, y ahora me surgen estas dudas boludas.

saludos!
24-08-2011 20:22
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 81
Agradecimientos: 232 en 78 posts
Registro en: Nov 2009
Mensaje: #2
RE: [ALGORITMOS] Ayuda con punteros y nodos
A mi parecer punteros es lo más difícil de entender(me lo tuvieron que explicar como 3 veces =P ), espero no marearte.

Pensá en un puntero como un integer que guarda un número(en C es muy fácil de comprobar porque te deja imprimir dicho número), ese número es la dirección de otra variable, la cuál se dice está siendo apuntada. Cuando un puntero vale NIL significa que no tiene ninguna dirección guardada como valor, no apunta a nada, es como una invitación a un cumpleaños sin nada escrito. Lo que hace la función new es conseguirte un sector de memoria libre y guardarte la dirección de dicho sector en el puntero que le pasaste, por ejemplo imaginate que la dirección fuera 123, entonces nuevo que antes valía NIL ahora vale 123. Después al hacer nuevo^.info <-valor lo que estás haciendo es almacenar el valor en el sector de memoria 123. Ahora vayamos al if:

lst = NIL
Esto significa que el puntero lista no tiene ninguna dirección guardada, al hacer lst<- nuevo lo que hacés es que lst ahora valga 123, por lo tanto hacer lista^.info te va a llevar al mismo lugar que nuevo^.info. Si te fijás en el encabezado del procedimiento, lst tiene var adelante, lo que significa que las modificaciones que hagas en el procedimiento van a afectar también a la variable que le pasaste, por lo tanto luego de haber salido de Agregar lst va a seguir valiendo 123 y por lo tanto va a estar apuntando al primer y único nodo de tu lista, el cuál está guardado en el sector de dirección 123.

Ahora vamos al caso en que lst no sea NIL:
¿Cuándo decimos que se pierden nodos? Cuando perdemos su dirección, si en el único lugar donde tenías guardada la dirección del primero, guardás la dirección del siguiente, ya no tenés guardada la dirección del 1 y no hay forma de saber cuál era, por lo tanto ese nodo está perdido porque no te acordás en qué parte de la memoria está. Esa es la razón por la cuál se usan punteros auxiliares, en lst vos tenés la dirección del primer nodo, entonces lo que hacés es guardarte en aux esa dirección y recién ahí recorrerla, así que por más que vayas sobreescribiendo la dirección que guarda aux por la de los nodos siguientes, en lst seguis teniendo la dirección del primer nodo, así que no lo "perdés".

El puntero 'aux', al finalizar el procedimiento, ¿No está apuntando a una lista que contiene únicamente dos nodos? (es decir, el último de la lista que pasé como parámetro y el nuevo que agregé ahora)

Así es, si aux fuera tu único puntero, habrías perdido el resto de la lista, pero la dirección del primer nodo la tenés todavía en lst, así que no la perdiste =)
24-08-2011 21:10
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
H3rnst Sin conexión
Secretario de la SAE
Overlord
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 644
Agradecimientos dados: 243
Agradecimientos: 112 en 49 posts
Registro en: Sep 2010
Mensaje: #3
RE: [ALGORITMOS] Ayuda con punteros y nodos
Muy clara la explicación thumbup3

Igual me sigue haciendo ruido. Cuando salgo del procedimiento 'agregar' tengo un puntero 'aux' que apunta a una lista de dos nodos, y tengo otro llamado 'lst' que está igual que antes que fuera invocado el procedimiento, ¿o no? Osea, en el único momento que se modifica el valor de ese puntero es en el caso de que la lista esté vacía, porque de la otra forma se le asigna el valor a 'aux' y se sigue trabajando con 'aux'. Por eso me parece que, o estoy confundido con algún concepto, o al algoritmo le falta algo.

No se si se entiende lo que quiero decir. Yo invoco al procedimiento "Agregar" y le paso el puntero a una lista (supongamos que no está vacía). Al terminar el procedimiento, tengo un puntero 'lst' que apunta a esa lista, y tengo otro 'aux' que apunta a dos nodos (el último de 'lst' y el nuevo que quiero agregar) y lo que yo necesito es que se agregue un nodo al final de la lista apuntada por 'lst'. Al fin y al cabo, esa debería ser la función del procedimiento "Agregar" Confused

gracias!
24-08-2011 22:40
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Anirus Sin conexión
Super Moderador
Sin estado :)
*********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 1.163
Agradecimientos dados: 81
Agradecimientos: 232 en 78 posts
Registro en: Nov 2009
Mensaje: #4
RE: [ALGORITMOS] Ayuda con punteros y nodos
Ah, ahí entendí tu duda =D, pasa que vos estás pensando en 'lst' como la lista entera, cuando en realidad 'lst' sólo apunta al primer nodo de la lista. Después ese nodo se guarda en 'sig' la dirección del siguiente y así, por lo tanto si agarrás un nodo (en este caso el último) y le cambiás el valor del campo 'sig' por la dirección de otro nodo te queda agregado en la lista.
Imaginá que tenés una lista de personas, por ejemplo una fila, y a cada uno le pedís que se acuerde el nombre del que está atras. Cada uno sólo puede recordar un nombre, vos también tenés esa limitación, y el nombre que conocés es el del primero, 'lst'. Si querés recorrer la fila le tenés que preguntar al primero cuál le sigue, pero si hacés eso te vas a olvidar del nombre que sabías (el del primero), por lo que le pedís a otro que la recorra, 'aux'. 'aux' va preguntando a cada uno cuál le sigue, hasta llegar al último, el cuál no sabe el nombre de nadie, entonces 'aux' le dice que detrás de él va a ir 'pepe' (lo agregó a la fila), 'aux' sólo se acuerda el nombre del que estaba último, y vos sólo te sabés el nombre del que está primero y no tenés idea de la existencia de 'pepe', sin embargo la lista cambió, porque la próxima vez que alguien la recorra, el que estaba último le va a decir que atras suyo está 'pepe'.
(Este mensaje fue modificado por última vez en: 24-08-2011 23:07 por Anirus.)
24-08-2011 23:02
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
H3rnst Sin conexión
Secretario de la SAE
Overlord
******

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 644
Agradecimientos dados: 243
Agradecimientos: 112 en 49 posts
Registro en: Sep 2010
Mensaje: #5
RE: [ALGORITMOS] Ayuda con punteros y nodos
Aaaahora si entendí!, la verdad que sin palabras, enorme tu explicación thumbup3 como mínimo te debo un café en el buffet!

Mil gracias!
24-08-2011 23:35
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)