Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Error con clase de listas enlazadas.

 Estas en el tema de Error con clase de listas enlazadas. en el foro de C/C++ en Foros del Web. Mi problema es que no me entero mucho de como hacer listas enlazadas por lo que queria saber si me podian ayudar con este ejercicio, ...
  #1 (permalink)  
Antiguo 21/04/2013, 04:38
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Error con clase de listas enlazadas.
Mi problema es que no me entero mucho de como hacer listas enlazadas por lo que queria saber si me podian ayudar con este ejercicio, que no me funciona. Gracias.


Código C++: 
Ver original
  1. #include <iostream>
  2. #include "Lista.h"
  3.  
  4. using namespace std;
  5.  
  6. Lista :: Lista (void){
  7.  
  8.     p=0;
  9.     numnodos=0;
  10.     
  11. }
  12.  
  13. Lista :: Lista (int nnodos){
  14.  
  15.     numnodos=nnodos;    
  16.  
  17.     for (int i=0; i<nnodos; i++){
  18.         l nuevo = new Nodo;
  19.         nuevo->valor = 0;
  20.         nuevo->siguiente = p;
  21.         p=nuevo;
  22.     }
  23.     
  24. }
  25.  
  26. Lista :: Lista (int nnodos, TipoBase val){
  27.     
  28.     numnodos=nnodos;    
  29.  
  30.     for (int i=0; i<nnodos; i++){
  31.         l nuevo = new Nodo;
  32.         nuevo->valor = val;
  33.         nuevo->siguiente = p;
  34.         p=nuevo;
  35.     }
  36. }
  37.  
  38. Lista :: ~Lista (void){
  39.  
  40.     delete p;
  41.     
  42. }
  43.  
  44. int Lista :: NNodos(void){
  45.  
  46.     return(numnodos);
  47.  
  48. }
  49.  
  50. bool Lista  :: EstaVacia(){
  51.     if (p==0)
  52.         return (true);
  53.  
  54.     else
  55.         return false;
  56. }
  57.  
  58. Lista Lista :: EscribirLista (void){
  59.  
  60.     l nuevo;
  61.     TipoBase val;
  62.     int n = NNodos();
  63.  
  64.     for (int i=0; i<n; i++){
  65.     cout << "Introduce un valor: ";
  66.     cin >> val;
  67.     nuevo->valor=val;
  68.     nuevo->siguiente=p; 
  69.     p=nuevo;
  70.     }
  71. }
  72.  
  73. void Lista :: Insertar (TipoBase val, int pos){
  74.  
  75.     l nuevo;
  76.     int n = NNodos();
  77.     
  78.     for (int i=0; i<n; i++){    
  79.         if (n==pos)
  80.             nuevo->valor=val;
  81.         nuevo->siguiente=p;
  82.         p=nuevo;        
  83.     }
  84. }
  85.             
  86. TipoBase Lista :: ObtenerValor (int pos){
  87.  
  88.     l nuevo;
  89.     int n = NNodos();
  90.  
  91.     for (int i=0; i<n; i++){
  92.         if (n==pos)
  93.             cout << nuevo->valor << endl;
  94.         nuevo->siguiente=p;
  95.         p=nuevo;
  96.     }
  97.     
  98. }

Código C++: 
Ver original
  1. #ifndef LISTA
  2. #define LISTA
  3.  
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. typedef double TipoBase;
  8.  
  9. class Lista{
  10.  
  11.     private: 
  12.         
  13.         struct Nodo{
  14.             TipoBase valor;
  15.             Nodo *siguiente;
  16.             };
  17.         typedef Nodo *l;
  18.         l p;
  19.         int numnodos;       
  20.  
  21.     public:
  22.         Lista (void);
  23.         Lista (int nnodos);
  24.         Lista (int nnodos, TipoBase val);
  25.         ~Lista (void);
  26.         int NNodos(void);
  27.         bool EstaVacia (void);
  28.         Lista EscribirLista (void);
  29.         void Insertar (TipoBase val, int pos);
  30.         void Borrar (int pos);
  31.         TipoBase ObtenerValor (int pos);
  32. };
  33.  
  34.  
  35.  
  36. #endif
  #2 (permalink)  
Antiguo 21/04/2013, 07:53
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
Antes de nada (y que conste que no quiero ser desagradable) no he mirado ni una sola linea del codigo que colgaste.

Por que no funciona? Peta el programa? Sale algo no esperado? Por que consideras que no funciona?

"...Mi problema es que no me entero mucho de como hacer listas enlazadas..."

