Curso C++: ¿Que son las Listas?

Introducción:

Las Listas son estructuras enlazadas, es decir de una serie de structs enlazados con un puntero. Cada uno de estos structs tiene un puntero al siguiente elemento de la lista, y además un único valor que guarda. Estos son los famosos struct Nodo que vimos en la publicación ¿Que son los Struct?.

Indice del Curso

Se ha realizado este curso con la idea que contenga 7 unidades hasta el momento, eso no quiere decir que se vaya anexando otros temas en el futuro.El mismo va tener el siguiente temario.Haz clic en los enlaces de los temas.

Variables y Tipos de Datos
Estructuras de Control
Manejo de Vectores
Principio Modular:Concepto de Acciones y Funciones
¿Que son los Structs?
Manejo de Archivos
Listas(Usted esta aquí.Este tema se va tratar en este curso)

Anexo

Direcciones de Memoria y Punteros

Tipos de struct Nodo que podemos tener:

StructNodo de enteros:

StructNodo de Caracteres:

StructNodo de Structs (los más usados):

Acordarse que un puntero, apunta a la dirección en memoria de una variable (ejemplo: &a ), no a la variable en sí. También hay que acordarse que cuando pasamos la dirección de memoria de una variable (&a) en una función/acción, por ej:

void funcion (int &a)

le estamos diciendo que el valor de la variable puede ser modificado.

Entonces, al tener un puntero (*sgte) que apunta a nuestro siguiente struct, tenemos un estilo de lógica secuencial, arman entre ellos una lista de elementos. Más fácil, se los muestro:

Vamos a utilizar a los Nodo Entero:

Nodo Entero* sgte; tiene guardada la dirección de memoria del siguiente struct. Se los muestro con una imagen:

Los 3 son structs Nodo Entero, los “0x28ffcc”,“0x29ffcc”,“0x30ffcc” son las direcciones de memoria de estos structs, y los punteros sgte apuntan a eso. ¿Cual es la gracia? Que apuntando a esas direcciones, podemos saber con precisión los datos del struct en memoria y a su vez dar una especie de “secuencia y orden”.

A su vez, teniendo esta variable sgte podemos recorrer esta lista, ya que llamando a sgte nos da el siguiente struct, llamándolo otra vez, nos da el que le sigue y así.

En estos nodos vamos a tener un puntero (*sgte), desde el cual vamos a poder acceder a las estructuras, la única forma en que podemos movernos por el struct, y es muy importante saber manejarlo bien.

Cuando vamos a crear una lista, vamos a tener un puntero *p (o como quieras llamarle), que va a ser el puntero con el que vamos a recorrer la lista, desde el que vamos a ir agregando/quitando elementos, etc.

p es un puntero a struct Nodo, y lo inicializamos en NULL (que se va a decir “es una lista vacía”, porque efectivamente… no tiene datos ese struct). Desde esa lista vacía, vamos a ir agregando structs, conforme lo necesitemos. Es importante tener en cuenta que el último “elemento” de la lista tiene que ser NULL, ¿por qué importante?, porque va a ser nuestro corte cuando leamos. O sea “mientras lo que lea p sea distinto de NULL, hace algo”. Es como el EOF (end of file) de los archivos.

