Continuando con el tema de listas trabajaremos con las listas genéricas. Una lista se comporta como genérica cuando las inserciones y extracciones se realizan en cualquier parte de la lista.
Codificaremos una serie de métodos para administrar listas genéricas.
Métodos a desarrollar:
Inserta un nodo en la posición (pos) y con la información que hay en el parámetro x.
void insertar(int pos, int x)
Extrae la información del nodo de la posición indicada (pos). Se debe eliminar el nodo.
int extraer(int pos)
Borra el nodo de la posición (pos).
void borrar(int pos)
Intercambia las informaciones de los nodos de las posiciones pos1 y pos2.
void intercambiar(int pos1,int pos2)
Retorna el valor del nodo con mayor información.
int mayor()
Retorna la posición del nodo con mayor información.
int posMayor()
Retorna la cantidad de nodos de la lista.
int cantidad()
Debe retornar true si la lista está ordenada de menor a mayor, false en caso contrario.
bool ordenada()
Debe retornar true si existe la información que llega en el parámetro, false en caso contrario.
bool existe(int info)
El método vacía debe retornar true si está vacía y false si no lo está.
boolean vacia()
#include <iostream>
using namespace std;
class ListaGenerica {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
ListaGenerica();
~ListaGenerica();
int cantidad();
void insertar(int pos, int x);
int extraer(int pos);
void borrar(int pos);
void intercambiar(int pos1, int pos2);
bool vacia();
int mayor();
void imprimir();
int posMayor();
bool ordenada();
bool existe(int x);
};
ListaGenerica::ListaGenerica()
{
raiz = NULL;
}
ListaGenerica::~ListaGenerica()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
int ListaGenerica::cantidad()
{
Nodo *reco = raiz;
int cant = 0;
while (reco != NULL)
{
cant++;
reco = reco->sig;
}
return cant;
}
void ListaGenerica::insertar(int pos, int x)
{
if (pos <= cantidad() + 1)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (pos == 1)
{
nuevo->sig = raiz;
raiz = nuevo;
}
else
if (pos == cantidad() + 1)
{
Nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
reco->sig = nuevo;
nuevo->sig = NULL;
}
else
{
Nodo *reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Nodo *siguiente = reco->sig;
reco->sig = nuevo;
nuevo->sig = siguiente;
}
}
}
int ListaGenerica::extraer(int pos)
{
if (pos <= cantidad())
{
int informacion;
Nodo *bor;
if (pos == 1)
{
informacion = raiz->info;
bor = raiz;
raiz = raiz->sig;
}
else
{
Nodo *reco;
reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Nodo *prox = reco->sig;
reco->sig = prox->sig;
informacion = prox->info;
bor = prox;
}
delete bor;
return informacion;
}
else
return -1;
}
void ListaGenerica::borrar(int pos)
{
if (pos <= cantidad())
{
Nodo *bor;
if (pos == 1)
{
bor = raiz;
raiz = raiz->sig;
}
else {
Nodo *reco;
reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Nodo *prox = reco->sig;
reco->sig = prox->sig;
bor = prox;
}
delete bor;
}
}
void ListaGenerica::intercambiar(int pos1, int pos2)
{
if (pos1 <= cantidad() && pos2 <= cantidad())
{
Nodo *reco1 = raiz;
for (int f = 1; f < pos1; f++)
{
reco1 = reco1->sig;
}
Nodo *reco2 = raiz;
for (int f = 1; f < pos2; f++)
{
reco2 = reco2->sig;
}
int aux = reco1->info;
reco1->info = reco2->info;
reco2->info = aux;
}
}
bool ListaGenerica::vacia()
{
if (raiz == NULL)
return true;
else
return false;
}
int ListaGenerica::mayor()
{
if (!vacia())
{
int may = raiz->info;
Nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
}
reco = reco->sig;
}
return may;
}
else
return -1;
}
void ListaGenerica::imprimir()
{
Nodo *reco = raiz;
cout << "Listado completo.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
int ListaGenerica::posMayor()
{
if (!vacia())
{
int may = raiz->info;
int x = 1;
int pos = x;
Nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
pos = x;
}
reco = reco->sig;
x++;
}
return pos;
}
else
return -1;
}
bool ListaGenerica::ordenada()
{
if (cantidad()>1)
{
Nodo *reco1 = raiz;
Nodo *reco2 = raiz->sig;
while (reco2 != NULL)
{
if (reco2->info<reco1->info)
{
return false;
}
reco2 = reco2->sig;
reco1 = reco1->sig;
}
}
return true;
}
bool ListaGenerica::existe(int x)
{
Nodo *reco = raiz;
while (reco != NULL)
{
if (reco->info == x)
return true;
reco = reco->sig;
}
return false;
}
void main()
{
ListaGenerica *lg = new ListaGenerica();
lg->insertar(1, 10);
lg->insertar(2, 20);
lg->insertar(3, 30);
lg->insertar(2, 15);
lg->insertar(1, 115);
lg->imprimir();
cout <<"Luego de Borrar el primero\n";
lg->borrar(1);
lg->imprimir();
cout<<"Luego de Extraer el segundo\n";
lg->extraer(2);
lg->imprimir();
cout<<"Luego de Intercambiar el primero con el tercero\n";
lg->intercambiar(1, 3);
lg->imprimir();
if (lg->existe(20))
cout<<"Se encuentra el 20 en la lista\n";
else
cout<<"No se encuentra el 20 en la lista\n";
cout <<"La posición del mayor es:" <<lg->posMayor() <<"\n";
if (lg->ordenada())
cout<<"La lista esta ordenada de menor a mayor\n";
else
cout<<"La lista no esta ordenada de menor a mayor\n";
delete lg;
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace : ListasGenericas1.zip
Para insertar en una determinada posición dentro de la lista:
void insertar (int pos, int x)
Primero con un if verificamos que exista esa posición en la lista (por ejemplo si la lista tiene 4 nodos podemos insertar hasta la posición 5, es decir uno más allá del último):
if (pos <= cantidad() + 1)
Si ingresa al if ya podemos crear el nodo:
Nodo *nuevo = new Nodo();
nuevo->info = x;
Ahora debemos analizar si la inserción es al principio de la lista, al final o en medio ya que los enlaces varían según donde se lo inserta.
Para saber si se inserta al principio de la lista preguntamos si en pos llega un 1:
if (pos == 1)
Si llega un 1 luego enlazamos el puntero sig del nodo que creamos con la dirección del primer nodo de la lista (raiz apunta siempre al primer nodo de la lista) y luego desplazamos raiz al nodo que acabamos de crear:
nuevo->sig = raiz;
raiz = nuevo;
Si no se inserta al principio de la lista preguntamos si se inserta al final:
if (pos == cantidad() + 1)
En caso de insertarse al final recorremos la lista hasta el último nodo:
Nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
y enlazamos el puntero sig del último nodo de la lista con la dirección del nodo que acabamos de crear (disponemos en sig del nodo creado el valor NULL ya que no hay otro nodo más adelante)
reco->sig = nuevo;
nuevo->sig = NULL;
Si no se inserta al principio o al final significa que tenemos que insertar en medio de la lista.
Disponemos un for donde avanzamos un puntero auxiliar y nos detenemos una posición antes a donde tenemos que insertarlo:
Nodo *reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Disponemos otro puntero auxiliar que apunte al nodo próximo a donde está apuntando reco. Ahora enlazamos el puntero sig del nodo apuntado por reco con la dirección del nodo creado y el puntero sig del nodo creado con la dirección del nodo siguiente:
Nodo *siguiente = reco->sig;
reco->sig = nuevo;
nuevo->sig = siguiente;
El método extraer recibe como parámetro la posición del nodo a extraer:
int extraer (int pos) {
Primero verificamos que la posición exista en la lista:
if (pos <= cantidad())
En caso que exista verificamos si el nodo a extraer es el primero de la lista (este análisis debe hacerse ya que si es el primero de la lista se modifica el puntero raiz):
if (pos == 1)
Si es el primero guardamos en una variable auxiliar la información del nodo, inicializamos bor con la dirección del nodo a borrar y avanzamos el puntero raiz:
informacion = raiz->info;
bor = raiz;
raiz = raiz->sig;
Si el nodo a extraer no está al principio de la lista avanzamos con una estructura repetitiva hasta el nodo anterior a extraer:
Nodo *reco;
reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Luego definimos otro puntero auxiliar y lo disponemos en el siguiente nodo a donde está apuntando reco:
Nodo *prox = reco->sig;
Ahora enlazamos el puntero sig del nodo apuntado por reco al nodo siguiente del nodo apuntado por prox (es decir el nodo apuntado por prox queda fuera de la lista):
reco->sig = prox->sig;
Inicializamos la variable auxiliar informacion con el dato a devolver y bor con la dirección del nodo a borrar.
informacion = prox->info;
bor = prox;
Por último borramos el nodo a extraer:
delete bor;
El método borrar el nodo de una determinada posición es muy similar al método extraer con la diferencia de que no retorna valor:
void ListaGenerica::borrar(int pos)
{
if (pos <= cantidad())
{
Nodo *bor;
if (pos == 1)
{
bor = raiz;
raiz = raiz->sig;
}
else {
Nodo *reco;
reco = raiz;
for (int f = 1; f <= pos - 2; f++)
{
reco = reco->sig;
}
Nodo *prox = reco->sig;
reco->sig = prox->sig;
bor = prox;
}
delete bor;
}
}
El método intercambiar recibe dos enteros que representan las posiciones de los nodos que queremos intercambiar sus informaciones:
void intercambiar (int pos1, int pos2) {
Mediante un if verificamos que las dos posiciones existan en la lista:
if (pos1 <= cantidad() && pos2 <= cantidad())
Definimos un puntero auxiliar llamado reco1, lo inicializamos con la dirección del primer nodo y mediante un for avanzamos hasta la posición almacenada en pos1:
Nodo *reco1 = raiz;
for (int f = 1; f < pos1; f++)
{
reco1 = reco1->sig;
}
De forma similar con un segundo puntero auxiliar avanzamos hasta la posición indicada por pos2:
Nodo *reco2 = raiz;
for (int f = 1; f < pos2; f++)
{
reco2 = reco2->sig;
}
Por último intercambiamos las informaciones que almacenan cada nodo:
int aux = reco1->info;
reco1->info = reco2->info;
reco2->info = aux;
El método que retorna el mayor de la lista:
int mayor () {
Verificamos que la lista no esté vacía:
if (!vacia())
Suponemos que el mayor es el primero de la lista e inicializamos un puntero auxiliar con la dirección del segundo nodo de la lista:
int may = raiz->info;
Nodo *reco = raiz->sig;
Mediante una estructura repetitiva recorremos toda la lista:
while (reco != NULL)
Cada vez que encontramos un nodo con información mayor que la variable may la actualizamos con este nuevo valor y avanzamos el puntero reco para visitar el siguiente nodo:
if (reco->info > may)
{
may = reco->info;
}
reco = reco->sig;
Fuera de la estructura repetitiva retornamos el mayor:
return may;
El método que retorna la posición del mayor es similar al anterior con la salvedad que debemos almacenar en otro auxiliar la posición donde se almacena el mayor:
int ListaGenerica::posMayor()
{
if (!vacia())
{
int may = raiz->info;
int x = 1;
int pos = x;
Nodo *reco = raiz->sig;
while (reco != NULL)
{
if (reco->info > may)
{
may = reco->info;
pos = x;
}
reco = reco->sig;
x++;
}
return pos;
}
else
return -1;
}
El método que debe retornar si está ordenada la lista de menor a mayor es:
bool ordenada() {
Lo primero que verificamos si la lista tiene más de un nodo significa que debemos controlarla:
if (cantidad()>1)
Disponemos dos punteros auxiliares con las direcciones del primer y segundo nodo de la lista:
Nodo *reco1 = raiz;
Nodo *reco2 = raiz->sig;
Mediante un while mientras no se finaliza la lista:
while (reco2 != NULL)
controlamos si la información del segundo nodo es menor al nodo anterior significa que la lista no está ordenada y podemos parar el análisis retornando un false
if (reco2->info<reco1->info)
{
return false;
}
Dentro del while avanzamos los dos punteros a sus nodos siguientes respectivamente.
reco2 = reco2->sig;
reco1 = reco1->sig;
Fuera del while retornamos true indicando que la lista está ordenada de menor a mayor
return true;
El método existe:
bool existe(int x) {
Mediante un while recorremos la la lista:
Nodo *reco = raiz;
while (reco != NULL)
y en cada nodo que visitamos controlamos si el parámetro x es igual a la información del nodo, en caso afirmativo salimos del método retornando true:
if (reco->info == x)
return true;
reco = reco->sig;
Fuera del while retornamos false indicando que ningún nodo coincide con el parámetro x:
return false;
Plantear una clase para administrar una lista genérica implementando los siguientes métodos:
a) Insertar un nodo al principio de la lista.
b) Insertar un nodo al final de la lista.
c) Insertar un nodo en la segunda posición. Si la lista está vacía no se inserta el nodo.
d) Insertar un nodo en la ante última posición.
e) Borrar el primer nodo.
f) Borrar el segundo nodo.
g) Borrar el último nodo.
h) Borrar el nodo con información mayor.
#include <iostream>
using namespace std;
class ListaGenerica {
private:
class Nodo {
public:
int info;
Nodo *sig;
};
Nodo *raiz;
public:
ListaGenerica();
~ListaGenerica();
void imprimir();
void insertarPrimero(int x);
void insertarUtlimo(int x);
void insertarSegundo(int x);
void insertarAnteUltimo(int x);
void borrarPrimero();
void borrarSegundo();
void borrarUltimo();
void borrarMayor();
};
ListaGenerica::ListaGenerica()
{
raiz = NULL;
}
ListaGenerica::~ListaGenerica()
{
Nodo *reco = raiz;
Nodo *bor;
while (reco != NULL)
{
bor = reco;
reco = reco->sig;
delete bor;
}
}
void ListaGenerica::imprimir()
{
Nodo *reco = raiz;
cout << "Listado completo.\n";
while (reco != NULL)
{
cout << reco->info << "-";
reco = reco->sig;
}
cout << "\n";
}
void ListaGenerica::insertarPrimero(int x)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
nuevo->sig = raiz;
raiz = nuevo;
}
void ListaGenerica::insertarUtlimo(int x)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
raiz = nuevo;
else
{
Nodo *reco = raiz;
while (reco->sig != NULL)
{
reco = reco->sig;
}
reco->sig = nuevo;
}
}
void ListaGenerica::insertarSegundo(int x)
{
if (raiz != NULL)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz->sig == NULL)
{
//Hay un solo nodo.
raiz->sig = nuevo;
}
else
{
nuevo->sig = raiz->sig;
raiz->sig = nuevo;
}
}
}
void ListaGenerica::insertarAnteUltimo(int x)
{
if (raiz != NULL)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz->sig == NULL) {
//Hay un solo nodo.
nuevo->sig = raiz;
raiz = nuevo;
}
else
{
Nodo *atras = raiz;
Nodo *reco = raiz->sig;
while (reco->sig != NULL)
{
atras = reco;
reco = reco->sig;
}
nuevo->sig = atras->sig;
atras->sig = nuevo;
}
}
}
void ListaGenerica::borrarPrimero()
{
if (raiz != NULL)
{
Nodo *bor = raiz;
raiz = raiz->sig;
delete bor;
}
}
void ListaGenerica::borrarSegundo()
{
if (raiz != NULL)
{
if (raiz->sig != NULL)
{
Nodo *bor = raiz->sig;
Nodo *tercero = raiz->sig;
tercero = tercero->sig;
raiz->sig = tercero;
delete bor;
}
}
}
void ListaGenerica::borrarUltimo()
{
if (raiz != NULL)
{
if (raiz->sig == NULL)
{
delete raiz;
raiz = NULL;
}
else
{
Nodo *reco = raiz->sig;
Nodo *atras = reco;
while (reco->sig != NULL)
{
atras = reco;
reco = reco->sig;
}
atras->sig = NULL;
delete reco;
}
}
}
void ListaGenerica::borrarMayor()
{
if (raiz != NULL)
{
Nodo *reco = raiz;
int may = raiz->info;
while (reco != NULL)
{
if (reco->info>may)
{
may = reco->info;
}
reco = reco->sig;
}
reco = raiz;
Nodo *atras = raiz;
Nodo *bor;
while (reco != NULL)
{
if (reco->info == may)
{
if (reco == raiz)
{
bor = raiz;
raiz = raiz->sig;
atras = raiz;
reco = raiz;
delete bor;
}
else {
atras->sig = reco->sig;
bor = reco;
reco = reco->sig;
delete bor;
}
}
else {
atras = reco;
reco = reco->sig;
}
}
}
}
void main()
{
ListaGenerica *lg = new ListaGenerica();
lg->insertarPrimero(10);
lg->insertarPrimero(45);
lg->insertarPrimero(23);
lg->insertarPrimero(89);
lg->imprimir();
cout<<"Insertamos un nodo al final:\n";
lg->insertarUtlimo(160);
lg->imprimir();
cout<<"Insertamos un nodo en la segunda posición:\n";
lg->insertarSegundo(13);
lg->imprimir();
cout<<"Insertamos un nodo en la anteultima posición:\n";
lg->insertarAnteUltimo(600);
lg->imprimir();
cout<<"Borramos el primer nodo de la lista:\n";
lg->borrarPrimero();
lg->imprimir();
cout<<"Borramos el segundo nodo de la lista:\n";
lg->borrarSegundo();
lg->imprimir();
cout<<"Borramos el ultimo nodo de la lista:\n";
lg->borrarUltimo();
lg->imprimir();
cout<<"Borramos el mayor de la lista:\n";
lg->borrarMayor();
lg->imprimir();
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace :ListasGenericas2.zip