Estructuras de datos dinámicas y plantillas En este capítulo veremos cómo implementar una lista enlazada, una lista doblemente enlazada, una pila dinámica y una cola dinámica. Finalmente, aprenderemos a reimplementar todas estas estructuras, pero de modo independiente del tipo de dato que manejen, por medio de las plantillas.

▼

Listas enlazadas ......................... 2

Listas doblemente enlazadas

¿Qué es una lista enlazada? ............... 2

con plantillas.................................... 47

Implementación de una lista enlazada 2

Pila .................................................. 54

La clase Nodo .................................... 3

Cola ................................................. 55

La clase Lista .................................... 6

▼

▼

Los iteradores .......................... 55

▼

Resumen................................... 59

▼

Actividades............................... 60

Listas doblemente enlazadas... 20 Pila .................................................. 35 Cola ................................................. 36

▼

Plantillas .................................. 37

Servicio de atención al lector: [email protected]

2

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Listas enlazadas La lista enlazada es una estructura versátil y popular. No existe curso de C/C++ que no trate el tema, y este libro no será la excepción.

¿Qué es una lista enlazada? Una lista enlazada es una estructura de datos compuesta por nodos; cada uno de ellos se encuentra enlazado a otro por medio de un puntero. El motivo de su popularidad reside en que la lista puede crecer y decrecer en forma dinámica.

primer nodo

datos próximo

datos próximo

datos próximo

NULL

Figura 1. Lista enlazada. Cada nodo está compuesto por dos elementos: datos y un puntero a otro nodo. Por lo general, la lista que gestiona los nodos posee un puntero a próximo nodo en NULL, lo que indica que estamos en presencia del último nodo de la lista. Existen implementaciones de listas que no solo poseen un puntero al próximo nodo, sino al anterior, variedad conocida como “lista doblemente enlazada”.

primer nodo NULL

datos próximo anterior

datos próximo anterior

datos próximo anterior

primer nodo NULL

Figura 2. Lista doblemente enlazada.

Implementación de lista enlazada Implementaremos una lista enlazada por medio de dos clases: la primera representará el nodo (datos + puntero a próximo a nodo), y la segunda representará la lista que gestionará un conjunto de nodos.

www.redusers.com

3

C++

La lista no tendrá un array de nodos, sino un puntero al primer nodo de la lista. Por esta razón, en el diagrama de clases observamos que la relación existente entre la entidad Lista y la entidad Nodo es 1 a 1. Luego un nodo poseerá un puntero al próximo nodo. Lista

Figura 3. El sencillo diagrama de clases de una lista enlazada.

1

1

Nodo 1 1

La clase Nodo Comencemos a ver cómo estará conformada nuestra clase Nodo: class Nodo { int m_dato; Nodo* m_pProx; // … };

Las dos propiedades que tendrá nuestra clase serán:

• El dato: en este caso, solo un número entero. • El puntero al próximo nodo: una propiedad del tipo Nodo*. Como estas propiedades serán privadas, deberemos colocar los métodos correspondientes para poder acceder a ellas. Veamos: class Nodo

DENOMINACIÓN DE TIPO DE LISTAS En algunas publicaciones, es posible encontrar que la lista doblemente enlazada se denomina “lista enlazada”, mientras que la lista con solo un puntero al próximo nodo, “lista simplemente enlazada”. En otros casos, se denomina genéricamente “listas enlazadas”, sin hacer referencia específica a ninguna de las dos implementaciones. Estas son simples convenciones.

www.redusers.com

4

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

{ // … public: // Seteo los valores del nodo void FijarValor(int dato) ñ m_dato = dato; } // Seteo el próximo nodo void FijarProximo(Nodo * pProx) { m_pProx = pProx; } // Leo la propiedad m_dato int LeerDato() const { return m_dato; } // Tomo la propiedad al próximo nodo Nodo * LeerProximo() const { return m_pProx; } };

Finalmente, se encuentran los constructores y el destructor de la clase: class Nodo { // … public: // Constructor estándar Nodo() : m_pProx(NULL) {} // Constructor de copia Nodo(const Nodo& copiaDe) : m_pProx(NILL) { m_dato = copiaDe.m_dato; } // Constructor con parámetros iniciales Nodos(int dato) : m_dato(dato), m_pProx(NULL) {} // Destructor ~Nodo() { if (m_pProx) delete this->m_pProx;

www.redusers.com

5

C++

} // … };

Como podemos notar, ofrecemos tres constructores distintos: 1) El constructor por defecto, que fija el puntero próximo a NULL. 2) El constructor de copia, que fija el puntero próximo a NULL, y copia el dato pasado como parámetro al nodo. 3) Un constructor con un parámetro entero, para crear un objeto nodo y asignarle un valor al dato en un solo paso (simplemente por comodidad). Respecto del destructor, sería interesante analizarlo. Posee dos líneas de código que dicen, resumidamente: “Si el nodo próximo es distinto de NULL, eliminarlo”. De este modo, si destruimos el primer nodo de la lista, se irán destruyendo todos en cascada hasta que no quede ninguno, ya que el destructor del primer nodo eliminará al segundo, disparando, a su vez, a su destructor, que eliminará al próximo nodo, que es el tercero, y así sucesivamente.

Primer nodo

Nodo 3 Nodo 2 Nodo

NULL

1

Figura 4. La destrucción del primer nodo acarrea la destrucción de todos los nodos próximos, hasta encontrar un NULL en el puntero a nodo próximo. En caso de que no queramos destruir todos los nodos en cascada, sino solo un nodo determinado, deberemos tener la precaución de fijar el puntero de próximo nodo a NULL en el nodo a destruir.

www.redusers.com

6

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

