Listas Encadenadas

Quisiera que me ayudaran con un programa que tengo que hacer, si no lo hago me reprueban, espero puedan ayudarme el planteamiento del problema es el siguiente:
Realiza un programa en C++ que implemente una pila como lista encadenada. Toma como base el programa que viste como ejemplo la clase anterior ListaEnc1.cpp.
Recuerda que una pila es una estructura de datos en la que sus elementos entran y salen siempre por el mismo extremo.
Implementa las funciones típicas de una pila:
a.Pus (insertar un elemento)
b.Pop (sacar un elemento)
c.Vacía, función que regresa true si la pila está vacía y false en caso contrario.
d.Mostrar, función que muestre todo el contenido de la pila.
Realiza una función main que permita al usuario probar todas las funciones de la pila.
El programa ListaEnc1.cpp es el siguiente:
#include <iostream>
using namespace std;
//estructura del Nodo
struct Nodo
{
int numero;
Nodo *siguiente;
};
// La clase Lista se usa para manejar una lista encadenada de nodos
class Lista
{
public:
Lista();
~Lista();
void Agregar(int num);// metodo que agrega a la lista en orden ascendente
void Mostrar();// muestra todos los elementos de la lista
void Borrar(int num);// elimina de la lista el nodo que contiene el valor num
private:
Nodo *inicio; // apuntador al inicio de la lista
};
// Constructor para la lista, inicializa el inicio con NULL porque la lista esta vacia
Lista::Lista()
{
inicio = NULL;
}
// Destructor de la lista, libera la memoria utilizada por la lista
Lista::~Lista()
{
Nodo *temp, *anterior;
temp = inicio;
while (temp != NULL)
{ anterior = temp;
temp = temp->siguiente;
delete anterior;
}
}
// Agregar Nodos en orden ascendente
void Lista::Agregar(int num)
{
Nodo *temp, *nuevo, *anterior;
nuevo = new Nodo;
nuevo->numero = num;
nuevo->siguiente = NULL;
temp = inicio;
anterior = NULL;// como no hay nodo anterior a inicio se pone NULL
if (inicio == NULL) // Si es el primer elemento de la lista
inicio = nuevo;
else
{
//busca la posicion para insertar en orden
while ((temp != NULL) && (temp->numero < num))
{
anterior = temp;
temp = temp->siguiente;
}
nuevo->siguiente = temp;
if (anterior == NULL) // si anterior es nulo significa que estoy en
// el primer elemento de la lista
inicio = nuevo;
else
anterior->siguiente = nuevo;
}
}
// Mostrar la lista de numeros
void Lista::Mostrar()
{
Nodo *n;
cout<<"\n Lista de Numeros \n";
n = inicio;
while (n != NULL)
{ cout<<n->numero<<endl;
n = n->siguiente;
}
}
// Elimina nodos
void Lista::Borrar(int num)
{ Nodo *nodo, *anterior;
nodo = inicio;
anterior = NULL;
while ((nodo != NULL) && (nodo->numero != num))
{ anterior = nodo;
nodo = nodo->siguiente;
}
if(nodo == NULL)
cout<<"No se encuentra ese numero"<<endl;
else
{
if(nodo == inicio)// se va a borrar el primer nodo
inicio = inicio->siguiente;
else // se va a borrar entre dos nodos
anterior->siguiente = nodo->siguiente;
delete nodo;
}
}
// funcion principal
int main( )
{
// Variables locales al main
int num;
int opc;
Lista ListaNum;
do
{
cout<< "Lista de numeros"<<endl;
cout<< "1. Agregar"<<endl;
cout<< "2. Mostrar Lista"<<endl;
cout<< "3. Eliminar"<<endl;
cout<< "4. Terminar"<<endl;
cout<< "Opcion ";
cin>>opc;
switch (opc)
{ case 1:
// Se leen los datos por pantalla
cout<<"Numero ? \n";
cin>>num;
ListaNum.Agregar(num);
break;
case 2:
// Muestra todos los numeros de la lista
ListaNum.Mostrar();
break;
case 3:
// Elimina un nodo
cout<<"Numero del producto\n";
cin>>num;
ListaNum.Borrar(num);
break;
}
} while (opc != 4);
return 0;
}
// Termina el programa ListaNum.cpp
2

