Listas ligadas en C++ (cplusplus) arrays dinámicos con struct y punteros

[5378453]

Me dejaron hacer este ejercicio:



Mi problema es que  se como iniciarlo, tendria que utilizar arrays? si es asi, como creo un array vacio como constructor por default?

[Ogramar]

Buenas cuando en C y C++ se habla de listas ligadas normalmente se refiere a listas dinámicas o arrays dinámicos basados en el uso de estructuras de datos que usan punteros para referenciar al siguiente elemento de la lista (hasta terminar en NULL).

Para hacer un programa de este tipo debes conocer el concepto de puntero y el concepto de struct.

Una vez conozcas estos conceptos puedes buscar documentación para comprender qué es y cómo funciona una lista enlazada.

Este es un ejemplo sencillo:

Código: [Seleccionar]

#include <iostream>
using namespace std;

/**
 * Estructura Nodo
 */
struct Nodo {
int valor;
Nodo *siguiente;
};

/**
 * Clase Lista
 */
class Lista {
private:
Nodo *_primero;
public:
Lista();
~Lista();
void agregar( int );
Nodo * primero();
};

/**
 * Constructor
 */
Lista::Lista() {
_primero = NULL;
}

/**
 * Destructor
 */
Lista::~Lista() {
Nodo *nodo_actual = _primero;
while( nodo_actual != NULL ) {
Nodo *siguiente = nodo_actual->siguiente;
delete nodo_actual;
nodo_actual = siguiente;
}
}

/**
 * Método Agregar
 * Agrega un nodo a la lista
 */
void Lista::agregar( int nuevo_valor ) {
Nodo *nuevo_nodo = new Nodo;
nuevo_nodo->valor = nuevo_valor;
nuevo_nodo->siguiente = NULL;
if( _primero == NULL ) {
_primero = nuevo_nodo;
} else {
Nodo *nodo_actual = _primero;
while( nodo_actual->siguiente != NULL ) nodo_actual = nodo_actual->siguiente;
nodo_actual->siguiente = nuevo_nodo;
}
}

/**
 * Método Primero
 * retorna el primer nodo de la lista
 */
Nodo * Lista::primero() {
return _primero;
}

/**
 * Función principal
 */
int main() {
Lista lista;

// se agregan algunos valores a la lista
lista.agregar( 17 );
lista.agregar( 21 );
lista.agregar( 12 );

// se recorre la lista y se muestran los valores agregados
Nodo * it = lista.primero();
while( it != NULL ) {
cout << it->valor << endl;
it = it->siguiente;
}
return 0;
}

En este código se define una estructura Nodo que contendrá un valor y un puntero hacia otro nodo. Y una clase llamada Lista que nos permitirá agregar un nodo nuevo y recorrer los ya existentes.

Cada vez que se llama al método agregar habrá dos caminos posibles. Por un lado podemos contar con una lista vacía, es decir, esta será la primera vez que agreguemos un nodo, será el primer nodo. En el segundo caso la lista ya contendrá otros nodos.

La variable _primero es un puntero cuyo valor inicial es NULL, es decir, al crearse el objeto Lista, la variable _primero no estará apuntando a ningún nodo.

Cuando agreguemos un nodo verificaremos si _primero contiene como valor NULL. De ser así afirmamos que es el primer nodo que estamos agregando, así que procedemos a asignarle la dirección de este nuevo nodo a la variable _primero. Y hacemos que este nuevo nodo apunte a NULL.

Cuando agreguemos un segundo nodo, veremos que _primero ya está apuntando al nodo que hemos agregado antes. Así que haremos que ese nodo apunte al nuevo nodo que estamos agregando. Y este último nodo apuntará a NULL.

Lo importante al trabajar con listas enlazadas es entender perfectamente que un nodo enlaza (referencia) al siguiente y que la lista termina cuando la siguiente referencia es NULL, que señala el final de la lista

Salu2