La idea es muy simple: una struct con un puntero a una siguiente struct. Si el puntero de la ultima struct apunta al primer elemento entonces es una lista circular; si en vez de un puntero pones dos punteros y derivas las entradas con un selector serializable entonces tienes un arbol balanceado, etc... Mientras liberes todo lo que bloqueas no tendras ningun problema, puedes ordenarlo como quieras.

Saludos
vosk
  #3 (permalink)  
Antiguo 21/04/2013, 07:59
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Le problema que tenía antes (el programa no se compilaba) ya lo arregle pero ahora tengo el problema que los metodos no guardan los valores que se le introducen.



Código C++: 
Ver original
  1. #include <iostream>
  2. #include "Lista.h"
  3.  
  4. using namespace std;
  5.  
  6. Lista :: Lista (void){
  7.  
  8.     p=0;
  9.     numnodos=0;
  10.     
  11. }
  12.  
  13. Lista :: Lista (int nnodos){
  14.  
  15.     numnodos=nnodos;    
  16.  
  17.     for (int i=0; i<nnodos; i++){
  18.         l nuevo = new Nodo;
  19.         nuevo->valor = 0;
  20.         nuevo->siguiente = p;
  21.         p=nuevo;
  22.     }
  23.     
  24. }
  25.  
  26. Lista :: Lista (int nnodos, TipoBase val){
  27.     
  28.     numnodos=nnodos;    
  29.  
  30.     for (int i=0; i<nnodos; i++){
  31.         l nuevo = new Nodo;
  32.         nuevo->valor = val;
  33.         nuevo->siguiente = p;
  34.         p=nuevo;
  35.     }
  36. }
  37.  
  38. Lista :: ~Lista (void){
  39.  
  40.     delete p;
  41.     
  42. }
  43.  
  44. int Lista :: NNodos(void){
  45.  
  46.     return(numnodos);
  47.  
  48. }
  49.  
  50. bool Lista  :: EstaVacia(){
  51.     if (p==0)
  52.         return (true);
  53.  
  54.     else
  55.         return false;
  56. }
  57.  
  58. Lista Lista :: EscribirLista (void){
  59.  
  60.     l nuevo;
  61.     TipoBase val;
  62.     int n = NNodos();
  63.  
  64.     for (int i=0; i<n; i++){
  65.     cout << "Introduce un valor: ";
  66.     cin >> val;
  67.     nuevo->valor=val;
  68.     nuevo->siguiente=p; 
  69.     p=nuevo;
  70.     }
  71. }
  72.  
  73. void Lista :: Insertar (TipoBase val, int pos){
  74.  
  75.     l nuevo;
  76.     int n = NNodos();
  77.     
  78.     for (int i=0; i<n; i++){    
  79.         if (n==pos)
  80.             nuevo->valor=val;
  81.         nuevo->siguiente=p;
  82.         p=nuevo;        
  83.     }
  84. }
  85.             
  86. TipoBase Lista :: ObtenerValor (int pos){
  87.  
  88.     l nuevo;
  89.     int n = NNodos();
  90.  
  91.     for (int i=0; i<n; i++){
  92.         if (n==pos)
  93.             cout << nuevo->valor << endl;
  94.         nuevo->siguiente=p;
  95.         p=nuevo;
  96.     }
  #4 (permalink)  
Antiguo 21/04/2013, 08:22
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
Una ultima observacion sobre tu codigo, si no llamas al constructor con un tamaño la lista siempre estará vacía, y aun cuando llames al constructor con un tamaño nunca podras sobrepasar ese limite porque si intentas sobrepasar ese limite la lista no se amplia, y ademas las funciones no te notifican el exito o fracaso de la operacion.

Echa otro vistazo a ~Lista, un delete sobre un puntero solo desbloquea ese puntero. Repito lo del otro post: para cada new necesitas un delete.

Parece que solo estoy viendo las partes malas de tu codigo, que conste que no te estoy criticando :)

El modelo que estas usando se llama memory pool y consiste en bloquear cierta memoria para controlar su administracion (este modelo tambien lo usa p.ej. el objeto vector). Para completarlo necesitas separar la funcion de bloqueo de memoria del constructor para que sea accesible desde otros metodos (p.ej. desde la insercion tienes que poder ampliar el tamaño admisible).

De momento lo mas importante a corregir es liberar la memoria de forma correcta.

Saludos
vosk
  #5 (permalink)  
Antiguo 21/04/2013, 08:34
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
Una ultima cosa: coge un papel y un boligrafo y haz el diagrama de flujo de datos, cuando lo tengas prueba algo basico y lo implementas manualmente. Es la unica forma que tienes para darte cuenta que la funcion Insertar nunca va a funcionar tal como la tienes, ok? Y ahora diras "Ok, pero porque no funciona?", y yo te dire "Eso tienes que saberlo tu que eres el que ha programado las funciones" no?