2 Respuestas

9.825 pts. Estoy de regreso: desde hace tiempo no estaba por el...
Yo utilizo el C++ Builder 6 para compilar y editar todo, y no me da errores, de momento he preguntado por aquí y me han dicho que lo mejor seria que tuvieras la teoría y que no te enviara código pues las diferencias de compiladores aunque no han de ser muchas pueden provocar errores como los que me planteas, de momento te envío TODO el código del programa que enviaste con mis modoficaciones, para que lo pruebes y me digas si los errores se mantienen o si hay cambios:
//---------------------------------------------------------------------------
#include <clx.h>
#pragma hdrstop
#include <iostream>
using namespace std;
//estructura del Nodo
struct Nodo
{
int numero;
Nodo *siguiente;
};
// La clase Lista se usa para manejar una lista encadenada de nodos
class Lista
{
public:
Lista();
~Lista();
void Agregar(int num);// metodo que agrega a la lista en orden ascendente
void Mostrar();// muestra todos los elementos de la lista
void Borrar(int num);// elimina de la lista el nodo que contiene el valor num
// Para retornar el nodo inicial
Nodo *Primero(); // Elimina el primero de la lista retornando el nodo inicio
void CambiarPrimero(Nodo *primero); // Pone al nodo primero como el inicio de la lista
private:
Nodo *inicio; // apuntador al inicio de la lista
};
// Constructor para la lista, inicializa el inicio con NULL porque la lista esta vacia
Lista::Lista()
{
inicio = NULL;
}
// Destructor de la lista, libera la memoria utilizada por la lista
Lista::~Lista()
{
Nodo *temp, *anterior;
temp = inicio;
while (temp != NULL)
{ anterior = temp;
temp = temp->siguiente;
delete anterior;
}
}
// Agregar Nodos en orden ascendente
void Lista::Agregar(int num)
{
Nodo *temp, *nuevo, *anterior;
nuevo = new Nodo;
nuevo->numero = num;
nuevo->siguiente = NULL;
temp = inicio;
anterior = NULL;// como no hay nodo anterior a inicio se pone NULL
if (inicio == NULL) // Si es el primer elemento de la lista
inicio = nuevo;
else
{
//busca la posicion para insertar en orden
while ((temp != NULL) && (temp->numero < num))
{
anterior = temp;
temp = temp->siguiente;
}
nuevo->siguiente = temp;
if (anterior == NULL) // si anterior es nulo significa que estoy en
// el primer elemento de la lista
inicio = nuevo;
else
anterior->siguiente = nuevo;
}
}
// Mostrar la lista de numeros
void Lista::Mostrar()
{
Nodo *n;
cout<<"\n Lista de Numeros \n";
n = inicio;
while (n != NULL)
{ cout<<n->numero<<endl;
n = n->siguiente;
}
}
// Elimina nodos
void Lista::Borrar(int num)
{ Nodo *nodo, *anterior;
nodo = inicio;
anterior = NULL;
while ((nodo != NULL) && (nodo->numero != num))
{ anterior = nodo;
nodo = nodo->siguiente;
}
if(nodo == NULL)
cout<<"No se encuentra ese numero"<<endl;
else
{
if(nodo == inicio)// se va a borrar el primer nodo
inicio = inicio->siguiente;
else // se va a borrar entre dos nodos
anterior->siguiente = nodo->siguiente;
delete nodo;
}
}
Nodo *Lista::Primero()
{
if(inicio != NULL)
{
Nodo *resultado = new Nodo;
resultado = inicio;
if(inicio->siguiente != NULL)
inicio = inicio->siguiente;
else
inicio = NULL;
return resultado;
}
else
return inicio;
}
void Lista::CambiarPrimero(Nodo *primero)
{
primero->siguiente = inicio;
inicio = primero;
}
class Pila : protected Lista
{
private:
Lista *elementos;
public:
Pila();
~Pila();
void Push(int);
int Pop();
bool Vacia();
void Mostrar();
};
Pila::Pila()
{
elementos = new Lista;
}
Pila::~Pila()
{
elementos->~Lista();
delete elementos;
}
void Pila::Push(int e)
{
Nodo *nuevo = new Nodo;
nuevo->numero = e;
nuevo->siguiente = NULL;
elementos->CambiarPrimero(nuevo);
}
int Pila::Pop()
{
Nodo *nodo = new Nodo;
nodo = elementos->Primero();
if(nodo != NULL)
return nodo->numero;
}
bool Pila::Vacia()
{
return elementos->Primero() == NULL;
}
void Pila::Mostrar()
{
elementos->Mostrar();
}
// funcion principal
int main( )
{
// Variables locales al main
int num;
int opc;
Pila pilaNumeros;
do
{
cout<< "Lista de numeros"<<endl;
cout<< "1. Agregar"<<endl;
cout<< "2. Mostrar Lista"<<endl;
cout<< "3. Eliminar"<<endl;
cout << "4. Vacia" << endl;
cout<< "5. Terminar"<<endl;
cout<< "Opcion ";
cin>>opc;
switch (opc)
{ case 1:
// Se leen los datos por pantalla
cout<<"Numero ? \n";
cin>>num;
pilaNumeros.Push(num);
break;
case 2:
// Muestra todos los numeros de la lista
pilaNumeros.Mostrar();
break;
case 3:
// Elimina un nodo
/*cout<<"Numero del producto\n";
cin>>num;*/
pilaNumeros.Pop();
break;
case 4:
if(pilaNumeros.Vacia())
cout << "Si" << endl;
else
cout << "No" << endl;
break;
}
} while (opc != 5);
return 0;
}
// Termina el programa ListaNum.cpp
Se que es engorroso leer todo esto pero es la forma que tengo de saber si los compiladores están muy distantes entre si. Pero si no puedes ejecutar el programa me lo dices y tratare de instalar C++ Builder 5 aquí, para ver si te ayudo del todo, también puedes visitar este enlace, te aseguro que podrás implementar tu estructura SIN problemas luego de estudiarte estas páginas.
http://c.conclase.net/edd/index.php
Espero que termines pronto el ejercicio y que te resulte de ayuda el enlace, recuerda decirme que respuesta te dio el compilador para así reimplementar tu Lista para que funcione como una Pila sin herencia.
El compilador que estoy utilizando lo baje de esta página:
http://www.borland.com/products/downloads/download_cbuilder.html#
En esta liga, donde dice Compiler para Windows 5.5.
Lo volví a copiar y me ahora me arrojo más errores, dos los pude corregir eran del contrsuctor y el desctructor, me decía que había una múltiple declaración del constructor Lista y Pila, pero les faltaba el símbolo "~" que según se yo, es para indicar que es un destructor.
Los errores que me arrojo son:
Error E2209 dos.cpp 1: Unable to open include file 'clx.h'
Error E2316 dos.cpp 161: 'Lista' is not member of 'Lista' in fuction Pila::Pila()
Warning W8070 dos.cpp 183: fuction should retun a value in fuction Pila::Pop()
Espero puedas ayudarme, si es más fácil el programa donde no ocupas la herencia, creo que seria bastante bien, muchas gracias.
Copie el código tal y como usted lo puso en la página y me aparecen 3 errores al momento de compilarlo, utilizoel compilador 5.5 de borland y el Crimson para editar, los errores que me salen son los siguientes:
Error E2141 uno.cpp 2: Declaration syntax error
Error E2451 uno.cpp 3: Undefiden symbol 'Nodo'
Error E2141 uno.cpp 5: Declaration syntax error
Error E2090 uno.cpp 47:Qualifier 'Pila' is not a class or namespace name
Error E2040 uno.cpp 47: Declaration termined incorrectly
Me dijo que si la clase no debe de heredar, pues la verdad yo creo que no, por que no lo especifica el problema, en caso de que así fuera, estaría especificado.
¿Me podría ayudar con estos errores? Muchas gracias.
Bien:
Aquí esta el ejemplo completo sin herencia, sin problemas en C++ Builder 6, dime si tienes alguno tu, lo de clx. H es propio de la version 6, la utiliza para poder crear la consola, intenta eliminar esa linea y dime.
//---------------------------------------------------------------------------
#include <clx.h>
#pragma hdrstop
#include <iostream>
using namespace std;
//estructura del Nodo
struct Nodo
{
int numero;
Nodo *siguiente;
};
// La clase Lista se usa para manejar una lista encadenada de nodos
class Lista
{
public:
Lista();
~Lista();
void Agregar(int num);// metodo que agrega a la lista en orden ascendente
void Mostrar();// muestra todos los elementos de la lista
void Borrar(int num);// elimina de la lista el nodo que contiene el valor num
// Para retornar el nodo inicial
/**********************************
aqui mis metodos para la Pila
***********************************/
void Push(int);
int Pop();
bool Vacia();
private:
Nodo *inicio; // apuntador al inicio de la lista
};
// Constructor para la lista, inicializa el inicio con NULL porque la lista esta vacia
Lista::Lista()
{
inicio = NULL;
}
// Destructor de la lista, libera la memoria utilizada por la lista
Lista::~Lista()
{
Nodo *temp, *anterior;
temp = inicio;
while (temp != NULL)
{ anterior = temp;
temp = temp->siguiente;
delete anterior;
}
}
// Agregar Nodos en orden ascendente
void Lista::Agregar(int num)
{
Nodo *temp, *nuevo, *anterior;
nuevo = new Nodo;
nuevo->numero = num;
nuevo->siguiente = NULL;
temp = inicio;
anterior = NULL;// como no hay nodo anterior a inicio se pone NULL
if (inicio == NULL) // Si es el primer elemento de la lista
inicio = nuevo;
else
{
//busca la posicion para insertar en orden
while ((temp != NULL) && (temp->numero < num))
{
anterior = temp;
temp = temp->siguiente;
}
nuevo->siguiente = temp;
if (anterior == NULL) // si anterior es nulo significa que estoy en
// el primer elemento de la lista
inicio = nuevo;
else
anterior->siguiente = nuevo;
}
}
// Mostrar la lista de numeros
void Lista::Mostrar()
{
Nodo *n;
cout<<"\n Lista de Numeros \n";
n = inicio;
while (n != NULL)
{ cout<<n->numero<<endl;
n = n->siguiente;
}
}
// Elimina nodos
void Lista::Borrar(int num)
{ Nodo *nodo, *anterior;
nodo = inicio;
anterior = NULL;
while ((nodo != NULL) && (nodo->numero != num))
{ anterior = nodo;
nodo = nodo->siguiente;
}
if(nodo == NULL)
cout<<"No se encuentra ese numero"<<endl;
else
{
if(nodo == inicio)// se va a borrar el primer nodo
inicio = inicio->siguiente;
else // se va a borrar entre dos nodos
anterior->siguiente = nodo->siguiente;
delete nodo;
}
}
/*********************************
aqui mis metodos para la Pila
*********************************/
void Lista::Push(int e)
{
Nodo *nuevo = new Nodo;
nuevo->numero = e;
nuevo->siguiente = inicio;
inicio = nuevo;
}
int Lista::Pop()
{
if(inicio != NULL)
{
Nodo *resultado = new Nodo;
resultado = inicio;
if(inicio->siguiente != NULL)
inicio = inicio->siguiente;
else
inicio = NULL;
return resultado->numero;
}
else
throw "Lista Vacia";
}
bool Lista::Vacia()
{
return inicio == NULL;
}
/******** hasta aqui la pila *********/
// funcion principal
int main( )
{
// Variables locales al main
int num;
int opc;
Lista pilaNumeros;
do
{
cout<< "Lista de numeros"<<endl;
cout<< "1. Agregar"<<endl;
cout<< "2. Mostrar Lista"<<endl;
cout<< "3. Eliminar"<<endl;
cout << "4. Vacia" << endl;
cout<< "5. Terminar"<<endl;
cout<< "Opcion ";
cin>>opc;
switch (opc)
{ case 1:
// Se leen los datos por pantalla
cout<<"Numero ? \n";
cin>>num;
pilaNumeros.Push(num);
break;
case 2:
// Muestra todos los numeros de la lista
pilaNumeros.Mostrar();
break;
case 3:
// Elimina un nodo
/*cout<<"Numero del producto\n";
cin>>num;*/
try
{
pilaNumeros.Pop();
}
catch(...)
{
cout << "Lista vacia" << endl;
}
break;
case 4:
if(pilaNumeros.Vacia())
cout << "Si" << endl;
else
cout << "No" << endl;
break;
}
} while (opc != 5);
return 0;
}
// Termina el programa ListaNum.cpp
Este es mi primer mensaje, quisiera que lo analizara y si en realidad no responde a su pregunta me lo comunique sin algún problema, acepto toda la critica que pueda opinar Ud.
El problema en general no es complicado, solo que la estructura Lista que le dieron es muy pobre, las listas necesitan un poco más de acciones, las operaciones clásicas son Adicionar(T x) adiciona un elemento x de tipo T al final de la lista, Eliminar(int pues) elimina lo que esta en pues, Obtener(int pues) este retorna el elemento de tipo T que esta en el subíndice n), EsVacia() dice si hay o no elementos, pero ademas es muy ÚTIL el uso de un método Insertar(T x, int pues) que inserte un elemento x de tipo T en la posición pues, este es muy importante al hacer implementaciones de listas como Pilas, Colas, Arboles y demás...
Ahora bien, el código que use para resolver su problema es el siguiente:
// Estos metodos los adicione a la clase Lista
Nodo *Primero(); // Elimina el primero de la lista retornando el nodo inicio
void CambiarPrimero(Nodo *primero); // Pone al nodo primero como el inicio de la lista
las implementaciones son:
Nodo *Lista::Primero()
{
if(inicio != NULL)
{
Nodo *resultado = new Nodo;
resultado = inicio;
if(inicio->siguiente != NULL)
inicio = inicio->siguiente;
else
inicio = NULL;
return resultado;
}
else
return inicio;
}
void Lista::CambiarPrimero(Nodo *primero)
{
primero->siguiente = inicio;
inicio = primero;
}
La clase Pila hereda de la clase Lista, esto es en caso que pueda emplear Herencia, si no es así, por favor dígamelo para rectificar mi respuesta.
class Pila : protected Lista
{
private:
Lista *elementos;
public:
Pila();
~Pila();
void Push(int);
int Pop();
bool Vacia();
void Mostrar();
};
Pila::Pila()
{
elementos = new Lista;
}
Pila::~Pila()
{
elementos->~Lista();
delete elementos;
}
void Pila::Push(int e)
{
Nodo *nuevo = new Nodo;
nuevo->numero = e;
nuevo->siguiente = NULL;
elementos->CambiarPrimero(nuevo);
}
int Pila::Pop()
{
Nodo *nodo = new Nodo;
nodo = elementos->Primero();
if(nodo != NULL)
return nodo->numero;
}
bool Pila::Vacia()
{
return elementos->Primero() == NULL;
}
void Pila::Mostrar()
{
elementos->Mostrar();
}
Y el main del programa quedaria:
// funcion principal
int main( )
{
// Variables locales al main
int num;
int opc;
Pila pilaNumeros;
do
{
cout<< "Lista de numeros"<<endl;
cout<< "1. Agregar"<<endl;
cout<< "2. Mostrar Lista"<<endl;
cout<< "3. Eliminar"<<endl;
cout << "4. Vacia" << endl;
cout<< "5. Terminar"<<endl;
cout<< "Opcion ";
cin>>opc;
switch (opc)
{ case 1:
// Se leen los datos por pantalla
cout<<"Numero ? \n";
cin>>num;
pilaNumeros.Push(num);
break;
case 2:
// Muestra todos los numeros de la lista
pilaNumeros.Mostrar();
break;
case 3:
// Elimina un nodo
/*cout<<"Numero del producto\n";
cin>>num;*/
pilaNumeros.Pop();
break;
case 4:
if(pilaNumeros.Vacia())
cout << "Si" << endl;
else
cout << "No" << endl;
break;
}
} while (opc != 5);
return 0;
}
// Termina el programa ListaNum.cpp
Espero que sea útil mi respuesta, y cualquier duda no dude en comentarla
Muchas gracias, solo tuve el problema del mismo signo con el destructor, por lo que veo la version 6 no lo necesita. Me sirvió mucho, espero mejorar en esto de los punteros. Saludos.
28.925 pts. informatica electronica y control automatico diseño de...
Implementación de una pila mediante lista enlazada que incluye las funciones para crear_pila, apilar_pila, desapilar_pila y es_vacia.
Implementación en C++ de una pila mediante listas enlazadas. Para ello utilizamos una cabecera ficticia. Realización en forma dinámica.
Se crea una estructura con un entero clave y un apuntador a estructura siguiente.
{Pre}={Existe estructura tipo_pila pila}
void crear(struct tipo_pila **pila)
{Post}={Se ha creado la pila apuntadora a NULL}
{Pre}={Existe elemento pila, elem tiene valor}
void apilar_pila(struct tipo_pila *pila, int elem)
{Post}={pila=pila+elemento añadido}
{Pre}={Existe elemento pila, existe elem}
void desapilar_pila(struct tipo_pila *pila, int *elem)
{Post}={pila=pila-ultimo valor añadido y elem apunta al valor descargado de la pila}
{Pre}={Existe pila}
void es_vacia(struct tipo_pila *pila)
{Post}={Cierto si la pila está vacía. Falso por lo contrario}
#include <stdio.h>
#include <stdlib.h>
/* declaracion de la pila*/
struct tipo_pila
{
int clave;
struct tipo_pila *sig;
};
/* Cabeceras de prototipos de funciones */
void crear_pila(struct tipo_pila **pila);
int es_vacia(struct tipo_pila *pila);
void apilar_pila(struct tipo_pila *pila, int elem);
void desapilar_pila(struct tipo_pila *pila, int *elem);
void crear_pila(struct tipo_pila **pila)
{
*pila=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
(*pila)->sig=NULL;
}
void apilar_pila(struct tipo_pila *pila, int elem)
{
struct tipo_pila *nuevo;
nuevo=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
nuevo->clave=elem;
nuevo->sig=pila->sig;
pila->sig=nuevo;
}
void desapilar_pila(struct tipo_pila *pila, int *elem)
{
struct tipo_pila *aux;
aux=pila->sig;
*elem=aux->clave;
pila->sig=aux->sig;
free(aux);
}
int es_vacia(struct tipo_pila *pila)
{
return (pila->sig==NULL);
}
/* programa principal */
main(void)
{
struct tipo_pila *pila;
int elem;
crear_pila(&pila);
if (es_vacia(pila)) printf("\nPila vacia!");
apilar_pila(pila, 1);
desapilar_pila(pila, &elem);
}

Añade tu respuesta

Haz clic para o

Más respuestas relacionadas