La clase Lista La clase Lista será la que gestione la lista enlazada propiamente dicha, por lo que hará el trabajo más duro, que consiste en la inserción y extracción de nodos. class Lista { // Puntero al primer nodo de la lista (NULL si la lista está vacía) Nodo * m_pPrimerNodo; // Cantidad de nodos en lista int m_iCantidad; // };

Las propiedades de la clase serán las siguientes:

• Puntero al primer nodo: la lista solo tendrá información de cuál es el primer nodo; para acceder al resto, siempre deberemos pasar por todos los anteriores. Inicialmente, el valor de este puntero es NULL, ya que la lista se encuentra vacía.

• Cantidad de nodos: aunque es posible contar la cantidad de nodos cada que vez que se requiera esa información, mejor será poseer una propiedad en la que llevemos cuenta de esta cantidad en todo momento. En un principio, la cantidad de nodos será cero.

• El constructor: cuando construyamos la lista, esta fijará el puntero a primer nodo en NULL y la cantidad de nodos en cero, como habíamos mencionado.

EL NODO COMO ESTRUCTURA En algunas implementaciones, el nodo no es una clase con métodos –como sí lo será en la nuestra– sino simplemente una estructura. Esto acarrea algunas líneas de código de más en la clase lista, ya que, por ejemplo, no existirá un constructor que fije los valores por defecto a las propiedades.

www.redusers.com

7

C++

Veamos su implementación en el siguiente código: Lista::Lista(void) { m_pPrimerNodo = NULL; m_iCantidad = 0; }

• El destructor: si alguien destruye una lista, deberemos tener la prudencia de eliminar todos los nodos relacionados con ella, para que no queden zonas de memoria reservadas pero sin usar (conocidas como memory leaks). Lista::~Lista(void) { if (m_pPrimerNodo) delete m_pPimerNodo; }

Para ellos, verificamos que la lista no se encuentra vacía y eliminamos el primer modo. Como habíamos visto en la clase Nodo, esta acción conlleva la eliminación de todos los nodos de la lista.

• El método Limpiar: es posible que, en un determinado momento, queramos vaciar codificado del siguiente modo: void Lista::Limpiar() { if (m_pPreimerNodo) delete m_pPrimerNodo; m_pPrimerNodo = NULL; m_iCantidad = 0; }

www.redusers.com

8

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Similar al destructor en cuanto al modo de destruir los nodos de la lista, fijamos las propiedades puntero al primer nodo en NULL, y la cantidad de nodos en cero, porque el objeto sigue vivo y seguirá siendo utilizado (en el destructor no molestaba, porque el objeto era destruido). Métodos de inserción y remoción de nodos: llegamos al corazón del problema. Todo lo visto hasta el momento fue el esqueleto de la lista. Para entender cómo funciona una lista enlazada, más allá del modo de implementación, es fundamental entender de qué manera debemos proceder en cada una de las operaciones básicas de la lista:

• • • •

Inserción de un nodo por delante. Inserción de un nodo por detrás. Extracción de un nodo por delante. Extracción de un nodo por detrás. Inserción de un nodo por delante: el método InsertarDelante

llevará a cabo esta operación, que consiste en crear un nuevo nodo y agregarlo delante de todos los demás. Veamos los pasos que son necesarios para realizar este procedimiento. 1. La lista en su estado, antes de realizar la inserción.

primer nodo

NULL

2. Creamos un nuevo nodo (comienza apuntando a NULL debido al constructor de la clase Nodo).

primer nodo primer nodo

NULL

NULL

3. Modificamos el puntero próximo del nodo recién creado para que apunte al primer nodo de la lista.

primer nodo primer nodo

www.redusers.com

NULL

9

C++

4. Modificamos el puntero al primer nodo de la lista de modo que apunte al nodo recién creado.

primer nodo primer nodo

NULL

Figura 5. La inserción por delante. Ahora, codifiquemos los pasos descritos en el diagrama anterior empleando el método InsertarDelante, según se muestra en el siguiente ejemplo: bool Lista::InsertarDelante(const int & dato) { Nodo * pNodo = new Nodo(dato); if (pNodo) {

pNodo->FijarProximo(m_pPrimerNodo); m_pPrimerNodo = pNodo; m_iCantidad++; return tue;

} else return false; }

Analicemos el código con más detalle: Nodo * pNodo = new Nodo(dato);

Debemos crear un nuevo nodo, y para eso utilizaremos el operador new. Como percibimos el dato como parámetro, aprovechamos que existe un constructor apropiado para crear el nodo y darle un valor en un solo paso.

www.redusers.com

10

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

if (pNodo)

Es importante verificar que el nodo haya sido creado correctamente. Las listas enlazadas pueden ser muy extensas y, eventualmente, el sistema puede quedarse sin la memoria suficiente como para crear un nuevo nodo. pNodo->FijarProximo(m_pPrimerNodo);

Aquí fijamos, por medio del método FijarProximo de la clase Nodo, cuál será el próximo al nodo recién creado. Como nuestro nodo será el primero de la lista, el que se ubique después será el que antes estaba primero. Por esta razón, utilizamos la propiedad de la clase lista m_pPrimerNodo para fijar el próximo nodo al nodo nuevo: m_pPrimerNodo = pNodo;

Ahora estamos diciendo que el nuevo primer nodo de la lista es el recién creado; de este modo, dejamos la lista debidamente enlazada. m_iCantidad++;

A continuación, aumentamos el contador de nodos, ya que existe uno nuevo enlazado en la lista. Tengamos siempre en cuenta un caso especial: cuando la lista esté vacía. En dicha instancia, nada cambiará, pero el método FijarProximo sería invocado con un parámetro NULL, porque el puntero al primer nodo posee este valor; por consiguiente, se volverá a fijar el puntero a próximo nodo al mismo valor que le había dejado el constructor: NULL. Es muy importante tener en claro que, si bien estamos haciendo el new sobre una variable local que será destruida al finalizar la ejecución del método, la dirección de memoria que ella conservaba será inserta en la propiedad de un nodo y, por lo tanto, esta dirección no se extravía.

www.redusers.com

11

C++

Inserción de un nodo por detrás: veamos cuáles son los pasos para insertar un nodo detrás de todos los demás. 1. La lista en su estado, antes de realizar la inserción.

primer nodo

NULL

2. Creamos un nuevo nodo (comienza apuntando a NULL debido al constructor de la clase Nodo).

primer nodo primer nodo

NULL

NULL

3. Encontramos el último nodo.

primer nodo

NULL

pUltimoNodo primer nodo

NULL

4. Finalmente, cambiamos el valor del puntero a próximo nodo del último para que apunte al nodo recientemente creado.

primer nodo pUltimoNodo

NULL

primer nodo

Figura 6. La inserción por detrás.

EL VALOR DE RETORNO DE LAS OPERACIONES Los métodos de las operaciones retornan un valor booleano, que indica si la operación se ha llevado a cabo con éxito o no. En el caso de la inserción, el método podrá fallar sólo si no existe memoria para crear el nuevo nodo. En cambio, en el caso de la extracción de nodos, el método podrá fallar cuando no existan más nodos que extraer, es decir, cuando la lista esté vacía.

www.redusers.com

12

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

La dificultad en esta operación es hallar el último nodo. Hallar el primero es una tarea muy sencilla, pues existe una propiedad (m_pPrimerNodo) que mantiene dicho valor. Pero si se quiere encontrar el último nodo en una lista simplemente enlazada, se deben recorrer todos los nodos. Para realizar esa labor, crearemos un método privado llamado LeerUltimo, que nos retorna un puntero al último nodo o NULL, si es que la lista está vacía. Veamos: Nodo = Lista::LeerUltimo(void) { Nodo * pNodo = m_pPrimerNodo; Nodo * pNodoAnt = pNodo; while(pNodo) {

pNodoAnt = pNodo; pNodo = pNodo->LeerProximo();

} return pNodoAnt; }

La idea subyacente del método LeerUltimo es recorrer la lista por medio de una sentencia while hasta encontrar el último nodo. 1. Comenzamos fijando los puntero pNodoAnt y pNodo apuntando al primer nodo.

pNodo pNodoAnt

primer nodo

NULL

2. Dentro de la sentencia while, los punteros avanzarán sobre la lista

pNodoAnt

primer nodo

www.redusers.com

pNodo

NULL

13

C++

3. Cuando pNodo quede apuntando a NULL, pNodoAnt atará apuntando al último nodo.

pNodoAnt

primer nodo

pNodo

NULL

Figura 7. Pasos para buscar el último nodo. Veamos cómo codificamos InsertarDetras haciendo uso de este método: bool Lista::InsertarDetras(const int & dato) { Nodo * pNodo = new Nodo(dato); if (pNodo) { Nodo * pUltimoNodo = LeerUltimo(); if (pUltimoNodo) pUltimoNodo->FijarProximo(pNodo); else // Si no existe ningún “ultimoNodo” significa que la lista estaba vacía. m_pPrimerNodo = pNodo; m_iCantidad++; return true; } else return false; } Nodo * pNodo = new Nodo(dato);

En primera instancia, debemos crear el nuevo nodo a insertar, al igual que en el método InsertarDelante.

www.redusers.com

14

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Nodo = pUltimoNodo = LeerUltimo();

Luego, en una variable local, obtenemos el último nodo de la lista. if (pUltimoNodo)

Lo que hacemos aquí es dividir el flujo de ejecución en función de si la lista se encuentra vacía o no. pUltimoNodo->FijarProximo(pNodo);

Si la lista no se encuentra vacía, entonces cambiamos el puntero a próximo del último nodo para que apunte al nuevo nodo creado. m_pPrimerNodo = pNodo;

Si la lista está vacía, entonces el nuevo nodo será el último y también el primero. Por lo tanto, debemos modificar el puntero m_pPrimerNodo. m_iCantidad++;

Finalmente, aumentamos el contador de nodo de la lista.

• Extracción de un nodo por delante: la extracción de un nodo por delante de la lista no reviste mayor dificultad.

SIMPLEMENTE VS. DOBLEMENTE ENLAZADA Como se puede observar en la implementación del método de inserción por detrás, se debe recorrer la lista entera para hallar el último nodo. Esto no es un detalle; la lista enlazada podría ser muy extensa. Como veremos enseguida, la lista doblemente enlazada no presenta este problema.

www.redusers.com

15

C++

Veamos el algoritmo en la siguiente figura: 1. La lista en su estado antes de realizar la remoción.

primer nodo

NULL

2. Creo un puntero pNodoAExtraer que apunte al primer nodo que es el nodo a extraer.

pNodoAExtraer primer nodo

NULL

3. Modificamos el puntero m_pPrimerNodo para que apunte al nodo próximo, que antes era el primero.

pNodoAExtraer

NULL primer nodo 4. Modificamos el puntero a próximo del nodo a extraer para que apunte a NULL.

pNodoAExtraer NULL NULL primer nodo 5. Eliminamos el nodo a extraer.

pNodoAExtraer NULL NULL primer nodo

Figura 8. Extracción por delante. Ahora, observemos el código del método ExtraerDelante: bool Lista::ExtraerDelante(int & dato) {

www.redusers.com

16

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Nodo * pNodoExtraer; if (m_pPrimerNodo) { // Existe al menos un nodo en la lista pNodoExtraer = m_pPrimerNodo; m_pPrimerNodo = m_pPrimerNodo->LeerProximo(); // Fijo el puntero a próximo del nodo a eliminar a NULL pNodoAExtraer->FijaProximo(NULL); dato = pNodoAExtraer->LeerDato(); // Elimino el nodo delete pNodoAExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

Analicemos el código del listado anterior: if (m_pPrimerNodo)

En primer lugar, verificamos que la lista no se encuentre vacía. pNodoAExtraer = m_pPrimerNodo;

Obtenemos el nodo a extraer, que, en este caso, será el primero. pNodoAExtraer->FijarProximo(NULL);

www.redusers.com

17

C++

Modificamos el puntero al próximo nodo del nodo a extraer. Esto es para evitar que el destructor del nodo comience a eliminar a todos los demás que se encuentren enlazados a él. dato = pNodoAExtraer->LeerDato();

Luego obtenemos el dato del nodo que debe retornar el método. delete pNodoAExtraer;

Totalmente aislado, eliminamos el nodo a extraer. m_iCantidad-;

Por último, decrementamos el contador que mantiene la cantidad de nodos en la lista.

• Extracción de un nodo por detrás: la dificultad en la extracción por detrás es que encontramos no solo el último nodo sino el anterior a él. Veamos el diagrama del algoritmo. 1. La lista en su estado antes de realizar la remoción.

primer nodo

NULL

2. Creamos un puntero al último (nodo a extraer) y otro que apunte al anteúltimo nodo.

pNodoAnteriorAExtraer

pNodoAExtraer

primer nodo

NULL

3. Modificamos el puntero a próximo del anteúltimo nodo para que apunte a NULL.

pNodoAnteriorAExtraer

pNodoAExtraer NULL

primer nodo

NULL

www.redusers.com

18

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

4. Aislado el nodo a extraer, lo eliminamos.

pNodoAnteriorAExtraer

pNodoAExtraer NULL

primer nodo

NULL

Figura 9. Extracción por detrás. El código será el más largo de los cuatro: bool Lista::ExtraerDetras(int & dato) { Nodo * pNodo = m_pPrimerNodo; Nodo * pNodoAextraer = pNodo; Nodo * pNodoAnteriorAExtraer = NULL; while (pNodo) {

pNodoAnteriorAExtraer = pNodoAExtraer; pNodoAExtraer = pNodo; pNodo = pNodo-ZLeerProximo();

} if (pNodoAEXtraer) { // Existe un nodo a eliminar -> La lista no está vacía if (pNodoAnteriorAExtraer == pNodoAExtraer) // Actualizo el puntero al primer nodo m_PrimerNodo = NULL; else // La lista posee más de un nodo pNodoAnteriorAExtraer->FijarProximo(NULL); // La lista tiene sólo un nodo -> Elimino El único nodo existente pNodoAExtraer->FijarProximo(NULL); dato = pNodoAExtraer;->LeerDato();

www.redusers.com

19

C++

// Elimino el nodo a extraer delete pNodoAExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

Analicemos el código anterior: while (pNodo) {

pNodoAnteriorAExtraer = pNodoAExtraer; pNodoAExtraer = pNodo; pNodo = pNodo->LeerProximo();

}

Con esta sentencia while, deseamos encontrar el último nodo de la lista y el anterior a él. Procedemos de un modo muy similar al método LeerUltimo. if (pNodoAExtraer)

Así, verificamos que la lista no se encuentra vacía. if (pNodoAnteriorAExtraer == pNodoAExtraer)

Luego verificamos si existe solo un nodo a extraer. m_pPrimerNodo = NULL;

www.redusers.com

20

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Si se comprueba la sentencia condicional anterior, debemos modificar el puntero al primer nodo para que apunte a NULL, ya que la lista quedará vacía. pNodoAnteriorAExtraer->FijarProximo(NULL);

Si existe más de un nodo en la lista, estaremos ante el caso más común. Fijaremos el puntero a próximo del nodo anteúltimo a NULL, para dejar aislado el nodo a extraer. Dato = pNodoAExtraer->LeerDaro();

Tomamos el dato que deberemos retornar. delete pNodoAExtraer;

Eliminamos el nodo a extraer. m_iCantidad-;

Como último paso, decrementamos el contador de la cantidad de nodos que posee la lista. Ahora veamos cómo trabajan las listas doblemente enlazadas.

Listas doblemente enlazadas La lista doblemente enlazada, hemos dicho, posee dos punteros por nodo: uno que mira hacia delante y otro que mira hacia atrás. De este modo, las operaciones de inserción y extracción son totalmente simétricas (algo que no ocurría con las listas simplemente enlazadas). Aunque tendremos más trabajo, al actualizar más nodos se facilitará la navegación por lista, ya que podremos hacerlo en ambos sentidos.

www.redusers.com

21

C++

Lista

1

2

Nodo 1 2

Figura 10. Diagrama de clases de una lista doblemente enlazada. Veamos de qué forma se modifica la clase Nodo ahora que le agregamos un puntero más a un nodo anterior: class Nodo { int m_dato; Nodo * m_Prox; Nodo * m_pPrev; public: // constructor estándar Nodo() : m_pProx(NULL), m_pPrev(NULL) {} // Constructor de copia Nodo(const Nodo& copiaDe) : m_pProx(NULL), m_pPrev(NULL) { m_dato = copiaDe.m_dato; } // Constructor con parámetros iniciales Nodo(int dato) _ m_dato(dato), m_pProx(NULL), m_pPrev(NULL) {} // Destructor ~Nodo() { if (m_pProx) delete this->m_pProx; }

ESPACIO OCUPADO EN MEMORIA En cuanto a la lista doblemente enlazada, otra diferencia que encontramos (y que se puede ver en los ejemplos) es que ocupará un poco más de memoria de nuestra lista. Este es un factor muy importante a tener en cuenta cuando deseemos seleccionar el tipo de estructura de datos correcto para resolver nuestros problemas.

www.redusers.com

22

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

//Seteo los valores del nodo void FijarValor(intdato) { m_dato ) dato; } // Seteo el nodo próximo void FijarProximo(Nodo * pProx) { m_pProx = pProx; } // Seteo el nodo anterior void FijarAnterior(Nodo * pPrev) { m_pPrev = pPrev; } // Leo la propiedad m_dato int LeerDato() const { return m_dato; } // Tomo la propiedad próximo nodo Nodo * LeerProximo() const { return m_pProx; } // Tomo la propiedad nodo anterior Nodo * LeerAnterior() cons { return m_pPrev; } };

Es bastante similar; se destaca la presencia del nuevo puntero y los métodos correspondientes a su lectura y modificación: Nodo * m_pPrev;

La clase Lista ahora tendrá no solo un puntero al primer nodo de la lista, sino también un puntero al último de la lista: class Lista { // Puntero al primer nodo de la lista (NULL si la lista está vacía) Nodo * m_pPrimerNodo; // Puntero al último nodo de la lista (NULL si la lista está vacía) Nodo * m_pUltimoNodo; // Cantidad de nodos en lista int m_iCantidad; public:

www.redusers.com

23

C++

Lista(); ~Lista();N // Elimino todos los nodos de la lista void Limpiar(); // Inserto un nodo por delante de la lista bool InsertarDelante(const int & dato); // Inserto un nodo por detrás de la lista bool InsertarDetras (const int & dato); // Extrae un nodo por delante de la lista bool ExtraerDelante(int & dato); // Extrae un nodo por detrás de la lista bool ExtraerDetras(int & dato); // Devuelve la cantidad de nodos que posee la lista int LeerCantidad() { return m_iCantidad; }; };

Como se puede apreciar, solamente agregamos el puntero al último nodo, llamado m_pUltimoNodo. A continuación, veamos en qué cambia cada una de las cuatro operaciones básicas:

• Inserción de un nodo por delante: en las operaciones de inserciones y remoción de una lista doblemente enlazada, deberemos actualizar más punteros, como observamos en el siguiente diagrama. 1. La lista, antes de realizarse alguna modificación.

primer nodo NULL

NULL último nodo

www.redusers.com

24

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

2. Creamos el nuevo nodo que insertaremos en la lista.

NULL NULL primer nodo NULL

NULL último nodo

3. Modificamos el puntero a próximo del nuevo nodo, para que apunte al que por el momento es el primer nodo.

NULL primer nodo NULL

NULL último nodo

4. Modificamos el puntero a interior del que por el momento es el primer nodo, para que apunte al nuevo nodo.

NULL primer nodo NULL

NULL último nodo

5. Modificamos el puntero al primer nodo, para que apunte al nodo a insertar.

NULL primer nodo NULL

NULL último nodo

Figura 11. Inserción por delante. Ahora veamos el código del método InsertarDelante: bool Lista::InsertarDelante(const in & dato) { // 1. Creo nodo a insertar Nodo * pNodo = new Nodo(dato); if (pNodo) {

// 2. Apunto el nodo nuevo adonde apuntaba m_pPrimerNodo pNodo->FijarProximo(m_pPrimerNodo); // 3. El primer nodo debe cambiar su “nodo previo” al

www.redusers.com

25

C++

// nuevo insertado if (m_pPrimerNodo) m_iPrimerNodo->FijarAnterior(pNodo); // 4. El primer nodo pasa a apuntar hacia el nodo insertado m_pPrimerNodo = pNodo) // 5. Si la lista estaba vacía (m_pUltimoNodo == NULL), apunto if (!m_pUltimoNodo) m_pUltimoNodo = pNodo; // Incremento la cantidad de nodos m_iCantidad++; return true; } else return false; }

Analicemos el listado anterior: Nodo * pNodo = new Nodo(dato);

Primero, creamos el nuevo nodo. if (pNodo)

Luego verificamos que el nodo haya sido creado. pNodo->FijarProximo(m_pPrimerNodo);

A continuación, cambiamos el puntero a próximo del nodo nuevo. if (m_pPrimerNodo) m_pPrimerNodo->FijarAnterior(pNodo);

www.redusers.com

26

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Así, cambiamos el puntero a nodo anterior del nodo que, por el momento, se encuentra primero en la lista, para que apunte al nodo nuevo. Esta acción se realiza solo si la lista no se encuentra vacía. m_pPrimerNodo = pNodo;

El primer nodo de la lista es el que insertamos ahora. if (!m_pUltimoNodo) m_pUltimoNodo = pNodo;

Si la lista estaba vacía, entonces el nodo insertado es el primero y también el último. Por lo tanto, debemos modificar el puntero a último nodo para que apunte al nodo nuevo. m_iCantidad++;

Aumentamos el contador de cantidad de nodos en lista.

• Inserción de un nodo por detrás: la inserción por detrás será muy similar a la inserción por delate, ya que la lista ahora es simétrica y tenemos un puntero al último nodo. Veamos la Figura 12. 1. La lista, antes de realizarse alguna modificación.

primer nodo NULL

NULL último nodo

2. Creamos el nuevo nodo que insertaremos en la lista.

NULL NULL primer nodo NULL

www.redusers.com

NULL último nodo

27

C++

3. Modificamos el puntero a próximo del nuevo nodo, para que apunte al que por el momento es el último nodo de la lista.

NULL primer nodo NULL

NULL último nodo

4. Modificamos el puntero a próximo del actual último nodo de la lista, para que apunte al nodo nuevo.

NULL primer nodo NULL

último nodo

5. Modificamos el puntero último de la lista, para que apunte al nodo nuevo.

NULL primer nodo NULL

último nodo

Figura 12. Inserción por detrás.

bool Lista::InsertarDetras(const int & dato) { // 1. Creo nodo a insertar Nodo * pNodo new Nodo(dato); if (pNodo) {

// 2. Apunto el nodo nuevo adonde apuntaba m_pUltimoNodo pNodo->FijarAnterior(m_pUlimoNodo); // 3. El que antes era el último nodo, ahora debe apuntar al nodo insertado if (m_pUltimoNodo) m_pUltimoNodo->FijarProximo(pNodo); // 4. El primer nodo pasa a apuntar hacia el nodo insertado m_pUltimoNodo = pNodo; // 5. Si la lista estaba vacía (m_pUltimoNodo == NULL), apunto // el último nodo hacia el nodo insertado

www.redusers.com

28

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

if (!m_pPrimerNodo) m_pPrimerNodo = pNodo; // Incremento la cantidad de nodos m_iCantidad++; return true; } else return false; }

Analizando el listado, veremos que es muy similar al método InsertarDelante, cambiando el uso de los punteros. Veamos: Nodo * pNodo = new Nodo(dato);

Para comenzar, creamos el nuevo nodo. pNodo->FijarAnterior(m_pUltimoBodo);

Modificamos el puntero a nodo anterior del nodo nuevo a insertar, de modo que apunte al que, por el momento, es el último nodo. if (m_pUltimoNodo) m_pUltimoNodo->FijarProximo(pNodo);

Si existe un último nodo, es decir, si la lista no está vacía, entonces le modificamos el puntero a nodo próximo para que apunte al nuevo nodo. m_pUltimoNodo = pNodo;

Modificamos el puntero al último nodo para que apunte al nodo nuevo.

www.redusers.com

29

C++

if (!m_pPrimerNodo) m_pPrimerNodo = pNodo;

Si no existe un primer nodo (si la lista está vacía), el último nodo también será primero. Por ende, modificamos el puntero al primer nodo.

• Extracción por delante: la extracción por delante es relativamente sencilla, como veremos a continuación (Figura 13): 1. La lista, antes de realizarse alguna modificación.

primer nodo NULL

NULL último nodo

2. Creamos un puntero que apunte al primer nodo de la lista, que es el nodo a extraer.

pNodoAExtraer primer nodo NULL

NULL último nodo

3. Modificamos el puntero al primer nodo de la lista que apunte al próximo nodo a extraer.

pNodoAExtraer

primer nodo

NULL último nodo

NULL 4. Modificamos el puntero del nuevo primero nodo, para que apunte a NULL.

pNodoAExtraer

primer nodo

NULL último nodo

NULL NULL 5. Modificamos el puntero a próximo nodo del nodo a extraer, para que apunte NULL.

pNodoAExtraer

primer nodo NULL NULL último nodo

NULL NULL

Figura 13. Extracción por delante. www.redusers.com

30

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

bool Lista::ExtraerDelante(int & dato) { // Creo puntero NodoAExtraer Nodo * pNodoAExtraer; // ¿La lista está vacía? if (m_pPrimerNodo) { // 1. Apunto el NodoAExtraer al primer nodo pNodoAExtraer = m_pPrimerNodo; // 2. Modifico el primer Nodo para que apunte al próximo nodo m_pPrimerNodo = m_pPrimerNodo->LeerProximo(); // 3. Si existe dicho nodo, modifico su propiedad m_prev para que apunte a NULL if (m_pPrimerNodo) m_pPrimerNodo->FijarAnterior(NULL); else // Si la lista quedó vacía, apunto el último nodo a NULL m_pUltimoNodo = NULL; // 4. Fijo el puntero a próximo del nodo a eliminar a NULL pNodoAExtraer->FijarProximo(NULL); // Copio el dato y lo paso como parámetro dato = pNodoAExtraer->LeerDato(); // Elimino el nodo delete pNodoAExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

www.redusers.com

31

C++

Analicemos el código del listado anterior. Nodo * pNodoAExtraer;

En primer lugar, creamos una variable local puntero a un nodo. if (m_pPrimerNodo)

A continuación, verificamos que la lista no esté vacía. pNodoAExtraer = m_pPrimerNodo;

En esta línea de código, fijamos entonces el valor del puntero local para que apunte al primer nodo, que es el nodo a extraer. m_pPrimerNodo = m_pPrimerNodo->LeerProximo();

Luego modificamos el puntero a primer nodo para que apunte al nodo próximo al nodo a extraer, que será, a partir de ahora, el primer nodo de la lista. if (m_pPrimerNodo) m_pPrimerNodo->FijarAnterior(NULL);

Verificamos que el nuevo primer nodo realmente exista (cuando solo queda un nodo, el nodo próximo al nodo a extraer es NULL), para modificar su puntero a nodo anterior, que, como será el primer nodo de la lista, deberá ser NULL.

else m_pUltimoNodo = NULL;

www.redusers.com

32

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Si no existe el nuevo primer nodo, entonces la lista quedará vacía, y deberemos modificar el valor del puntero al último nodo. pNodoAExtreaer->FijarProximo(NULL); Modificamos el puntero a próximo nodo del nodo a extraer, ya que, como lo eliminaremos, queremos evitar que su destructor destruya otros nodos. dato = pNodoAExtraer->LeerDato();

Rescatamos el dato que debemos retornar por método. delete pNodoAExtraer;

Y así destruimos el nodo. m_iCantidad-;

Por último, decrementamos el contador de cantidad de nodos en lista.

• Extracción por detrás: la extracción por detrás también es muy similar a la extracción por delante debido a la simetría de la lista. 1. La lista, antes de realizarse alguna modificación.

primer nodo NULL

NULL último nodo

2. Creamos un puntero que apunte al último nodo de la lista, que es el nodo a extraer.

pNodoAExtraer primer nodo NULL

www.redusers.com

NULL último nodo

33

C++

3. Modificamos el puntero a último nodo de la lista, para que apunte al nodo anterior del nodo a extraer.

último nodo

pNodoAExtraer

primer nodo NULL

NULL

4. Modificamos el puntero a próximo del nuevo último nodo, para que apunte a NULL.

último nodo

pNodoAExtraer

primer nodo NULL

NULL

5. Modificamos el puntero nodo anterior, del nodo a extraerpara que apunte a NULL.

último nodo

pNodoAExtraer NULL

primer nodo NULL

NULL

NULL

Figura 14. Extracción por detrás. bool Lista::ExtraerDetras(int & dato) { // Creo puntero NodoExtraer Nodo * pNodoAExtraer; // ¿La lista está vacía? if (m_pUltimoNodo=) { // 1. Apunto el NodoAExtraer al primer nodo pNodoAExtraer = m_ pUltimoNodo; // 2. Modifico el pimer Nodo para que apunte al próximo nodo m_pUltimoNodo = m_pUltimoNodo->LeerAnterior(); // 3. Si existe dicho nodo, modifico su propiedad m_prev para // que apunte a NULL if (m_pUltimoNodo)

www.redusers.com

34

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

m_pUltimoNodo->FijarProximo(NULL); else // La lista quedó vacía, cambio el apuntador al PrimerNodo m_pPrimerNodo = NULL; // Copio el dato y lo paso como parámetro dato = pNodoAExtraer->LeerDato(); // Elimino el nodo delete AExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

Nodo * pNodoAExtraer;

En la primera línea, creamos una variable local puntero a un nodo. if (m_pUltimoNodo)

Verificamos que la lista no está vacía. pNodoAExtraer = m_pUltimoNodo;

Fijamos el valor del puntero local para que apunte al último nodo, que es el nodo a extraer, y que será, a partir de ahora, el último nodo de la lista.

www.redusers.com

35

C++

if (m_pUltimoNodo) m_pUltimoNodo->FijarProximo(NULL);

Verificamos que el nuevo último nodo realmente exista (cuando solo queda un nodo, el nodo anterior al nodo a extraer es NULL), para modificar su puntero a nodo próximo, que, como será el último nodo de la lista, deberá ser NULL. else m_pPrimerNodo = NULL;

Si no existe el nuevo último nodo, entonces la lista quedará vacía, y deberemos modificar el valor del puntero al primer nodo. dato = pNodoAExtraer->LeerDato();

Rescatamos el dato que debemos retornar por el método. delete pNodoAExtraer;

Luego destruimos el nodo. m_iCantidad-;

Y decrementamos el contador de cantidad de nodos en lista.

Pila Crear una pila, tomando como base alguna de las listas que hemos creado, es realmente muy sencillo. Veamos: class Pila

www.redusers.com

36

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

{ Lista m_lista; public: bool Insertar(int & dato) { return m_lista.InsertarDelante(dato); } bool Extraer(int & dato) { return m_lista.ExtraerDelante(dato); } bool EstaVacia(void) { return (m_lista.LeerCantidad() == 0); } };

El método Insertar realizará una inserción por delante de la lista. Por lo tanto, bastará con que invoquemos el método InsertarDelante de la lista que posee la pila como propiedad. El método Extraer hará una extracción por delante, debido a que en una pila se inserta y extrae por el mismo extremo. Entonces, realizaremos la invocación del método ExtraerDelante de la lista que posee la pila como propiedad. El método EstaVacia simplemente retorna el resultado de la expresión que verifica si la cantidad de elementos de la lista es cero.

Cola Crear una cola también es muy sencillo haciendo uso de nuestra lista. class Cola { Lista m_lista; public: Cola(void); ~Cola(void);

PILA Y COLA Recordemos que en el Capítulo 6 habíamos hecho una introducción acerca de cómo funcionaban estas estructuras de datos, y también habíamos realizado una implementación sobre una clase que encapsulaba un array. Si tenemos dudas en este punto, podemos consultarlo antes de continuar.

www.redusers.com

37

C++

bool Insertar(int & dato) { return m_lista.InsertarDelante(dato); } bool Extraer(int & dato) { return m_lista.ExtraerDelante(dato); } bool EstaVacia(void) { return (m_lista.LeerCantidad() == 0); } };

Esto es muy similar a la pila, solamente que, en este caso, Extraer invoca el método ExtraerDetras, ya que en una cola se inserta por un extremo y se extrae por el otro. De las implementaciones de listas enlazadas y doblemente enlazadas que vimos, basta decir que poseen una limitación enorme: trabajan con un tipo de dato predeterminado (que en nuestro ejemplo es un número entero). Veremos ahora que C++ dispone de un recurso muy poderoso con el cual es posible evitar esa limitación de raíz.

Plantillas Hasta ahora, hemos implementado una lista doblemente enlazada de números enteros, pero ¿qué ocurriría si necesitáramos una lista enlazada de números flotantes? Desgraciadamente, deberíamos recodificar todo de nuevo. Para evitar eso, C++ ofrece un mecanismo llamado plantillas, que permite crear estructuras de datos independientes del tipo. Cuando introdujimos el tema de funciones, vimos que por medio de ellas era posible realizar una operación basándonos en datos parametrizados que podían variar invocación tras invocación. Las plantillas, de cierto modo, tienen algo en común a esto: pueden recibir uno o varios parámetros en el momento de su creación. Pero, en lugar de referirnos a una variable, nos estamos refiriendo a un tipo de variable. De esta manera, nuestras listas no trabajarán con enteros o con flotantes, ni con ningún tipo de dato preestablecido, sino que lo harán con cualquiera que le especifiquemos al realizar la instancia del objeto en cuestión. Veamos un ejemplo:

www.redusers.com

38

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

class array { // Cantidad de elementos actual del array int m_iCantElementos; // Puntero a array de números enteros int * m_piArray; public: Array(int iCantidadElementos); ~Array(void); // Fija el tamaño del array bool FijaTam(int iCantidadElementos); // Lee el tamaño del array int LeerTam() const; // Fija el valor en un elemento determinado del array bool FijarValor(inti Elemento, inti Valor); // Retorna el valor en un elemento determinado del array bool LeerValor(intiElemento, int & iValor) const; // Limpia el array con el valor pasado como parámetro void Limpiar(inti Valor); };

La clase Array que construimos algunos capítulos atrás solo podía manejar enteros. Veamos ahora cómo convertir dicha clase en una plantilla y, de ese modo, poder manejar diferentes tipos de datos. En primera instancia, cambiaremos la declaración de la clase agregando la palabra reservada template antes del clásico class. Revisemos cómo escribíamos antes: class Array

www.redusers.com

39

C++

{ // declaración de propiedades y métodos };

Utilizando template sería: template class Array { };

¿Qué fue lo que hicimos aquí? Convertimos nuestra clase en una plantilla. En este caso, nuestra plantilla podrá recibir un tipo de dato, representado por la letra T, en el momento de la instanciación (podría haber sido cualquier letra o palabra que siguiera la regla de cualquier otro identificador). Veamos cómo sería la instanciación de un objeto tipo Array. Antes escribíamos: int main() { // Antes, creábamos un objeto del tipo Array del siguiente modo: Array unObjArray; // … }

CANTIDAD DE TIPOS DE UNA PLANTILLA Una plantilla podría recibir más de un tipo de dato; simplemente debemos realizar una separación por medio de comas dentro de las llaves. Por ejemplo: template >class T1, class T2> class …

www.redusers.com

40

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Ahora podemos escribir: int main() { // Ahora, como Array es una plantilla lo haremos así: Array unObjArray; // … }

La novedad es haber colocado un tipo de dato entre llaves inmediatamente después del nombre de la plantilla. No existe otro modo de realizar la instanciación, ya que es necesario pasarle el tipo de dato con el cual trabajará la plantilla. En nuestro ejemplo, decidimos hacerlo con el tipo de dato entero, pero otras instanciaciones válidas también habrían sido las siguientes: Array arr1; Array arr2; Array arr3; Array arr4;

Del listado anterior, observamos rápidamente que todos estos nuevos objetos tipo Array manejan diferentes tipos de datos y, sin embargo, no tuvimos la necesidad de modificar nuestra plantilla. Sin duda, las plantillas son un recurso poderoso del lenguaje. ¿Qué es lo que hace realmente C++ en estos casos? Cuando codificamos una plantilla, si esta no es utilizada, no formará parte nuestro programa. Dicho de otro modo: la plantilla solo es compilada cuando el compilador advierte que es utilizada; en ese caso, construye una clase con el tipo de dato correspondiente, y es compilada. Por esta razón, es posible que no se adviertan errores en la definición de los métodos de una plantilla hasta que se invoque el método en cuestión por medio de una instancia de dicha plantilla. El compilador creará las clases que correspondan por cada tipo de dato con el cual se utilice la plantilla.

www.redusers.com

41

C++

Veamos ahora cómo sería la declaración completa de nuestra plantilla Array en el código de ejemplo que se muestra en la página siguiente: template class Array { // Cantidad de elementos actual del array int m_iCantElementos; // Puntero a array T * m_pArray; public: Array(int iCantidadElementos); ~Array(void); // Fija el tamaño del array bool FijaTam(int iCantidadElementos); // Lee el tamaño del array int LeerTam() const; // Fija el valor en un elemento determinado del array bool FijarValor(inti Elemento, T valor); // Retorna el valor en un elemento determinado del array bool LeerValor(inti Elemento, T & valor) const; // Limpia el array con el valor pasado como parámetro void Limpiar(T valor); };

Observemos que hemos reemplazado todos los tipos de datos int (que antes hacían referencia al tipo de dato utilizado por la clase) por el parámetro T, que representa el tipo de dato que es pasado al momento de instanciar el objeto. T * m_pArray;

www.redusers.com

42

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Según esta línea de código, la propiedad en la que se almacenaba el puntero a un array de números enteros es ahora una propiedad en la que se almacena un puntero a un array de tipo de datos T. bool FijarValor(int iElemento, T valor);

El método que utilizábamos para fijar un valor a un elemento del array, ahora, en su segundo parámetro, no recibe un entero sino un tipo de dato T (que podrá ser finalmente un entero, un flotante, un carácter, etcétera). bool LeerValor(int iElemento, T & valor) const; void Limpiar(T valor);

Lo mismo ocurre con el método LeerValor y Limpiar, y todo método que reciba o entregue datos relacionados con el tipo del array. Entonces, ¿qué cambia en la definición de estos métodos? En primer lugar, las definiciones de los métodos de las plantillas no se colocan en los archivos cpp, sino en el mismo archivo cabecera en el que se realiza su declaración. Es decir que la definición de los métodos que teníamos en el archivo array.cpp se moverá al archivo array.h justo después de la declaración de la plantilla.

clase convencional

plantilla cabecera(.h)

cabecera(.h) (declaración de la clase)

cuerpo (.cpp)

cuerpo (.cpp) (definición de los métodos)

(declaración de la plantilla) + (definición de los métodos)

Figura 15. En las plantillas, la definición de todos los métodos debe colocarse en el archivo cabecera. Además, existe un cambio en el modo de definir el método. Anteriormente, al método Limpiar lo definíamos de esta forma:

www.redusers.com

43

C++

int Array::LeerTam() const { return m_iCantElementos; }

Ahora, deberemos anteponer template ante cada método y, además, deberemos agregar un después del nombre de la clase. Veamos: template int Array::LeerTam() const { return m_iCantElementos; }

Claro que siempre tendremos la posibilidad de colocar la definición de los métodos dentro del cuerpo de la plantilla. En dicho caso, no existe salvedad alguna; si procediéramos de esa manera, como con el método Limpiar, quedaría codificado de acuerdo a como se muestra a continuación: template class Array { // … public: // … int LeerTam() const { return m_iCantElementos; } // … };

www.redusers.com

44

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Ahora, veamos la declaración completa de todos los métodos de la clase. El constructor: template Array::Array(int iCantidadElementos) { // Asigno el valor m_iCantElementos = iCantidadElementos; // Creo un array de forma dinámica en función de la cantidad de elementos fijada m_pArray = new T[iCantidadElementos]; }

El destructor: template Array::~Array(void) { // Libero la memoria solicitada if (m_pArray) delete [] m_pArray; }

El método FijaTam: template bool Array::FijaTam(int iCantidadElementos) { m_iCantElementos = iCantidadElementos;: // Libero la memoria solicitada

www.redusers.com

45

C++

if (m_pArray) delete [] m_pArray; // Vuelvo a solicitar memoria con el nuevo valor m_pArray = new T[m_iCantElementos]; if [m_pArray) return true; else return false; }

El método FijarValor: template bool Array::FijarValor(int iElemento, T valor) { // Verifico que el elemento propuesto sea válido if (iElemento >= 0 && iElemento < m_iCantElementos) {

m_pArray[iElemento]; return true;

} else return false; }

El método LeerValor: template bool Array::LeerValor(inti Elemento, T & valor) const { if (iElemento >= 0 && iElemento < m_iCanElementos) {

valor = m_pArray[iElemento]; return true;

}

www.redusers.com

46

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

else return false; }

El método Limpiar: template > void Array::Limpiar(T valor) { for (int i=0; im_pProx; } // Seteo los valores del nodo void FijarValor(T dato) { m_dato = dato; } // Seteo el nodo próximo void FijarProximo(Nodo * pProx) { m_pProx = pProx; } // Seteo el nodo anterior void FijarAnterior(Nodo * pPrev) { m_pPrev = pPrev; } // Leo la propiedad m_dato

www.redusers.com

48

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

T LeerDato() const { return m_dato; } // Tomo la propiedad próximo nodo Nodo * LeerProximo() const { return m_pProx; } // Tomo la propiedad nodo anterior Nodo * LeerAnterior() const { return m_pPrev; } };

En pocas palabras, cambiamos todos los int relacionados con el dato encapsulado dentro de la clase Nodo por el T del tipo de dato de la plantilla. template class Lista { // Puntero al primer nodo de la lista (NULL si la lista está vacía) Nodo * m_pPrimerNodo; // Puntero al último nodo de la lista (NULL si la lista está vacía) Nodo * m_pUltimoNodo; // Cantidad de nodos en la lista int m_iCantidad; public: Lista(); Virtual ~Lista(); // Inserto un nodo por delante de la lista bool InsertarDelante(const T & dato); // Inserto un nodo por detrás de la lista bool InsertarDetras(const T & dato); // Extrae un nodo por delante de la lista bool ExtraerDelante(T & dato); // Extrae un nodo por detrás de la lista bool ExtraerDetras(T & dato); // Devuelve la cantidad de nodos que posee la lista int LeerCantidad() { return m_iCantidad; }; };

www.redusers.com

49

C++

Procedemos de manera análoga con la clase Lista. Notemos que esta clase hace uso de propiedades tipo Nodo, que ahora son del tipo Nodo debido a que le hacemos el pase del tipo de dato con el cual se instancia la lista. La definición de los métodos también deberá ser modificada, ya que donde exista: Nodo * pNodo = new Nodo(dato);

tendremos que colocar: Nodo * pNodo = new Nodo(dato);

Además, deberemos pasar todo este código a la cabecera (al archivo Lista.h), porque, como habíamos mencionado, las plantillas se codifican enteramente allí. Por lo tanto, el código de los métodos quedará del siguiente modo. El constructor: template Lista::Lista(void) { m_pPrimerNodo = m_pUltimoNodo = NULL; m_iCantidad= 0; }

El destructor: template Lista::~Lista(void) { if (m_pPrimerNodo) delete m_pPrimerNodo; }

www.redusers.com

50

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

El método Limpiar: template void Lista::limpiar() { if (m_pPrimerNodo) delete m_pPrimerNodo; m_pPrimerNodo = m_pUltimoNodo = NULL; m_iCantidad = 0; }

El método InsertarDelante: template bool Lists::InsertarDelante(const T & dato) { // 1. Creo nodo a insertar Nodo * pNodo = new Nodo(dato); if (pNodo) { // 2. Apunto el nodo nuevo a donde apuntaba m_pPrimerNodo pNodo->FijarProximo(m_pPrimerNodo); // 3. El primer nodo debe cambiar su “nodo previo” al nuevo insertado if (m_pPrimerNodo) m_pPrimerNodo->FijarAnterior(pNodo); // 4. El primer nodo pasa a apuntar hacia el nodo insertado m_pPrimerNodo = pNodo; // 5. Si la lista estaba vacía (m_pUltimoNodo == NULL), apunto el último nodo hacia el nodo insertado if (!m_pUltimoNodo)

www.redusers.com

51

C++

m_pUltimoNodo = PnODO; // Incremento la cantidad de nodos m_iCantidad++; return true; } else return false; }

El método InsertarDetras: template bool Lista::InsertarDetras(const T & dato) { // 1. Creo nodo a insertar Nodo * pNodo = new Nodo(dato); if (pNodo) { // 2. Apunto el nodo nuevo adonde apuntaba m_pUltimoNodo pNodo->FijarAnterior(m_pUltimoNodo); // 3. El que antes era el último nodo, ahora debe apuntar al nodo insertado if (m_pUltimo nod) m_pUltimoNodo->FijarProximo(pNodo); // 4. El primer nodo pasa a apuntar hacia el nodo insertado m_pUltimoNodo = pNodo; // 5. Si la lista estaba vacía (m_pUltimoNodo == NULL), apunto // el último nodo hacia el nodo insertado if (!m_pPrimerNodo) m_pPrimerNodo = pNodo;

www.redusers.com

52

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

// Incremento la cantidad de nodos m_iCantidad++; return true; } else return false; }

El método ExtraerDelante: template bool Lista::ExtraerDelante(T & dato) { // Creo puntero NodoAExtraer Nodo * pNodoAExtraer // ¿La lista está vacía? if (m_pPrimerNodo) { // 1. Apunto el NodoAExtraer al primer nodo pNodoAExtraer = m_pPrimerNodo; // 2. Modifico el pimer nodo para que apunte al próximo nodo m_pPrimerNodo = m_pPrimerNodo->LeerProximo(); // Si existe dicho nodo, modifico su propiedad m_prev para // que apunte a NULL if (m_pPrimerNodo) m_pPrimerNodo->FijarAnterior(NULL); else // Si la lista quedó vacía, apunto el último nodo a NULL m_pUltimoNodo = NULL; // 4. Fijo el puntero a próximo del nodo a eliminar a NULL

www.redusers.com

53

C++

pNodoAExtraer->FijarProximo(NULL); // Copio el dato y lo paso como parámetro dato = pNodoAExtraer->LeerDato(); // Elimino el nodo delete pNodoAExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

El método ExtraerDetras: template bool Lista::ExtraerDetras(T & dato) { // Creo puntero NodoAExtraer Nodo * pNodoAExtraer; // ¿La lista está vacía? if (m_pUltimoNodo) { // 1. Apunto el NodoAExtraer al primer nodo pNodoAExtraer = m_pUltimoNodo; // 2. Modifico el pimer nodo para que apunte al próximo nodo m_pUltimoNodo = m_pUltimoNodo->LeerAnterior(); // 3. Si existe dicho nodo, modifico su propiedad m_prew para // que apunte a NULL

www.redusers.com

54

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

if m_pUltimoNodo) m_pUltimoNodo->FijarProximo(NULL); else // La lista quedó vacía, cambio el apuntador Al primernodo m_pPrimerNodo = NULL; // Copio el dato y lo paso como parámetro dato = pNodoAExtraer->LeerDato(); // Elimino el nodo delete pNodoAExtraer; // Decremento la cantidad de nodos m_iCantidad-; return true; } else return false; }

No realizaremos un análisis método por método porque, lógicamente, estos son iguales a los utilizados en la lista que manejaba números enteros; solamente cambiaron los tipos int relacionados con el dato tipo T. Por lo tanto, ¡ya tenemos nuestra lista doblemente enlazada, que puede manejar cualquier tipo de dato!

Pila ¿Cómo hacer uso de nuestra flamante plantilla Lista para crear una Pila? Veamos: template class Pila

www.redusers.com

55

C++

{ Lista m_lista; public: bool Insertar(T & dato) { return m_lista.InsertarDelante(dato); } bool Extraer(T & dato) { return m_lista.ExtraerDelante(dato); } bool EstaVacia(void) { return (m_lista.LeerCantidad() == 0); } };

Cola La implementación de la cola es tan sencilla como la de la pila: template class Cola { Lista m_lista; Public; bool Insertar(T & dato) { return m_lista.InsertarDelante(dato); } bool Extraer(T & dato) { return m_lista.ExtraerDelante(dato); } bool EstaVacia(void) { return (m_lista.LeerCantidad() == 0); } };

Los iteradores Utilizando la plantilla de la lista doblemente enlazada, la pila y la cola han quedado muy bien implementadas. Sin embargo, respecto de la lista en sí nos falta algo bastante importante: un modo de recorrer los nodos. Supongamos que una aplicación desea hacer uso de nuestra plantilla Lista. Veamos:

www.redusers.com

56

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

float fValor; Lista lis; fValor = 1.0f; lis.InsertarDelante(fValor); fValor = 2.0f; lis.InsertarDelante(fValor); fValor = 3.0f; lis.InsertarDelante(fValor);

Bien, hemos insertado tres números en nuestra lista de números flotantes. ¿Cómo podríamos hacer ahora si quisiéramos recorrer la lista de punta a punta sin extraer nodos? Una posible solución sería retornando el puntero al primer nodo y, desde fuera, hacer una llamada a nodo próximo (es decir, algo parecido al modo en que la recortamos desde dentro). Pero, de esta forma, estaríamos exponiendo el funcionamiento interno de la lista a quien quiera usarla. Una solución más elegante es el uso de iteradores. Un iterador es un objeto que almacena en su interior un puntero a un nodo de la lista y ofrece primitivas para moverse por ella. Analicemos el siguiente código: template class Iterador { Nodo * m_pNodo; public: // Constructor Iterador(void) { m_pNodo = NULL; } // Constructor de copia Iterador(const Iterador & it) { m_pNodo = it.m_pNodo; } // Destructor ~Iterador(void) {} // Fija valor al iterador void FijarValor(Nodo * pNodo) { m_pNodo = pNodo; }

www.redusers.com

57

C++

// Mueve el curso al próximo nodo void MoverProximo(); // Mueve el cursor al nodo anterior // Retorna el dato asociado al nodo apuntado bool LeerDato(T & dato); // Indica si el iterador se encuentra apuntando a un nodo válido bool Final() { return (m_pNodo == NULL); } };

Como se puede apreciar, la plantilla Iterador posee en su interior una propiedad puntero a nodo; este nodo no será el primero o el último necesariamente, sino que será el nodo apuntado por el iterador en un momento determinado. Luego existirán varias primitivas con las cuales podremos operar con el iterador:

• • • •

MoverProximo: se moverá hacia el próximo nodo de la lista. MoverAnterior: se moverá al nodo anterior de la lista. LeerDato: retornará el dato asociado con el nodo actual. Final: indica si el iterador se encuentra apuntando a un nodo válido de la lista. El método MoverProximo: template void Iterator::MoverProximo() { if (m_pNodo) m_pNodo = m_pNodo->LeerPróximo(); }

Simplemente verificamos que el nodo apuntado sea válido y luego nos movemos al próximo haciendo uso del método LeerProximo de la plantilla Nodo.

www.redusers.com

58

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

El método LeerDato: template bool Iterador::LeerDato(T & dato) { if (m_pNodo) { Dato = m_pNodo->LeerDato(); } else return false; }

También es muy sencillo: verificamos el puntero y después invocamos el método LeerDato. Para la implementación de iteradores, tendremos que hacer un agregado a la plantilla Lista. Crearemos un nuevo método llamado Comienzo, que retornará un iterador apuntando al primer nodo de la lista (podríamos crear otro método que retorne un iterador al último nodo). Veamos cómo debería estar definido: template Iterador Lista::Comienzo() { Iterador it; It.FijarValor(m_pPrimerNodo); return it; }

El uso de iteradores facilita la navegación por una estructura de datos sin necesidad de saber cómo está compuesta o de qué manera funciona dicha estructura. Existe la posibilidad de tener muchos iteradores para la misma lista, solo debemos tener la precaución de reiniciarlos una vez que se haya modificado la lista, ya que podrían quedar apuntando a un nodo ya eliminado. Sería muy útil sobrecargar algunos operadores

www.redusers.com

59

C++

para que el uso del iterador sea más sencillo e intuitivo. Por ejemplo, podríamos sobrecargar el operador de postincremento para movernos al próximo nodo.

RESUMEN En este capítulo, descubrimos algunos conceptos fundamentales de la programación en C++. Estudiamos cómo crear una estructura de datos dinámica a través de las listas enlazadas y de qué forma, a través de las plantillas, podemos modificar todas las estructuras.

www.redusers.com

60

APÉNDICE B. ESTRUCTURAS DE DATOS DINÁMICAS Y PLANTILLAS

Actividades TEST DE AUTOEVALUACIÓN 1

¿Qué ventaja tiene una lista doblemente enlazada sobre una simplemente enlazada?

2

¿Cuál es la ventaja de una lista simplemente enlazada sobre una doblemente enlazada?

3

Qué es una plantilla y para qué se utiliza?

4

¿Qué son los iteradores?

EJERCICIOS PRÁCTICOS 1

Para una lista simplemente enlazada de números enteros, agregue un método llamado InsertarDespuesDe que reciba un puntero a un nodo como parámetro y un dato. Este método deberá insertar un nodo después del nodo especificado.

2

Para una lista simplemente enlazada de números enteros, agregue un método llamado InsertarEnOrden que inserte el número entero pasado como parámetro dentro de la lista, manteniendo un orden ascendente.

PROFESOR EN LÍNEA Si tiene alguna consulta técnica relacionada con el contenido, puede contactarse con nuestros expertos: [email protected]

www.redusers.com