Animos, que no es tan complicado como parece

Saludos
vosk
  #6 (permalink)  
Antiguo 21/04/2013, 10:22
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Creo que lo que me faltaba era inicializar el nodo nuevo, por lo que puse l nuevo = p. Pero tampoco me funciona.
  #7 (permalink)  
Antiguo 21/04/2013, 10:25
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Asi lo tengo ahora:


Código C++: 
Ver original
  1. #include <iostream>
  2. #include "Lista.h"
  3.  
  4. using namespace std;
  5.  
  6. Lista :: Lista (void){
  7.  
  8.     p=0;
  9.     numnodos=0;
  10.     
  11. }
  12.  
  13. Lista :: Lista (int nnodos){
  14.  
  15.     numnodos=nnodos;    
  16.  
  17.     for (int i=0; i<nnodos; i++){
  18.         l nuevo = new Nodo;
  19.         nuevo->valor = 0;
  20.         nuevo->siguiente = p;
  21.         p=nuevo;
  22.     }
  23.     p->siguiente = 0;
  24.     
  25. }
  26.  
  27. Lista :: Lista (int nnodos, TipoBase val){
  28.     
  29.     numnodos=nnodos;    
  30.  
  31.     for (int i=0; i<nnodos; i++){
  32.         l nuevo = new Nodo;
  33.         nuevo->valor = val;
  34.         nuevo->siguiente = p;
  35.         p=nuevo;
  36.     }
  37.     p->siguiente = 0;
  38. }
  39.  
  40. Lista :: ~Lista (void){
  41.  
  42.     delete p;
  43.     
  44.     
  45. }
  46.  
  47. int Lista :: NNodos(void){
  48.  
  49.     return(numnodos);
  50.  
  51. }
  52.  
  53. bool Lista  :: EstaVacia(){
  54.     if (p==0)
  55.         return (true);
  56.  
  57.     else
  58.         return false;
  59. }
  60.  
  61. void Lista :: EscribirLista (void){
  62.  
  63.     l nuevo,ant;
  64.     TipoBase val;
  65.     nuevo = p;
  66.     int n = NNodos();
  67.     for (int i=0; i<n; i++){
  68.     cout << "Introduce un valor: ";
  69.     cin >> val;
  70.     nuevo->valor=val;
  71.     nuevo->siguiente=ant;   
  72.     ant=nuevo;
  73.     }
  74. }
  75.  
  76. void Lista :: Insertar (TipoBase val, int pos){
  77.  
  78.     l nuevo,ant;
  79.     nuevo=p;
  80.     int n = NNodos();
  81.     for (int i=0; i<n; i++){    
  82.         if (n==pos)
  83.             nuevo->valor=val;
  84.         nuevo->siguiente=ant;
  85.         ant=nuevo;      
  86.     }
  87. }
  88.             
  89. TipoBase Lista :: ObtenerValor (int pos){
  90.  
  91.     l nuevo,ant;
  92.     nuevo=p;
  93.     int n = NNodos();
  94.     for (int i=0; i<n; i++){
  95.         if (n==pos)
  96.             return (nuevo->valor);
  97.         nuevo->siguiente=ant;
  98.         ant=nuevo;
  99.     }
  100.     
  101. }
  #8 (permalink)  
Antiguo 21/04/2013, 10:59
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
Y tampoco funciona, tienes que curratelo un poco mas; sigue el codigo paso a paso, pon algun printf para mostrar los datos que estas manipulando y veras que el Inserta nunca entra en el condicional 'if (n==pos)':

Código: 
Lista lista(2);
lista.Insertar(123, 0);