Efectivamente, mientras que p sea distinto de NULL, hace algo y dame el siguiente struct (para obviamente evaluar si es null, hacer algo…

Existen dos tipos de estructuras enlazadas, las pilas y las colas.

¿Que son las Pilas?

Son una colección de elementos de un mismo tipo, a las cuales se les puede añadir un elemento, quitar un elemento, recorrer, etc. Utilizan el modo LIFO (Last input, first out), que indica que el último Nodo que se agregó, es el primero que se saca de la lista. Como una pila de platos apilados, no se puede sacar cualquiera porque se caerá toda la pila, se va sacando el de más arriba, casualmente es el último que se colocó hasta el momento.

Las funciones son:

Push → Para agregar un valor al principio de la pila

Pop → Para quitar el último valor ingresado.

Push

La función new Alumno() genera un nuevo struct y le asigna espacio en memoria. Este struct tiene los valores sin asignar, o sea tienen basura.

Básicamente resume algunos pasos en cuanto al manejo de memoria en código, lo que es bueno para este caso

“Alumno*& alumno” es el puntero con el que nos movemos por la lista, que se la pasa por referencia, para modificar a donde va a apuntar.

Genero una variable aux que es un puntero a Alumno y le asigno el resultado de new Alumno() que va a ser una porción de memoria que la misma función elige para el tamaño del struct que se utiliza (en este caso, Alumno). Ya teniendo este struct Alumno listo, le cargo los datos “info” con “valor”( ver imagen de arriba).

Acordémonos que *alumno apunta a la lista original, y por ser una pila, apunta al último elemento de mi lista original. Entonces a este *aux va a pasar a ser mi último cuando lo agregue.Para esto hago que aux -> siguiente sea alumno, de esta forma queda enlazada la lista.

“alumno=aux” sirve para actualizar a “alumno”, porque “alumno” en pilas, SIEMPRE tiene que apuntar al primero de la lista. Ese es el sentido, con el puntero agrego, y saco Nodos.

El valor que nosotros conocemos y tenemos manera de acceder y manejar es a alumno. De ahí que necesitamos si o si que alumno sea siempre el primer elemento, si no, pierde todo tipo de lógica tener una lista al no conocer su primer elemento.

Pop

La función Pop lo que hace, es sacarle el valor al primer Nodo y eliminarlo.

Declaro v, que es básicamente un auxiliar que utilizamos para poder devolver el valor del struct que vamos a eliminar (Sino se pierde, y no queremos eso).
Creamos una variable puntero q (*q) que apunta a Info y le decimos que apunte al primer elemento (p en el ejemplo del main() ).
Pasamos el valor del struct a v, así lo podemos utilizar, luego hacemos que el primer elemento, EL SIGUIENTE, porque a ese primer elemento lo vamos a borrar.Otra vez, veamos el imagen:

Acuerdarse que primerElem y q, son punteros, y tienen direcciones de memoria. Asignarle el valor de un puntero a otro, es como decirle “Ahora vas a apuntar a donde estoy apuntando yo”.

Un programa completo con push y pop es el siguiente:

y el resultado por pantalla será:

Básicamente, le agrego a una lista, los valores 22, 48, 125. Y luego se los saco mientras la lista no sea NULL (es decir, mientras exista un Nodo en la lista).

Push()/Pop() usando struct

Todo bien, pero este es el caso más fácil que existe… Y no te van a pedir que hagas eso en la mayoría de los casos, sino que te van a pedir que uses un Nodo Struct. Entonces ¿Qué pasaría si un Nodo tuviera en vez de un entero, otro struct? Veamos:

Si bien la lógica sigue siendo exactamente la misma, cambian un poco las funciones, mas que nada los tipos de datos.

NodoPersona tiene una Persona adentro.
Push() ahora agrega una Persona a la lista de personas (NodoPersona), no un entero.
Pop() ya no devuelve un entero, sino que devuelve un struct Persona.

¿Como los llamamos en el main()?

Ahora, cómo vamos a agregar un struct, hay que darle valores y recien después agregarlo. Pero vean que no tiene nada de distinto solamente que el Pop() lo guardamos en una Persona, y no un entero.

¿Que son las Colas?

La diferencia más crucial entre pilas y colas es la forma en que se agregan y eliminan los elementos. Mientras que la pila usa LIFO, las colas usan FIFO(first input, first out), primero entra, primero sale. Traten de pensarlo como una cola de supermercado, el primero en llegar es el primero que sale.

Efectivamente, el 1 que fue el primero que entró, fue el primero que salió.

¿Como agregar()?

agregar() son 3 simples pasos.

Crear un nodo nuevo (p), en donde le vamos a cargar los datos
Cargarle los datos al nuevo nodo (p)
Preguntar si el frente de la cola es NULL, o sea si es cola vacía o no.

Las colas se manejan con 2 punteros, el primero de la cola y el último de la cola. En el caso inicial, ambos apuntan a NULL. Cuando se agrega el primero, tanto el primero como el último apuntan a ese… porque no hay otro valor, cuando se empiezan a agregar mas, ahí se empiezan a ver la diferencia.

Cabe aclarar que en la línea 22, el último de la cola es siempre el que se está agregando, porque básicamente es el último en agregarse hasta ese momento. El primero nunca se toca.

¿Como Suprimir()?

Declaro v que es el valor que voy a retornar.
Declaro un auxiliar (q), el cual voy a borrar, y le digo que apunte al frente.
Hago que el frente, sea ahora el siguiente al que voy a borrar.
Si inicio = NULL, es porque no hay más elementos en la lista, entonces fin y frente van a apuntar a NULL.