for (int i=0; i<n; i++) {
    if (n==pos)

pos es 0
n vale 2
entre i = 0, i < 2 nunca se cumple que n==pos, en numeros nunca se cumple que [0,1]==2
Una vez tengas solucionado esto veras que te provoca una violacion de acceso por escribir sobre un puntero no inicializado:

Código: 
l nuevo;
nuevo->valor=val;//violacion de acceso
Estas trabajando sobre el modelo de memory pools pero dentro de las funciones estas usando cosas de bloqueo e insercion dinamico. No mezcles las cosas, cada modelo funciona de una forma. Si quieres trabajar con el memory pool no puedes insertar datos porque la lista ya está declarada, solo puedes asignar datos

Código: 
void Lista :: Insertar(TipoBase val, int pos) {//deberias renombrarla como Asignar
    int n = NNodos();
    Nodo *ptr;

    ptr = p;
    for (int i=0; i<n; i++){
        if (i == pos) {//ojo, aqui es donde tenias n==pos
	    ptr->valor = val;
	    break;//aqui sales del for para acelerar el proceso
        }
	ptr = ptr->siguiente;
    }
}
Esto es un memory pool y se basa en una reserva de memoria previa, por eso no puedes insertar datos sino que puedes asignar datos (claro que puedes llamarlo como quieras, pero se recomienda que el nombre de las funciones sea descriptivo acorde con lo que hacen).

El puntero ptr se usa para moverte por dentro de la lista, y siempre tienes que usar comprovaciones de error para asegurarte que ptr->siguiente no sea nulo (provocarias un b.o.f.) aun cuando el contador te indique lo contrario. Esto te sirve para corregir todas las demas funciones porque tambien te provocan violacion de acceso.

Saludos
vosk
  #9 (permalink)  
Antiguo 21/04/2013, 11:41
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Muchas gracias por las molestias que te estas tomando pero me podrias decir si los constructores tambien estan mal. Es que ya arreglé las funciones usando la que pusiste tu como guia pero ahora me da un error de segmentacion.
  #10 (permalink)  
Antiguo 21/04/2013, 11:59
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Muchas gracias por todo. Por fin me funciona, ya solo me queda arreglar un constructor, el destructor y al alguna cosillas.
  #11 (permalink)  
Antiguo 21/04/2013, 12:51
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
"...Muchas gracias por las molestias que te estas tomando..."

De nada hombre, estamos a domingo por la tarde y no tengo nada mejor que hacer :)

Personalmente separaría la funcion de reserva de memoria por si fuese necesario implementar la opcion de ampliar la lista, y sobretodo haz comprovaciones de error. Pongo el ejemplo de como haría el constructor (es una forma de las mil que hay)

Código: 
Lista :: Lista (int nnodos) {
    if(reserva(nnodos) != nnodos) {
	//condicion de error
    }
    numnodos += nnodos;
}
	
int Lista::reserva(int nnodos) {
    Nodo *nuevo, *anterior;
    int reservados = 0;
 
    anterior = p;
    for(int i=0; i<nnodos; i++) {

        nuevo = new (nothrow) Nodo;
        if(!nuevo) {
	    break;
	}
        	
        nuevo->valor = 0;
        nuevo->siguiente = 0;
        	
        if(anterior) {
	    anterior->siguiente = nuevo;
	}
        else {
	    p = nuevo;
	}

	anterior = nuevo;
        reservados++;
    }
    	
    return reservados;
}
Y el destructor tal como te comenté: para cada new necesitas un delete

Código: 
Lista::~Lista() {
    Nodo *ptr, *sig;
 
    ptr = p;
    while(ptr) {
        sig = ptr->siguiente;
	delete ptr;
	ptr = sig;
    }
    numnodos = 0;
    p = 0;
}
Saludos
vosk
  #12 (permalink)  
Antiguo 21/04/2013, 13:19
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Perdon, una ultima pregunta, ¿Que tendria mal mi constructor?:

Código C++: 
Ver original
  1. Lista :: Lista (int nnodos){
  2.     
  3.     numnodos=nnodos;    
  4.     for (int i=0; i<nnodos; i++){
  5.         Nodo *ptr = new Nodo;
  6.         ptr->valor = 0;
  7.         ptr->siguiente = p;
  8.         p=ptr;
  9.     }
  10. }


Es que cuando tenia el destructor delete p, me funcionaba, pero puse el tuyo y ahora me da error.
  #13 (permalink)  
Antiguo 21/04/2013, 13:43
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
Código: 
ptr->siguiente = p;
Esto hace que el ultimo nodo apunte a su anterior (no hay nada de malo solo que no lo habia visto nunca) y que necesites el contador numnodos para recorrer la lista sin llegar a un bucle infinito.

Código: 
p=ptr;
Haciendo esto la lista siempre te queda inicializada al ultimo nodo creado, que segun lo de antes lleva un puntero a su nodo anterior:

Código: 
Lista p = nulo;

Creas nuevo_nodo, indice 0, valor 0, siguiente = p = nulo
Asignas nuevo_nodo a p

Creas nuevo_nodo, indice 1, valor 0, siguiente = p = nodo_anterior
Asignas nuevo_nodo a p

Creas nuevo_nodo, indice 2, valor 0, siguiente = p = nodo_anterior
Asignas nuevo_nodo a p

Ahora 'p' apunta al ultimo nodo de indice 2

Nodo2 -> Nodo1 -> Nodo0 -> nulo
Ten en cuenta que estas creando la lista del revés, es decir que los punteros 'siguiente' no apuntan al nodo siguiente sino al anterior.

La reserva de memoria que colgué asigna a la lista el primer nodo, y para cada nodo un puntero a los siguientes excepto el ultimo que apunta a nulo, con lo que puedes recorrer la lista sin el contador externo.

Cuando en el destructor haces 'delete p' lo unico que haces es liberar el nodo al que apunta 'p', que tal como tienes el constructor es el ultimo, pero los demas nodos no se liberan. Por eso tienes que recorrer la lista y liberar cada nodo.

"...Es que cuando tenia el destructor delete p, me funcionaba, pero puse el tuyo y ahora me da error..."

El destructor que colgué funciona cuando el primer nodo de la lista es realmente el primero, tal como lo deja la funcion de reserva pero que no es tal como lo deja tu constructor. Ese bucle de liberado de memoria se basa en recorrer la lista hasta que finaliza sin tener en cuenta el contador externo.

Saludos
vosk
  #14 (permalink)  
Antiguo 21/04/2013, 14:02
 
Fecha de Ingreso: enero-2013
Mensajes: 25
Antigüedad: 12 años
Puntos: 0
Respuesta: Error con clase de listas enlazadas.
Ahora me da error de segmentación, por favor me puedes decir que tengo mal aqui, lo siento por ser pesado pero estoy estresado porque tengo que entregar el ejercicio dentro de 2 horas.


Código C++: 
Ver original
  1. Lista :: Lista (int nnodos){
  2.     Nodo *sig;
  3.     numnodos=nnodos;    
  4.     for (int i=0; i<nnodos; i++){
  5.         Nodo *ptr = new Nodo;
  6.         ptr->valor = 0;
  7.         ptr->siguiente = sig;
  8.         sig=ptr;
  9.     }
  10. }
  11.  
  12. void Lista :: EscribirLista (void){
  13.     int n = NNodos();
  14.     Nodo *ptr;
  15.     ptr = p;
  16.     TipoBase val;
  17.  
  18.     for (int i=0; i<n; i++){
  19.         cout << "Introduce un valor: ";
  20.         cin >> val;
  21.         ptr->valor=val;
  22.         ptr=ptr->siguiente; 
  23.     }
  24. }
  #15 (permalink)  
Antiguo 21/04/2013, 14:35
 
Fecha de Ingreso: agosto-2012
Mensajes: 601
Antigüedad: 12 años, 4 meses
Puntos: 83
Respuesta: Error con clase de listas enlazadas.
A ver ante todo mucha calma: no se trata de resolver ejercicios, se trata de entender lo que estas haciendo; y como norma general no dejes las cosas para el ultimo momento.

Te da un sfault porque el constructor no está trabajando sobre el puntero de lista 'p'. Cuando creas la lista tienes que asignar al puntero 'p' el primer nodo, y para cada nodo apuntar al siguiente excepto para el ultimo nodo que apunta a nulo (o al primero si quieres una lista circular). Echa un vistazo al codigo que colgué antes; y si es necesario hazte un diagrama de flujo de datos en un papel y comprueba manualmente el funcionamiento.

Como el constructor no trabaja sobre 'p', en la funcion de escribir asignas 'p' a un puntero de recorrido, como 'p' es nulo el puntero tambien es nulo; compila correctamente porque el puntero de recorrido es de tipo Lista y tiene 'siguiente', pero ejecuta mal porque un nulo no contiene nada y al primer 'ptr = ptr->siguiente' peta.

Tambien te comenté otra cosa que no has implementado: las comprovaciones de error sirven para evitar precisamente estos casos. Si hubieras puesto un simple if(!ptr) verias que antes de entrar al ciclo de escritura el ptr ya es nulo independientemente de lo que diga el contador numnodos y por lo tanto podrias evitar el sfault. Todas las aplicaciones deben tener un control de errores, no para quedar bien con el cliente sino porque provocan agujeros de seguridad (como p.ej. ejecucion de codigo). Si yo fuese profesor y un alumno me entrega un ejecutable con una violacion de acceso le pongo un sin mirar nada mas. Por eso las comprovaciones de error son tan importantes.

Resumen: asigna el primer nodo creado al puntero 'p' y pon la comprovacion de error.

Saludos
vosk

Etiquetas: clase, funcion, int, listas, struct
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta


« Tema Anterior | Próximo Tema »


La zona horaria es GMT -6. Ahora son las 18:24.